1119.12/291.47 WORST_CASE(Omega(n^2), ?) 1125.01/292.98 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1125.01/292.98 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1125.01/292.98 1125.01/292.98 1125.01/292.98 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1125.01/292.98 1125.01/292.98 (0) CpxTRS 1125.01/292.98 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1125.01/292.98 (2) CpxTRS 1125.01/292.98 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1125.01/292.98 (4) typed CpxTrs 1125.01/292.98 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1125.01/292.98 (6) typed CpxTrs 1125.01/292.98 (7) RewriteLemmaProof [LOWER BOUND(ID), 532 ms] 1125.01/292.98 (8) BEST 1125.01/292.98 (9) proven lower bound 1125.01/292.98 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1125.01/292.98 (11) BOUNDS(n^1, INF) 1125.01/292.98 (12) typed CpxTrs 1125.01/292.98 (13) RewriteLemmaProof [LOWER BOUND(ID), 756 ms] 1125.01/292.98 (14) BEST 1125.01/292.98 (15) proven lower bound 1125.01/292.98 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1125.01/292.98 (17) BOUNDS(n^2, INF) 1125.01/292.98 (18) typed CpxTrs 1125.01/292.98 (19) RewriteLemmaProof [LOWER BOUND(ID), 42 ms] 1125.01/292.98 (20) BOUNDS(1, INF) 1125.01/292.98 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (0) 1125.01/292.98 Obligation: 1125.01/292.98 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1125.01/292.98 1125.01/292.98 1125.01/292.98 The TRS R consists of the following rules: 1125.01/292.98 1125.01/292.98 a__and(tt, X) -> mark(X) 1125.01/292.98 a__plus(N, 0) -> mark(N) 1125.01/292.98 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1125.01/292.98 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1125.01/292.98 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1125.01/292.98 mark(tt) -> tt 1125.01/292.98 mark(0) -> 0 1125.01/292.98 mark(s(X)) -> s(mark(X)) 1125.01/292.98 a__and(X1, X2) -> and(X1, X2) 1125.01/292.98 a__plus(X1, X2) -> plus(X1, X2) 1125.01/292.98 1125.01/292.98 S is empty. 1125.01/292.98 Rewrite Strategy: FULL 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1125.01/292.98 Renamed function symbols to avoid clashes with predefined symbol. 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (2) 1125.01/292.98 Obligation: 1125.01/292.98 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1125.01/292.98 1125.01/292.98 1125.01/292.98 The TRS R consists of the following rules: 1125.01/292.98 1125.01/292.98 a__and(tt, X) -> mark(X) 1125.01/292.98 a__plus(N, 0') -> mark(N) 1125.01/292.98 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1125.01/292.98 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1125.01/292.98 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1125.01/292.98 mark(tt) -> tt 1125.01/292.98 mark(0') -> 0' 1125.01/292.98 mark(s(X)) -> s(mark(X)) 1125.01/292.98 a__and(X1, X2) -> and(X1, X2) 1125.01/292.98 a__plus(X1, X2) -> plus(X1, X2) 1125.01/292.98 1125.01/292.98 S is empty. 1125.01/292.98 Rewrite Strategy: FULL 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1125.01/292.98 Infered types. 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (4) 1125.01/292.98 Obligation: 1125.01/292.98 TRS: 1125.01/292.98 Rules: 1125.01/292.98 a__and(tt, X) -> mark(X) 1125.01/292.98 a__plus(N, 0') -> mark(N) 1125.01/292.98 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1125.01/292.98 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1125.01/292.98 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1125.01/292.98 mark(tt) -> tt 1125.01/292.98 mark(0') -> 0' 1125.01/292.98 mark(s(X)) -> s(mark(X)) 1125.01/292.98 a__and(X1, X2) -> and(X1, X2) 1125.01/292.98 a__plus(X1, X2) -> plus(X1, X2) 1125.01/292.98 1125.01/292.98 Types: 1125.01/292.98 a__and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 tt :: tt:0':s:and:plus 1125.01/292.98 mark :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 a__plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 0' :: tt:0':s:and:plus 1125.01/292.98 s :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 hole_tt:0':s:and:plus1_0 :: tt:0':s:and:plus 1125.01/292.98 gen_tt:0':s:and:plus2_0 :: Nat -> tt:0':s:and:plus 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (5) OrderProof (LOWER BOUND(ID)) 1125.01/292.98 Heuristically decided to analyse the following defined symbols: 1125.01/292.98 mark, a__plus 1125.01/292.98 1125.01/292.98 They will be analysed ascendingly in the following order: 1125.01/292.98 mark = a__plus 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (6) 1125.01/292.98 Obligation: 1125.01/292.98 TRS: 1125.01/292.98 Rules: 1125.01/292.98 a__and(tt, X) -> mark(X) 1125.01/292.98 a__plus(N, 0') -> mark(N) 1125.01/292.98 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1125.01/292.98 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1125.01/292.98 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1125.01/292.98 mark(tt) -> tt 1125.01/292.98 mark(0') -> 0' 1125.01/292.98 mark(s(X)) -> s(mark(X)) 1125.01/292.98 a__and(X1, X2) -> and(X1, X2) 1125.01/292.98 a__plus(X1, X2) -> plus(X1, X2) 1125.01/292.98 1125.01/292.98 Types: 1125.01/292.98 a__and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 tt :: tt:0':s:and:plus 1125.01/292.98 mark :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 a__plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 0' :: tt:0':s:and:plus 1125.01/292.98 s :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 hole_tt:0':s:and:plus1_0 :: tt:0':s:and:plus 1125.01/292.98 gen_tt:0':s:and:plus2_0 :: Nat -> tt:0':s:and:plus 1125.01/292.98 1125.01/292.98 1125.01/292.98 Generator Equations: 1125.01/292.98 gen_tt:0':s:and:plus2_0(0) <=> tt 1125.01/292.98 gen_tt:0':s:and:plus2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus2_0(x)) 1125.01/292.98 1125.01/292.98 1125.01/292.98 The following defined symbols remain to be analysed: 1125.01/292.98 a__plus, mark 1125.01/292.98 1125.01/292.98 They will be analysed ascendingly in the following order: 1125.01/292.98 mark = a__plus 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1125.01/292.98 Proved the following rewrite lemma: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(n5360_0)) -> gen_tt:0':s:and:plus2_0(n5360_0), rt in Omega(1 + n5360_0) 1125.01/292.98 1125.01/292.98 Induction Base: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(0)) ->_R^Omega(1) 1125.01/292.98 tt 1125.01/292.98 1125.01/292.98 Induction Step: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(+(n5360_0, 1))) ->_R^Omega(1) 1125.01/292.98 s(mark(gen_tt:0':s:and:plus2_0(n5360_0))) ->_IH 1125.01/292.98 s(gen_tt:0':s:and:plus2_0(c5361_0)) 1125.01/292.98 1125.01/292.98 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (8) 1125.01/292.98 Complex Obligation (BEST) 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (9) 1125.01/292.98 Obligation: 1125.01/292.98 Proved the lower bound n^1 for the following obligation: 1125.01/292.98 1125.01/292.98 TRS: 1125.01/292.98 Rules: 1125.01/292.98 a__and(tt, X) -> mark(X) 1125.01/292.98 a__plus(N, 0') -> mark(N) 1125.01/292.98 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1125.01/292.98 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1125.01/292.98 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1125.01/292.98 mark(tt) -> tt 1125.01/292.98 mark(0') -> 0' 1125.01/292.98 mark(s(X)) -> s(mark(X)) 1125.01/292.98 a__and(X1, X2) -> and(X1, X2) 1125.01/292.98 a__plus(X1, X2) -> plus(X1, X2) 1125.01/292.98 1125.01/292.98 Types: 1125.01/292.98 a__and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 tt :: tt:0':s:and:plus 1125.01/292.98 mark :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 a__plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 0' :: tt:0':s:and:plus 1125.01/292.98 s :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 hole_tt:0':s:and:plus1_0 :: tt:0':s:and:plus 1125.01/292.98 gen_tt:0':s:and:plus2_0 :: Nat -> tt:0':s:and:plus 1125.01/292.98 1125.01/292.98 1125.01/292.98 Generator Equations: 1125.01/292.98 gen_tt:0':s:and:plus2_0(0) <=> tt 1125.01/292.98 gen_tt:0':s:and:plus2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus2_0(x)) 1125.01/292.98 1125.01/292.98 1125.01/292.98 The following defined symbols remain to be analysed: 1125.01/292.98 mark 1125.01/292.98 1125.01/292.98 They will be analysed ascendingly in the following order: 1125.01/292.98 mark = a__plus 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (10) LowerBoundPropagationProof (FINISHED) 1125.01/292.98 Propagated lower bound. 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (11) 1125.01/292.98 BOUNDS(n^1, INF) 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (12) 1125.01/292.98 Obligation: 1125.01/292.98 TRS: 1125.01/292.98 Rules: 1125.01/292.98 a__and(tt, X) -> mark(X) 1125.01/292.98 a__plus(N, 0') -> mark(N) 1125.01/292.98 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1125.01/292.98 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1125.01/292.98 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1125.01/292.98 mark(tt) -> tt 1125.01/292.98 mark(0') -> 0' 1125.01/292.98 mark(s(X)) -> s(mark(X)) 1125.01/292.98 a__and(X1, X2) -> and(X1, X2) 1125.01/292.98 a__plus(X1, X2) -> plus(X1, X2) 1125.01/292.98 1125.01/292.98 Types: 1125.01/292.98 a__and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 tt :: tt:0':s:and:plus 1125.01/292.98 mark :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 a__plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 0' :: tt:0':s:and:plus 1125.01/292.98 s :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 hole_tt:0':s:and:plus1_0 :: tt:0':s:and:plus 1125.01/292.98 gen_tt:0':s:and:plus2_0 :: Nat -> tt:0':s:and:plus 1125.01/292.98 1125.01/292.98 1125.01/292.98 Lemmas: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(n5360_0)) -> gen_tt:0':s:and:plus2_0(n5360_0), rt in Omega(1 + n5360_0) 1125.01/292.98 1125.01/292.98 1125.01/292.98 Generator Equations: 1125.01/292.98 gen_tt:0':s:and:plus2_0(0) <=> tt 1125.01/292.98 gen_tt:0':s:and:plus2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus2_0(x)) 1125.01/292.98 1125.01/292.98 1125.01/292.98 The following defined symbols remain to be analysed: 1125.01/292.98 a__plus 1125.01/292.98 1125.01/292.98 They will be analysed ascendingly in the following order: 1125.01/292.98 mark = a__plus 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1125.01/292.98 Proved the following rewrite lemma: 1125.01/292.98 a__plus(gen_tt:0':s:and:plus2_0(a), gen_tt:0':s:and:plus2_0(+(1, n5915_0))) -> *3_0, rt in Omega(a*n5915_0 + n5915_0 + n5915_0^2) 1125.01/292.98 1125.01/292.98 Induction Base: 1125.01/292.98 a__plus(gen_tt:0':s:and:plus2_0(a), gen_tt:0':s:and:plus2_0(+(1, 0))) 1125.01/292.98 1125.01/292.98 Induction Step: 1125.01/292.98 a__plus(gen_tt:0':s:and:plus2_0(a), gen_tt:0':s:and:plus2_0(+(1, +(n5915_0, 1)))) ->_R^Omega(1) 1125.01/292.98 s(a__plus(mark(gen_tt:0':s:and:plus2_0(a)), mark(gen_tt:0':s:and:plus2_0(+(1, n5915_0))))) ->_L^Omega(1 + a) 1125.01/292.98 s(a__plus(gen_tt:0':s:and:plus2_0(a), mark(gen_tt:0':s:and:plus2_0(+(1, n5915_0))))) ->_L^Omega(2 + n5915_0) 1125.01/292.98 s(a__plus(gen_tt:0':s:and:plus2_0(a), gen_tt:0':s:and:plus2_0(+(1, n5915_0)))) ->_IH 1125.01/292.98 s(*3_0) 1125.01/292.98 1125.01/292.98 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (14) 1125.01/292.98 Complex Obligation (BEST) 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (15) 1125.01/292.98 Obligation: 1125.01/292.98 Proved the lower bound n^2 for the following obligation: 1125.01/292.98 1125.01/292.98 TRS: 1125.01/292.98 Rules: 1125.01/292.98 a__and(tt, X) -> mark(X) 1125.01/292.98 a__plus(N, 0') -> mark(N) 1125.01/292.98 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1125.01/292.98 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1125.01/292.98 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1125.01/292.98 mark(tt) -> tt 1125.01/292.98 mark(0') -> 0' 1125.01/292.98 mark(s(X)) -> s(mark(X)) 1125.01/292.98 a__and(X1, X2) -> and(X1, X2) 1125.01/292.98 a__plus(X1, X2) -> plus(X1, X2) 1125.01/292.98 1125.01/292.98 Types: 1125.01/292.98 a__and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 tt :: tt:0':s:and:plus 1125.01/292.98 mark :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 a__plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 0' :: tt:0':s:and:plus 1125.01/292.98 s :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 hole_tt:0':s:and:plus1_0 :: tt:0':s:and:plus 1125.01/292.98 gen_tt:0':s:and:plus2_0 :: Nat -> tt:0':s:and:plus 1125.01/292.98 1125.01/292.98 1125.01/292.98 Lemmas: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(n5360_0)) -> gen_tt:0':s:and:plus2_0(n5360_0), rt in Omega(1 + n5360_0) 1125.01/292.98 1125.01/292.98 1125.01/292.98 Generator Equations: 1125.01/292.98 gen_tt:0':s:and:plus2_0(0) <=> tt 1125.01/292.98 gen_tt:0':s:and:plus2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus2_0(x)) 1125.01/292.98 1125.01/292.98 1125.01/292.98 The following defined symbols remain to be analysed: 1125.01/292.98 a__plus 1125.01/292.98 1125.01/292.98 They will be analysed ascendingly in the following order: 1125.01/292.98 mark = a__plus 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (16) LowerBoundPropagationProof (FINISHED) 1125.01/292.98 Propagated lower bound. 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (17) 1125.01/292.98 BOUNDS(n^2, INF) 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (18) 1125.01/292.98 Obligation: 1125.01/292.98 TRS: 1125.01/292.98 Rules: 1125.01/292.98 a__and(tt, X) -> mark(X) 1125.01/292.98 a__plus(N, 0') -> mark(N) 1125.01/292.98 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1125.01/292.98 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1125.01/292.98 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1125.01/292.98 mark(tt) -> tt 1125.01/292.98 mark(0') -> 0' 1125.01/292.98 mark(s(X)) -> s(mark(X)) 1125.01/292.98 a__and(X1, X2) -> and(X1, X2) 1125.01/292.98 a__plus(X1, X2) -> plus(X1, X2) 1125.01/292.98 1125.01/292.98 Types: 1125.01/292.98 a__and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 tt :: tt:0':s:and:plus 1125.01/292.98 mark :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 a__plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 0' :: tt:0':s:and:plus 1125.01/292.98 s :: tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 and :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 plus :: tt:0':s:and:plus -> tt:0':s:and:plus -> tt:0':s:and:plus 1125.01/292.98 hole_tt:0':s:and:plus1_0 :: tt:0':s:and:plus 1125.01/292.98 gen_tt:0':s:and:plus2_0 :: Nat -> tt:0':s:and:plus 1125.01/292.98 1125.01/292.98 1125.01/292.98 Lemmas: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(n5360_0)) -> gen_tt:0':s:and:plus2_0(n5360_0), rt in Omega(1 + n5360_0) 1125.01/292.98 a__plus(gen_tt:0':s:and:plus2_0(a), gen_tt:0':s:and:plus2_0(+(1, n5915_0))) -> *3_0, rt in Omega(a*n5915_0 + n5915_0 + n5915_0^2) 1125.01/292.98 1125.01/292.98 1125.01/292.98 Generator Equations: 1125.01/292.98 gen_tt:0':s:and:plus2_0(0) <=> tt 1125.01/292.98 gen_tt:0':s:and:plus2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus2_0(x)) 1125.01/292.98 1125.01/292.98 1125.01/292.98 The following defined symbols remain to be analysed: 1125.01/292.98 mark 1125.01/292.98 1125.01/292.98 They will be analysed ascendingly in the following order: 1125.01/292.98 mark = a__plus 1125.01/292.98 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1125.01/292.98 Proved the following rewrite lemma: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(n7074_0)) -> gen_tt:0':s:and:plus2_0(n7074_0), rt in Omega(1 + n7074_0) 1125.01/292.98 1125.01/292.98 Induction Base: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(0)) ->_R^Omega(1) 1125.01/292.98 tt 1125.01/292.98 1125.01/292.98 Induction Step: 1125.01/292.98 mark(gen_tt:0':s:and:plus2_0(+(n7074_0, 1))) ->_R^Omega(1) 1125.01/292.98 s(mark(gen_tt:0':s:and:plus2_0(n7074_0))) ->_IH 1125.01/292.98 s(gen_tt:0':s:and:plus2_0(c7075_0)) 1125.01/292.98 1125.01/292.98 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1125.01/292.98 ---------------------------------------- 1125.01/292.98 1125.01/292.98 (20) 1125.01/292.98 BOUNDS(1, INF) 1125.15/293.05 EOF