1116.45/291.62 WORST_CASE(Omega(n^1), ?) 1127.44/294.37 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1127.44/294.37 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1127.44/294.37 1127.44/294.37 1127.44/294.37 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1127.44/294.37 1127.44/294.37 (0) CpxTRS 1127.44/294.37 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1127.44/294.37 (2) CpxTRS 1127.44/294.37 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1127.44/294.37 (4) typed CpxTrs 1127.44/294.37 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1127.44/294.37 (6) typed CpxTrs 1127.44/294.37 (7) RewriteLemmaProof [LOWER BOUND(ID), 475 ms] 1127.44/294.37 (8) BEST 1127.44/294.37 (9) proven lower bound 1127.44/294.37 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1127.44/294.37 (11) BOUNDS(n^1, INF) 1127.44/294.37 (12) typed CpxTrs 1127.44/294.37 (13) RewriteLemmaProof [LOWER BOUND(ID), 118 ms] 1127.44/294.37 (14) typed CpxTrs 1127.44/294.37 (15) RewriteLemmaProof [LOWER BOUND(ID), 67 ms] 1127.44/294.37 (16) typed CpxTrs 1127.44/294.37 (17) RewriteLemmaProof [LOWER BOUND(ID), 93 ms] 1127.44/294.37 (18) typed CpxTrs 1127.44/294.37 (19) RewriteLemmaProof [LOWER BOUND(ID), 50 ms] 1127.44/294.37 (20) typed CpxTrs 1127.44/294.37 1127.44/294.37 1127.44/294.37 ---------------------------------------- 1127.44/294.37 1127.44/294.37 (0) 1127.44/294.37 Obligation: 1127.44/294.37 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1127.44/294.37 1127.44/294.37 1127.44/294.37 The TRS R consists of the following rules: 1127.44/294.37 1127.44/294.37 active(nats) -> mark(cons(0, incr(nats))) 1127.44/294.37 active(pairs) -> mark(cons(0, incr(odds))) 1127.44/294.37 active(odds) -> mark(incr(pairs)) 1127.44/294.37 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.37 active(head(cons(X, XS))) -> mark(X) 1127.44/294.37 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.37 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.37 active(incr(X)) -> incr(active(X)) 1127.44/294.37 active(s(X)) -> s(active(X)) 1127.44/294.37 active(head(X)) -> head(active(X)) 1127.44/294.37 active(tail(X)) -> tail(active(X)) 1127.44/294.37 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.37 incr(mark(X)) -> mark(incr(X)) 1127.44/294.37 s(mark(X)) -> mark(s(X)) 1127.44/294.37 head(mark(X)) -> mark(head(X)) 1127.44/294.37 tail(mark(X)) -> mark(tail(X)) 1127.44/294.37 proper(nats) -> ok(nats) 1127.44/294.37 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.37 proper(0) -> ok(0) 1127.44/294.37 proper(incr(X)) -> incr(proper(X)) 1127.44/294.37 proper(pairs) -> ok(pairs) 1127.44/294.37 proper(odds) -> ok(odds) 1127.44/294.37 proper(s(X)) -> s(proper(X)) 1127.44/294.37 proper(head(X)) -> head(proper(X)) 1127.44/294.37 proper(tail(X)) -> tail(proper(X)) 1127.44/294.37 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.37 incr(ok(X)) -> ok(incr(X)) 1127.44/294.37 s(ok(X)) -> ok(s(X)) 1127.44/294.37 head(ok(X)) -> ok(head(X)) 1127.44/294.37 tail(ok(X)) -> ok(tail(X)) 1127.44/294.37 top(mark(X)) -> top(proper(X)) 1127.44/294.37 top(ok(X)) -> top(active(X)) 1127.44/294.37 1127.44/294.37 S is empty. 1127.44/294.37 Rewrite Strategy: FULL 1127.44/294.37 ---------------------------------------- 1127.44/294.37 1127.44/294.37 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1127.44/294.37 Renamed function symbols to avoid clashes with predefined symbol. 1127.44/294.37 ---------------------------------------- 1127.44/294.37 1127.44/294.37 (2) 1127.44/294.37 Obligation: 1127.44/294.37 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1127.44/294.37 1127.44/294.37 1127.44/294.37 The TRS R consists of the following rules: 1127.44/294.37 1127.44/294.37 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.37 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.37 active(odds) -> mark(incr(pairs)) 1127.44/294.37 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.37 active(head(cons(X, XS))) -> mark(X) 1127.44/294.37 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.37 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.37 active(incr(X)) -> incr(active(X)) 1127.44/294.37 active(s(X)) -> s(active(X)) 1127.44/294.37 active(head(X)) -> head(active(X)) 1127.44/294.37 active(tail(X)) -> tail(active(X)) 1127.44/294.37 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.37 incr(mark(X)) -> mark(incr(X)) 1127.44/294.37 s(mark(X)) -> mark(s(X)) 1127.44/294.37 head(mark(X)) -> mark(head(X)) 1127.44/294.37 tail(mark(X)) -> mark(tail(X)) 1127.44/294.37 proper(nats) -> ok(nats) 1127.44/294.37 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.37 proper(0') -> ok(0') 1127.44/294.37 proper(incr(X)) -> incr(proper(X)) 1127.44/294.37 proper(pairs) -> ok(pairs) 1127.44/294.37 proper(odds) -> ok(odds) 1127.44/294.37 proper(s(X)) -> s(proper(X)) 1127.44/294.37 proper(head(X)) -> head(proper(X)) 1127.44/294.37 proper(tail(X)) -> tail(proper(X)) 1127.44/294.37 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.37 incr(ok(X)) -> ok(incr(X)) 1127.44/294.37 s(ok(X)) -> ok(s(X)) 1127.44/294.37 head(ok(X)) -> ok(head(X)) 1127.44/294.37 tail(ok(X)) -> ok(tail(X)) 1127.44/294.37 top(mark(X)) -> top(proper(X)) 1127.44/294.37 top(ok(X)) -> top(active(X)) 1127.44/294.37 1127.44/294.37 S is empty. 1127.44/294.37 Rewrite Strategy: FULL 1127.44/294.37 ---------------------------------------- 1127.44/294.37 1127.44/294.37 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1127.44/294.37 Infered types. 1127.44/294.37 ---------------------------------------- 1127.44/294.37 1127.44/294.37 (4) 1127.44/294.37 Obligation: 1127.44/294.37 TRS: 1127.44/294.37 Rules: 1127.44/294.37 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.37 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.37 active(odds) -> mark(incr(pairs)) 1127.44/294.37 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.37 active(head(cons(X, XS))) -> mark(X) 1127.44/294.37 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.37 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.37 active(incr(X)) -> incr(active(X)) 1127.44/294.37 active(s(X)) -> s(active(X)) 1127.44/294.37 active(head(X)) -> head(active(X)) 1127.44/294.37 active(tail(X)) -> tail(active(X)) 1127.44/294.37 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.37 incr(mark(X)) -> mark(incr(X)) 1127.44/294.37 s(mark(X)) -> mark(s(X)) 1127.44/294.37 head(mark(X)) -> mark(head(X)) 1127.44/294.37 tail(mark(X)) -> mark(tail(X)) 1127.44/294.37 proper(nats) -> ok(nats) 1127.44/294.37 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.37 proper(0') -> ok(0') 1127.44/294.37 proper(incr(X)) -> incr(proper(X)) 1127.44/294.37 proper(pairs) -> ok(pairs) 1127.44/294.37 proper(odds) -> ok(odds) 1127.44/294.37 proper(s(X)) -> s(proper(X)) 1127.44/294.37 proper(head(X)) -> head(proper(X)) 1127.44/294.37 proper(tail(X)) -> tail(proper(X)) 1127.44/294.37 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.37 incr(ok(X)) -> ok(incr(X)) 1127.44/294.37 s(ok(X)) -> ok(s(X)) 1127.44/294.37 head(ok(X)) -> ok(head(X)) 1127.44/294.37 tail(ok(X)) -> ok(tail(X)) 1127.44/294.37 top(mark(X)) -> top(proper(X)) 1127.44/294.37 top(ok(X)) -> top(active(X)) 1127.44/294.37 1127.44/294.37 Types: 1127.44/294.37 active :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 nats :: nats:0':mark:pairs:odds:ok 1127.44/294.37 mark :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 cons :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 0' :: nats:0':mark:pairs:odds:ok 1127.44/294.37 incr :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 pairs :: nats:0':mark:pairs:odds:ok 1127.44/294.37 odds :: nats:0':mark:pairs:odds:ok 1127.44/294.37 s :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 head :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 tail :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 proper :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 ok :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 top :: nats:0':mark:pairs:odds:ok -> top 1127.44/294.37 hole_nats:0':mark:pairs:odds:ok1_0 :: nats:0':mark:pairs:odds:ok 1127.44/294.37 hole_top2_0 :: top 1127.44/294.37 gen_nats:0':mark:pairs:odds:ok3_0 :: Nat -> nats:0':mark:pairs:odds:ok 1127.44/294.37 1127.44/294.37 ---------------------------------------- 1127.44/294.37 1127.44/294.37 (5) OrderProof (LOWER BOUND(ID)) 1127.44/294.37 Heuristically decided to analyse the following defined symbols: 1127.44/294.37 active, cons, incr, s, head, tail, proper, top 1127.44/294.37 1127.44/294.37 They will be analysed ascendingly in the following order: 1127.44/294.37 cons < active 1127.44/294.37 incr < active 1127.44/294.37 s < active 1127.44/294.37 head < active 1127.44/294.37 tail < active 1127.44/294.37 active < top 1127.44/294.37 cons < proper 1127.44/294.37 incr < proper 1127.44/294.37 s < proper 1127.44/294.37 head < proper 1127.44/294.37 tail < proper 1127.44/294.37 proper < top 1127.44/294.37 1127.44/294.37 ---------------------------------------- 1127.44/294.37 1127.44/294.37 (6) 1127.44/294.37 Obligation: 1127.44/294.37 TRS: 1127.44/294.37 Rules: 1127.44/294.37 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.37 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.37 active(odds) -> mark(incr(pairs)) 1127.44/294.37 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.37 active(head(cons(X, XS))) -> mark(X) 1127.44/294.37 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.37 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.37 active(incr(X)) -> incr(active(X)) 1127.44/294.37 active(s(X)) -> s(active(X)) 1127.44/294.37 active(head(X)) -> head(active(X)) 1127.44/294.37 active(tail(X)) -> tail(active(X)) 1127.44/294.37 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.37 incr(mark(X)) -> mark(incr(X)) 1127.44/294.37 s(mark(X)) -> mark(s(X)) 1127.44/294.37 head(mark(X)) -> mark(head(X)) 1127.44/294.37 tail(mark(X)) -> mark(tail(X)) 1127.44/294.37 proper(nats) -> ok(nats) 1127.44/294.37 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.37 proper(0') -> ok(0') 1127.44/294.37 proper(incr(X)) -> incr(proper(X)) 1127.44/294.37 proper(pairs) -> ok(pairs) 1127.44/294.37 proper(odds) -> ok(odds) 1127.44/294.37 proper(s(X)) -> s(proper(X)) 1127.44/294.37 proper(head(X)) -> head(proper(X)) 1127.44/294.37 proper(tail(X)) -> tail(proper(X)) 1127.44/294.37 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.37 incr(ok(X)) -> ok(incr(X)) 1127.44/294.37 s(ok(X)) -> ok(s(X)) 1127.44/294.37 head(ok(X)) -> ok(head(X)) 1127.44/294.37 tail(ok(X)) -> ok(tail(X)) 1127.44/294.37 top(mark(X)) -> top(proper(X)) 1127.44/294.37 top(ok(X)) -> top(active(X)) 1127.44/294.37 1127.44/294.37 Types: 1127.44/294.37 active :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 nats :: nats:0':mark:pairs:odds:ok 1127.44/294.37 mark :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 cons :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 0' :: nats:0':mark:pairs:odds:ok 1127.44/294.37 incr :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 pairs :: nats:0':mark:pairs:odds:ok 1127.44/294.37 odds :: nats:0':mark:pairs:odds:ok 1127.44/294.37 s :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 head :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 tail :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 proper :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 ok :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.37 top :: nats:0':mark:pairs:odds:ok -> top 1127.44/294.37 hole_nats:0':mark:pairs:odds:ok1_0 :: nats:0':mark:pairs:odds:ok 1127.44/294.37 hole_top2_0 :: top 1127.44/294.37 gen_nats:0':mark:pairs:odds:ok3_0 :: Nat -> nats:0':mark:pairs:odds:ok 1127.44/294.37 1127.44/294.37 1127.44/294.37 Generator Equations: 1127.44/294.37 gen_nats:0':mark:pairs:odds:ok3_0(0) <=> nats 1127.44/294.37 gen_nats:0':mark:pairs:odds:ok3_0(+(x, 1)) <=> mark(gen_nats:0':mark:pairs:odds:ok3_0(x)) 1127.44/294.37 1127.44/294.37 1127.44/294.37 The following defined symbols remain to be analysed: 1127.44/294.37 cons, active, incr, s, head, tail, proper, top 1127.44/294.37 1127.44/294.37 They will be analysed ascendingly in the following order: 1127.44/294.37 cons < active 1127.44/294.37 incr < active 1127.44/294.37 s < active 1127.44/294.37 head < active 1127.44/294.37 tail < active 1127.44/294.37 active < top 1127.44/294.37 cons < proper 1127.44/294.37 incr < proper 1127.44/294.37 s < proper 1127.44/294.37 head < proper 1127.44/294.37 tail < proper 1127.44/294.37 proper < top 1127.44/294.37 1127.44/294.37 ---------------------------------------- 1127.44/294.37 1127.44/294.37 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1127.44/294.37 Proved the following rewrite lemma: 1127.44/294.38 cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n5_0)), gen_nats:0':mark:pairs:odds:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1127.44/294.38 1127.44/294.38 Induction Base: 1127.44/294.38 cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, 0)), gen_nats:0':mark:pairs:odds:ok3_0(b)) 1127.44/294.38 1127.44/294.38 Induction Step: 1127.44/294.38 cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, +(n5_0, 1))), gen_nats:0':mark:pairs:odds:ok3_0(b)) ->_R^Omega(1) 1127.44/294.38 mark(cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n5_0)), gen_nats:0':mark:pairs:odds:ok3_0(b))) ->_IH 1127.44/294.38 mark(*4_0) 1127.44/294.38 1127.44/294.38 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (8) 1127.44/294.38 Complex Obligation (BEST) 1127.44/294.38 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (9) 1127.44/294.38 Obligation: 1127.44/294.38 Proved the lower bound n^1 for the following obligation: 1127.44/294.38 1127.44/294.38 TRS: 1127.44/294.38 Rules: 1127.44/294.38 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.38 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.38 active(odds) -> mark(incr(pairs)) 1127.44/294.38 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.38 active(head(cons(X, XS))) -> mark(X) 1127.44/294.38 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.38 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.38 active(incr(X)) -> incr(active(X)) 1127.44/294.38 active(s(X)) -> s(active(X)) 1127.44/294.38 active(head(X)) -> head(active(X)) 1127.44/294.38 active(tail(X)) -> tail(active(X)) 1127.44/294.38 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.38 incr(mark(X)) -> mark(incr(X)) 1127.44/294.38 s(mark(X)) -> mark(s(X)) 1127.44/294.38 head(mark(X)) -> mark(head(X)) 1127.44/294.38 tail(mark(X)) -> mark(tail(X)) 1127.44/294.38 proper(nats) -> ok(nats) 1127.44/294.38 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.38 proper(0') -> ok(0') 1127.44/294.38 proper(incr(X)) -> incr(proper(X)) 1127.44/294.38 proper(pairs) -> ok(pairs) 1127.44/294.38 proper(odds) -> ok(odds) 1127.44/294.38 proper(s(X)) -> s(proper(X)) 1127.44/294.38 proper(head(X)) -> head(proper(X)) 1127.44/294.38 proper(tail(X)) -> tail(proper(X)) 1127.44/294.38 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.38 incr(ok(X)) -> ok(incr(X)) 1127.44/294.38 s(ok(X)) -> ok(s(X)) 1127.44/294.38 head(ok(X)) -> ok(head(X)) 1127.44/294.38 tail(ok(X)) -> ok(tail(X)) 1127.44/294.38 top(mark(X)) -> top(proper(X)) 1127.44/294.38 top(ok(X)) -> top(active(X)) 1127.44/294.38 1127.44/294.38 Types: 1127.44/294.38 active :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 nats :: nats:0':mark:pairs:odds:ok 1127.44/294.38 mark :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 cons :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 0' :: nats:0':mark:pairs:odds:ok 1127.44/294.38 incr :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 pairs :: nats:0':mark:pairs:odds:ok 1127.44/294.38 odds :: nats:0':mark:pairs:odds:ok 1127.44/294.38 s :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 head :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 tail :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 proper :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 ok :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 top :: nats:0':mark:pairs:odds:ok -> top 1127.44/294.38 hole_nats:0':mark:pairs:odds:ok1_0 :: nats:0':mark:pairs:odds:ok 1127.44/294.38 hole_top2_0 :: top 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0 :: Nat -> nats:0':mark:pairs:odds:ok 1127.44/294.38 1127.44/294.38 1127.44/294.38 Generator Equations: 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(0) <=> nats 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(+(x, 1)) <=> mark(gen_nats:0':mark:pairs:odds:ok3_0(x)) 1127.44/294.38 1127.44/294.38 1127.44/294.38 The following defined symbols remain to be analysed: 1127.44/294.38 cons, active, incr, s, head, tail, proper, top 1127.44/294.38 1127.44/294.38 They will be analysed ascendingly in the following order: 1127.44/294.38 cons < active 1127.44/294.38 incr < active 1127.44/294.38 s < active 1127.44/294.38 head < active 1127.44/294.38 tail < active 1127.44/294.38 active < top 1127.44/294.38 cons < proper 1127.44/294.38 incr < proper 1127.44/294.38 s < proper 1127.44/294.38 head < proper 1127.44/294.38 tail < proper 1127.44/294.38 proper < top 1127.44/294.38 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (10) LowerBoundPropagationProof (FINISHED) 1127.44/294.38 Propagated lower bound. 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (11) 1127.44/294.38 BOUNDS(n^1, INF) 1127.44/294.38 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (12) 1127.44/294.38 Obligation: 1127.44/294.38 TRS: 1127.44/294.38 Rules: 1127.44/294.38 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.38 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.38 active(odds) -> mark(incr(pairs)) 1127.44/294.38 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.38 active(head(cons(X, XS))) -> mark(X) 1127.44/294.38 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.38 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.38 active(incr(X)) -> incr(active(X)) 1127.44/294.38 active(s(X)) -> s(active(X)) 1127.44/294.38 active(head(X)) -> head(active(X)) 1127.44/294.38 active(tail(X)) -> tail(active(X)) 1127.44/294.38 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.38 incr(mark(X)) -> mark(incr(X)) 1127.44/294.38 s(mark(X)) -> mark(s(X)) 1127.44/294.38 head(mark(X)) -> mark(head(X)) 1127.44/294.38 tail(mark(X)) -> mark(tail(X)) 1127.44/294.38 proper(nats) -> ok(nats) 1127.44/294.38 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.38 proper(0') -> ok(0') 1127.44/294.38 proper(incr(X)) -> incr(proper(X)) 1127.44/294.38 proper(pairs) -> ok(pairs) 1127.44/294.38 proper(odds) -> ok(odds) 1127.44/294.38 proper(s(X)) -> s(proper(X)) 1127.44/294.38 proper(head(X)) -> head(proper(X)) 1127.44/294.38 proper(tail(X)) -> tail(proper(X)) 1127.44/294.38 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.38 incr(ok(X)) -> ok(incr(X)) 1127.44/294.38 s(ok(X)) -> ok(s(X)) 1127.44/294.38 head(ok(X)) -> ok(head(X)) 1127.44/294.38 tail(ok(X)) -> ok(tail(X)) 1127.44/294.38 top(mark(X)) -> top(proper(X)) 1127.44/294.38 top(ok(X)) -> top(active(X)) 1127.44/294.38 1127.44/294.38 Types: 1127.44/294.38 active :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 nats :: nats:0':mark:pairs:odds:ok 1127.44/294.38 mark :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 cons :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 0' :: nats:0':mark:pairs:odds:ok 1127.44/294.38 incr :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 pairs :: nats:0':mark:pairs:odds:ok 1127.44/294.38 odds :: nats:0':mark:pairs:odds:ok 1127.44/294.38 s :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 head :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 tail :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 proper :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 ok :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 top :: nats:0':mark:pairs:odds:ok -> top 1127.44/294.38 hole_nats:0':mark:pairs:odds:ok1_0 :: nats:0':mark:pairs:odds:ok 1127.44/294.38 hole_top2_0 :: top 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0 :: Nat -> nats:0':mark:pairs:odds:ok 1127.44/294.38 1127.44/294.38 1127.44/294.38 Lemmas: 1127.44/294.38 cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n5_0)), gen_nats:0':mark:pairs:odds:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1127.44/294.38 1127.44/294.38 1127.44/294.38 Generator Equations: 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(0) <=> nats 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(+(x, 1)) <=> mark(gen_nats:0':mark:pairs:odds:ok3_0(x)) 1127.44/294.38 1127.44/294.38 1127.44/294.38 The following defined symbols remain to be analysed: 1127.44/294.38 incr, active, s, head, tail, proper, top 1127.44/294.38 1127.44/294.38 They will be analysed ascendingly in the following order: 1127.44/294.38 incr < active 1127.44/294.38 s < active 1127.44/294.38 head < active 1127.44/294.38 tail < active 1127.44/294.38 active < top 1127.44/294.38 incr < proper 1127.44/294.38 s < proper 1127.44/294.38 head < proper 1127.44/294.38 tail < proper 1127.44/294.38 proper < top 1127.44/294.38 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1127.44/294.38 Proved the following rewrite lemma: 1127.44/294.38 incr(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n888_0))) -> *4_0, rt in Omega(n888_0) 1127.44/294.38 1127.44/294.38 Induction Base: 1127.44/294.38 incr(gen_nats:0':mark:pairs:odds:ok3_0(+(1, 0))) 1127.44/294.38 1127.44/294.38 Induction Step: 1127.44/294.38 incr(gen_nats:0':mark:pairs:odds:ok3_0(+(1, +(n888_0, 1)))) ->_R^Omega(1) 1127.44/294.38 mark(incr(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n888_0)))) ->_IH 1127.44/294.38 mark(*4_0) 1127.44/294.38 1127.44/294.38 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (14) 1127.44/294.38 Obligation: 1127.44/294.38 TRS: 1127.44/294.38 Rules: 1127.44/294.38 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.38 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.38 active(odds) -> mark(incr(pairs)) 1127.44/294.38 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.38 active(head(cons(X, XS))) -> mark(X) 1127.44/294.38 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.38 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.38 active(incr(X)) -> incr(active(X)) 1127.44/294.38 active(s(X)) -> s(active(X)) 1127.44/294.38 active(head(X)) -> head(active(X)) 1127.44/294.38 active(tail(X)) -> tail(active(X)) 1127.44/294.38 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.38 incr(mark(X)) -> mark(incr(X)) 1127.44/294.38 s(mark(X)) -> mark(s(X)) 1127.44/294.38 head(mark(X)) -> mark(head(X)) 1127.44/294.38 tail(mark(X)) -> mark(tail(X)) 1127.44/294.38 proper(nats) -> ok(nats) 1127.44/294.38 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.38 proper(0') -> ok(0') 1127.44/294.38 proper(incr(X)) -> incr(proper(X)) 1127.44/294.38 proper(pairs) -> ok(pairs) 1127.44/294.38 proper(odds) -> ok(odds) 1127.44/294.38 proper(s(X)) -> s(proper(X)) 1127.44/294.38 proper(head(X)) -> head(proper(X)) 1127.44/294.38 proper(tail(X)) -> tail(proper(X)) 1127.44/294.38 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.38 incr(ok(X)) -> ok(incr(X)) 1127.44/294.38 s(ok(X)) -> ok(s(X)) 1127.44/294.38 head(ok(X)) -> ok(head(X)) 1127.44/294.38 tail(ok(X)) -> ok(tail(X)) 1127.44/294.38 top(mark(X)) -> top(proper(X)) 1127.44/294.38 top(ok(X)) -> top(active(X)) 1127.44/294.38 1127.44/294.38 Types: 1127.44/294.38 active :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 nats :: nats:0':mark:pairs:odds:ok 1127.44/294.38 mark :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 cons :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 0' :: nats:0':mark:pairs:odds:ok 1127.44/294.38 incr :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 pairs :: nats:0':mark:pairs:odds:ok 1127.44/294.38 odds :: nats:0':mark:pairs:odds:ok 1127.44/294.38 s :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 head :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 tail :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 proper :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 ok :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 top :: nats:0':mark:pairs:odds:ok -> top 1127.44/294.38 hole_nats:0':mark:pairs:odds:ok1_0 :: nats:0':mark:pairs:odds:ok 1127.44/294.38 hole_top2_0 :: top 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0 :: Nat -> nats:0':mark:pairs:odds:ok 1127.44/294.38 1127.44/294.38 1127.44/294.38 Lemmas: 1127.44/294.38 cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n5_0)), gen_nats:0':mark:pairs:odds:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1127.44/294.38 incr(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n888_0))) -> *4_0, rt in Omega(n888_0) 1127.44/294.38 1127.44/294.38 1127.44/294.38 Generator Equations: 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(0) <=> nats 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(+(x, 1)) <=> mark(gen_nats:0':mark:pairs:odds:ok3_0(x)) 1127.44/294.38 1127.44/294.38 1127.44/294.38 The following defined symbols remain to be analysed: 1127.44/294.38 s, active, head, tail, proper, top 1127.44/294.38 1127.44/294.38 They will be analysed ascendingly in the following order: 1127.44/294.38 s < active 1127.44/294.38 head < active 1127.44/294.38 tail < active 1127.44/294.38 active < top 1127.44/294.38 s < proper 1127.44/294.38 head < proper 1127.44/294.38 tail < proper 1127.44/294.38 proper < top 1127.44/294.38 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1127.44/294.38 Proved the following rewrite lemma: 1127.44/294.38 s(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n1401_0))) -> *4_0, rt in Omega(n1401_0) 1127.44/294.38 1127.44/294.38 Induction Base: 1127.44/294.38 s(gen_nats:0':mark:pairs:odds:ok3_0(+(1, 0))) 1127.44/294.38 1127.44/294.38 Induction Step: 1127.44/294.38 s(gen_nats:0':mark:pairs:odds:ok3_0(+(1, +(n1401_0, 1)))) ->_R^Omega(1) 1127.44/294.38 mark(s(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n1401_0)))) ->_IH 1127.44/294.38 mark(*4_0) 1127.44/294.38 1127.44/294.38 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (16) 1127.44/294.38 Obligation: 1127.44/294.38 TRS: 1127.44/294.38 Rules: 1127.44/294.38 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.38 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.38 active(odds) -> mark(incr(pairs)) 1127.44/294.38 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.38 active(head(cons(X, XS))) -> mark(X) 1127.44/294.38 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.38 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.38 active(incr(X)) -> incr(active(X)) 1127.44/294.38 active(s(X)) -> s(active(X)) 1127.44/294.38 active(head(X)) -> head(active(X)) 1127.44/294.38 active(tail(X)) -> tail(active(X)) 1127.44/294.38 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.38 incr(mark(X)) -> mark(incr(X)) 1127.44/294.38 s(mark(X)) -> mark(s(X)) 1127.44/294.38 head(mark(X)) -> mark(head(X)) 1127.44/294.38 tail(mark(X)) -> mark(tail(X)) 1127.44/294.38 proper(nats) -> ok(nats) 1127.44/294.38 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.38 proper(0') -> ok(0') 1127.44/294.38 proper(incr(X)) -> incr(proper(X)) 1127.44/294.38 proper(pairs) -> ok(pairs) 1127.44/294.38 proper(odds) -> ok(odds) 1127.44/294.38 proper(s(X)) -> s(proper(X)) 1127.44/294.38 proper(head(X)) -> head(proper(X)) 1127.44/294.38 proper(tail(X)) -> tail(proper(X)) 1127.44/294.38 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.38 incr(ok(X)) -> ok(incr(X)) 1127.44/294.38 s(ok(X)) -> ok(s(X)) 1127.44/294.38 head(ok(X)) -> ok(head(X)) 1127.44/294.38 tail(ok(X)) -> ok(tail(X)) 1127.44/294.38 top(mark(X)) -> top(proper(X)) 1127.44/294.38 top(ok(X)) -> top(active(X)) 1127.44/294.38 1127.44/294.38 Types: 1127.44/294.38 active :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 nats :: nats:0':mark:pairs:odds:ok 1127.44/294.38 mark :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 cons :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 0' :: nats:0':mark:pairs:odds:ok 1127.44/294.38 incr :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 pairs :: nats:0':mark:pairs:odds:ok 1127.44/294.38 odds :: nats:0':mark:pairs:odds:ok 1127.44/294.38 s :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 head :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 tail :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 proper :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 ok :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 top :: nats:0':mark:pairs:odds:ok -> top 1127.44/294.38 hole_nats:0':mark:pairs:odds:ok1_0 :: nats:0':mark:pairs:odds:ok 1127.44/294.38 hole_top2_0 :: top 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0 :: Nat -> nats:0':mark:pairs:odds:ok 1127.44/294.38 1127.44/294.38 1127.44/294.38 Lemmas: 1127.44/294.38 cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n5_0)), gen_nats:0':mark:pairs:odds:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1127.44/294.38 incr(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n888_0))) -> *4_0, rt in Omega(n888_0) 1127.44/294.38 s(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n1401_0))) -> *4_0, rt in Omega(n1401_0) 1127.44/294.38 1127.44/294.38 1127.44/294.38 Generator Equations: 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(0) <=> nats 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(+(x, 1)) <=> mark(gen_nats:0':mark:pairs:odds:ok3_0(x)) 1127.44/294.38 1127.44/294.38 1127.44/294.38 The following defined symbols remain to be analysed: 1127.44/294.38 head, active, tail, proper, top 1127.44/294.38 1127.44/294.38 They will be analysed ascendingly in the following order: 1127.44/294.38 head < active 1127.44/294.38 tail < active 1127.44/294.38 active < top 1127.44/294.38 head < proper 1127.44/294.38 tail < proper 1127.44/294.38 proper < top 1127.44/294.38 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1127.44/294.38 Proved the following rewrite lemma: 1127.44/294.38 head(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n2015_0))) -> *4_0, rt in Omega(n2015_0) 1127.44/294.38 1127.44/294.38 Induction Base: 1127.44/294.38 head(gen_nats:0':mark:pairs:odds:ok3_0(+(1, 0))) 1127.44/294.38 1127.44/294.38 Induction Step: 1127.44/294.38 head(gen_nats:0':mark:pairs:odds:ok3_0(+(1, +(n2015_0, 1)))) ->_R^Omega(1) 1127.44/294.38 mark(head(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n2015_0)))) ->_IH 1127.44/294.38 mark(*4_0) 1127.44/294.38 1127.44/294.38 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (18) 1127.44/294.38 Obligation: 1127.44/294.38 TRS: 1127.44/294.38 Rules: 1127.44/294.38 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.38 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.38 active(odds) -> mark(incr(pairs)) 1127.44/294.38 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.38 active(head(cons(X, XS))) -> mark(X) 1127.44/294.38 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.38 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.38 active(incr(X)) -> incr(active(X)) 1127.44/294.38 active(s(X)) -> s(active(X)) 1127.44/294.38 active(head(X)) -> head(active(X)) 1127.44/294.38 active(tail(X)) -> tail(active(X)) 1127.44/294.38 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.38 incr(mark(X)) -> mark(incr(X)) 1127.44/294.38 s(mark(X)) -> mark(s(X)) 1127.44/294.38 head(mark(X)) -> mark(head(X)) 1127.44/294.38 tail(mark(X)) -> mark(tail(X)) 1127.44/294.38 proper(nats) -> ok(nats) 1127.44/294.38 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.38 proper(0') -> ok(0') 1127.44/294.38 proper(incr(X)) -> incr(proper(X)) 1127.44/294.38 proper(pairs) -> ok(pairs) 1127.44/294.38 proper(odds) -> ok(odds) 1127.44/294.38 proper(s(X)) -> s(proper(X)) 1127.44/294.38 proper(head(X)) -> head(proper(X)) 1127.44/294.38 proper(tail(X)) -> tail(proper(X)) 1127.44/294.38 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.38 incr(ok(X)) -> ok(incr(X)) 1127.44/294.38 s(ok(X)) -> ok(s(X)) 1127.44/294.38 head(ok(X)) -> ok(head(X)) 1127.44/294.38 tail(ok(X)) -> ok(tail(X)) 1127.44/294.38 top(mark(X)) -> top(proper(X)) 1127.44/294.38 top(ok(X)) -> top(active(X)) 1127.44/294.38 1127.44/294.38 Types: 1127.44/294.38 active :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 nats :: nats:0':mark:pairs:odds:ok 1127.44/294.38 mark :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 cons :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 0' :: nats:0':mark:pairs:odds:ok 1127.44/294.38 incr :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 pairs :: nats:0':mark:pairs:odds:ok 1127.44/294.38 odds :: nats:0':mark:pairs:odds:ok 1127.44/294.38 s :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 head :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 tail :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 proper :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 ok :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 top :: nats:0':mark:pairs:odds:ok -> top 1127.44/294.38 hole_nats:0':mark:pairs:odds:ok1_0 :: nats:0':mark:pairs:odds:ok 1127.44/294.38 hole_top2_0 :: top 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0 :: Nat -> nats:0':mark:pairs:odds:ok 1127.44/294.38 1127.44/294.38 1127.44/294.38 Lemmas: 1127.44/294.38 cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n5_0)), gen_nats:0':mark:pairs:odds:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1127.44/294.38 incr(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n888_0))) -> *4_0, rt in Omega(n888_0) 1127.44/294.38 s(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n1401_0))) -> *4_0, rt in Omega(n1401_0) 1127.44/294.38 head(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n2015_0))) -> *4_0, rt in Omega(n2015_0) 1127.44/294.38 1127.44/294.38 1127.44/294.38 Generator Equations: 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(0) <=> nats 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(+(x, 1)) <=> mark(gen_nats:0':mark:pairs:odds:ok3_0(x)) 1127.44/294.38 1127.44/294.38 1127.44/294.38 The following defined symbols remain to be analysed: 1127.44/294.38 tail, active, proper, top 1127.44/294.38 1127.44/294.38 They will be analysed ascendingly in the following order: 1127.44/294.38 tail < active 1127.44/294.38 active < top 1127.44/294.38 tail < proper 1127.44/294.38 proper < top 1127.44/294.38 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1127.44/294.38 Proved the following rewrite lemma: 1127.44/294.38 tail(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n2730_0))) -> *4_0, rt in Omega(n2730_0) 1127.44/294.38 1127.44/294.38 Induction Base: 1127.44/294.38 tail(gen_nats:0':mark:pairs:odds:ok3_0(+(1, 0))) 1127.44/294.38 1127.44/294.38 Induction Step: 1127.44/294.38 tail(gen_nats:0':mark:pairs:odds:ok3_0(+(1, +(n2730_0, 1)))) ->_R^Omega(1) 1127.44/294.38 mark(tail(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n2730_0)))) ->_IH 1127.44/294.38 mark(*4_0) 1127.44/294.38 1127.44/294.38 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1127.44/294.38 ---------------------------------------- 1127.44/294.38 1127.44/294.38 (20) 1127.44/294.38 Obligation: 1127.44/294.38 TRS: 1127.44/294.38 Rules: 1127.44/294.38 active(nats) -> mark(cons(0', incr(nats))) 1127.44/294.38 active(pairs) -> mark(cons(0', incr(odds))) 1127.44/294.38 active(odds) -> mark(incr(pairs)) 1127.44/294.38 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 1127.44/294.38 active(head(cons(X, XS))) -> mark(X) 1127.44/294.38 active(tail(cons(X, XS))) -> mark(XS) 1127.44/294.38 active(cons(X1, X2)) -> cons(active(X1), X2) 1127.44/294.38 active(incr(X)) -> incr(active(X)) 1127.44/294.38 active(s(X)) -> s(active(X)) 1127.44/294.38 active(head(X)) -> head(active(X)) 1127.44/294.38 active(tail(X)) -> tail(active(X)) 1127.44/294.38 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1127.44/294.38 incr(mark(X)) -> mark(incr(X)) 1127.44/294.38 s(mark(X)) -> mark(s(X)) 1127.44/294.38 head(mark(X)) -> mark(head(X)) 1127.44/294.38 tail(mark(X)) -> mark(tail(X)) 1127.44/294.38 proper(nats) -> ok(nats) 1127.44/294.38 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1127.44/294.38 proper(0') -> ok(0') 1127.44/294.38 proper(incr(X)) -> incr(proper(X)) 1127.44/294.38 proper(pairs) -> ok(pairs) 1127.44/294.38 proper(odds) -> ok(odds) 1127.44/294.38 proper(s(X)) -> s(proper(X)) 1127.44/294.38 proper(head(X)) -> head(proper(X)) 1127.44/294.38 proper(tail(X)) -> tail(proper(X)) 1127.44/294.38 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1127.44/294.38 incr(ok(X)) -> ok(incr(X)) 1127.44/294.38 s(ok(X)) -> ok(s(X)) 1127.44/294.38 head(ok(X)) -> ok(head(X)) 1127.44/294.38 tail(ok(X)) -> ok(tail(X)) 1127.44/294.38 top(mark(X)) -> top(proper(X)) 1127.44/294.38 top(ok(X)) -> top(active(X)) 1127.44/294.38 1127.44/294.38 Types: 1127.44/294.38 active :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 nats :: nats:0':mark:pairs:odds:ok 1127.44/294.38 mark :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 cons :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 0' :: nats:0':mark:pairs:odds:ok 1127.44/294.38 incr :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 pairs :: nats:0':mark:pairs:odds:ok 1127.44/294.38 odds :: nats:0':mark:pairs:odds:ok 1127.44/294.38 s :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 head :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 tail :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 proper :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 ok :: nats:0':mark:pairs:odds:ok -> nats:0':mark:pairs:odds:ok 1127.44/294.38 top :: nats:0':mark:pairs:odds:ok -> top 1127.44/294.38 hole_nats:0':mark:pairs:odds:ok1_0 :: nats:0':mark:pairs:odds:ok 1127.44/294.38 hole_top2_0 :: top 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0 :: Nat -> nats:0':mark:pairs:odds:ok 1127.44/294.38 1127.44/294.38 1127.44/294.38 Lemmas: 1127.44/294.38 cons(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n5_0)), gen_nats:0':mark:pairs:odds:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 1127.44/294.38 incr(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n888_0))) -> *4_0, rt in Omega(n888_0) 1127.44/294.38 s(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n1401_0))) -> *4_0, rt in Omega(n1401_0) 1127.44/294.38 head(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n2015_0))) -> *4_0, rt in Omega(n2015_0) 1127.44/294.38 tail(gen_nats:0':mark:pairs:odds:ok3_0(+(1, n2730_0))) -> *4_0, rt in Omega(n2730_0) 1127.44/294.38 1127.44/294.38 1127.44/294.38 Generator Equations: 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(0) <=> nats 1127.44/294.38 gen_nats:0':mark:pairs:odds:ok3_0(+(x, 1)) <=> mark(gen_nats:0':mark:pairs:odds:ok3_0(x)) 1127.44/294.38 1127.44/294.38 1127.44/294.38 The following defined symbols remain to be analysed: 1127.44/294.38 active, proper, top 1127.44/294.38 1127.44/294.38 They will be analysed ascendingly in the following order: 1127.44/294.38 active < top 1127.44/294.38 proper < top 1127.65/294.44 EOF