314.51/291.50 WORST_CASE(Omega(n^2), ?) 314.51/291.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 314.51/291.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 314.51/291.51 314.51/291.51 314.51/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 314.51/291.51 314.51/291.51 (0) CpxTRS 314.51/291.51 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 314.51/291.51 (2) CpxTRS 314.51/291.51 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 314.51/291.51 (4) CpxTRS 314.51/291.51 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 314.51/291.51 (6) typed CpxTrs 314.51/291.51 (7) OrderProof [LOWER BOUND(ID), 0 ms] 314.51/291.51 (8) typed CpxTrs 314.51/291.51 (9) RewriteLemmaProof [LOWER BOUND(ID), 283 ms] 314.51/291.51 (10) BEST 314.51/291.51 (11) proven lower bound 314.51/291.51 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 314.51/291.51 (13) BOUNDS(n^1, INF) 314.51/291.51 (14) typed CpxTrs 314.51/291.51 (15) RewriteLemmaProof [LOWER BOUND(ID), 65 ms] 314.51/291.51 (16) BEST 314.51/291.51 (17) proven lower bound 314.51/291.51 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 314.51/291.51 (19) BOUNDS(n^2, INF) 314.51/291.51 (20) typed CpxTrs 314.51/291.51 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (0) 314.51/291.51 Obligation: 314.51/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 314.51/291.51 314.51/291.51 314.51/291.51 The TRS R consists of the following rules: 314.51/291.51 314.51/291.51 from(X) -> cons(X, n__from(s(X))) 314.51/291.51 2ndspos(0, Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0, Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from(0)) 314.51/291.51 plus(0, Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0, Y) -> 0 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from(X) -> n__from(X) 314.51/291.51 activate(n__from(X)) -> from(X) 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 S is empty. 314.51/291.51 Rewrite Strategy: FULL 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 314.51/291.51 Renamed function symbols to avoid clashes with predefined symbol. 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (2) 314.51/291.51 Obligation: 314.51/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 314.51/291.51 314.51/291.51 314.51/291.51 The TRS R consists of the following rules: 314.51/291.51 314.51/291.51 from(X) -> cons(X, n__from(s(X))) 314.51/291.51 2ndspos(0', Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0', Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from(0')) 314.51/291.51 plus(0', Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0', Y) -> 0' 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from(X) -> n__from(X) 314.51/291.51 activate(n__from(X)) -> from(X) 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 S is empty. 314.51/291.51 Rewrite Strategy: FULL 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (3) SlicingProof (LOWER BOUND(ID)) 314.51/291.51 Sliced the following arguments: 314.51/291.51 from/0 314.51/291.51 cons/0 314.51/291.51 n__from/0 314.51/291.51 cons2/0 314.51/291.51 rcons/0 314.51/291.51 posrecip/0 314.51/291.51 negrecip/0 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (4) 314.51/291.51 Obligation: 314.51/291.51 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 314.51/291.51 314.51/291.51 314.51/291.51 The TRS R consists of the following rules: 314.51/291.51 314.51/291.51 from -> cons(n__from) 314.51/291.51 2ndspos(0', Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0', Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from) 314.51/291.51 plus(0', Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0', Y) -> 0' 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from -> n__from 314.51/291.51 activate(n__from) -> from 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 S is empty. 314.51/291.51 Rewrite Strategy: FULL 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 314.51/291.51 Infered types. 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (6) 314.51/291.51 Obligation: 314.51/291.51 TRS: 314.51/291.51 Rules: 314.51/291.51 from -> cons(n__from) 314.51/291.51 2ndspos(0', Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0', Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from) 314.51/291.51 plus(0', Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0', Y) -> 0' 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from -> n__from 314.51/291.51 activate(n__from) -> from 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 Types: 314.51/291.51 from :: n__from:cons:cons2 314.51/291.51 cons :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 n__from :: n__from:cons:cons2 314.51/291.51 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 0' :: 0':s 314.51/291.51 rnil :: rnil:rcons 314.51/291.51 s :: 0':s -> 0':s 314.51/291.51 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 activate :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 rcons :: rnil:rcons -> rnil:rcons 314.51/291.51 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 pi :: 0':s -> rnil:rcons 314.51/291.51 plus :: 0':s -> 0':s -> 0':s 314.51/291.51 times :: 0':s -> 0':s -> 0':s 314.51/291.51 square :: 0':s -> 0':s 314.51/291.51 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 314.51/291.51 hole_rnil:rcons2_0 :: rnil:rcons 314.51/291.51 hole_0':s3_0 :: 0':s 314.51/291.51 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 314.51/291.51 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 314.51/291.51 gen_0':s6_0 :: Nat -> 0':s 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (7) OrderProof (LOWER BOUND(ID)) 314.51/291.51 Heuristically decided to analyse the following defined symbols: 314.51/291.51 2ndspos, 2ndsneg, plus, times 314.51/291.51 314.51/291.51 They will be analysed ascendingly in the following order: 314.51/291.51 2ndspos = 2ndsneg 314.51/291.51 plus < times 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (8) 314.51/291.51 Obligation: 314.51/291.51 TRS: 314.51/291.51 Rules: 314.51/291.51 from -> cons(n__from) 314.51/291.51 2ndspos(0', Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0', Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from) 314.51/291.51 plus(0', Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0', Y) -> 0' 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from -> n__from 314.51/291.51 activate(n__from) -> from 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 Types: 314.51/291.51 from :: n__from:cons:cons2 314.51/291.51 cons :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 n__from :: n__from:cons:cons2 314.51/291.51 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 0' :: 0':s 314.51/291.51 rnil :: rnil:rcons 314.51/291.51 s :: 0':s -> 0':s 314.51/291.51 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 activate :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 rcons :: rnil:rcons -> rnil:rcons 314.51/291.51 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 pi :: 0':s -> rnil:rcons 314.51/291.51 plus :: 0':s -> 0':s -> 0':s 314.51/291.51 times :: 0':s -> 0':s -> 0':s 314.51/291.51 square :: 0':s -> 0':s 314.51/291.51 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 314.51/291.51 hole_rnil:rcons2_0 :: rnil:rcons 314.51/291.51 hole_0':s3_0 :: 0':s 314.51/291.51 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 314.51/291.51 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 314.51/291.51 gen_0':s6_0 :: Nat -> 0':s 314.51/291.51 314.51/291.51 314.51/291.51 Generator Equations: 314.51/291.51 gen_n__from:cons:cons24_0(0) <=> n__from 314.51/291.51 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 314.51/291.51 gen_rnil:rcons5_0(0) <=> rnil 314.51/291.51 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 314.51/291.51 gen_0':s6_0(0) <=> 0' 314.51/291.51 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 314.51/291.51 314.51/291.51 314.51/291.51 The following defined symbols remain to be analysed: 314.51/291.51 plus, 2ndspos, 2ndsneg, times 314.51/291.51 314.51/291.51 They will be analysed ascendingly in the following order: 314.51/291.51 2ndspos = 2ndsneg 314.51/291.51 plus < times 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (9) RewriteLemmaProof (LOWER BOUND(ID)) 314.51/291.51 Proved the following rewrite lemma: 314.51/291.51 plus(gen_0':s6_0(n8_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n8_0, b)), rt in Omega(1 + n8_0) 314.51/291.51 314.51/291.51 Induction Base: 314.51/291.51 plus(gen_0':s6_0(0), gen_0':s6_0(b)) ->_R^Omega(1) 314.51/291.51 gen_0':s6_0(b) 314.51/291.51 314.51/291.51 Induction Step: 314.51/291.51 plus(gen_0':s6_0(+(n8_0, 1)), gen_0':s6_0(b)) ->_R^Omega(1) 314.51/291.51 s(plus(gen_0':s6_0(n8_0), gen_0':s6_0(b))) ->_IH 314.51/291.51 s(gen_0':s6_0(+(b, c9_0))) 314.51/291.51 314.51/291.51 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (10) 314.51/291.51 Complex Obligation (BEST) 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (11) 314.51/291.51 Obligation: 314.51/291.51 Proved the lower bound n^1 for the following obligation: 314.51/291.51 314.51/291.51 TRS: 314.51/291.51 Rules: 314.51/291.51 from -> cons(n__from) 314.51/291.51 2ndspos(0', Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0', Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from) 314.51/291.51 plus(0', Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0', Y) -> 0' 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from -> n__from 314.51/291.51 activate(n__from) -> from 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 Types: 314.51/291.51 from :: n__from:cons:cons2 314.51/291.51 cons :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 n__from :: n__from:cons:cons2 314.51/291.51 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 0' :: 0':s 314.51/291.51 rnil :: rnil:rcons 314.51/291.51 s :: 0':s -> 0':s 314.51/291.51 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 activate :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 rcons :: rnil:rcons -> rnil:rcons 314.51/291.51 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 pi :: 0':s -> rnil:rcons 314.51/291.51 plus :: 0':s -> 0':s -> 0':s 314.51/291.51 times :: 0':s -> 0':s -> 0':s 314.51/291.51 square :: 0':s -> 0':s 314.51/291.51 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 314.51/291.51 hole_rnil:rcons2_0 :: rnil:rcons 314.51/291.51 hole_0':s3_0 :: 0':s 314.51/291.51 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 314.51/291.51 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 314.51/291.51 gen_0':s6_0 :: Nat -> 0':s 314.51/291.51 314.51/291.51 314.51/291.51 Generator Equations: 314.51/291.51 gen_n__from:cons:cons24_0(0) <=> n__from 314.51/291.51 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 314.51/291.51 gen_rnil:rcons5_0(0) <=> rnil 314.51/291.51 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 314.51/291.51 gen_0':s6_0(0) <=> 0' 314.51/291.51 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 314.51/291.51 314.51/291.51 314.51/291.51 The following defined symbols remain to be analysed: 314.51/291.51 plus, 2ndspos, 2ndsneg, times 314.51/291.51 314.51/291.51 They will be analysed ascendingly in the following order: 314.51/291.51 2ndspos = 2ndsneg 314.51/291.51 plus < times 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (12) LowerBoundPropagationProof (FINISHED) 314.51/291.51 Propagated lower bound. 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (13) 314.51/291.51 BOUNDS(n^1, INF) 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (14) 314.51/291.51 Obligation: 314.51/291.51 TRS: 314.51/291.51 Rules: 314.51/291.51 from -> cons(n__from) 314.51/291.51 2ndspos(0', Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0', Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from) 314.51/291.51 plus(0', Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0', Y) -> 0' 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from -> n__from 314.51/291.51 activate(n__from) -> from 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 Types: 314.51/291.51 from :: n__from:cons:cons2 314.51/291.51 cons :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 n__from :: n__from:cons:cons2 314.51/291.51 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 0' :: 0':s 314.51/291.51 rnil :: rnil:rcons 314.51/291.51 s :: 0':s -> 0':s 314.51/291.51 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 activate :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 rcons :: rnil:rcons -> rnil:rcons 314.51/291.51 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 pi :: 0':s -> rnil:rcons 314.51/291.51 plus :: 0':s -> 0':s -> 0':s 314.51/291.51 times :: 0':s -> 0':s -> 0':s 314.51/291.51 square :: 0':s -> 0':s 314.51/291.51 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 314.51/291.51 hole_rnil:rcons2_0 :: rnil:rcons 314.51/291.51 hole_0':s3_0 :: 0':s 314.51/291.51 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 314.51/291.51 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 314.51/291.51 gen_0':s6_0 :: Nat -> 0':s 314.51/291.51 314.51/291.51 314.51/291.51 Lemmas: 314.51/291.51 plus(gen_0':s6_0(n8_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n8_0, b)), rt in Omega(1 + n8_0) 314.51/291.51 314.51/291.51 314.51/291.51 Generator Equations: 314.51/291.51 gen_n__from:cons:cons24_0(0) <=> n__from 314.51/291.51 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 314.51/291.51 gen_rnil:rcons5_0(0) <=> rnil 314.51/291.51 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 314.51/291.51 gen_0':s6_0(0) <=> 0' 314.51/291.51 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 314.51/291.51 314.51/291.51 314.51/291.51 The following defined symbols remain to be analysed: 314.51/291.51 times, 2ndspos, 2ndsneg 314.51/291.51 314.51/291.51 They will be analysed ascendingly in the following order: 314.51/291.51 2ndspos = 2ndsneg 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (15) RewriteLemmaProof (LOWER BOUND(ID)) 314.51/291.51 Proved the following rewrite lemma: 314.51/291.51 times(gen_0':s6_0(n1027_0), gen_0':s6_0(b)) -> gen_0':s6_0(*(n1027_0, b)), rt in Omega(1 + b*n1027_0 + n1027_0) 314.51/291.51 314.51/291.51 Induction Base: 314.51/291.51 times(gen_0':s6_0(0), gen_0':s6_0(b)) ->_R^Omega(1) 314.51/291.51 0' 314.51/291.51 314.51/291.51 Induction Step: 314.51/291.51 times(gen_0':s6_0(+(n1027_0, 1)), gen_0':s6_0(b)) ->_R^Omega(1) 314.51/291.51 plus(gen_0':s6_0(b), times(gen_0':s6_0(n1027_0), gen_0':s6_0(b))) ->_IH 314.51/291.51 plus(gen_0':s6_0(b), gen_0':s6_0(*(c1028_0, b))) ->_L^Omega(1 + b) 314.51/291.51 gen_0':s6_0(+(b, *(n1027_0, b))) 314.51/291.51 314.51/291.51 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (16) 314.51/291.51 Complex Obligation (BEST) 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (17) 314.51/291.51 Obligation: 314.51/291.51 Proved the lower bound n^2 for the following obligation: 314.51/291.51 314.51/291.51 TRS: 314.51/291.51 Rules: 314.51/291.51 from -> cons(n__from) 314.51/291.51 2ndspos(0', Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0', Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from) 314.51/291.51 plus(0', Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0', Y) -> 0' 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from -> n__from 314.51/291.51 activate(n__from) -> from 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 Types: 314.51/291.51 from :: n__from:cons:cons2 314.51/291.51 cons :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 n__from :: n__from:cons:cons2 314.51/291.51 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 0' :: 0':s 314.51/291.51 rnil :: rnil:rcons 314.51/291.51 s :: 0':s -> 0':s 314.51/291.51 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 activate :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 rcons :: rnil:rcons -> rnil:rcons 314.51/291.51 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 pi :: 0':s -> rnil:rcons 314.51/291.51 plus :: 0':s -> 0':s -> 0':s 314.51/291.51 times :: 0':s -> 0':s -> 0':s 314.51/291.51 square :: 0':s -> 0':s 314.51/291.51 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 314.51/291.51 hole_rnil:rcons2_0 :: rnil:rcons 314.51/291.51 hole_0':s3_0 :: 0':s 314.51/291.51 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 314.51/291.51 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 314.51/291.51 gen_0':s6_0 :: Nat -> 0':s 314.51/291.51 314.51/291.51 314.51/291.51 Lemmas: 314.51/291.51 plus(gen_0':s6_0(n8_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n8_0, b)), rt in Omega(1 + n8_0) 314.51/291.51 314.51/291.51 314.51/291.51 Generator Equations: 314.51/291.51 gen_n__from:cons:cons24_0(0) <=> n__from 314.51/291.51 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 314.51/291.51 gen_rnil:rcons5_0(0) <=> rnil 314.51/291.51 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 314.51/291.51 gen_0':s6_0(0) <=> 0' 314.51/291.51 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 314.51/291.51 314.51/291.51 314.51/291.51 The following defined symbols remain to be analysed: 314.51/291.51 times, 2ndspos, 2ndsneg 314.51/291.51 314.51/291.51 They will be analysed ascendingly in the following order: 314.51/291.51 2ndspos = 2ndsneg 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (18) LowerBoundPropagationProof (FINISHED) 314.51/291.51 Propagated lower bound. 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (19) 314.51/291.51 BOUNDS(n^2, INF) 314.51/291.51 314.51/291.51 ---------------------------------------- 314.51/291.51 314.51/291.51 (20) 314.51/291.51 Obligation: 314.51/291.51 TRS: 314.51/291.51 Rules: 314.51/291.51 from -> cons(n__from) 314.51/291.51 2ndspos(0', Z) -> rnil 314.51/291.51 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 314.51/291.51 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 314.51/291.51 2ndsneg(0', Z) -> rnil 314.51/291.51 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 314.51/291.51 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 314.51/291.51 pi(X) -> 2ndspos(X, from) 314.51/291.51 plus(0', Y) -> Y 314.51/291.51 plus(s(X), Y) -> s(plus(X, Y)) 314.51/291.51 times(0', Y) -> 0' 314.51/291.51 times(s(X), Y) -> plus(Y, times(X, Y)) 314.51/291.51 square(X) -> times(X, X) 314.51/291.51 from -> n__from 314.51/291.51 activate(n__from) -> from 314.51/291.51 activate(X) -> X 314.51/291.51 314.51/291.51 Types: 314.51/291.51 from :: n__from:cons:cons2 314.51/291.51 cons :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 n__from :: n__from:cons:cons2 314.51/291.51 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 0' :: 0':s 314.51/291.51 rnil :: rnil:rcons 314.51/291.51 s :: 0':s -> 0':s 314.51/291.51 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 activate :: n__from:cons:cons2 -> n__from:cons:cons2 314.51/291.51 rcons :: rnil:rcons -> rnil:rcons 314.51/291.51 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 314.51/291.51 pi :: 0':s -> rnil:rcons 314.51/291.51 plus :: 0':s -> 0':s -> 0':s 314.51/291.51 times :: 0':s -> 0':s -> 0':s 314.51/291.51 square :: 0':s -> 0':s 314.51/291.51 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 314.51/291.51 hole_rnil:rcons2_0 :: rnil:rcons 314.51/291.51 hole_0':s3_0 :: 0':s 314.51/291.51 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 314.51/291.51 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 314.51/291.51 gen_0':s6_0 :: Nat -> 0':s 314.51/291.51 314.51/291.51 314.51/291.51 Lemmas: 314.51/291.51 plus(gen_0':s6_0(n8_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n8_0, b)), rt in Omega(1 + n8_0) 314.51/291.51 times(gen_0':s6_0(n1027_0), gen_0':s6_0(b)) -> gen_0':s6_0(*(n1027_0, b)), rt in Omega(1 + b*n1027_0 + n1027_0) 314.51/291.51 314.51/291.51 314.51/291.51 Generator Equations: 314.51/291.51 gen_n__from:cons:cons24_0(0) <=> n__from 314.51/291.51 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 314.51/291.51 gen_rnil:rcons5_0(0) <=> rnil 314.51/291.51 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 314.51/291.51 gen_0':s6_0(0) <=> 0' 314.51/291.51 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 314.51/291.51 314.51/291.51 314.51/291.51 The following defined symbols remain to be analysed: 314.51/291.51 2ndsneg, 2ndspos 314.51/291.51 314.51/291.51 They will be analysed ascendingly in the following order: 314.51/291.51 2ndspos = 2ndsneg 314.55/291.55 EOF