1098.69/291.93 WORST_CASE(Omega(n^2), ?) 1099.35/292.13 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1099.35/292.13 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1099.35/292.13 1099.35/292.13 1099.35/292.13 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1099.35/292.13 1099.35/292.13 (0) CpxTRS 1099.35/292.13 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1099.35/292.13 (2) CpxTRS 1099.35/292.13 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1099.35/292.13 (4) typed CpxTrs 1099.35/292.13 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1099.35/292.13 (6) typed CpxTrs 1099.35/292.13 (7) RewriteLemmaProof [LOWER BOUND(ID), 575 ms] 1099.35/292.13 (8) BEST 1099.35/292.13 (9) proven lower bound 1099.35/292.13 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1099.35/292.13 (11) BOUNDS(n^1, INF) 1099.35/292.13 (12) typed CpxTrs 1099.35/292.13 (13) RewriteLemmaProof [LOWER BOUND(ID), 743 ms] 1099.35/292.13 (14) BEST 1099.35/292.13 (15) proven lower bound 1099.35/292.13 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1099.35/292.13 (17) BOUNDS(n^2, INF) 1099.35/292.13 (18) typed CpxTrs 1099.35/292.13 (19) RewriteLemmaProof [LOWER BOUND(ID), 365 ms] 1099.35/292.13 (20) typed CpxTrs 1099.35/292.13 (21) RewriteLemmaProof [LOWER BOUND(ID), 16 ms] 1099.35/292.13 (22) typed CpxTrs 1099.35/292.13 (23) RewriteLemmaProof [LOWER BOUND(ID), 743 ms] 1099.35/292.13 (24) BOUNDS(1, INF) 1099.35/292.13 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (0) 1099.35/292.13 Obligation: 1099.35/292.13 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1099.35/292.13 1099.35/292.13 1099.35/292.13 The TRS R consists of the following rules: 1099.35/292.13 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0) -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0) -> 0 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0) -> 0 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 S is empty. 1099.35/292.13 Rewrite Strategy: INNERMOST 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1099.35/292.13 Renamed function symbols to avoid clashes with predefined symbol. 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (2) 1099.35/292.13 Obligation: 1099.35/292.13 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1099.35/292.13 1099.35/292.13 1099.35/292.13 The TRS R consists of the following rules: 1099.35/292.13 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0') -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0') -> 0' 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0') -> 0' 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 S is empty. 1099.35/292.13 Rewrite Strategy: INNERMOST 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1099.35/292.13 Infered types. 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (4) 1099.35/292.13 Obligation: 1099.35/292.13 Innermost TRS: 1099.35/292.13 Rules: 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0') -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0') -> 0' 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0') -> 0' 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 Types: 1099.35/292.13 a__and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 tt :: tt:0':s:and:plus:x 1099.35/292.13 mark :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 0' :: tt:0':s:and:plus:x 1099.35/292.13 s :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 hole_tt:0':s:and:plus:x1_0 :: tt:0':s:and:plus:x 1099.35/292.13 gen_tt:0':s:and:plus:x2_0 :: Nat -> tt:0':s:and:plus:x 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (5) OrderProof (LOWER BOUND(ID)) 1099.35/292.13 Heuristically decided to analyse the following defined symbols: 1099.35/292.13 mark, a__plus, a__x 1099.35/292.13 1099.35/292.13 They will be analysed ascendingly in the following order: 1099.35/292.13 mark = a__plus 1099.35/292.13 mark = a__x 1099.35/292.13 a__plus = a__x 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (6) 1099.35/292.13 Obligation: 1099.35/292.13 Innermost TRS: 1099.35/292.13 Rules: 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0') -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0') -> 0' 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0') -> 0' 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 Types: 1099.35/292.13 a__and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 tt :: tt:0':s:and:plus:x 1099.35/292.13 mark :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 0' :: tt:0':s:and:plus:x 1099.35/292.13 s :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 hole_tt:0':s:and:plus:x1_0 :: tt:0':s:and:plus:x 1099.35/292.13 gen_tt:0':s:and:plus:x2_0 :: Nat -> tt:0':s:and:plus:x 1099.35/292.13 1099.35/292.13 1099.35/292.13 Generator Equations: 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(0) <=> tt 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus:x2_0(x)) 1099.35/292.13 1099.35/292.13 1099.35/292.13 The following defined symbols remain to be analysed: 1099.35/292.13 a__plus, mark, a__x 1099.35/292.13 1099.35/292.13 They will be analysed ascendingly in the following order: 1099.35/292.13 mark = a__plus 1099.35/292.13 mark = a__x 1099.35/292.13 a__plus = a__x 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1099.35/292.13 Proved the following rewrite lemma: 1099.35/292.13 mark(gen_tt:0':s:and:plus:x2_0(n11447_0)) -> gen_tt:0':s:and:plus:x2_0(n11447_0), rt in Omega(1 + n11447_0) 1099.35/292.13 1099.35/292.13 Induction Base: 1099.35/292.13 mark(gen_tt:0':s:and:plus:x2_0(0)) ->_R^Omega(1) 1099.35/292.13 tt 1099.35/292.13 1099.35/292.13 Induction Step: 1099.35/292.13 mark(gen_tt:0':s:and:plus:x2_0(+(n11447_0, 1))) ->_R^Omega(1) 1099.35/292.13 s(mark(gen_tt:0':s:and:plus:x2_0(n11447_0))) ->_IH 1099.35/292.13 s(gen_tt:0':s:and:plus:x2_0(c11448_0)) 1099.35/292.13 1099.35/292.13 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (8) 1099.35/292.13 Complex Obligation (BEST) 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (9) 1099.35/292.13 Obligation: 1099.35/292.13 Proved the lower bound n^1 for the following obligation: 1099.35/292.13 1099.35/292.13 Innermost TRS: 1099.35/292.13 Rules: 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0') -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0') -> 0' 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0') -> 0' 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 Types: 1099.35/292.13 a__and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 tt :: tt:0':s:and:plus:x 1099.35/292.13 mark :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 0' :: tt:0':s:and:plus:x 1099.35/292.13 s :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 hole_tt:0':s:and:plus:x1_0 :: tt:0':s:and:plus:x 1099.35/292.13 gen_tt:0':s:and:plus:x2_0 :: Nat -> tt:0':s:and:plus:x 1099.35/292.13 1099.35/292.13 1099.35/292.13 Generator Equations: 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(0) <=> tt 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus:x2_0(x)) 1099.35/292.13 1099.35/292.13 1099.35/292.13 The following defined symbols remain to be analysed: 1099.35/292.13 mark, a__x 1099.35/292.13 1099.35/292.13 They will be analysed ascendingly in the following order: 1099.35/292.13 mark = a__plus 1099.35/292.13 mark = a__x 1099.35/292.13 a__plus = a__x 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (10) LowerBoundPropagationProof (FINISHED) 1099.35/292.13 Propagated lower bound. 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (11) 1099.35/292.13 BOUNDS(n^1, INF) 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (12) 1099.35/292.13 Obligation: 1099.35/292.13 Innermost TRS: 1099.35/292.13 Rules: 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0') -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0') -> 0' 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0') -> 0' 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 Types: 1099.35/292.13 a__and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 tt :: tt:0':s:and:plus:x 1099.35/292.13 mark :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 0' :: tt:0':s:and:plus:x 1099.35/292.13 s :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 hole_tt:0':s:and:plus:x1_0 :: tt:0':s:and:plus:x 1099.35/292.13 gen_tt:0':s:and:plus:x2_0 :: Nat -> tt:0':s:and:plus:x 1099.35/292.13 1099.35/292.13 1099.35/292.13 Lemmas: 1099.35/292.13 mark(gen_tt:0':s:and:plus:x2_0(n11447_0)) -> gen_tt:0':s:and:plus:x2_0(n11447_0), rt in Omega(1 + n11447_0) 1099.35/292.13 1099.35/292.13 1099.35/292.13 Generator Equations: 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(0) <=> tt 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus:x2_0(x)) 1099.35/292.13 1099.35/292.13 1099.35/292.13 The following defined symbols remain to be analysed: 1099.35/292.13 a__x, a__plus 1099.35/292.13 1099.35/292.13 They will be analysed ascendingly in the following order: 1099.35/292.13 mark = a__plus 1099.35/292.13 mark = a__x 1099.35/292.13 a__plus = a__x 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1099.35/292.13 Proved the following rewrite lemma: 1099.35/292.13 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n12608_0))) -> *3_0, rt in Omega(a*n12608_0 + n12608_0 + n12608_0^2) 1099.35/292.13 1099.35/292.13 Induction Base: 1099.35/292.13 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, 0))) 1099.35/292.13 1099.35/292.13 Induction Step: 1099.35/292.13 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, +(n12608_0, 1)))) ->_R^Omega(1) 1099.35/292.13 a__plus(a__x(mark(gen_tt:0':s:and:plus:x2_0(a)), mark(gen_tt:0':s:and:plus:x2_0(+(1, n12608_0)))), mark(gen_tt:0':s:and:plus:x2_0(a))) ->_L^Omega(1 + a) 1099.35/292.13 a__plus(a__x(gen_tt:0':s:and:plus:x2_0(a), mark(gen_tt:0':s:and:plus:x2_0(+(1, n12608_0)))), mark(gen_tt:0':s:and:plus:x2_0(a))) ->_L^Omega(2 + n12608_0) 1099.35/292.13 a__plus(a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n12608_0))), mark(gen_tt:0':s:and:plus:x2_0(a))) ->_IH 1099.35/292.13 a__plus(*3_0, mark(gen_tt:0':s:and:plus:x2_0(a))) ->_L^Omega(1 + a) 1099.35/292.13 a__plus(*3_0, gen_tt:0':s:and:plus:x2_0(a)) 1099.35/292.13 1099.35/292.13 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (14) 1099.35/292.13 Complex Obligation (BEST) 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (15) 1099.35/292.13 Obligation: 1099.35/292.13 Proved the lower bound n^2 for the following obligation: 1099.35/292.13 1099.35/292.13 Innermost TRS: 1099.35/292.13 Rules: 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0') -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0') -> 0' 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0') -> 0' 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 Types: 1099.35/292.13 a__and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 tt :: tt:0':s:and:plus:x 1099.35/292.13 mark :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 0' :: tt:0':s:and:plus:x 1099.35/292.13 s :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 hole_tt:0':s:and:plus:x1_0 :: tt:0':s:and:plus:x 1099.35/292.13 gen_tt:0':s:and:plus:x2_0 :: Nat -> tt:0':s:and:plus:x 1099.35/292.13 1099.35/292.13 1099.35/292.13 Lemmas: 1099.35/292.13 mark(gen_tt:0':s:and:plus:x2_0(n11447_0)) -> gen_tt:0':s:and:plus:x2_0(n11447_0), rt in Omega(1 + n11447_0) 1099.35/292.13 1099.35/292.13 1099.35/292.13 Generator Equations: 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(0) <=> tt 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus:x2_0(x)) 1099.35/292.13 1099.35/292.13 1099.35/292.13 The following defined symbols remain to be analysed: 1099.35/292.13 a__x, a__plus 1099.35/292.13 1099.35/292.13 They will be analysed ascendingly in the following order: 1099.35/292.13 mark = a__plus 1099.35/292.13 mark = a__x 1099.35/292.13 a__plus = a__x 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (16) LowerBoundPropagationProof (FINISHED) 1099.35/292.13 Propagated lower bound. 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (17) 1099.35/292.13 BOUNDS(n^2, INF) 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (18) 1099.35/292.13 Obligation: 1099.35/292.13 Innermost TRS: 1099.35/292.13 Rules: 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0') -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0') -> 0' 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0') -> 0' 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 Types: 1099.35/292.13 a__and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 tt :: tt:0':s:and:plus:x 1099.35/292.13 mark :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 0' :: tt:0':s:and:plus:x 1099.35/292.13 s :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 hole_tt:0':s:and:plus:x1_0 :: tt:0':s:and:plus:x 1099.35/292.13 gen_tt:0':s:and:plus:x2_0 :: Nat -> tt:0':s:and:plus:x 1099.35/292.13 1099.35/292.13 1099.35/292.13 Lemmas: 1099.35/292.13 mark(gen_tt:0':s:and:plus:x2_0(n11447_0)) -> gen_tt:0':s:and:plus:x2_0(n11447_0), rt in Omega(1 + n11447_0) 1099.35/292.13 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n12608_0))) -> *3_0, rt in Omega(a*n12608_0 + n12608_0 + n12608_0^2) 1099.35/292.13 1099.35/292.13 1099.35/292.13 Generator Equations: 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(0) <=> tt 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus:x2_0(x)) 1099.35/292.13 1099.35/292.13 1099.35/292.13 The following defined symbols remain to be analysed: 1099.35/292.13 a__plus, mark 1099.35/292.13 1099.35/292.13 They will be analysed ascendingly in the following order: 1099.35/292.13 mark = a__plus 1099.35/292.13 mark = a__x 1099.35/292.13 a__plus = a__x 1099.35/292.13 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1099.35/292.13 Proved the following rewrite lemma: 1099.35/292.13 a__plus(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n17144_0))) -> *3_0, rt in Omega(a*n17144_0 + n17144_0 + n17144_0^2) 1099.35/292.13 1099.35/292.13 Induction Base: 1099.35/292.13 a__plus(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, 0))) 1099.35/292.13 1099.35/292.13 Induction Step: 1099.35/292.13 a__plus(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, +(n17144_0, 1)))) ->_R^Omega(1) 1099.35/292.13 s(a__plus(mark(gen_tt:0':s:and:plus:x2_0(a)), mark(gen_tt:0':s:and:plus:x2_0(+(1, n17144_0))))) ->_L^Omega(1 + a) 1099.35/292.13 s(a__plus(gen_tt:0':s:and:plus:x2_0(a), mark(gen_tt:0':s:and:plus:x2_0(+(1, n17144_0))))) ->_L^Omega(2 + n17144_0) 1099.35/292.13 s(a__plus(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n17144_0)))) ->_IH 1099.35/292.13 s(*3_0) 1099.35/292.13 1099.35/292.13 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1099.35/292.13 ---------------------------------------- 1099.35/292.13 1099.35/292.13 (20) 1099.35/292.13 Obligation: 1099.35/292.13 Innermost TRS: 1099.35/292.13 Rules: 1099.35/292.13 a__and(tt, X) -> mark(X) 1099.35/292.13 a__plus(N, 0') -> mark(N) 1099.35/292.13 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.13 a__x(N, 0') -> 0' 1099.35/292.13 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.13 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.13 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.13 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.13 mark(tt) -> tt 1099.35/292.13 mark(0') -> 0' 1099.35/292.13 mark(s(X)) -> s(mark(X)) 1099.35/292.13 a__and(X1, X2) -> and(X1, X2) 1099.35/292.13 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.13 a__x(X1, X2) -> x(X1, X2) 1099.35/292.13 1099.35/292.13 Types: 1099.35/292.13 a__and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 tt :: tt:0':s:and:plus:x 1099.35/292.13 mark :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 0' :: tt:0':s:and:plus:x 1099.35/292.13 s :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 a__x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.13 hole_tt:0':s:and:plus:x1_0 :: tt:0':s:and:plus:x 1099.35/292.13 gen_tt:0':s:and:plus:x2_0 :: Nat -> tt:0':s:and:plus:x 1099.35/292.13 1099.35/292.13 1099.35/292.13 Lemmas: 1099.35/292.13 mark(gen_tt:0':s:and:plus:x2_0(n11447_0)) -> gen_tt:0':s:and:plus:x2_0(n11447_0), rt in Omega(1 + n11447_0) 1099.35/292.13 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n12608_0))) -> *3_0, rt in Omega(a*n12608_0 + n12608_0 + n12608_0^2) 1099.35/292.13 a__plus(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n17144_0))) -> *3_0, rt in Omega(a*n17144_0 + n17144_0 + n17144_0^2) 1099.35/292.13 1099.35/292.13 1099.35/292.13 Generator Equations: 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(0) <=> tt 1099.35/292.13 gen_tt:0':s:and:plus:x2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus:x2_0(x)) 1099.35/292.13 1099.35/292.13 1099.35/292.13 The following defined symbols remain to be analysed: 1099.35/292.13 mark, a__x 1099.35/292.13 1099.35/292.13 They will be analysed ascendingly in the following order: 1099.35/292.14 mark = a__plus 1099.35/292.14 mark = a__x 1099.35/292.14 a__plus = a__x 1099.35/292.14 1099.35/292.14 ---------------------------------------- 1099.35/292.14 1099.35/292.14 (21) RewriteLemmaProof (LOWER BOUND(ID)) 1099.35/292.14 Proved the following rewrite lemma: 1099.35/292.14 mark(gen_tt:0':s:and:plus:x2_0(n19317_0)) -> gen_tt:0':s:and:plus:x2_0(n19317_0), rt in Omega(1 + n19317_0) 1099.35/292.14 1099.35/292.14 Induction Base: 1099.35/292.14 mark(gen_tt:0':s:and:plus:x2_0(0)) ->_R^Omega(1) 1099.35/292.14 tt 1099.35/292.14 1099.35/292.14 Induction Step: 1099.35/292.14 mark(gen_tt:0':s:and:plus:x2_0(+(n19317_0, 1))) ->_R^Omega(1) 1099.35/292.14 s(mark(gen_tt:0':s:and:plus:x2_0(n19317_0))) ->_IH 1099.35/292.14 s(gen_tt:0':s:and:plus:x2_0(c19318_0)) 1099.35/292.14 1099.35/292.14 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1099.35/292.14 ---------------------------------------- 1099.35/292.14 1099.35/292.14 (22) 1099.35/292.14 Obligation: 1099.35/292.14 Innermost TRS: 1099.35/292.14 Rules: 1099.35/292.14 a__and(tt, X) -> mark(X) 1099.35/292.14 a__plus(N, 0') -> mark(N) 1099.35/292.14 a__plus(N, s(M)) -> s(a__plus(mark(N), mark(M))) 1099.35/292.14 a__x(N, 0') -> 0' 1099.35/292.14 a__x(N, s(M)) -> a__plus(a__x(mark(N), mark(M)), mark(N)) 1099.35/292.14 mark(and(X1, X2)) -> a__and(mark(X1), X2) 1099.35/292.14 mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) 1099.35/292.14 mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) 1099.35/292.14 mark(tt) -> tt 1099.35/292.14 mark(0') -> 0' 1099.35/292.14 mark(s(X)) -> s(mark(X)) 1099.35/292.14 a__and(X1, X2) -> and(X1, X2) 1099.35/292.14 a__plus(X1, X2) -> plus(X1, X2) 1099.35/292.14 a__x(X1, X2) -> x(X1, X2) 1099.35/292.14 1099.35/292.14 Types: 1099.35/292.14 a__and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.14 tt :: tt:0':s:and:plus:x 1099.35/292.14 mark :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.14 a__plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.14 0' :: tt:0':s:and:plus:x 1099.35/292.14 s :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.14 a__x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.14 and :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.14 plus :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.14 x :: tt:0':s:and:plus:x -> tt:0':s:and:plus:x -> tt:0':s:and:plus:x 1099.35/292.14 hole_tt:0':s:and:plus:x1_0 :: tt:0':s:and:plus:x 1099.35/292.14 gen_tt:0':s:and:plus:x2_0 :: Nat -> tt:0':s:and:plus:x 1099.35/292.14 1099.35/292.14 1099.35/292.14 Lemmas: 1099.35/292.14 mark(gen_tt:0':s:and:plus:x2_0(n19317_0)) -> gen_tt:0':s:and:plus:x2_0(n19317_0), rt in Omega(1 + n19317_0) 1099.35/292.14 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n12608_0))) -> *3_0, rt in Omega(a*n12608_0 + n12608_0 + n12608_0^2) 1099.35/292.14 a__plus(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n17144_0))) -> *3_0, rt in Omega(a*n17144_0 + n17144_0 + n17144_0^2) 1099.35/292.14 1099.35/292.14 1099.35/292.14 Generator Equations: 1099.35/292.14 gen_tt:0':s:and:plus:x2_0(0) <=> tt 1099.35/292.14 gen_tt:0':s:and:plus:x2_0(+(x, 1)) <=> s(gen_tt:0':s:and:plus:x2_0(x)) 1099.35/292.14 1099.35/292.14 1099.35/292.14 The following defined symbols remain to be analysed: 1099.35/292.14 a__x 1099.35/292.14 1099.35/292.14 They will be analysed ascendingly in the following order: 1099.35/292.14 mark = a__plus 1099.35/292.14 mark = a__x 1099.35/292.14 a__plus = a__x 1099.35/292.14 1099.35/292.14 ---------------------------------------- 1099.35/292.14 1099.35/292.14 (23) RewriteLemmaProof (LOWER BOUND(ID)) 1099.35/292.14 Proved the following rewrite lemma: 1099.35/292.14 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n20684_0))) -> *3_0, rt in Omega(a*n20684_0 + n20684_0 + n20684_0^2) 1099.35/292.14 1099.35/292.14 Induction Base: 1099.35/292.14 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, 0))) 1099.35/292.14 1099.35/292.14 Induction Step: 1099.35/292.14 a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, +(n20684_0, 1)))) ->_R^Omega(1) 1099.35/292.14 a__plus(a__x(mark(gen_tt:0':s:and:plus:x2_0(a)), mark(gen_tt:0':s:and:plus:x2_0(+(1, n20684_0)))), mark(gen_tt:0':s:and:plus:x2_0(a))) ->_L^Omega(1 + a) 1099.35/292.14 a__plus(a__x(gen_tt:0':s:and:plus:x2_0(a), mark(gen_tt:0':s:and:plus:x2_0(+(1, n20684_0)))), mark(gen_tt:0':s:and:plus:x2_0(a))) ->_L^Omega(2 + n20684_0) 1099.35/292.14 a__plus(a__x(gen_tt:0':s:and:plus:x2_0(a), gen_tt:0':s:and:plus:x2_0(+(1, n20684_0))), mark(gen_tt:0':s:and:plus:x2_0(a))) ->_IH 1099.35/292.14 a__plus(*3_0, mark(gen_tt:0':s:and:plus:x2_0(a))) ->_L^Omega(1 + a) 1099.35/292.14 a__plus(*3_0, gen_tt:0':s:and:plus:x2_0(a)) 1099.35/292.14 1099.35/292.14 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1099.35/292.14 ---------------------------------------- 1099.35/292.14 1099.35/292.14 (24) 1099.35/292.14 BOUNDS(1, INF) 1099.67/292.23 EOF