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