/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). (0) CpxTRS (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxTRS (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (4) typed CpxTrs (5) OrderProof [LOWER BOUND(ID), 0 ms] (6) typed CpxTrs (7) RewriteLemmaProof [LOWER BOUND(ID), 7333 ms] (8) BEST (9) proven lower bound (10) LowerBoundPropagationProof [FINISHED, 0 ms] (11) BOUNDS(n^1, INF) (12) typed CpxTrs (13) RewriteLemmaProof [LOWER BOUND(ID), 183 ms] (14) typed CpxTrs (15) RewriteLemmaProof [LOWER BOUND(ID), 6097 ms] (16) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0) -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0, zeros) a__take(0, IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0) -> 0 mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0') -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0', zeros) a__take(0', IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0') -> 0' mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (4) Obligation: Innermost TRS: Rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0') -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0', zeros) a__take(0', IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0') -> 0' mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Types: a__and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength tt :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength mark :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength 0' :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength s :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength cons :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength nil :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength hole_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength1_0 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0 :: Nat -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength ---------------------------------------- (5) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: a__and, mark, a__isNatIList, a__isNatList, a__isNat, a__length, a__uLength They will be analysed ascendingly in the following order: a__and = mark a__and = a__isNatIList a__and = a__isNatList a__and = a__isNat a__and = a__length a__and = a__uLength mark = a__isNatIList mark = a__isNatList mark = a__isNat mark = a__length mark = a__uLength a__isNatIList = a__isNatList a__isNatIList = a__isNat a__isNatIList = a__length a__isNatIList = a__uLength a__isNatList = a__isNat a__isNatList = a__length a__isNatList = a__uLength a__isNat = a__length a__isNat = a__uLength a__length = a__uLength ---------------------------------------- (6) Obligation: Innermost TRS: Rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0') -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0', zeros) a__take(0', IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0') -> 0' mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Types: a__and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength tt :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength mark :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength 0' :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength s :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength cons :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength nil :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength hole_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength1_0 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0 :: Nat -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength Generator Equations: gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(0) <=> tt gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(x, 1)) <=> s(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(x)) The following defined symbols remain to be analysed: mark, a__and, a__isNatIList, a__isNatList, a__isNat, a__length, a__uLength They will be analysed ascendingly in the following order: a__and = mark a__and = a__isNatIList a__and = a__isNatList a__and = a__isNat a__and = a__length a__and = a__uLength mark = a__isNatIList mark = a__isNatList mark = a__isNat mark = a__length mark = a__uLength a__isNatIList = a__isNatList a__isNatIList = a__isNat a__isNatIList = a__length a__isNatIList = a__uLength a__isNatList = a__isNat a__isNatList = a__length a__isNatList = a__uLength a__isNat = a__length a__isNat = a__uLength a__length = a__uLength ---------------------------------------- (7) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n4_0)) -> gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n4_0), rt in Omega(1 + n4_0) Induction Base: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(0)) ->_R^Omega(1) tt Induction Step: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(n4_0, 1))) ->_R^Omega(1) s(mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n4_0))) ->_IH s(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(c5_0)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (8) Complex Obligation (BEST) ---------------------------------------- (9) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0') -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0', zeros) a__take(0', IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0') -> 0' mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Types: a__and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength tt :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength mark :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength 0' :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength s :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength cons :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength nil :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength hole_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength1_0 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0 :: Nat -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength Generator Equations: gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(0) <=> tt gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(x, 1)) <=> s(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(x)) The following defined symbols remain to be analysed: mark, a__and, a__isNatIList, a__isNatList, a__isNat, a__length, a__uLength They will be analysed ascendingly in the following order: a__and = mark a__and = a__isNatIList a__and = a__isNatList a__and = a__isNat a__and = a__length a__and = a__uLength mark = a__isNatIList mark = a__isNatList mark = a__isNat mark = a__length mark = a__uLength a__isNatIList = a__isNatList a__isNatIList = a__isNat a__isNatIList = a__length a__isNatIList = a__uLength a__isNatList = a__isNat a__isNatList = a__length a__isNatList = a__uLength a__isNat = a__length a__isNat = a__uLength a__length = a__uLength ---------------------------------------- (10) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (11) BOUNDS(n^1, INF) ---------------------------------------- (12) Obligation: Innermost TRS: Rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0') -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0', zeros) a__take(0', IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0') -> 0' mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Types: a__and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength tt :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength mark :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength 0' :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength s :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength cons :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength nil :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength hole_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength1_0 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0 :: Nat -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength Lemmas: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n4_0)) -> gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n4_0), rt in Omega(1 + n4_0) Generator Equations: gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(0) <=> tt gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(x, 1)) <=> s(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(x)) The following defined symbols remain to be analysed: a__and, a__isNatIList, a__isNatList, a__isNat, a__length, a__uLength They will be analysed ascendingly in the following order: a__and = mark a__and = a__isNatIList a__and = a__isNatList a__and = a__isNat a__and = a__length a__and = a__uLength mark = a__isNatIList mark = a__isNatList mark = a__isNat mark = a__length mark = a__uLength a__isNatIList = a__isNatList a__isNatIList = a__isNat a__isNatIList = a__length a__isNatIList = a__uLength a__isNatList = a__isNat a__isNatList = a__length a__isNatList = a__uLength a__isNat = a__length a__isNat = a__uLength a__length = a__uLength ---------------------------------------- (13) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: a__isNat(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(1, n1266818_0))) -> *3_0, rt in Omega(n1266818_0) Induction Base: a__isNat(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(1, 0))) Induction Step: a__isNat(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(1, +(n1266818_0, 1)))) ->_R^Omega(1) a__isNat(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(1, n1266818_0))) ->_IH *3_0 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (14) Obligation: Innermost TRS: Rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0') -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0', zeros) a__take(0', IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0') -> 0' mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Types: a__and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength tt :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength mark :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength 0' :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength s :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength cons :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength nil :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength hole_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength1_0 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0 :: Nat -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength Lemmas: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n4_0)) -> gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n4_0), rt in Omega(1 + n4_0) a__isNat(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(1, n1266818_0))) -> *3_0, rt in Omega(n1266818_0) Generator Equations: gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(0) <=> tt gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(x, 1)) <=> s(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(x)) The following defined symbols remain to be analysed: a__length, a__and, mark, a__isNatIList, a__isNatList, a__uLength They will be analysed ascendingly in the following order: a__and = mark a__and = a__isNatIList a__and = a__isNatList a__and = a__isNat a__and = a__length a__and = a__uLength mark = a__isNatIList mark = a__isNatList mark = a__isNat mark = a__length mark = a__uLength a__isNatIList = a__isNatList a__isNatIList = a__isNat a__isNatIList = a__length a__isNatIList = a__uLength a__isNatList = a__isNat a__isNatList = a__length a__isNatList = a__uLength a__isNat = a__length a__isNat = a__uLength a__length = a__uLength ---------------------------------------- (15) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n1268257_0)) -> gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n1268257_0), rt in Omega(1 + n1268257_0) Induction Base: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(0)) ->_R^Omega(1) tt Induction Step: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(n1268257_0, 1))) ->_R^Omega(1) s(mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n1268257_0))) ->_IH s(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(c1268258_0)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (16) Obligation: Innermost TRS: Rules: a__and(tt, T) -> mark(T) a__isNatIList(IL) -> a__isNatList(IL) a__isNat(0') -> tt a__isNat(s(N)) -> a__isNat(N) a__isNat(length(L)) -> a__isNatList(L) a__isNatIList(zeros) -> tt a__isNatIList(cons(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__isNatList(nil) -> tt a__isNatList(cons(N, L)) -> a__and(a__isNat(N), a__isNatList(L)) a__isNatList(take(N, IL)) -> a__and(a__isNat(N), a__isNatIList(IL)) a__zeros -> cons(0', zeros) a__take(0', IL) -> a__uTake1(a__isNatIList(IL)) a__uTake1(tt) -> nil a__take(s(M), cons(N, IL)) -> a__uTake2(a__and(a__isNat(M), a__and(a__isNat(N), a__isNatIList(IL))), M, N, IL) a__uTake2(tt, M, N, IL) -> cons(mark(N), take(M, IL)) a__length(cons(N, L)) -> a__uLength(a__and(a__isNat(N), a__isNatList(L)), L) a__uLength(tt, L) -> s(a__length(mark(L))) mark(and(X1, X2)) -> a__and(mark(X1), mark(X2)) mark(isNatIList(X)) -> a__isNatIList(X) mark(isNatList(X)) -> a__isNatList(X) mark(isNat(X)) -> a__isNat(X) mark(length(X)) -> a__length(mark(X)) mark(zeros) -> a__zeros mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) mark(uTake1(X)) -> a__uTake1(mark(X)) mark(uTake2(X1, X2, X3, X4)) -> a__uTake2(mark(X1), X2, X3, X4) mark(uLength(X1, X2)) -> a__uLength(mark(X1), X2) mark(tt) -> tt mark(0') -> 0' mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(nil) -> nil a__and(X1, X2) -> and(X1, X2) a__isNatIList(X) -> isNatIList(X) a__isNatList(X) -> isNatList(X) a__isNat(X) -> isNat(X) a__length(X) -> length(X) a__zeros -> zeros a__take(X1, X2) -> take(X1, X2) a__uTake1(X) -> uTake1(X) a__uTake2(X1, X2, X3, X4) -> uTake2(X1, X2, X3, X4) a__uLength(X1, X2) -> uLength(X1, X2) Types: a__and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength tt :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength mark :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength 0' :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength s :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength cons :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength nil :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__zeros :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__take :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__length :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength a__uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength and :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatIList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNatList :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength isNat :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake1 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uTake2 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength uLength :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength hole_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength1_0 :: tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0 :: Nat -> tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength Lemmas: mark(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n1268257_0)) -> gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(n1268257_0), rt in Omega(1 + n1268257_0) a__isNat(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(1, n1266818_0))) -> *3_0, rt in Omega(n1266818_0) Generator Equations: gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(0) <=> tt gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(+(x, 1)) <=> s(gen_tt:0':s:length:zeros:cons:nil:take:and:isNatIList:isNatList:isNat:uTake1:uTake2:uLength2_0(x)) The following defined symbols remain to be analysed: a__and, a__isNatIList, a__isNatList They will be analysed ascendingly in the following order: a__and = mark a__and = a__isNatIList a__and = a__isNatList a__and = a__isNat a__and = a__length a__and = a__uLength mark = a__isNatIList mark = a__isNatList mark = a__isNat mark = a__length mark = a__uLength a__isNatIList = a__isNatList a__isNatIList = a__isNat a__isNatIList = a__length a__isNatIList = a__uLength a__isNatList = a__isNat a__isNatList = a__length a__isNatList = a__uLength a__isNat = a__length a__isNat = a__uLength a__length = a__uLength