1102.36/291.52 WORST_CASE(Omega(n^1), O(n^1)) 1102.58/291.54 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1102.58/291.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1102.58/291.54 1102.58/291.54 1102.58/291.54 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1102.58/291.54 1102.58/291.54 (0) CpxTRS 1102.58/291.54 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 1102.58/291.54 (2) CpxTRS 1102.58/291.54 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 1102.58/291.54 (4) CpxTRS 1102.58/291.54 (5) CpxTrsMatchBoundsTAProof [FINISHED, 676 ms] 1102.58/291.54 (6) BOUNDS(1, n^1) 1102.58/291.54 (7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1102.58/291.54 (8) CpxTRS 1102.58/291.54 (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1102.58/291.54 (10) typed CpxTrs 1102.58/291.54 (11) OrderProof [LOWER BOUND(ID), 0 ms] 1102.58/291.54 (12) typed CpxTrs 1102.58/291.54 (13) RewriteLemmaProof [LOWER BOUND(ID), 541 ms] 1102.58/291.54 (14) BEST 1102.58/291.54 (15) proven lower bound 1102.58/291.54 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1102.58/291.54 (17) BOUNDS(n^1, INF) 1102.58/291.54 (18) typed CpxTrs 1102.58/291.54 (19) RewriteLemmaProof [LOWER BOUND(ID), 135 ms] 1102.58/291.54 (20) typed CpxTrs 1102.58/291.54 (21) RewriteLemmaProof [LOWER BOUND(ID), 106 ms] 1102.58/291.54 (22) typed CpxTrs 1102.58/291.54 (23) RewriteLemmaProof [LOWER BOUND(ID), 88 ms] 1102.58/291.54 (24) typed CpxTrs 1102.58/291.54 (25) RewriteLemmaProof [LOWER BOUND(ID), 86 ms] 1102.58/291.54 (26) typed CpxTrs 1102.58/291.54 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (0) 1102.58/291.54 Obligation: 1102.58/291.54 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1102.58/291.54 1102.58/291.54 1102.58/291.54 The TRS R consists of the following rules: 1102.58/291.54 1102.58/291.54 active(zeros) -> mark(cons(0, zeros)) 1102.58/291.54 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.54 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.54 active(length(nil)) -> mark(0) 1102.58/291.54 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.54 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.54 active(s(X)) -> s(active(X)) 1102.58/291.54 active(length(X)) -> length(active(X)) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0) -> ok(0) 1102.58/291.54 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.54 proper(s(X)) -> s(proper(X)) 1102.58/291.54 proper(length(X)) -> length(proper(X)) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 S is empty. 1102.58/291.54 Rewrite Strategy: FULL 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 1102.58/291.54 The following defined symbols can occur below the 0th argument of cons: active, proper, cons 1102.58/291.54 The following defined symbols can occur below the 1th argument of cons: active, proper, cons 1102.58/291.54 The following defined symbols can occur below the 0th argument of top: active, proper, cons 1102.58/291.54 The following defined symbols can occur below the 0th argument of proper: active, proper, cons 1102.58/291.54 The following defined symbols can occur below the 0th argument of active: active, proper, cons 1102.58/291.54 1102.58/291.54 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 1102.58/291.54 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.54 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.54 active(length(nil)) -> mark(0) 1102.58/291.54 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.54 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.54 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.54 active(s(X)) -> s(active(X)) 1102.58/291.54 active(length(X)) -> length(active(X)) 1102.58/291.54 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.54 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.54 proper(s(X)) -> s(proper(X)) 1102.58/291.54 proper(length(X)) -> length(proper(X)) 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (2) 1102.58/291.54 Obligation: 1102.58/291.54 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 1102.58/291.54 1102.58/291.54 1102.58/291.54 The TRS R consists of the following rules: 1102.58/291.54 1102.58/291.54 active(zeros) -> mark(cons(0, zeros)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0) -> ok(0) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 S is empty. 1102.58/291.54 Rewrite Strategy: FULL 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 1102.58/291.54 transformed relative TRS to TRS 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (4) 1102.58/291.54 Obligation: 1102.58/291.54 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 1102.58/291.54 1102.58/291.54 1102.58/291.54 The TRS R consists of the following rules: 1102.58/291.54 1102.58/291.54 active(zeros) -> mark(cons(0, zeros)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0) -> ok(0) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 S is empty. 1102.58/291.54 Rewrite Strategy: FULL 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (5) CpxTrsMatchBoundsTAProof (FINISHED) 1102.58/291.54 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 5. 1102.58/291.54 1102.58/291.54 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 1102.58/291.54 final states : [1, 2, 3, 4, 5, 6, 7, 8] 1102.58/291.54 transitions: 1102.58/291.54 zeros0() -> 0 1102.58/291.54 mark0(0) -> 0 1102.58/291.54 00() -> 0 1102.58/291.54 ok0(0) -> 0 1102.58/291.54 tt0() -> 0 1102.58/291.54 nil0() -> 0 1102.58/291.54 active0(0) -> 1 1102.58/291.54 cons0(0, 0) -> 2 1102.58/291.54 U110(0, 0) -> 3 1102.58/291.54 U120(0, 0) -> 4 1102.58/291.54 s0(0) -> 5 1102.58/291.54 length0(0) -> 6 1102.58/291.54 proper0(0) -> 7 1102.58/291.54 top0(0) -> 8 1102.58/291.54 01() -> 10 1102.58/291.54 zeros1() -> 11 1102.58/291.54 cons1(10, 11) -> 9 1102.58/291.54 mark1(9) -> 1 1102.58/291.54 cons1(0, 0) -> 12 1102.58/291.54 mark1(12) -> 2 1102.58/291.54 U111(0, 0) -> 13 1102.58/291.54 mark1(13) -> 3 1102.58/291.54 U121(0, 0) -> 14 1102.58/291.54 mark1(14) -> 4 1102.58/291.54 s1(0) -> 15 1102.58/291.54 mark1(15) -> 5 1102.58/291.54 length1(0) -> 16 1102.58/291.54 mark1(16) -> 6 1102.58/291.54 zeros1() -> 17 1102.58/291.54 ok1(17) -> 7 1102.58/291.54 01() -> 18 1102.58/291.54 ok1(18) -> 7 1102.58/291.54 tt1() -> 19 1102.58/291.54 ok1(19) -> 7 1102.58/291.54 nil1() -> 20 1102.58/291.54 ok1(20) -> 7 1102.58/291.54 cons1(0, 0) -> 21 1102.58/291.54 ok1(21) -> 2 1102.58/291.54 U111(0, 0) -> 22 1102.58/291.54 ok1(22) -> 3 1102.58/291.54 U121(0, 0) -> 23 1102.58/291.54 ok1(23) -> 4 1102.58/291.54 s1(0) -> 24 1102.58/291.54 ok1(24) -> 5 1102.58/291.54 length1(0) -> 25 1102.58/291.54 ok1(25) -> 6 1102.58/291.54 proper1(0) -> 26 1102.58/291.54 top1(26) -> 8 1102.58/291.54 active1(0) -> 27 1102.58/291.54 top1(27) -> 8 1102.58/291.54 mark1(9) -> 27 1102.58/291.54 mark1(12) -> 12 1102.58/291.54 mark1(12) -> 21 1102.58/291.54 mark1(13) -> 13 1102.58/291.54 mark1(13) -> 22 1102.58/291.54 mark1(14) -> 14 1102.58/291.54 mark1(14) -> 23 1102.58/291.54 mark1(15) -> 15 1102.58/291.54 mark1(15) -> 24 1102.58/291.54 mark1(16) -> 16 1102.58/291.54 mark1(16) -> 25 1102.58/291.54 ok1(17) -> 26 1102.58/291.54 ok1(18) -> 26 1102.58/291.54 ok1(19) -> 26 1102.58/291.54 ok1(20) -> 26 1102.58/291.54 ok1(21) -> 12 1102.58/291.54 ok1(21) -> 21 1102.58/291.54 ok1(22) -> 13 1102.58/291.54 ok1(22) -> 22 1102.58/291.54 ok1(23) -> 14 1102.58/291.54 ok1(23) -> 23 1102.58/291.54 ok1(24) -> 15 1102.58/291.54 ok1(24) -> 24 1102.58/291.54 ok1(25) -> 16 1102.58/291.54 ok1(25) -> 25 1102.58/291.54 proper2(9) -> 28 1102.58/291.54 top2(28) -> 8 1102.58/291.54 active2(17) -> 29 1102.58/291.54 top2(29) -> 8 1102.58/291.54 active2(18) -> 29 1102.58/291.54 active2(19) -> 29 1102.58/291.54 active2(20) -> 29 1102.58/291.54 02() -> 31 1102.58/291.54 zeros2() -> 32 1102.58/291.54 cons2(31, 32) -> 30 1102.58/291.54 mark2(30) -> 29 1102.58/291.54 proper2(10) -> 33 1102.58/291.54 proper2(11) -> 34 1102.58/291.54 cons2(33, 34) -> 28 1102.58/291.54 zeros2() -> 35 1102.58/291.54 ok2(35) -> 34 1102.58/291.54 02() -> 36 1102.58/291.54 ok2(36) -> 33 1102.58/291.54 proper3(30) -> 37 1102.58/291.54 top3(37) -> 8 1102.58/291.54 proper3(31) -> 38 1102.58/291.54 proper3(32) -> 39 1102.58/291.54 cons3(38, 39) -> 37 1102.58/291.54 cons3(36, 35) -> 40 1102.58/291.54 ok3(40) -> 28 1102.58/291.54 zeros3() -> 41 1102.58/291.54 ok3(41) -> 39 1102.58/291.54 03() -> 42 1102.58/291.54 ok3(42) -> 38 1102.58/291.54 active3(40) -> 43 1102.58/291.54 top3(43) -> 8 1102.58/291.54 cons4(42, 41) -> 44 1102.58/291.54 ok4(44) -> 37 1102.58/291.54 active4(36) -> 45 1102.58/291.54 cons4(45, 35) -> 43 1102.58/291.54 active4(44) -> 46 1102.58/291.54 top4(46) -> 8 1102.58/291.54 active5(42) -> 47 1102.58/291.54 cons5(47, 41) -> 46 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (6) 1102.58/291.54 BOUNDS(1, n^1) 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (7) RenamingProof (BOTH BOUNDS(ID, ID)) 1102.58/291.54 Renamed function symbols to avoid clashes with predefined symbol. 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (8) 1102.58/291.54 Obligation: 1102.58/291.54 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1102.58/291.54 1102.58/291.54 1102.58/291.54 The TRS R consists of the following rules: 1102.58/291.54 1102.58/291.54 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.54 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.54 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.54 active(length(nil)) -> mark(0') 1102.58/291.54 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.54 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.54 active(s(X)) -> s(active(X)) 1102.58/291.54 active(length(X)) -> length(active(X)) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0') -> ok(0') 1102.58/291.54 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.54 proper(s(X)) -> s(proper(X)) 1102.58/291.54 proper(length(X)) -> length(proper(X)) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 S is empty. 1102.58/291.54 Rewrite Strategy: FULL 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1102.58/291.54 Infered types. 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (10) 1102.58/291.54 Obligation: 1102.58/291.54 TRS: 1102.58/291.54 Rules: 1102.58/291.54 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.54 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.54 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.54 active(length(nil)) -> mark(0') 1102.58/291.54 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.54 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.54 active(s(X)) -> s(active(X)) 1102.58/291.54 active(length(X)) -> length(active(X)) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0') -> ok(0') 1102.58/291.54 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.54 proper(s(X)) -> s(proper(X)) 1102.58/291.54 proper(length(X)) -> length(proper(X)) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 Types: 1102.58/291.54 active :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 zeros :: zeros:0':mark:tt:nil:ok 1102.58/291.54 mark :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 cons :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 0' :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U11 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 tt :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U12 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 s :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 length :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 nil :: zeros:0':mark:tt:nil:ok 1102.58/291.54 proper :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 ok :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 top :: zeros:0':mark:tt:nil:ok -> top 1102.58/291.54 hole_zeros:0':mark:tt:nil:ok1_0 :: zeros:0':mark:tt:nil:ok 1102.58/291.54 hole_top2_0 :: top 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0 :: Nat -> zeros:0':mark:tt:nil:ok 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (11) OrderProof (LOWER BOUND(ID)) 1102.58/291.54 Heuristically decided to analyse the following defined symbols: 1102.58/291.54 active, cons, U12, s, length, U11, proper, top 1102.58/291.54 1102.58/291.54 They will be analysed ascendingly in the following order: 1102.58/291.54 cons < active 1102.58/291.54 U12 < active 1102.58/291.54 s < active 1102.58/291.54 length < active 1102.58/291.54 U11 < active 1102.58/291.54 active < top 1102.58/291.54 cons < proper 1102.58/291.54 U12 < proper 1102.58/291.54 s < proper 1102.58/291.54 length < proper 1102.58/291.54 U11 < proper 1102.58/291.54 proper < top 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (12) 1102.58/291.54 Obligation: 1102.58/291.54 TRS: 1102.58/291.54 Rules: 1102.58/291.54 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.54 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.54 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.54 active(length(nil)) -> mark(0') 1102.58/291.54 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.54 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.54 active(s(X)) -> s(active(X)) 1102.58/291.54 active(length(X)) -> length(active(X)) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0') -> ok(0') 1102.58/291.54 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.54 proper(s(X)) -> s(proper(X)) 1102.58/291.54 proper(length(X)) -> length(proper(X)) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 Types: 1102.58/291.54 active :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 zeros :: zeros:0':mark:tt:nil:ok 1102.58/291.54 mark :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 cons :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 0' :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U11 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 tt :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U12 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 s :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 length :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 nil :: zeros:0':mark:tt:nil:ok 1102.58/291.54 proper :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 ok :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 top :: zeros:0':mark:tt:nil:ok -> top 1102.58/291.54 hole_zeros:0':mark:tt:nil:ok1_0 :: zeros:0':mark:tt:nil:ok 1102.58/291.54 hole_top2_0 :: top 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0 :: Nat -> zeros:0':mark:tt:nil:ok 1102.58/291.54 1102.58/291.54 1102.58/291.54 Generator Equations: 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0(0) <=> zeros 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0(+(x, 1)) <=> mark(gen_zeros:0':mark:tt:nil:ok3_0(x)) 1102.58/291.54 1102.58/291.54 1102.58/291.54 The following defined symbols remain to be analysed: 1102.58/291.54 cons, active, U12, s, length, U11, proper, top 1102.58/291.54 1102.58/291.54 They will be analysed ascendingly in the following order: 1102.58/291.54 cons < active 1102.58/291.54 U12 < active 1102.58/291.54 s < active 1102.58/291.54 length < active 1102.58/291.54 U11 < active 1102.58/291.54 active < top 1102.58/291.54 cons < proper 1102.58/291.54 U12 < proper 1102.58/291.54 s < proper 1102.58/291.54 length < proper 1102.58/291.54 U11 < proper 1102.58/291.54 proper < top 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1102.58/291.54 Proved the following rewrite lemma: 1102.58/291.54 cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n5_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1102.58/291.54 1102.58/291.54 Induction Base: 1102.58/291.54 cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, 0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) 1102.58/291.54 1102.58/291.54 Induction Step: 1102.58/291.54 cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, +(n5_0, 1))), gen_zeros:0':mark:tt:nil:ok3_0(b)) ->_R^Omega(1) 1102.58/291.54 mark(cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n5_0)), gen_zeros:0':mark:tt:nil:ok3_0(b))) ->_IH 1102.58/291.54 mark(*4_0) 1102.58/291.54 1102.58/291.54 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (14) 1102.58/291.54 Complex Obligation (BEST) 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (15) 1102.58/291.54 Obligation: 1102.58/291.54 Proved the lower bound n^1 for the following obligation: 1102.58/291.54 1102.58/291.54 TRS: 1102.58/291.54 Rules: 1102.58/291.54 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.54 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.54 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.54 active(length(nil)) -> mark(0') 1102.58/291.54 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.54 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.54 active(s(X)) -> s(active(X)) 1102.58/291.54 active(length(X)) -> length(active(X)) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0') -> ok(0') 1102.58/291.54 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.54 proper(s(X)) -> s(proper(X)) 1102.58/291.54 proper(length(X)) -> length(proper(X)) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 Types: 1102.58/291.54 active :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 zeros :: zeros:0':mark:tt:nil:ok 1102.58/291.54 mark :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 cons :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 0' :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U11 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 tt :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U12 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 s :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 length :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 nil :: zeros:0':mark:tt:nil:ok 1102.58/291.54 proper :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 ok :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 top :: zeros:0':mark:tt:nil:ok -> top 1102.58/291.54 hole_zeros:0':mark:tt:nil:ok1_0 :: zeros:0':mark:tt:nil:ok 1102.58/291.54 hole_top2_0 :: top 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0 :: Nat -> zeros:0':mark:tt:nil:ok 1102.58/291.54 1102.58/291.54 1102.58/291.54 Generator Equations: 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0(0) <=> zeros 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0(+(x, 1)) <=> mark(gen_zeros:0':mark:tt:nil:ok3_0(x)) 1102.58/291.54 1102.58/291.54 1102.58/291.54 The following defined symbols remain to be analysed: 1102.58/291.54 cons, active, U12, s, length, U11, proper, top 1102.58/291.54 1102.58/291.54 They will be analysed ascendingly in the following order: 1102.58/291.54 cons < active 1102.58/291.54 U12 < active 1102.58/291.54 s < active 1102.58/291.54 length < active 1102.58/291.54 U11 < active 1102.58/291.54 active < top 1102.58/291.54 cons < proper 1102.58/291.54 U12 < proper 1102.58/291.54 s < proper 1102.58/291.54 length < proper 1102.58/291.54 U11 < proper 1102.58/291.54 proper < top 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (16) LowerBoundPropagationProof (FINISHED) 1102.58/291.54 Propagated lower bound. 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (17) 1102.58/291.54 BOUNDS(n^1, INF) 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (18) 1102.58/291.54 Obligation: 1102.58/291.54 TRS: 1102.58/291.54 Rules: 1102.58/291.54 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.54 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.54 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.54 active(length(nil)) -> mark(0') 1102.58/291.54 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.54 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.54 active(s(X)) -> s(active(X)) 1102.58/291.54 active(length(X)) -> length(active(X)) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0') -> ok(0') 1102.58/291.54 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.54 proper(s(X)) -> s(proper(X)) 1102.58/291.54 proper(length(X)) -> length(proper(X)) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 Types: 1102.58/291.54 active :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 zeros :: zeros:0':mark:tt:nil:ok 1102.58/291.54 mark :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 cons :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 0' :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U11 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 tt :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U12 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 s :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 length :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 nil :: zeros:0':mark:tt:nil:ok 1102.58/291.54 proper :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 ok :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 top :: zeros:0':mark:tt:nil:ok -> top 1102.58/291.54 hole_zeros:0':mark:tt:nil:ok1_0 :: zeros:0':mark:tt:nil:ok 1102.58/291.54 hole_top2_0 :: top 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0 :: Nat -> zeros:0':mark:tt:nil:ok 1102.58/291.54 1102.58/291.54 1102.58/291.54 Lemmas: 1102.58/291.54 cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n5_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1102.58/291.54 1102.58/291.54 1102.58/291.54 Generator Equations: 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0(0) <=> zeros 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0(+(x, 1)) <=> mark(gen_zeros:0':mark:tt:nil:ok3_0(x)) 1102.58/291.54 1102.58/291.54 1102.58/291.54 The following defined symbols remain to be analysed: 1102.58/291.54 U12, active, s, length, U11, proper, top 1102.58/291.54 1102.58/291.54 They will be analysed ascendingly in the following order: 1102.58/291.54 U12 < active 1102.58/291.54 s < active 1102.58/291.54 length < active 1102.58/291.54 U11 < active 1102.58/291.54 active < top 1102.58/291.54 U12 < proper 1102.58/291.54 s < proper 1102.58/291.54 length < proper 1102.58/291.54 U11 < proper 1102.58/291.54 proper < top 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1102.58/291.54 Proved the following rewrite lemma: 1102.58/291.54 U12(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n874_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n874_0) 1102.58/291.54 1102.58/291.54 Induction Base: 1102.58/291.54 U12(gen_zeros:0':mark:tt:nil:ok3_0(+(1, 0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) 1102.58/291.54 1102.58/291.54 Induction Step: 1102.58/291.54 U12(gen_zeros:0':mark:tt:nil:ok3_0(+(1, +(n874_0, 1))), gen_zeros:0':mark:tt:nil:ok3_0(b)) ->_R^Omega(1) 1102.58/291.54 mark(U12(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n874_0)), gen_zeros:0':mark:tt:nil:ok3_0(b))) ->_IH 1102.58/291.54 mark(*4_0) 1102.58/291.54 1102.58/291.54 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (20) 1102.58/291.54 Obligation: 1102.58/291.54 TRS: 1102.58/291.54 Rules: 1102.58/291.54 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.54 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.54 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.54 active(length(nil)) -> mark(0') 1102.58/291.54 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.54 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.54 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.54 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.54 active(s(X)) -> s(active(X)) 1102.58/291.54 active(length(X)) -> length(active(X)) 1102.58/291.54 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.54 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.54 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.54 s(mark(X)) -> mark(s(X)) 1102.58/291.54 length(mark(X)) -> mark(length(X)) 1102.58/291.54 proper(zeros) -> ok(zeros) 1102.58/291.54 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.54 proper(0') -> ok(0') 1102.58/291.54 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.54 proper(tt) -> ok(tt) 1102.58/291.54 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.54 proper(s(X)) -> s(proper(X)) 1102.58/291.54 proper(length(X)) -> length(proper(X)) 1102.58/291.54 proper(nil) -> ok(nil) 1102.58/291.54 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.54 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.54 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.54 s(ok(X)) -> ok(s(X)) 1102.58/291.54 length(ok(X)) -> ok(length(X)) 1102.58/291.54 top(mark(X)) -> top(proper(X)) 1102.58/291.54 top(ok(X)) -> top(active(X)) 1102.58/291.54 1102.58/291.54 Types: 1102.58/291.54 active :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 zeros :: zeros:0':mark:tt:nil:ok 1102.58/291.54 mark :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 cons :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 0' :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U11 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 tt :: zeros:0':mark:tt:nil:ok 1102.58/291.54 U12 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 s :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 length :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 nil :: zeros:0':mark:tt:nil:ok 1102.58/291.54 proper :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 ok :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.54 top :: zeros:0':mark:tt:nil:ok -> top 1102.58/291.54 hole_zeros:0':mark:tt:nil:ok1_0 :: zeros:0':mark:tt:nil:ok 1102.58/291.54 hole_top2_0 :: top 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0 :: Nat -> zeros:0':mark:tt:nil:ok 1102.58/291.54 1102.58/291.54 1102.58/291.54 Lemmas: 1102.58/291.54 cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n5_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1102.58/291.54 U12(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n874_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n874_0) 1102.58/291.54 1102.58/291.54 1102.58/291.54 Generator Equations: 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0(0) <=> zeros 1102.58/291.54 gen_zeros:0':mark:tt:nil:ok3_0(+(x, 1)) <=> mark(gen_zeros:0':mark:tt:nil:ok3_0(x)) 1102.58/291.54 1102.58/291.54 1102.58/291.54 The following defined symbols remain to be analysed: 1102.58/291.54 s, active, length, U11, proper, top 1102.58/291.54 1102.58/291.54 They will be analysed ascendingly in the following order: 1102.58/291.54 s < active 1102.58/291.54 length < active 1102.58/291.54 U11 < active 1102.58/291.54 active < top 1102.58/291.54 s < proper 1102.58/291.54 length < proper 1102.58/291.54 U11 < proper 1102.58/291.54 proper < top 1102.58/291.54 1102.58/291.54 ---------------------------------------- 1102.58/291.54 1102.58/291.54 (21) RewriteLemmaProof (LOWER BOUND(ID)) 1102.58/291.54 Proved the following rewrite lemma: 1102.58/291.54 s(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2049_0))) -> *4_0, rt in Omega(n2049_0) 1102.58/291.55 1102.58/291.55 Induction Base: 1102.58/291.55 s(gen_zeros:0':mark:tt:nil:ok3_0(+(1, 0))) 1102.58/291.55 1102.58/291.55 Induction Step: 1102.58/291.55 s(gen_zeros:0':mark:tt:nil:ok3_0(+(1, +(n2049_0, 1)))) ->_R^Omega(1) 1102.58/291.55 mark(s(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2049_0)))) ->_IH 1102.58/291.55 mark(*4_0) 1102.58/291.55 1102.58/291.55 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1102.58/291.55 ---------------------------------------- 1102.58/291.55 1102.58/291.55 (22) 1102.58/291.55 Obligation: 1102.58/291.55 TRS: 1102.58/291.55 Rules: 1102.58/291.55 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.55 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.55 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.55 active(length(nil)) -> mark(0') 1102.58/291.55 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.55 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.55 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.55 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.55 active(s(X)) -> s(active(X)) 1102.58/291.55 active(length(X)) -> length(active(X)) 1102.58/291.55 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.55 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.55 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.55 s(mark(X)) -> mark(s(X)) 1102.58/291.55 length(mark(X)) -> mark(length(X)) 1102.58/291.55 proper(zeros) -> ok(zeros) 1102.58/291.55 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.55 proper(0') -> ok(0') 1102.58/291.55 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.55 proper(tt) -> ok(tt) 1102.58/291.55 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.55 proper(s(X)) -> s(proper(X)) 1102.58/291.55 proper(length(X)) -> length(proper(X)) 1102.58/291.55 proper(nil) -> ok(nil) 1102.58/291.55 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.55 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.55 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.55 s(ok(X)) -> ok(s(X)) 1102.58/291.55 length(ok(X)) -> ok(length(X)) 1102.58/291.55 top(mark(X)) -> top(proper(X)) 1102.58/291.55 top(ok(X)) -> top(active(X)) 1102.58/291.55 1102.58/291.55 Types: 1102.58/291.55 active :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 zeros :: zeros:0':mark:tt:nil:ok 1102.58/291.55 mark :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 cons :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 0' :: zeros:0':mark:tt:nil:ok 1102.58/291.55 U11 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 tt :: zeros:0':mark:tt:nil:ok 1102.58/291.55 U12 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 s :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 length :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 nil :: zeros:0':mark:tt:nil:ok 1102.58/291.55 proper :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 ok :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 top :: zeros:0':mark:tt:nil:ok -> top 1102.58/291.55 hole_zeros:0':mark:tt:nil:ok1_0 :: zeros:0':mark:tt:nil:ok 1102.58/291.55 hole_top2_0 :: top 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0 :: Nat -> zeros:0':mark:tt:nil:ok 1102.58/291.55 1102.58/291.55 1102.58/291.55 Lemmas: 1102.58/291.55 cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n5_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1102.58/291.55 U12(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n874_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n874_0) 1102.58/291.55 s(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2049_0))) -> *4_0, rt in Omega(n2049_0) 1102.58/291.55 1102.58/291.55 1102.58/291.55 Generator Equations: 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0(0) <=> zeros 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0(+(x, 1)) <=> mark(gen_zeros:0':mark:tt:nil:ok3_0(x)) 1102.58/291.55 1102.58/291.55 1102.58/291.55 The following defined symbols remain to be analysed: 1102.58/291.55 length, active, U11, proper, top 1102.58/291.55 1102.58/291.55 They will be analysed ascendingly in the following order: 1102.58/291.55 length < active 1102.58/291.55 U11 < active 1102.58/291.55 active < top 1102.58/291.55 length < proper 1102.58/291.55 U11 < proper 1102.58/291.55 proper < top 1102.58/291.55 1102.58/291.55 ---------------------------------------- 1102.58/291.55 1102.58/291.55 (23) RewriteLemmaProof (LOWER BOUND(ID)) 1102.58/291.55 Proved the following rewrite lemma: 1102.58/291.55 length(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2709_0))) -> *4_0, rt in Omega(n2709_0) 1102.58/291.55 1102.58/291.55 Induction Base: 1102.58/291.55 length(gen_zeros:0':mark:tt:nil:ok3_0(+(1, 0))) 1102.58/291.55 1102.58/291.55 Induction Step: 1102.58/291.55 length(gen_zeros:0':mark:tt:nil:ok3_0(+(1, +(n2709_0, 1)))) ->_R^Omega(1) 1102.58/291.55 mark(length(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2709_0)))) ->_IH 1102.58/291.55 mark(*4_0) 1102.58/291.55 1102.58/291.55 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1102.58/291.55 ---------------------------------------- 1102.58/291.55 1102.58/291.55 (24) 1102.58/291.55 Obligation: 1102.58/291.55 TRS: 1102.58/291.55 Rules: 1102.58/291.55 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.55 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.55 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.55 active(length(nil)) -> mark(0') 1102.58/291.55 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.55 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.55 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.55 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.55 active(s(X)) -> s(active(X)) 1102.58/291.55 active(length(X)) -> length(active(X)) 1102.58/291.55 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.55 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.55 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.55 s(mark(X)) -> mark(s(X)) 1102.58/291.55 length(mark(X)) -> mark(length(X)) 1102.58/291.55 proper(zeros) -> ok(zeros) 1102.58/291.55 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.55 proper(0') -> ok(0') 1102.58/291.55 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.55 proper(tt) -> ok(tt) 1102.58/291.55 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.55 proper(s(X)) -> s(proper(X)) 1102.58/291.55 proper(length(X)) -> length(proper(X)) 1102.58/291.55 proper(nil) -> ok(nil) 1102.58/291.55 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.55 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.55 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.55 s(ok(X)) -> ok(s(X)) 1102.58/291.55 length(ok(X)) -> ok(length(X)) 1102.58/291.55 top(mark(X)) -> top(proper(X)) 1102.58/291.55 top(ok(X)) -> top(active(X)) 1102.58/291.55 1102.58/291.55 Types: 1102.58/291.55 active :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 zeros :: zeros:0':mark:tt:nil:ok 1102.58/291.55 mark :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 cons :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 0' :: zeros:0':mark:tt:nil:ok 1102.58/291.55 U11 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 tt :: zeros:0':mark:tt:nil:ok 1102.58/291.55 U12 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 s :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 length :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 nil :: zeros:0':mark:tt:nil:ok 1102.58/291.55 proper :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 ok :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 top :: zeros:0':mark:tt:nil:ok -> top 1102.58/291.55 hole_zeros:0':mark:tt:nil:ok1_0 :: zeros:0':mark:tt:nil:ok 1102.58/291.55 hole_top2_0 :: top 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0 :: Nat -> zeros:0':mark:tt:nil:ok 1102.58/291.55 1102.58/291.55 1102.58/291.55 Lemmas: 1102.58/291.55 cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n5_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1102.58/291.55 U12(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n874_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n874_0) 1102.58/291.55 s(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2049_0))) -> *4_0, rt in Omega(n2049_0) 1102.58/291.55 length(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2709_0))) -> *4_0, rt in Omega(n2709_0) 1102.58/291.55 1102.58/291.55 1102.58/291.55 Generator Equations: 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0(0) <=> zeros 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0(+(x, 1)) <=> mark(gen_zeros:0':mark:tt:nil:ok3_0(x)) 1102.58/291.55 1102.58/291.55 1102.58/291.55 The following defined symbols remain to be analysed: 1102.58/291.55 U11, active, proper, top 1102.58/291.55 1102.58/291.55 They will be analysed ascendingly in the following order: 1102.58/291.55 U11 < active 1102.58/291.55 active < top 1102.58/291.55 U11 < proper 1102.58/291.55 proper < top 1102.58/291.55 1102.58/291.55 ---------------------------------------- 1102.58/291.55 1102.58/291.55 (25) RewriteLemmaProof (LOWER BOUND(ID)) 1102.58/291.55 Proved the following rewrite lemma: 1102.58/291.55 U11(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n3470_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n3470_0) 1102.58/291.55 1102.58/291.55 Induction Base: 1102.58/291.55 U11(gen_zeros:0':mark:tt:nil:ok3_0(+(1, 0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) 1102.58/291.55 1102.58/291.55 Induction Step: 1102.58/291.55 U11(gen_zeros:0':mark:tt:nil:ok3_0(+(1, +(n3470_0, 1))), gen_zeros:0':mark:tt:nil:ok3_0(b)) ->_R^Omega(1) 1102.58/291.55 mark(U11(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n3470_0)), gen_zeros:0':mark:tt:nil:ok3_0(b))) ->_IH 1102.58/291.55 mark(*4_0) 1102.58/291.55 1102.58/291.55 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1102.58/291.55 ---------------------------------------- 1102.58/291.55 1102.58/291.55 (26) 1102.58/291.55 Obligation: 1102.58/291.55 TRS: 1102.58/291.55 Rules: 1102.58/291.55 active(zeros) -> mark(cons(0', zeros)) 1102.58/291.55 active(U11(tt, L)) -> mark(U12(tt, L)) 1102.58/291.55 active(U12(tt, L)) -> mark(s(length(L))) 1102.58/291.55 active(length(nil)) -> mark(0') 1102.58/291.55 active(length(cons(N, L))) -> mark(U11(tt, L)) 1102.58/291.55 active(cons(X1, X2)) -> cons(active(X1), X2) 1102.58/291.55 active(U11(X1, X2)) -> U11(active(X1), X2) 1102.58/291.55 active(U12(X1, X2)) -> U12(active(X1), X2) 1102.58/291.55 active(s(X)) -> s(active(X)) 1102.58/291.55 active(length(X)) -> length(active(X)) 1102.58/291.55 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1102.58/291.55 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1102.58/291.55 U12(mark(X1), X2) -> mark(U12(X1, X2)) 1102.58/291.55 s(mark(X)) -> mark(s(X)) 1102.58/291.55 length(mark(X)) -> mark(length(X)) 1102.58/291.55 proper(zeros) -> ok(zeros) 1102.58/291.55 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1102.58/291.55 proper(0') -> ok(0') 1102.58/291.55 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1102.58/291.55 proper(tt) -> ok(tt) 1102.58/291.55 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 1102.58/291.55 proper(s(X)) -> s(proper(X)) 1102.58/291.55 proper(length(X)) -> length(proper(X)) 1102.58/291.55 proper(nil) -> ok(nil) 1102.58/291.55 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1102.58/291.55 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1102.58/291.55 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 1102.58/291.55 s(ok(X)) -> ok(s(X)) 1102.58/291.55 length(ok(X)) -> ok(length(X)) 1102.58/291.55 top(mark(X)) -> top(proper(X)) 1102.58/291.55 top(ok(X)) -> top(active(X)) 1102.58/291.55 1102.58/291.55 Types: 1102.58/291.55 active :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 zeros :: zeros:0':mark:tt:nil:ok 1102.58/291.55 mark :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 cons :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 0' :: zeros:0':mark:tt:nil:ok 1102.58/291.55 U11 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 tt :: zeros:0':mark:tt:nil:ok 1102.58/291.55 U12 :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 s :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 length :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 nil :: zeros:0':mark:tt:nil:ok 1102.58/291.55 proper :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 ok :: zeros:0':mark:tt:nil:ok -> zeros:0':mark:tt:nil:ok 1102.58/291.55 top :: zeros:0':mark:tt:nil:ok -> top 1102.58/291.55 hole_zeros:0':mark:tt:nil:ok1_0 :: zeros:0':mark:tt:nil:ok 1102.58/291.55 hole_top2_0 :: top 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0 :: Nat -> zeros:0':mark:tt:nil:ok 1102.58/291.55 1102.58/291.55 1102.58/291.55 Lemmas: 1102.58/291.55 cons(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n5_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1102.58/291.55 U12(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n874_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n874_0) 1102.58/291.55 s(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2049_0))) -> *4_0, rt in Omega(n2049_0) 1102.58/291.55 length(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n2709_0))) -> *4_0, rt in Omega(n2709_0) 1102.58/291.55 U11(gen_zeros:0':mark:tt:nil:ok3_0(+(1, n3470_0)), gen_zeros:0':mark:tt:nil:ok3_0(b)) -> *4_0, rt in Omega(n3470_0) 1102.58/291.55 1102.58/291.55 1102.58/291.55 Generator Equations: 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0(0) <=> zeros 1102.58/291.55 gen_zeros:0':mark:tt:nil:ok3_0(+(x, 1)) <=> mark(gen_zeros:0':mark:tt:nil:ok3_0(x)) 1102.58/291.55 1102.58/291.55 1102.58/291.55 The following defined symbols remain to be analysed: 1102.58/291.55 active, proper, top 1102.58/291.55 1102.58/291.55 They will be analysed ascendingly in the following order: 1102.58/291.55 active < top 1102.58/291.55 proper < top 1102.62/291.61 EOF