1145.15/291.58 WORST_CASE(Omega(n^1), ?) 1151.24/293.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1151.24/293.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1151.24/293.11 1151.24/293.11 1151.24/293.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1151.24/293.11 1151.24/293.11 (0) CpxTRS 1151.24/293.11 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1151.24/293.11 (2) CpxTRS 1151.24/293.11 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1151.24/293.11 (4) typed CpxTrs 1151.24/293.11 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1151.24/293.11 (6) typed CpxTrs 1151.24/293.11 (7) RewriteLemmaProof [LOWER BOUND(ID), 467 ms] 1151.24/293.11 (8) BEST 1151.24/293.11 (9) proven lower bound 1151.24/293.11 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1151.24/293.11 (11) BOUNDS(n^1, INF) 1151.24/293.11 (12) typed CpxTrs 1151.24/293.11 (13) RewriteLemmaProof [LOWER BOUND(ID), 164 ms] 1151.24/293.11 (14) typed CpxTrs 1151.24/293.11 (15) RewriteLemmaProof [LOWER BOUND(ID), 109 ms] 1151.24/293.11 (16) typed CpxTrs 1151.24/293.11 (17) RewriteLemmaProof [LOWER BOUND(ID), 154 ms] 1151.24/293.11 (18) typed CpxTrs 1151.24/293.11 (19) RewriteLemmaProof [LOWER BOUND(ID), 95 ms] 1151.24/293.11 (20) typed CpxTrs 1151.24/293.11 (21) RewriteLemmaProof [LOWER BOUND(ID), 156 ms] 1151.24/293.11 (22) typed CpxTrs 1151.24/293.11 (23) RewriteLemmaProof [LOWER BOUND(ID), 118 ms] 1151.24/293.11 (24) typed CpxTrs 1151.24/293.11 (25) RewriteLemmaProof [LOWER BOUND(ID), 83 ms] 1151.24/293.11 (26) typed CpxTrs 1151.24/293.11 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (0) 1151.24/293.11 Obligation: 1151.24/293.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1151.24/293.11 1151.24/293.11 1151.24/293.11 The TRS R consists of the following rules: 1151.24/293.11 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0)) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0, zeros)) 1151.24/293.11 active(take(0, IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0) -> ok(0) 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 S is empty. 1151.24/293.11 Rewrite Strategy: FULL 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1151.24/293.11 Renamed function symbols to avoid clashes with predefined symbol. 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (2) 1151.24/293.11 Obligation: 1151.24/293.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1151.24/293.11 1151.24/293.11 1151.24/293.11 The TRS R consists of the following rules: 1151.24/293.11 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 S is empty. 1151.24/293.11 Rewrite Strategy: FULL 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1151.24/293.11 Infered types. 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (4) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (5) OrderProof (LOWER BOUND(ID)) 1151.24/293.11 Heuristically decided to analyse the following defined symbols: 1151.24/293.11 active, isNatList, isNat, and, isNatIList, cons, uTake1, uTake2, take, uLength, s, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 isNatList < active 1151.24/293.11 isNat < active 1151.24/293.11 and < active 1151.24/293.11 isNatIList < active 1151.24/293.11 cons < active 1151.24/293.11 uTake1 < active 1151.24/293.11 uTake2 < active 1151.24/293.11 take < active 1151.24/293.11 uLength < active 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 isNatList < proper 1151.24/293.11 isNat < proper 1151.24/293.11 and < proper 1151.24/293.11 isNatIList < proper 1151.24/293.11 cons < proper 1151.24/293.11 uTake1 < proper 1151.24/293.11 uTake2 < proper 1151.24/293.11 take < proper 1151.24/293.11 uLength < proper 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (6) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 1151.24/293.11 Generator Equations: 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.11 1151.24/293.11 1151.24/293.11 The following defined symbols remain to be analysed: 1151.24/293.11 isNatList, active, isNat, and, isNatIList, cons, uTake1, uTake2, take, uLength, s, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 isNatList < active 1151.24/293.11 isNat < active 1151.24/293.11 and < active 1151.24/293.11 isNatIList < active 1151.24/293.11 cons < active 1151.24/293.11 uTake1 < active 1151.24/293.11 uTake2 < active 1151.24/293.11 take < active 1151.24/293.11 uLength < active 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 isNatList < proper 1151.24/293.11 isNat < proper 1151.24/293.11 and < proper 1151.24/293.11 isNatIList < proper 1151.24/293.11 cons < proper 1151.24/293.11 uTake1 < proper 1151.24/293.11 uTake2 < proper 1151.24/293.11 take < proper 1151.24/293.11 uLength < proper 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1151.24/293.11 Proved the following rewrite lemma: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.11 1151.24/293.11 Induction Base: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, 0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) 1151.24/293.11 1151.24/293.11 Induction Step: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, +(n13_0, 1))), gen_tt:mark:0':zeros:nil:ok3_0(b)) ->_R^Omega(1) 1151.24/293.11 mark(and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b))) ->_IH 1151.24/293.11 mark(*4_0) 1151.24/293.11 1151.24/293.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (8) 1151.24/293.11 Complex Obligation (BEST) 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (9) 1151.24/293.11 Obligation: 1151.24/293.11 Proved the lower bound n^1 for the following obligation: 1151.24/293.11 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 1151.24/293.11 Generator Equations: 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.11 1151.24/293.11 1151.24/293.11 The following defined symbols remain to be analysed: 1151.24/293.11 and, active, isNatIList, cons, uTake1, uTake2, take, uLength, s, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 and < active 1151.24/293.11 isNatIList < active 1151.24/293.11 cons < active 1151.24/293.11 uTake1 < active 1151.24/293.11 uTake2 < active 1151.24/293.11 take < active 1151.24/293.11 uLength < active 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 and < proper 1151.24/293.11 isNatIList < proper 1151.24/293.11 cons < proper 1151.24/293.11 uTake1 < proper 1151.24/293.11 uTake2 < proper 1151.24/293.11 take < proper 1151.24/293.11 uLength < proper 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (10) LowerBoundPropagationProof (FINISHED) 1151.24/293.11 Propagated lower bound. 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (11) 1151.24/293.11 BOUNDS(n^1, INF) 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (12) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 1151.24/293.11 Lemmas: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.11 1151.24/293.11 1151.24/293.11 Generator Equations: 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.11 1151.24/293.11 1151.24/293.11 The following defined symbols remain to be analysed: 1151.24/293.11 isNatIList, active, cons, uTake1, uTake2, take, uLength, s, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 isNatIList < active 1151.24/293.11 cons < active 1151.24/293.11 uTake1 < active 1151.24/293.11 uTake2 < active 1151.24/293.11 take < active 1151.24/293.11 uLength < active 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 isNatIList < proper 1151.24/293.11 cons < proper 1151.24/293.11 uTake1 < proper 1151.24/293.11 uTake2 < proper 1151.24/293.11 take < proper 1151.24/293.11 uLength < proper 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1151.24/293.11 Proved the following rewrite lemma: 1151.24/293.11 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n1566_0) 1151.24/293.11 1151.24/293.11 Induction Base: 1151.24/293.11 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, 0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) 1151.24/293.11 1151.24/293.11 Induction Step: 1151.24/293.11 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, +(n1566_0, 1))), gen_tt:mark:0':zeros:nil:ok3_0(b)) ->_R^Omega(1) 1151.24/293.11 mark(cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b))) ->_IH 1151.24/293.11 mark(*4_0) 1151.24/293.11 1151.24/293.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (14) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 1151.24/293.11 Lemmas: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.11 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n1566_0) 1151.24/293.11 1151.24/293.11 1151.24/293.11 Generator Equations: 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.11 1151.24/293.11 1151.24/293.11 The following defined symbols remain to be analysed: 1151.24/293.11 uTake1, active, uTake2, take, uLength, s, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 uTake1 < active 1151.24/293.11 uTake2 < active 1151.24/293.11 take < active 1151.24/293.11 uLength < active 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 uTake1 < proper 1151.24/293.11 uTake2 < proper 1151.24/293.11 take < proper 1151.24/293.11 uLength < proper 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1151.24/293.11 Proved the following rewrite lemma: 1151.24/293.11 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3217_0))) -> *4_0, rt in Omega(n3217_0) 1151.24/293.11 1151.24/293.11 Induction Base: 1151.24/293.11 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, 0))) 1151.24/293.11 1151.24/293.11 Induction Step: 1151.24/293.11 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, +(n3217_0, 1)))) ->_R^Omega(1) 1151.24/293.11 mark(uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3217_0)))) ->_IH 1151.24/293.11 mark(*4_0) 1151.24/293.11 1151.24/293.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (16) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 1151.24/293.11 Lemmas: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.11 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n1566_0) 1151.24/293.11 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3217_0))) -> *4_0, rt in Omega(n3217_0) 1151.24/293.11 1151.24/293.11 1151.24/293.11 Generator Equations: 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.11 1151.24/293.11 1151.24/293.11 The following defined symbols remain to be analysed: 1151.24/293.11 uTake2, active, take, uLength, s, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 uTake2 < active 1151.24/293.11 take < active 1151.24/293.11 uLength < active 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 uTake2 < proper 1151.24/293.11 take < proper 1151.24/293.11 uLength < proper 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1151.24/293.11 Proved the following rewrite lemma: 1151.24/293.11 uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3979_0)), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d)) -> *4_0, rt in Omega(n3979_0) 1151.24/293.11 1151.24/293.11 Induction Base: 1151.24/293.11 uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, 0)), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d)) 1151.24/293.11 1151.24/293.11 Induction Step: 1151.24/293.11 uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, +(n3979_0, 1))), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d)) ->_R^Omega(1) 1151.24/293.11 mark(uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3979_0)), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d))) ->_IH 1151.24/293.11 mark(*4_0) 1151.24/293.11 1151.24/293.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (18) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 1151.24/293.11 Lemmas: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.11 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n1566_0) 1151.24/293.11 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3217_0))) -> *4_0, rt in Omega(n3217_0) 1151.24/293.11 uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3979_0)), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d)) -> *4_0, rt in Omega(n3979_0) 1151.24/293.11 1151.24/293.11 1151.24/293.11 Generator Equations: 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.11 1151.24/293.11 1151.24/293.11 The following defined symbols remain to be analysed: 1151.24/293.11 take, active, uLength, s, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 take < active 1151.24/293.11 uLength < active 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 take < proper 1151.24/293.11 uLength < proper 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1151.24/293.11 Proved the following rewrite lemma: 1151.24/293.11 take(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n8748_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n8748_0) 1151.24/293.11 1151.24/293.11 Induction Base: 1151.24/293.11 take(gen_tt:mark:0':zeros:nil:ok3_0(+(1, 0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) 1151.24/293.11 1151.24/293.11 Induction Step: 1151.24/293.11 take(gen_tt:mark:0':zeros:nil:ok3_0(+(1, +(n8748_0, 1))), gen_tt:mark:0':zeros:nil:ok3_0(b)) ->_R^Omega(1) 1151.24/293.11 mark(take(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n8748_0)), gen_tt:mark:0':zeros:nil:ok3_0(b))) ->_IH 1151.24/293.11 mark(*4_0) 1151.24/293.11 1151.24/293.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (20) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 1151.24/293.11 Lemmas: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.11 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n1566_0) 1151.24/293.11 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3217_0))) -> *4_0, rt in Omega(n3217_0) 1151.24/293.11 uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3979_0)), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d)) -> *4_0, rt in Omega(n3979_0) 1151.24/293.11 take(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n8748_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n8748_0) 1151.24/293.11 1151.24/293.11 1151.24/293.11 Generator Equations: 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.11 1151.24/293.11 1151.24/293.11 The following defined symbols remain to be analysed: 1151.24/293.11 uLength, active, s, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 uLength < active 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 uLength < proper 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (21) RewriteLemmaProof (LOWER BOUND(ID)) 1151.24/293.11 Proved the following rewrite lemma: 1151.24/293.11 uLength(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n11614_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n11614_0) 1151.24/293.11 1151.24/293.11 Induction Base: 1151.24/293.11 uLength(gen_tt:mark:0':zeros:nil:ok3_0(+(1, 0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) 1151.24/293.11 1151.24/293.11 Induction Step: 1151.24/293.11 uLength(gen_tt:mark:0':zeros:nil:ok3_0(+(1, +(n11614_0, 1))), gen_tt:mark:0':zeros:nil:ok3_0(b)) ->_R^Omega(1) 1151.24/293.11 mark(uLength(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n11614_0)), gen_tt:mark:0':zeros:nil:ok3_0(b))) ->_IH 1151.24/293.11 mark(*4_0) 1151.24/293.11 1151.24/293.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (22) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.11 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.11 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.11 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.11 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(isNatList(nil)) -> mark(tt) 1151.24/293.11 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.11 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.11 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.11 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.11 active(uTake1(tt)) -> mark(nil) 1151.24/293.11 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.11 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.11 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.11 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.11 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.11 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.11 active(s(X)) -> s(active(X)) 1151.24/293.11 active(length(X)) -> length(active(X)) 1151.24/293.11 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.11 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.11 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.11 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.11 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.11 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.11 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.11 s(mark(X)) -> mark(s(X)) 1151.24/293.11 length(mark(X)) -> mark(length(X)) 1151.24/293.11 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.11 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.11 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.11 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.11 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.11 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.11 proper(tt) -> ok(tt) 1151.24/293.11 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.11 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.11 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.11 proper(0') -> ok(0') 1151.24/293.11 proper(s(X)) -> s(proper(X)) 1151.24/293.11 proper(length(X)) -> length(proper(X)) 1151.24/293.11 proper(zeros) -> ok(zeros) 1151.24/293.11 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.11 proper(nil) -> ok(nil) 1151.24/293.11 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.11 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.11 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.11 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.11 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.11 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.11 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.11 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.11 s(ok(X)) -> ok(s(X)) 1151.24/293.11 length(ok(X)) -> ok(length(X)) 1151.24/293.11 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.11 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.11 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.11 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.11 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.11 top(mark(X)) -> top(proper(X)) 1151.24/293.11 top(ok(X)) -> top(active(X)) 1151.24/293.11 1151.24/293.11 Types: 1151.24/293.11 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.11 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.11 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.11 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.11 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.11 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.11 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.11 hole_top2_0 :: top 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.11 1151.24/293.11 1151.24/293.11 Lemmas: 1151.24/293.11 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.11 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n1566_0) 1151.24/293.11 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3217_0))) -> *4_0, rt in Omega(n3217_0) 1151.24/293.11 uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3979_0)), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d)) -> *4_0, rt in Omega(n3979_0) 1151.24/293.11 take(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n8748_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n8748_0) 1151.24/293.11 uLength(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n11614_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n11614_0) 1151.24/293.11 1151.24/293.11 1151.24/293.11 Generator Equations: 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.11 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.11 1151.24/293.11 1151.24/293.11 The following defined symbols remain to be analysed: 1151.24/293.11 s, active, length, proper, top 1151.24/293.11 1151.24/293.11 They will be analysed ascendingly in the following order: 1151.24/293.11 s < active 1151.24/293.11 length < active 1151.24/293.11 active < top 1151.24/293.11 s < proper 1151.24/293.11 length < proper 1151.24/293.11 proper < top 1151.24/293.11 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (23) RewriteLemmaProof (LOWER BOUND(ID)) 1151.24/293.11 Proved the following rewrite lemma: 1151.24/293.11 s(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n14587_0))) -> *4_0, rt in Omega(n14587_0) 1151.24/293.11 1151.24/293.11 Induction Base: 1151.24/293.11 s(gen_tt:mark:0':zeros:nil:ok3_0(+(1, 0))) 1151.24/293.11 1151.24/293.11 Induction Step: 1151.24/293.11 s(gen_tt:mark:0':zeros:nil:ok3_0(+(1, +(n14587_0, 1)))) ->_R^Omega(1) 1151.24/293.11 mark(s(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n14587_0)))) ->_IH 1151.24/293.11 mark(*4_0) 1151.24/293.11 1151.24/293.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1151.24/293.11 ---------------------------------------- 1151.24/293.11 1151.24/293.11 (24) 1151.24/293.11 Obligation: 1151.24/293.11 TRS: 1151.24/293.11 Rules: 1151.24/293.11 active(and(tt, T)) -> mark(T) 1151.24/293.11 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.11 active(isNat(0')) -> mark(tt) 1151.24/293.12 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.12 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.12 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.12 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.12 active(isNatList(nil)) -> mark(tt) 1151.24/293.12 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.12 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.12 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.12 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.12 active(uTake1(tt)) -> mark(nil) 1151.24/293.12 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.12 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.12 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.12 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.12 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.12 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.12 active(s(X)) -> s(active(X)) 1151.24/293.12 active(length(X)) -> length(active(X)) 1151.24/293.12 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.12 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.12 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.12 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.12 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.12 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.12 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.12 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.12 s(mark(X)) -> mark(s(X)) 1151.24/293.12 length(mark(X)) -> mark(length(X)) 1151.24/293.12 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.12 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.12 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.12 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.12 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.12 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.12 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.12 proper(tt) -> ok(tt) 1151.24/293.12 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.12 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.12 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.12 proper(0') -> ok(0') 1151.24/293.12 proper(s(X)) -> s(proper(X)) 1151.24/293.12 proper(length(X)) -> length(proper(X)) 1151.24/293.12 proper(zeros) -> ok(zeros) 1151.24/293.12 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.12 proper(nil) -> ok(nil) 1151.24/293.12 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.12 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.12 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.12 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.12 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.12 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.12 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.12 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.12 s(ok(X)) -> ok(s(X)) 1151.24/293.12 length(ok(X)) -> ok(length(X)) 1151.24/293.12 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.12 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.12 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.12 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.12 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.12 top(mark(X)) -> top(proper(X)) 1151.24/293.12 top(ok(X)) -> top(active(X)) 1151.24/293.12 1151.24/293.12 Types: 1151.24/293.12 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.12 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.12 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.12 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.12 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.12 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.12 hole_top2_0 :: top 1151.24/293.12 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.12 1151.24/293.12 1151.24/293.12 Lemmas: 1151.24/293.12 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.12 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n1566_0) 1151.24/293.12 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3217_0))) -> *4_0, rt in Omega(n3217_0) 1151.24/293.12 uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3979_0)), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d)) -> *4_0, rt in Omega(n3979_0) 1151.24/293.12 take(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n8748_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n8748_0) 1151.24/293.12 uLength(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n11614_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n11614_0) 1151.24/293.12 s(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n14587_0))) -> *4_0, rt in Omega(n14587_0) 1151.24/293.12 1151.24/293.12 1151.24/293.12 Generator Equations: 1151.24/293.12 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.12 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.12 1151.24/293.12 1151.24/293.12 The following defined symbols remain to be analysed: 1151.24/293.12 length, active, proper, top 1151.24/293.12 1151.24/293.12 They will be analysed ascendingly in the following order: 1151.24/293.12 length < active 1151.24/293.12 active < top 1151.24/293.12 length < proper 1151.24/293.12 proper < top 1151.24/293.12 1151.24/293.12 ---------------------------------------- 1151.24/293.12 1151.24/293.12 (25) RewriteLemmaProof (LOWER BOUND(ID)) 1151.24/293.12 Proved the following rewrite lemma: 1151.24/293.12 length(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n15998_0))) -> *4_0, rt in Omega(n15998_0) 1151.24/293.12 1151.24/293.12 Induction Base: 1151.24/293.12 length(gen_tt:mark:0':zeros:nil:ok3_0(+(1, 0))) 1151.24/293.12 1151.24/293.12 Induction Step: 1151.24/293.12 length(gen_tt:mark:0':zeros:nil:ok3_0(+(1, +(n15998_0, 1)))) ->_R^Omega(1) 1151.24/293.12 mark(length(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n15998_0)))) ->_IH 1151.24/293.12 mark(*4_0) 1151.24/293.12 1151.24/293.12 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1151.24/293.12 ---------------------------------------- 1151.24/293.12 1151.24/293.12 (26) 1151.24/293.12 Obligation: 1151.24/293.12 TRS: 1151.24/293.12 Rules: 1151.24/293.12 active(and(tt, T)) -> mark(T) 1151.24/293.12 active(isNatIList(IL)) -> mark(isNatList(IL)) 1151.24/293.12 active(isNat(0')) -> mark(tt) 1151.24/293.12 active(isNat(s(N))) -> mark(isNat(N)) 1151.24/293.12 active(isNat(length(L))) -> mark(isNatList(L)) 1151.24/293.12 active(isNatIList(zeros)) -> mark(tt) 1151.24/293.12 active(isNatIList(cons(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.12 active(isNatList(nil)) -> mark(tt) 1151.24/293.12 active(isNatList(cons(N, L))) -> mark(and(isNat(N), isNatList(L))) 1151.24/293.12 active(isNatList(take(N, IL))) -> mark(and(isNat(N), isNatIList(IL))) 1151.24/293.12 active(zeros) -> mark(cons(0', zeros)) 1151.24/293.12 active(take(0', IL)) -> mark(uTake1(isNatIList(IL))) 1151.24/293.12 active(uTake1(tt)) -> mark(nil) 1151.24/293.12 active(take(s(M), cons(N, IL))) -> mark(uTake2(and(isNat(M), and(isNat(N), isNatIList(IL))), M, N, IL)) 1151.24/293.12 active(uTake2(tt, M, N, IL)) -> mark(cons(N, take(M, IL))) 1151.24/293.12 active(length(cons(N, L))) -> mark(uLength(and(isNat(N), isNatList(L)), L)) 1151.24/293.12 active(uLength(tt, L)) -> mark(s(length(L))) 1151.24/293.12 active(and(X1, X2)) -> and(active(X1), X2) 1151.24/293.12 active(and(X1, X2)) -> and(X1, active(X2)) 1151.24/293.12 active(s(X)) -> s(active(X)) 1151.24/293.12 active(length(X)) -> length(active(X)) 1151.24/293.12 active(cons(X1, X2)) -> cons(active(X1), X2) 1151.24/293.12 active(take(X1, X2)) -> take(active(X1), X2) 1151.24/293.12 active(take(X1, X2)) -> take(X1, active(X2)) 1151.24/293.12 active(uTake1(X)) -> uTake1(active(X)) 1151.24/293.12 active(uTake2(X1, X2, X3, X4)) -> uTake2(active(X1), X2, X3, X4) 1151.24/293.12 active(uLength(X1, X2)) -> uLength(active(X1), X2) 1151.24/293.12 and(mark(X1), X2) -> mark(and(X1, X2)) 1151.24/293.12 and(X1, mark(X2)) -> mark(and(X1, X2)) 1151.24/293.12 s(mark(X)) -> mark(s(X)) 1151.24/293.12 length(mark(X)) -> mark(length(X)) 1151.24/293.12 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1151.24/293.12 take(mark(X1), X2) -> mark(take(X1, X2)) 1151.24/293.12 take(X1, mark(X2)) -> mark(take(X1, X2)) 1151.24/293.12 uTake1(mark(X)) -> mark(uTake1(X)) 1151.24/293.12 uTake2(mark(X1), X2, X3, X4) -> mark(uTake2(X1, X2, X3, X4)) 1151.24/293.12 uLength(mark(X1), X2) -> mark(uLength(X1, X2)) 1151.24/293.12 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1151.24/293.12 proper(tt) -> ok(tt) 1151.24/293.12 proper(isNatIList(X)) -> isNatIList(proper(X)) 1151.24/293.12 proper(isNatList(X)) -> isNatList(proper(X)) 1151.24/293.12 proper(isNat(X)) -> isNat(proper(X)) 1151.24/293.12 proper(0') -> ok(0') 1151.24/293.12 proper(s(X)) -> s(proper(X)) 1151.24/293.12 proper(length(X)) -> length(proper(X)) 1151.24/293.12 proper(zeros) -> ok(zeros) 1151.24/293.12 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1151.24/293.12 proper(nil) -> ok(nil) 1151.24/293.12 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 1151.24/293.12 proper(uTake1(X)) -> uTake1(proper(X)) 1151.24/293.12 proper(uTake2(X1, X2, X3, X4)) -> uTake2(proper(X1), proper(X2), proper(X3), proper(X4)) 1151.24/293.12 proper(uLength(X1, X2)) -> uLength(proper(X1), proper(X2)) 1151.24/293.12 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1151.24/293.12 isNatIList(ok(X)) -> ok(isNatIList(X)) 1151.24/293.12 isNatList(ok(X)) -> ok(isNatList(X)) 1151.24/293.12 isNat(ok(X)) -> ok(isNat(X)) 1151.24/293.12 s(ok(X)) -> ok(s(X)) 1151.24/293.12 length(ok(X)) -> ok(length(X)) 1151.24/293.12 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1151.24/293.12 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 1151.24/293.12 uTake1(ok(X)) -> ok(uTake1(X)) 1151.24/293.12 uTake2(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(uTake2(X1, X2, X3, X4)) 1151.24/293.12 uLength(ok(X1), ok(X2)) -> ok(uLength(X1, X2)) 1151.24/293.12 top(mark(X)) -> top(proper(X)) 1151.24/293.12 top(ok(X)) -> top(active(X)) 1151.24/293.12 1151.24/293.12 Types: 1151.24/293.12 active :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 and :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 tt :: tt:mark:0':zeros:nil:ok 1151.24/293.12 mark :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 isNatIList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 isNatList :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 isNat :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 0' :: tt:mark:0':zeros:nil:ok 1151.24/293.12 s :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 length :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 zeros :: tt:mark:0':zeros:nil:ok 1151.24/293.12 cons :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 nil :: tt:mark:0':zeros:nil:ok 1151.24/293.12 take :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 uTake1 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 uTake2 :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 uLength :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 proper :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 ok :: tt:mark:0':zeros:nil:ok -> tt:mark:0':zeros:nil:ok 1151.24/293.12 top :: tt:mark:0':zeros:nil:ok -> top 1151.24/293.12 hole_tt:mark:0':zeros:nil:ok1_0 :: tt:mark:0':zeros:nil:ok 1151.24/293.12 hole_top2_0 :: top 1151.24/293.12 gen_tt:mark:0':zeros:nil:ok3_0 :: Nat -> tt:mark:0':zeros:nil:ok 1151.24/293.12 1151.24/293.12 1151.24/293.12 Lemmas: 1151.24/293.12 and(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n13_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n13_0) 1151.24/293.12 cons(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n1566_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n1566_0) 1151.24/293.12 uTake1(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3217_0))) -> *4_0, rt in Omega(n3217_0) 1151.24/293.12 uTake2(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n3979_0)), gen_tt:mark:0':zeros:nil:ok3_0(b), gen_tt:mark:0':zeros:nil:ok3_0(c), gen_tt:mark:0':zeros:nil:ok3_0(d)) -> *4_0, rt in Omega(n3979_0) 1151.24/293.12 take(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n8748_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n8748_0) 1151.24/293.12 uLength(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n11614_0)), gen_tt:mark:0':zeros:nil:ok3_0(b)) -> *4_0, rt in Omega(n11614_0) 1151.24/293.12 s(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n14587_0))) -> *4_0, rt in Omega(n14587_0) 1151.24/293.12 length(gen_tt:mark:0':zeros:nil:ok3_0(+(1, n15998_0))) -> *4_0, rt in Omega(n15998_0) 1151.24/293.12 1151.24/293.12 1151.24/293.12 Generator Equations: 1151.24/293.12 gen_tt:mark:0':zeros:nil:ok3_0(0) <=> tt 1151.24/293.12 gen_tt:mark:0':zeros:nil:ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':zeros:nil:ok3_0(x)) 1151.24/293.12 1151.24/293.12 1151.24/293.12 The following defined symbols remain to be analysed: 1151.24/293.12 active, proper, top 1151.24/293.12 1151.24/293.12 They will be analysed ascendingly in the following order: 1151.24/293.12 active < top 1151.24/293.12 proper < top 1151.35/293.20 EOF