1118.46/291.46 WORST_CASE(Omega(n^2), ?) 1118.46/291.48 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1118.46/291.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1118.46/291.48 1118.46/291.48 1118.46/291.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1118.46/291.48 1118.46/291.48 (0) CpxTRS 1118.46/291.48 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.46/291.48 (2) CpxTRS 1118.46/291.48 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 8 ms] 1118.46/291.48 (4) typed CpxTrs 1118.46/291.48 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1118.46/291.48 (6) typed CpxTrs 1118.46/291.48 (7) RewriteLemmaProof [LOWER BOUND(ID), 670 ms] 1118.46/291.48 (8) BEST 1118.46/291.48 (9) proven lower bound 1118.46/291.48 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1118.46/291.48 (11) BOUNDS(n^1, INF) 1118.46/291.48 (12) typed CpxTrs 1118.46/291.48 (13) RewriteLemmaProof [LOWER BOUND(ID), 137 ms] 1118.46/291.48 (14) BEST 1118.46/291.48 (15) proven lower bound 1118.46/291.48 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1118.46/291.48 (17) BOUNDS(n^2, INF) 1118.46/291.48 (18) typed CpxTrs 1118.46/291.48 (19) RewriteLemmaProof [LOWER BOUND(ID), 155 ms] 1118.46/291.48 (20) typed CpxTrs 1118.46/291.48 (21) RewriteLemmaProof [LOWER BOUND(ID), 141 ms] 1118.46/291.48 (22) typed CpxTrs 1118.46/291.48 (23) RewriteLemmaProof [LOWER BOUND(ID), 34 ms] 1118.46/291.48 (24) typed CpxTrs 1118.46/291.48 (25) RewriteLemmaProof [LOWER BOUND(ID), 95 ms] 1118.46/291.48 (26) typed CpxTrs 1118.46/291.48 (27) RewriteLemmaProof [LOWER BOUND(ID), 138 ms] 1118.46/291.48 (28) BOUNDS(1, INF) 1118.46/291.48 1118.46/291.48 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (0) 1118.46/291.48 Obligation: 1118.46/291.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1118.46/291.48 1118.46/291.48 1118.46/291.48 The TRS R consists of the following rules: 1118.46/291.48 1118.46/291.48 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.46/291.48 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.46/291.48 a__plus(N, 0) -> mark(N) 1118.46/291.48 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.46/291.48 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.46/291.48 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.46/291.48 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.46/291.48 mark(tt) -> tt 1118.46/291.48 mark(s(X)) -> s(mark(X)) 1118.46/291.48 mark(0) -> 0 1118.46/291.48 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.46/291.48 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.46/291.48 a__plus(X1, X2) -> plus(X1, X2) 1118.46/291.48 1118.46/291.48 S is empty. 1118.46/291.48 Rewrite Strategy: INNERMOST 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1118.46/291.48 Renamed function symbols to avoid clashes with predefined symbol. 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (2) 1118.46/291.48 Obligation: 1118.46/291.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1118.46/291.48 1118.46/291.48 1118.46/291.48 The TRS R consists of the following rules: 1118.46/291.48 1118.46/291.48 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.46/291.48 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.46/291.48 a__plus(N, 0') -> mark(N) 1118.46/291.48 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.46/291.48 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.46/291.48 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.46/291.48 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.46/291.48 mark(tt) -> tt 1118.46/291.48 mark(s(X)) -> s(mark(X)) 1118.46/291.48 mark(0') -> 0' 1118.46/291.48 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.46/291.48 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.46/291.48 a__plus(X1, X2) -> plus(X1, X2) 1118.46/291.48 1118.46/291.48 S is empty. 1118.46/291.48 Rewrite Strategy: INNERMOST 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1118.46/291.48 Infered types. 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (4) 1118.46/291.48 Obligation: 1118.46/291.48 Innermost TRS: 1118.46/291.48 Rules: 1118.46/291.48 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.46/291.48 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.46/291.48 a__plus(N, 0') -> mark(N) 1118.46/291.48 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.46/291.48 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.46/291.48 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.46/291.48 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.46/291.48 mark(tt) -> tt 1118.46/291.48 mark(s(X)) -> s(mark(X)) 1118.46/291.48 mark(0') -> 0' 1118.46/291.48 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.46/291.48 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.46/291.48 a__plus(X1, X2) -> plus(X1, X2) 1118.46/291.48 1118.46/291.48 Types: 1118.46/291.48 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 tt :: tt:s:0':U11:U12:plus 1118.46/291.48 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 0' :: tt:s:0':U11:U12:plus 1118.46/291.48 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.46/291.48 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.46/291.48 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (5) OrderProof (LOWER BOUND(ID)) 1118.46/291.48 Heuristically decided to analyse the following defined symbols: 1118.46/291.48 a__U11, a__U12, a__plus, mark 1118.46/291.48 1118.46/291.48 They will be analysed ascendingly in the following order: 1118.46/291.48 a__U11 = a__U12 1118.46/291.48 a__U11 = a__plus 1118.46/291.48 a__U11 = mark 1118.46/291.48 a__U12 = a__plus 1118.46/291.48 a__U12 = mark 1118.46/291.48 a__plus = mark 1118.46/291.48 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (6) 1118.46/291.48 Obligation: 1118.46/291.48 Innermost TRS: 1118.46/291.48 Rules: 1118.46/291.48 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.46/291.48 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.46/291.48 a__plus(N, 0') -> mark(N) 1118.46/291.48 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.46/291.48 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.46/291.48 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.46/291.48 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.46/291.48 mark(tt) -> tt 1118.46/291.48 mark(s(X)) -> s(mark(X)) 1118.46/291.48 mark(0') -> 0' 1118.46/291.48 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.46/291.48 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.46/291.48 a__plus(X1, X2) -> plus(X1, X2) 1118.46/291.48 1118.46/291.48 Types: 1118.46/291.48 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 tt :: tt:s:0':U11:U12:plus 1118.46/291.48 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 0' :: tt:s:0':U11:U12:plus 1118.46/291.48 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.46/291.48 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.46/291.48 1118.46/291.48 1118.46/291.48 Generator Equations: 1118.46/291.48 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.46/291.48 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.46/291.48 1118.46/291.48 1118.46/291.48 The following defined symbols remain to be analysed: 1118.46/291.48 a__U12, a__U11, a__plus, mark 1118.46/291.48 1118.46/291.48 They will be analysed ascendingly in the following order: 1118.46/291.48 a__U11 = a__U12 1118.46/291.48 a__U11 = a__plus 1118.46/291.48 a__U11 = mark 1118.46/291.48 a__U12 = a__plus 1118.46/291.48 a__U12 = mark 1118.46/291.48 a__plus = mark 1118.46/291.48 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1118.46/291.48 Proved the following rewrite lemma: 1118.46/291.48 mark(gen_tt:s:0':U11:U12:plus2_0(n7802_0)) -> gen_tt:s:0':U11:U12:plus2_0(n7802_0), rt in Omega(1 + n7802_0) 1118.46/291.48 1118.46/291.48 Induction Base: 1118.46/291.48 mark(gen_tt:s:0':U11:U12:plus2_0(0)) ->_R^Omega(1) 1118.46/291.48 tt 1118.46/291.48 1118.46/291.48 Induction Step: 1118.46/291.48 mark(gen_tt:s:0':U11:U12:plus2_0(+(n7802_0, 1))) ->_R^Omega(1) 1118.46/291.48 s(mark(gen_tt:s:0':U11:U12:plus2_0(n7802_0))) ->_IH 1118.46/291.48 s(gen_tt:s:0':U11:U12:plus2_0(c7803_0)) 1118.46/291.48 1118.46/291.48 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (8) 1118.46/291.48 Complex Obligation (BEST) 1118.46/291.48 1118.46/291.48 ---------------------------------------- 1118.46/291.48 1118.46/291.48 (9) 1118.46/291.48 Obligation: 1118.46/291.48 Proved the lower bound n^1 for the following obligation: 1118.46/291.48 1118.46/291.48 Innermost TRS: 1118.46/291.48 Rules: 1118.46/291.48 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.46/291.48 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.46/291.48 a__plus(N, 0') -> mark(N) 1118.46/291.48 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.46/291.48 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.46/291.48 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.46/291.48 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.46/291.48 mark(tt) -> tt 1118.46/291.48 mark(s(X)) -> s(mark(X)) 1118.46/291.48 mark(0') -> 0' 1118.46/291.48 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.46/291.48 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.46/291.48 a__plus(X1, X2) -> plus(X1, X2) 1118.46/291.48 1118.46/291.48 Types: 1118.46/291.48 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 tt :: tt:s:0':U11:U12:plus 1118.46/291.48 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.46/291.48 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 0' :: tt:s:0':U11:U12:plus 1118.61/291.50 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.61/291.50 1118.61/291.50 1118.61/291.50 Generator Equations: 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.61/291.50 1118.61/291.50 1118.61/291.50 The following defined symbols remain to be analysed: 1118.61/291.50 mark, a__U11 1118.61/291.50 1118.61/291.50 They will be analysed ascendingly in the following order: 1118.61/291.50 a__U11 = a__U12 1118.61/291.50 a__U11 = a__plus 1118.61/291.50 a__U11 = mark 1118.61/291.50 a__U12 = a__plus 1118.61/291.50 a__U12 = mark 1118.61/291.50 a__plus = mark 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (10) LowerBoundPropagationProof (FINISHED) 1118.61/291.50 Propagated lower bound. 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (11) 1118.61/291.50 BOUNDS(n^1, INF) 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (12) 1118.61/291.50 Obligation: 1118.61/291.50 Innermost TRS: 1118.61/291.50 Rules: 1118.61/291.50 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.61/291.50 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.61/291.50 a__plus(N, 0') -> mark(N) 1118.61/291.50 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.61/291.50 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.61/291.50 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.61/291.50 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.61/291.50 mark(tt) -> tt 1118.61/291.50 mark(s(X)) -> s(mark(X)) 1118.61/291.50 mark(0') -> 0' 1118.61/291.50 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.61/291.50 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.61/291.50 a__plus(X1, X2) -> plus(X1, X2) 1118.61/291.50 1118.61/291.50 Types: 1118.61/291.50 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 tt :: tt:s:0':U11:U12:plus 1118.61/291.50 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 0' :: tt:s:0':U11:U12:plus 1118.61/291.50 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.61/291.50 1118.61/291.50 1118.61/291.50 Lemmas: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(n7802_0)) -> gen_tt:s:0':U11:U12:plus2_0(n7802_0), rt in Omega(1 + n7802_0) 1118.61/291.50 1118.61/291.50 1118.61/291.50 Generator Equations: 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.61/291.50 1118.61/291.50 1118.61/291.50 The following defined symbols remain to be analysed: 1118.61/291.50 a__U11, a__U12, a__plus 1118.61/291.50 1118.61/291.50 They will be analysed ascendingly in the following order: 1118.61/291.50 a__U11 = a__U12 1118.61/291.50 a__U11 = a__plus 1118.61/291.50 a__U11 = mark 1118.61/291.50 a__U12 = a__plus 1118.61/291.50 a__U12 = mark 1118.61/291.50 a__plus = mark 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1118.61/291.50 Proved the following rewrite lemma: 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n8550_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n8550_0 + n8550_0 + n8550_0^2) 1118.61/291.50 1118.61/291.50 Induction Base: 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(c)) 1118.61/291.50 1118.61/291.50 Induction Step: 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(+(n8550_0, 1)), gen_tt:s:0':U11:U12:plus2_0(c)) ->_R^Omega(1) 1118.61/291.50 a__U12(tt, gen_tt:s:0':U11:U12:plus2_0(+(n8550_0, 1)), gen_tt:s:0':U11:U12:plus2_0(c)) ->_R^Omega(1) 1118.61/291.50 s(a__plus(mark(gen_tt:s:0':U11:U12:plus2_0(c)), mark(gen_tt:s:0':U11:U12:plus2_0(+(1, n8550_0))))) ->_L^Omega(1 + c) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(c), mark(gen_tt:s:0':U11:U12:plus2_0(+(1, n8550_0))))) ->_L^Omega(2 + n8550_0) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(c), gen_tt:s:0':U11:U12:plus2_0(+(1, n8550_0)))) ->_R^Omega(1) 1118.61/291.50 s(a__U11(tt, gen_tt:s:0':U11:U12:plus2_0(n8550_0), gen_tt:s:0':U11:U12:plus2_0(c))) ->_IH 1118.61/291.50 s(*3_0) 1118.61/291.50 1118.61/291.50 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (14) 1118.61/291.50 Complex Obligation (BEST) 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (15) 1118.61/291.50 Obligation: 1118.61/291.50 Proved the lower bound n^2 for the following obligation: 1118.61/291.50 1118.61/291.50 Innermost TRS: 1118.61/291.50 Rules: 1118.61/291.50 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.61/291.50 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.61/291.50 a__plus(N, 0') -> mark(N) 1118.61/291.50 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.61/291.50 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.61/291.50 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.61/291.50 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.61/291.50 mark(tt) -> tt 1118.61/291.50 mark(s(X)) -> s(mark(X)) 1118.61/291.50 mark(0') -> 0' 1118.61/291.50 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.61/291.50 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.61/291.50 a__plus(X1, X2) -> plus(X1, X2) 1118.61/291.50 1118.61/291.50 Types: 1118.61/291.50 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 tt :: tt:s:0':U11:U12:plus 1118.61/291.50 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 0' :: tt:s:0':U11:U12:plus 1118.61/291.50 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.61/291.50 1118.61/291.50 1118.61/291.50 Lemmas: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(n7802_0)) -> gen_tt:s:0':U11:U12:plus2_0(n7802_0), rt in Omega(1 + n7802_0) 1118.61/291.50 1118.61/291.50 1118.61/291.50 Generator Equations: 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.61/291.50 1118.61/291.50 1118.61/291.50 The following defined symbols remain to be analysed: 1118.61/291.50 a__U11, a__U12, a__plus 1118.61/291.50 1118.61/291.50 They will be analysed ascendingly in the following order: 1118.61/291.50 a__U11 = a__U12 1118.61/291.50 a__U11 = a__plus 1118.61/291.50 a__U11 = mark 1118.61/291.50 a__U12 = a__plus 1118.61/291.50 a__U12 = mark 1118.61/291.50 a__plus = mark 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (16) LowerBoundPropagationProof (FINISHED) 1118.61/291.50 Propagated lower bound. 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (17) 1118.61/291.50 BOUNDS(n^2, INF) 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (18) 1118.61/291.50 Obligation: 1118.61/291.50 Innermost TRS: 1118.61/291.50 Rules: 1118.61/291.50 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.61/291.50 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.61/291.50 a__plus(N, 0') -> mark(N) 1118.61/291.50 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.61/291.50 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.61/291.50 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.61/291.50 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.61/291.50 mark(tt) -> tt 1118.61/291.50 mark(s(X)) -> s(mark(X)) 1118.61/291.50 mark(0') -> 0' 1118.61/291.50 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.61/291.50 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.61/291.50 a__plus(X1, X2) -> plus(X1, X2) 1118.61/291.50 1118.61/291.50 Types: 1118.61/291.50 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 tt :: tt:s:0':U11:U12:plus 1118.61/291.50 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 0' :: tt:s:0':U11:U12:plus 1118.61/291.50 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.61/291.50 1118.61/291.50 1118.61/291.50 Lemmas: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(n7802_0)) -> gen_tt:s:0':U11:U12:plus2_0(n7802_0), rt in Omega(1 + n7802_0) 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n8550_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n8550_0 + n8550_0 + n8550_0^2) 1118.61/291.50 1118.61/291.50 1118.61/291.50 Generator Equations: 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.61/291.50 1118.61/291.50 1118.61/291.50 The following defined symbols remain to be analysed: 1118.61/291.50 a__U12, a__plus, mark 1118.61/291.50 1118.61/291.50 They will be analysed ascendingly in the following order: 1118.61/291.50 a__U11 = a__U12 1118.61/291.50 a__U11 = a__plus 1118.61/291.50 a__U11 = mark 1118.61/291.50 a__U12 = a__plus 1118.61/291.50 a__U12 = mark 1118.61/291.50 a__plus = mark 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1118.61/291.50 Proved the following rewrite lemma: 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n11303_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n11303_0 + n11303_0 + n11303_0^2) 1118.61/291.50 1118.61/291.50 Induction Base: 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(c)) 1118.61/291.50 1118.61/291.50 Induction Step: 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(+(n11303_0, 1)), gen_tt:s:0':U11:U12:plus2_0(c)) ->_R^Omega(1) 1118.61/291.50 s(a__plus(mark(gen_tt:s:0':U11:U12:plus2_0(c)), mark(gen_tt:s:0':U11:U12:plus2_0(+(n11303_0, 1))))) ->_L^Omega(1 + c) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(c), mark(gen_tt:s:0':U11:U12:plus2_0(+(1, n11303_0))))) ->_L^Omega(2 + n11303_0) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(c), gen_tt:s:0':U11:U12:plus2_0(+(1, n11303_0)))) ->_R^Omega(1) 1118.61/291.50 s(a__U11(tt, gen_tt:s:0':U11:U12:plus2_0(n11303_0), gen_tt:s:0':U11:U12:plus2_0(c))) ->_R^Omega(1) 1118.61/291.50 s(a__U12(tt, gen_tt:s:0':U11:U12:plus2_0(n11303_0), gen_tt:s:0':U11:U12:plus2_0(c))) ->_IH 1118.61/291.50 s(*3_0) 1118.61/291.50 1118.61/291.50 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (20) 1118.61/291.50 Obligation: 1118.61/291.50 Innermost TRS: 1118.61/291.50 Rules: 1118.61/291.50 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.61/291.50 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.61/291.50 a__plus(N, 0') -> mark(N) 1118.61/291.50 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.61/291.50 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.61/291.50 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.61/291.50 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.61/291.50 mark(tt) -> tt 1118.61/291.50 mark(s(X)) -> s(mark(X)) 1118.61/291.50 mark(0') -> 0' 1118.61/291.50 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.61/291.50 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.61/291.50 a__plus(X1, X2) -> plus(X1, X2) 1118.61/291.50 1118.61/291.50 Types: 1118.61/291.50 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 tt :: tt:s:0':U11:U12:plus 1118.61/291.50 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 0' :: tt:s:0':U11:U12:plus 1118.61/291.50 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.61/291.50 1118.61/291.50 1118.61/291.50 Lemmas: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(n7802_0)) -> gen_tt:s:0':U11:U12:plus2_0(n7802_0), rt in Omega(1 + n7802_0) 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n8550_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n8550_0 + n8550_0 + n8550_0^2) 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n11303_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n11303_0 + n11303_0 + n11303_0^2) 1118.61/291.50 1118.61/291.50 1118.61/291.50 Generator Equations: 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.61/291.50 1118.61/291.50 1118.61/291.50 The following defined symbols remain to be analysed: 1118.61/291.50 a__plus, a__U11, mark 1118.61/291.50 1118.61/291.50 They will be analysed ascendingly in the following order: 1118.61/291.50 a__U11 = a__U12 1118.61/291.50 a__U11 = a__plus 1118.61/291.50 a__U11 = mark 1118.61/291.50 a__U12 = a__plus 1118.61/291.50 a__U12 = mark 1118.61/291.50 a__plus = mark 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (21) RewriteLemmaProof (LOWER BOUND(ID)) 1118.61/291.50 Proved the following rewrite lemma: 1118.61/291.50 a__plus(gen_tt:s:0':U11:U12:plus2_0(a), gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0))) -> *3_0, rt in Omega(a*n14266_0 + n14266_0 + n14266_0^2) 1118.61/291.50 1118.61/291.50 Induction Base: 1118.61/291.50 a__plus(gen_tt:s:0':U11:U12:plus2_0(a), gen_tt:s:0':U11:U12:plus2_0(+(1, 0))) 1118.61/291.50 1118.61/291.50 Induction Step: 1118.61/291.50 a__plus(gen_tt:s:0':U11:U12:plus2_0(a), gen_tt:s:0':U11:U12:plus2_0(+(1, +(n14266_0, 1)))) ->_R^Omega(1) 1118.61/291.50 a__U11(tt, gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0)), gen_tt:s:0':U11:U12:plus2_0(a)) ->_R^Omega(1) 1118.61/291.50 a__U12(tt, gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0)), gen_tt:s:0':U11:U12:plus2_0(a)) ->_R^Omega(1) 1118.61/291.50 s(a__plus(mark(gen_tt:s:0':U11:U12:plus2_0(a)), mark(gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0))))) ->_L^Omega(1 + a) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(a), mark(gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0))))) ->_L^Omega(2 + n14266_0) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(a), gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0)))) ->_IH 1118.61/291.50 s(*3_0) 1118.61/291.50 1118.61/291.50 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (22) 1118.61/291.50 Obligation: 1118.61/291.50 Innermost TRS: 1118.61/291.50 Rules: 1118.61/291.50 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.61/291.50 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.61/291.50 a__plus(N, 0') -> mark(N) 1118.61/291.50 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.61/291.50 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.61/291.50 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.61/291.50 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.61/291.50 mark(tt) -> tt 1118.61/291.50 mark(s(X)) -> s(mark(X)) 1118.61/291.50 mark(0') -> 0' 1118.61/291.50 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.61/291.50 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.61/291.50 a__plus(X1, X2) -> plus(X1, X2) 1118.61/291.50 1118.61/291.50 Types: 1118.61/291.50 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 tt :: tt:s:0':U11:U12:plus 1118.61/291.50 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 0' :: tt:s:0':U11:U12:plus 1118.61/291.50 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.61/291.50 1118.61/291.50 1118.61/291.50 Lemmas: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(n7802_0)) -> gen_tt:s:0':U11:U12:plus2_0(n7802_0), rt in Omega(1 + n7802_0) 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n8550_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n8550_0 + n8550_0 + n8550_0^2) 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n11303_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n11303_0 + n11303_0 + n11303_0^2) 1118.61/291.50 a__plus(gen_tt:s:0':U11:U12:plus2_0(a), gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0))) -> *3_0, rt in Omega(a*n14266_0 + n14266_0 + n14266_0^2) 1118.61/291.50 1118.61/291.50 1118.61/291.50 Generator Equations: 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.61/291.50 1118.61/291.50 1118.61/291.50 The following defined symbols remain to be analysed: 1118.61/291.50 mark, a__U11, a__U12 1118.61/291.50 1118.61/291.50 They will be analysed ascendingly in the following order: 1118.61/291.50 a__U11 = a__U12 1118.61/291.50 a__U11 = a__plus 1118.61/291.50 a__U11 = mark 1118.61/291.50 a__U12 = a__plus 1118.61/291.50 a__U12 = mark 1118.61/291.50 a__plus = mark 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (23) RewriteLemmaProof (LOWER BOUND(ID)) 1118.61/291.50 Proved the following rewrite lemma: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(n17964_0)) -> gen_tt:s:0':U11:U12:plus2_0(n17964_0), rt in Omega(1 + n17964_0) 1118.61/291.50 1118.61/291.50 Induction Base: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(0)) ->_R^Omega(1) 1118.61/291.50 tt 1118.61/291.50 1118.61/291.50 Induction Step: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(+(n17964_0, 1))) ->_R^Omega(1) 1118.61/291.50 s(mark(gen_tt:s:0':U11:U12:plus2_0(n17964_0))) ->_IH 1118.61/291.50 s(gen_tt:s:0':U11:U12:plus2_0(c17965_0)) 1118.61/291.50 1118.61/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (24) 1118.61/291.50 Obligation: 1118.61/291.50 Innermost TRS: 1118.61/291.50 Rules: 1118.61/291.50 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.61/291.50 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.61/291.50 a__plus(N, 0') -> mark(N) 1118.61/291.50 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.61/291.50 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.61/291.50 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.61/291.50 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.61/291.50 mark(tt) -> tt 1118.61/291.50 mark(s(X)) -> s(mark(X)) 1118.61/291.50 mark(0') -> 0' 1118.61/291.50 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.61/291.50 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.61/291.50 a__plus(X1, X2) -> plus(X1, X2) 1118.61/291.50 1118.61/291.50 Types: 1118.61/291.50 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 tt :: tt:s:0':U11:U12:plus 1118.61/291.50 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 0' :: tt:s:0':U11:U12:plus 1118.61/291.50 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.61/291.50 1118.61/291.50 1118.61/291.50 Lemmas: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(n17964_0)) -> gen_tt:s:0':U11:U12:plus2_0(n17964_0), rt in Omega(1 + n17964_0) 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n8550_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n8550_0 + n8550_0 + n8550_0^2) 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n11303_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n11303_0 + n11303_0 + n11303_0^2) 1118.61/291.50 a__plus(gen_tt:s:0':U11:U12:plus2_0(a), gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0))) -> *3_0, rt in Omega(a*n14266_0 + n14266_0 + n14266_0^2) 1118.61/291.50 1118.61/291.50 1118.61/291.50 Generator Equations: 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.61/291.50 1118.61/291.50 1118.61/291.50 The following defined symbols remain to be analysed: 1118.61/291.50 a__U11, a__U12 1118.61/291.50 1118.61/291.50 They will be analysed ascendingly in the following order: 1118.61/291.50 a__U11 = a__U12 1118.61/291.50 a__U11 = a__plus 1118.61/291.50 a__U11 = mark 1118.61/291.50 a__U12 = a__plus 1118.61/291.50 a__U12 = mark 1118.61/291.50 a__plus = mark 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (25) RewriteLemmaProof (LOWER BOUND(ID)) 1118.61/291.50 Proved the following rewrite lemma: 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n19021_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n19021_0 + n19021_0 + n19021_0^2) 1118.61/291.50 1118.61/291.50 Induction Base: 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(c)) 1118.61/291.50 1118.61/291.50 Induction Step: 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(+(n19021_0, 1)), gen_tt:s:0':U11:U12:plus2_0(c)) ->_R^Omega(1) 1118.61/291.50 a__U12(tt, gen_tt:s:0':U11:U12:plus2_0(+(n19021_0, 1)), gen_tt:s:0':U11:U12:plus2_0(c)) ->_R^Omega(1) 1118.61/291.50 s(a__plus(mark(gen_tt:s:0':U11:U12:plus2_0(c)), mark(gen_tt:s:0':U11:U12:plus2_0(+(1, n19021_0))))) ->_L^Omega(1 + c) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(c), mark(gen_tt:s:0':U11:U12:plus2_0(+(1, n19021_0))))) ->_L^Omega(2 + n19021_0) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(c), gen_tt:s:0':U11:U12:plus2_0(+(1, n19021_0)))) ->_R^Omega(1) 1118.61/291.50 s(a__U11(tt, gen_tt:s:0':U11:U12:plus2_0(n19021_0), gen_tt:s:0':U11:U12:plus2_0(c))) ->_IH 1118.61/291.50 s(*3_0) 1118.61/291.50 1118.61/291.50 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (26) 1118.61/291.50 Obligation: 1118.61/291.50 Innermost TRS: 1118.61/291.50 Rules: 1118.61/291.50 a__U11(tt, M, N) -> a__U12(tt, M, N) 1118.61/291.50 a__U12(tt, M, N) -> s(a__plus(mark(N), mark(M))) 1118.61/291.50 a__plus(N, 0') -> mark(N) 1118.61/291.50 a__plus(N, s(M)) -> a__U11(tt, M, N) 1118.61/291.50 mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) 1118.61/291.50 mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) 1118.61/291.50 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1118.61/291.50 mark(tt) -> tt 1118.61/291.50 mark(s(X)) -> s(mark(X)) 1118.61/291.50 mark(0') -> 0' 1118.61/291.50 a__U11(X1, X2, X3) -> U11(X1, X2, X3) 1118.61/291.50 a__U12(X1, X2, X3) -> U12(X1, X2, X3) 1118.61/291.50 a__plus(X1, X2) -> plus(X1, X2) 1118.61/291.50 1118.61/291.50 Types: 1118.61/291.50 a__U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 tt :: tt:s:0':U11:U12:plus 1118.61/291.50 a__U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 s :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 a__plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 mark :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 0' :: tt:s:0':U11:U12:plus 1118.61/291.50 U11 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 U12 :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 plus :: tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus -> tt:s:0':U11:U12:plus 1118.61/291.50 hole_tt:s:0':U11:U12:plus1_0 :: tt:s:0':U11:U12:plus 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0 :: Nat -> tt:s:0':U11:U12:plus 1118.61/291.50 1118.61/291.50 1118.61/291.50 Lemmas: 1118.61/291.50 mark(gen_tt:s:0':U11:U12:plus2_0(n17964_0)) -> gen_tt:s:0':U11:U12:plus2_0(n17964_0), rt in Omega(1 + n17964_0) 1118.61/291.50 a__U11(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n19021_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n19021_0 + n19021_0 + n19021_0^2) 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n11303_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n11303_0 + n11303_0 + n11303_0^2) 1118.61/291.50 a__plus(gen_tt:s:0':U11:U12:plus2_0(a), gen_tt:s:0':U11:U12:plus2_0(+(1, n14266_0))) -> *3_0, rt in Omega(a*n14266_0 + n14266_0 + n14266_0^2) 1118.61/291.50 1118.61/291.50 1118.61/291.50 Generator Equations: 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(0) <=> tt 1118.61/291.50 gen_tt:s:0':U11:U12:plus2_0(+(x, 1)) <=> s(gen_tt:s:0':U11:U12:plus2_0(x)) 1118.61/291.50 1118.61/291.50 1118.61/291.50 The following defined symbols remain to be analysed: 1118.61/291.50 a__U12 1118.61/291.50 1118.61/291.50 They will be analysed ascendingly in the following order: 1118.61/291.50 a__U11 = a__U12 1118.61/291.50 a__U11 = a__plus 1118.61/291.50 a__U11 = mark 1118.61/291.50 a__U12 = a__plus 1118.61/291.50 a__U12 = mark 1118.61/291.50 a__plus = mark 1118.61/291.50 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (27) RewriteLemmaProof (LOWER BOUND(ID)) 1118.61/291.50 Proved the following rewrite lemma: 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(n22989_0), gen_tt:s:0':U11:U12:plus2_0(c)) -> *3_0, rt in Omega(c*n22989_0 + n22989_0 + n22989_0^2) 1118.61/291.50 1118.61/291.50 Induction Base: 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(c)) 1118.61/291.50 1118.61/291.50 Induction Step: 1118.61/291.50 a__U12(gen_tt:s:0':U11:U12:plus2_0(0), gen_tt:s:0':U11:U12:plus2_0(+(n22989_0, 1)), gen_tt:s:0':U11:U12:plus2_0(c)) ->_R^Omega(1) 1118.61/291.50 s(a__plus(mark(gen_tt:s:0':U11:U12:plus2_0(c)), mark(gen_tt:s:0':U11:U12:plus2_0(+(n22989_0, 1))))) ->_L^Omega(1 + c) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(c), mark(gen_tt:s:0':U11:U12:plus2_0(+(1, n22989_0))))) ->_L^Omega(2 + n22989_0) 1118.61/291.50 s(a__plus(gen_tt:s:0':U11:U12:plus2_0(c), gen_tt:s:0':U11:U12:plus2_0(+(1, n22989_0)))) ->_R^Omega(1) 1118.61/291.50 s(a__U11(tt, gen_tt:s:0':U11:U12:plus2_0(n22989_0), gen_tt:s:0':U11:U12:plus2_0(c))) ->_R^Omega(1) 1118.61/291.50 s(a__U12(tt, gen_tt:s:0':U11:U12:plus2_0(n22989_0), gen_tt:s:0':U11:U12:plus2_0(c))) ->_IH 1118.61/291.50 s(*3_0) 1118.61/291.50 1118.61/291.50 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1118.61/291.50 ---------------------------------------- 1118.61/291.50 1118.61/291.50 (28) 1118.61/291.50 BOUNDS(1, INF) 1118.87/291.61 EOF