/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxTRS (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] (2) CpxTRS (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (4) CpxTRS (5) CpxTrsMatchBoundsTAProof [FINISHED, 206 ms] (6) BOUNDS(1, n^1) (7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTRS (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (10) typed CpxTrs (11) OrderProof [LOWER BOUND(ID), 0 ms] (12) typed CpxTrs (13) RewriteLemmaProof [LOWER BOUND(ID), 430 ms] (14) BEST (15) proven lower bound (16) LowerBoundPropagationProof [FINISHED, 0 ms] (17) BOUNDS(n^1, INF) (18) typed CpxTrs (19) RewriteLemmaProof [LOWER BOUND(ID), 113 ms] (20) typed CpxTrs (21) RewriteLemmaProof [LOWER BOUND(ID), 121 ms] (22) typed CpxTrs (23) RewriteLemmaProof [LOWER BOUND(ID), 92 ms] (24) typed CpxTrs (25) RewriteLemmaProof [LOWER BOUND(ID), 93 ms] (26) typed CpxTrs (27) RewriteLemmaProof [LOWER BOUND(ID), 47 ms] (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 100 ms] (30) typed CpxTrs (31) RewriteLemmaProof [LOWER BOUND(ID), 96 ms] (32) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: active(dbl(0)) -> mark(0) active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0, cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0)) -> mark(01) active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0, cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0)) -> mark(01) active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0) -> ok(0) proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01) -> ok(01) proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) The following defined symbols can occur below the 0th argument of top: proper, active The following defined symbols can occur below the 0th argument of proper: proper, active The following defined symbols can occur below the 0th argument of active: proper, active Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: active(dbl(0)) -> mark(0) active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0, cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0)) -> mark(01) active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0, cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0)) -> mark(01) active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) proper(dbl(X)) -> dbl(proper(X)) proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(0) -> ok(0) proper(nil) -> ok(nil) proper(01) -> ok(01) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (3) RelTrsToTrsProof (UPPER BOUND(ID)) transformed relative TRS to TRS ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(0) -> ok(0) proper(nil) -> ok(nil) proper(01) -> ok(01) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (5) CpxTrsMatchBoundsTAProof (FINISHED) 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 2. The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] transitions: mark0(0) -> 0 00() -> 0 ok0(0) -> 0 nil0() -> 0 010() -> 0 active0(0) -> 0 dbl0(0) -> 1 dbls0(0) -> 2 sel0(0, 0) -> 3 indx0(0, 0) -> 4 dbl10(0) -> 5 s10(0) -> 6 sel10(0, 0) -> 7 quote0(0) -> 8 proper0(0) -> 9 s0(0) -> 10 cons0(0, 0) -> 11 from0(0) -> 12 top0(0) -> 13 dbl1(0) -> 14 mark1(14) -> 1 dbls1(0) -> 15 mark1(15) -> 2 sel1(0, 0) -> 16 mark1(16) -> 3 indx1(0, 0) -> 17 mark1(17) -> 4 dbl11(0) -> 18 mark1(18) -> 5 s11(0) -> 19 mark1(19) -> 6 sel11(0, 0) -> 20 mark1(20) -> 7 quote1(0) -> 21 mark1(21) -> 8 01() -> 22 ok1(22) -> 9 nil1() -> 23 ok1(23) -> 9 011() -> 24 ok1(24) -> 9 dbl1(0) -> 25 ok1(25) -> 1 s1(0) -> 26 ok1(26) -> 10 dbls1(0) -> 27 ok1(27) -> 2 cons1(0, 0) -> 28 ok1(28) -> 11 sel1(0, 0) -> 29 ok1(29) -> 3 indx1(0, 0) -> 30 ok1(30) -> 4 from1(0) -> 31 ok1(31) -> 12 dbl11(0) -> 32 ok1(32) -> 5 s11(0) -> 33 ok1(33) -> 6 sel11(0, 0) -> 34 ok1(34) -> 7 quote1(0) -> 35 ok1(35) -> 8 proper1(0) -> 36 top1(36) -> 13 active1(0) -> 37 top1(37) -> 13 mark1(14) -> 14 mark1(14) -> 25 mark1(15) -> 15 mark1(15) -> 27 mark1(16) -> 16 mark1(16) -> 29 mark1(17) -> 17 mark1(17) -> 30 mark1(18) -> 18 mark1(18) -> 32 mark1(19) -> 19 mark1(19) -> 33 mark1(20) -> 20 mark1(20) -> 34 mark1(21) -> 21 mark1(21) -> 35 ok1(22) -> 36 ok1(23) -> 36 ok1(24) -> 36 ok1(25) -> 14 ok1(25) -> 25 ok1(26) -> 26 ok1(27) -> 15 ok1(27) -> 27 ok1(28) -> 28 ok1(29) -> 16 ok1(29) -> 29 ok1(30) -> 17 ok1(30) -> 30 ok1(31) -> 31 ok1(32) -> 18 ok1(32) -> 32 ok1(33) -> 19 ok1(33) -> 33 ok1(34) -> 20 ok1(34) -> 34 ok1(35) -> 21 ok1(35) -> 35 active2(22) -> 38 top2(38) -> 13 active2(23) -> 38 active2(24) -> 38 ---------------------------------------- (6) BOUNDS(1, n^1) ---------------------------------------- (7) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (8) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (10) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok ---------------------------------------- (11) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: active, s, dbl, cons, dbls, sel, indx, from, s1, dbl1, sel1, quote, proper, top They will be analysed ascendingly in the following order: s < active dbl < active cons < active dbls < active sel < active indx < active from < active s1 < active dbl1 < active sel1 < active quote < active active < top s < proper dbl < proper cons < proper dbls < proper sel < proper indx < proper from < proper s1 < proper dbl1 < proper sel1 < proper quote < proper proper < top ---------------------------------------- (12) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: s, active, dbl, cons, dbls, sel, indx, from, s1, dbl1, sel1, quote, proper, top They will be analysed ascendingly in the following order: s < active dbl < active cons < active dbls < active sel < active indx < active from < active s1 < active dbl1 < active sel1 < active quote < active active < top s < proper dbl < proper cons < proper dbls < proper sel < proper indx < proper from < proper s1 < proper dbl1 < proper sel1 < proper quote < proper proper < top ---------------------------------------- (13) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) Induction Base: dbl(gen_0':mark:nil:01':ok3_0(+(1, 0))) Induction Step: dbl(gen_0':mark:nil:01':ok3_0(+(1, +(n9_0, 1)))) ->_R^Omega(1) mark(dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0)))) ->_IH mark(*4_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (14) Complex Obligation (BEST) ---------------------------------------- (15) Obligation: Proved the lower bound n^1 for the following obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: dbl, active, cons, dbls, sel, indx, from, s1, dbl1, sel1, quote, proper, top They will be analysed ascendingly in the following order: dbl < active cons < active dbls < active sel < active indx < active from < active s1 < active dbl1 < active sel1 < active quote < active active < top dbl < proper cons < proper dbls < proper sel < proper indx < proper from < proper s1 < proper dbl1 < proper sel1 < proper quote < proper proper < top ---------------------------------------- (16) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (17) BOUNDS(n^1, INF) ---------------------------------------- (18) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Lemmas: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: cons, active, dbls, sel, indx, from, s1, dbl1, sel1, quote, proper, top They will be analysed ascendingly in the following order: cons < active dbls < active sel < active indx < active from < active s1 < active dbl1 < active sel1 < active quote < active active < top cons < proper dbls < proper sel < proper indx < proper from < proper s1 < proper dbl1 < proper sel1 < proper quote < proper proper < top ---------------------------------------- (19) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0) Induction Base: dbls(gen_0':mark:nil:01':ok3_0(+(1, 0))) Induction Step: dbls(gen_0':mark:nil:01':ok3_0(+(1, +(n478_0, 1)))) ->_R^Omega(1) mark(dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0)))) ->_IH mark(*4_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (20) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Lemmas: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0) Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: sel, active, indx, from, s1, dbl1, sel1, quote, proper, top They will be analysed ascendingly in the following order: sel < active indx < active from < active s1 < active dbl1 < active sel1 < active quote < active active < top sel < proper indx < proper from < proper s1 < proper dbl1 < proper sel1 < proper quote < proper proper < top ---------------------------------------- (21) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0) Induction Base: sel(gen_0':mark:nil:01':ok3_0(+(1, 0)), gen_0':mark:nil:01':ok3_0(b)) Induction Step: sel(gen_0':mark:nil:01':ok3_0(+(1, +(n1038_0, 1))), gen_0':mark:nil:01':ok3_0(b)) ->_R^Omega(1) mark(sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b))) ->_IH mark(*4_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (22) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Lemmas: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0) sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0) Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: indx, active, from, s1, dbl1, sel1, quote, proper, top They will be analysed ascendingly in the following order: indx < active from < active s1 < active dbl1 < active sel1 < active quote < active active < top indx < proper from < proper s1 < proper dbl1 < proper sel1 < proper quote < proper proper < top ---------------------------------------- (23) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0) Induction Base: indx(gen_0':mark:nil:01':ok3_0(+(1, 0)), gen_0':mark:nil:01':ok3_0(b)) Induction Step: indx(gen_0':mark:nil:01':ok3_0(+(1, +(n2984_0, 1))), gen_0':mark:nil:01':ok3_0(b)) ->_R^Omega(1) mark(indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b))) ->_IH mark(*4_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (24) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Lemmas: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0) sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0) indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0) Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: from, active, s1, dbl1, sel1, quote, proper, top They will be analysed ascendingly in the following order: from < active s1 < active dbl1 < active sel1 < active quote < active active < top from < proper s1 < proper dbl1 < proper sel1 < proper quote < proper proper < top ---------------------------------------- (25) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0) Induction Base: s1(gen_0':mark:nil:01':ok3_0(+(1, 0))) Induction Step: s1(gen_0':mark:nil:01':ok3_0(+(1, +(n5057_0, 1)))) ->_R^Omega(1) mark(s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0)))) ->_IH mark(*4_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (26) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Lemmas: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0) sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0) indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0) s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0) Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: dbl1, active, sel1, quote, proper, top They will be analysed ascendingly in the following order: dbl1 < active sel1 < active quote < active active < top dbl1 < proper sel1 < proper quote < proper proper < top ---------------------------------------- (27) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0))) -> *4_0, rt in Omega(n6018_0) Induction Base: dbl1(gen_0':mark:nil:01':ok3_0(+(1, 0))) Induction Step: dbl1(gen_0':mark:nil:01':ok3_0(+(1, +(n6018_0, 1)))) ->_R^Omega(1) mark(dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0)))) ->_IH mark(*4_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (28) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Lemmas: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0) sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0) indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0) s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0) dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0))) -> *4_0, rt in Omega(n6018_0) Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: sel1, active, quote, proper, top They will be analysed ascendingly in the following order: sel1 < active quote < active active < top sel1 < proper quote < proper proper < top ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: sel1(gen_0':mark:nil:01':ok3_0(+(1, n7080_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n7080_0) Induction Base: sel1(gen_0':mark:nil:01':ok3_0(+(1, 0)), gen_0':mark:nil:01':ok3_0(b)) Induction Step: sel1(gen_0':mark:nil:01':ok3_0(+(1, +(n7080_0, 1))), gen_0':mark:nil:01':ok3_0(b)) ->_R^Omega(1) mark(sel1(gen_0':mark:nil:01':ok3_0(+(1, n7080_0)), gen_0':mark:nil:01':ok3_0(b))) ->_IH mark(*4_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (30) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Lemmas: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0) sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0) indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0) s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0) dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0))) -> *4_0, rt in Omega(n6018_0) sel1(gen_0':mark:nil:01':ok3_0(+(1, n7080_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n7080_0) Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: quote, active, proper, top They will be analysed ascendingly in the following order: quote < active active < top quote < proper proper < top ---------------------------------------- (31) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: quote(gen_0':mark:nil:01':ok3_0(+(1, n10054_0))) -> *4_0, rt in Omega(n10054_0) Induction Base: quote(gen_0':mark:nil:01':ok3_0(+(1, 0))) Induction Step: quote(gen_0':mark:nil:01':ok3_0(+(1, +(n10054_0, 1)))) ->_R^Omega(1) mark(quote(gen_0':mark:nil:01':ok3_0(+(1, n10054_0)))) ->_IH mark(*4_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (32) Obligation: TRS: Rules: active(dbl(0')) -> mark(0') active(dbl(s(X))) -> mark(s(s(dbl(X)))) active(dbls(nil)) -> mark(nil) active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y))) active(sel(0', cons(X, Y))) -> mark(X) active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(indx(nil, X)) -> mark(nil) active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(dbl1(0')) -> mark(01') active(dbl1(s(X))) -> mark(s1(s1(dbl1(X)))) active(sel1(0', cons(X, Y))) -> mark(X) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(quote(0')) -> mark(01') active(quote(s(X))) -> mark(s1(quote(X))) active(quote(dbl(X))) -> mark(dbl1(X)) active(quote(sel(X, Y))) -> mark(sel1(X, Y)) active(dbl(X)) -> dbl(active(X)) active(dbls(X)) -> dbls(active(X)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(indx(X1, X2)) -> indx(active(X1), X2) active(dbl1(X)) -> dbl1(active(X)) active(s1(X)) -> s1(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(quote(X)) -> quote(active(X)) dbl(mark(X)) -> mark(dbl(X)) dbls(mark(X)) -> mark(dbls(X)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) indx(mark(X1), X2) -> mark(indx(X1, X2)) dbl1(mark(X)) -> mark(dbl1(X)) s1(mark(X)) -> mark(s1(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) quote(mark(X)) -> mark(quote(X)) proper(dbl(X)) -> dbl(proper(X)) proper(0') -> ok(0') proper(s(X)) -> s(proper(X)) proper(dbls(X)) -> dbls(proper(X)) proper(nil) -> ok(nil) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(indx(X1, X2)) -> indx(proper(X1), proper(X2)) proper(from(X)) -> from(proper(X)) proper(dbl1(X)) -> dbl1(proper(X)) proper(01') -> ok(01') proper(s1(X)) -> s1(proper(X)) proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2)) proper(quote(X)) -> quote(proper(X)) dbl(ok(X)) -> ok(dbl(X)) s(ok(X)) -> ok(s(X)) dbls(ok(X)) -> ok(dbls(X)) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) indx(ok(X1), ok(X2)) -> ok(indx(X1, X2)) from(ok(X)) -> ok(from(X)) dbl1(ok(X)) -> ok(dbl1(X)) s1(ok(X)) -> ok(s1(X)) sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2)) quote(ok(X)) -> ok(quote(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Types: active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 0' :: 0':mark:nil:01':ok mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok nil :: 0':mark:nil:01':ok cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok 01' :: 0':mark:nil:01':ok s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok top :: 0':mark:nil:01':ok -> top hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok hole_top2_0 :: top gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok Lemmas: dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0) dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0) sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0) indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0) s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0) dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0))) -> *4_0, rt in Omega(n6018_0) sel1(gen_0':mark:nil:01':ok3_0(+(1, n7080_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n7080_0) quote(gen_0':mark:nil:01':ok3_0(+(1, n10054_0))) -> *4_0, rt in Omega(n10054_0) Generator Equations: gen_0':mark:nil:01':ok3_0(0) <=> 0' gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x)) The following defined symbols remain to be analysed: active, proper, top They will be analysed ascendingly in the following order: active < top proper < top