309.85/291.46 WORST_CASE(Omega(n^2), ?) 309.85/291.47 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 309.85/291.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 309.85/291.47 309.85/291.47 309.85/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 309.85/291.47 309.85/291.47 (0) CpxTRS 309.85/291.47 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 309.85/291.47 (2) CpxTRS 309.85/291.47 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 309.85/291.47 (4) typed CpxTrs 309.85/291.47 (5) OrderProof [LOWER BOUND(ID), 0 ms] 309.85/291.47 (6) typed CpxTrs 309.85/291.47 (7) RewriteLemmaProof [LOWER BOUND(ID), 305 ms] 309.85/291.47 (8) BEST 309.85/291.47 (9) proven lower bound 309.85/291.47 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 309.85/291.47 (11) BOUNDS(n^1, INF) 309.85/291.47 (12) typed CpxTrs 309.85/291.47 (13) RewriteLemmaProof [LOWER BOUND(ID), 56 ms] 309.85/291.47 (14) BEST 309.85/291.47 (15) proven lower bound 309.85/291.47 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 309.85/291.47 (17) BOUNDS(n^2, INF) 309.85/291.47 (18) typed CpxTrs 309.85/291.47 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (0) 309.85/291.47 Obligation: 309.85/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 309.85/291.47 309.85/291.47 309.85/291.47 The TRS R consists of the following rules: 309.85/291.47 309.85/291.47 from(X) -> cons(X, n__from(s(X))) 309.85/291.47 2ndspos(0, Z) -> rnil 309.85/291.47 2ndspos(s(N), cons(X, n__cons(Y, Z))) -> rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z))) 309.85/291.47 2ndsneg(0, Z) -> rnil 309.85/291.47 2ndsneg(s(N), cons(X, n__cons(Y, Z))) -> rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z))) 309.85/291.47 pi(X) -> 2ndspos(X, from(0)) 309.85/291.47 plus(0, Y) -> Y 309.85/291.47 plus(s(X), Y) -> s(plus(X, Y)) 309.85/291.47 times(0, Y) -> 0 309.85/291.47 times(s(X), Y) -> plus(Y, times(X, Y)) 309.85/291.47 square(X) -> times(X, X) 309.85/291.47 from(X) -> n__from(X) 309.85/291.47 cons(X1, X2) -> n__cons(X1, X2) 309.85/291.47 activate(n__from(X)) -> from(X) 309.85/291.47 activate(n__cons(X1, X2)) -> cons(X1, X2) 309.85/291.47 activate(X) -> X 309.85/291.47 309.85/291.47 S is empty. 309.85/291.47 Rewrite Strategy: FULL 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 309.85/291.47 Renamed function symbols to avoid clashes with predefined symbol. 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (2) 309.85/291.47 Obligation: 309.85/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 309.85/291.47 309.85/291.47 309.85/291.47 The TRS R consists of the following rules: 309.85/291.47 309.85/291.47 from(X) -> cons(X, n__from(s(X))) 309.85/291.47 2ndspos(0', Z) -> rnil 309.85/291.47 2ndspos(s(N), cons(X, n__cons(Y, Z))) -> rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z))) 309.85/291.47 2ndsneg(0', Z) -> rnil 309.85/291.47 2ndsneg(s(N), cons(X, n__cons(Y, Z))) -> rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z))) 309.85/291.47 pi(X) -> 2ndspos(X, from(0')) 309.85/291.47 plus(0', Y) -> Y 309.85/291.47 plus(s(X), Y) -> s(plus(X, Y)) 309.85/291.47 times(0', Y) -> 0' 309.85/291.47 times(s(X), Y) -> plus(Y, times(X, Y)) 309.85/291.47 square(X) -> times(X, X) 309.85/291.47 from(X) -> n__from(X) 309.85/291.47 cons(X1, X2) -> n__cons(X1, X2) 309.85/291.47 activate(n__from(X)) -> from(X) 309.85/291.47 activate(n__cons(X1, X2)) -> cons(X1, X2) 309.85/291.47 activate(X) -> X 309.85/291.47 309.85/291.47 S is empty. 309.85/291.47 Rewrite Strategy: FULL 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 309.85/291.47 Infered types. 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (4) 309.85/291.47 Obligation: 309.85/291.47 TRS: 309.85/291.47 Rules: 309.85/291.47 from(X) -> cons(X, n__from(s(X))) 309.85/291.47 2ndspos(0', Z) -> rnil 309.85/291.47 2ndspos(s(N), cons(X, n__cons(Y, Z))) -> rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z))) 309.85/291.47 2ndsneg(0', Z) -> rnil 309.85/291.47 2ndsneg(s(N), cons(X, n__cons(Y, Z))) -> rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z))) 309.85/291.47 pi(X) -> 2ndspos(X, from(0')) 309.85/291.47 plus(0', Y) -> Y 309.85/291.47 plus(s(X), Y) -> s(plus(X, Y)) 309.85/291.47 times(0', Y) -> 0' 309.85/291.47 times(s(X), Y) -> plus(Y, times(X, Y)) 309.85/291.47 square(X) -> times(X, X) 309.85/291.47 from(X) -> n__from(X) 309.85/291.47 cons(X1, X2) -> n__cons(X1, X2) 309.85/291.47 activate(n__from(X)) -> from(X) 309.85/291.47 activate(n__cons(X1, X2)) -> cons(X1, X2) 309.85/291.47 activate(X) -> X 309.85/291.47 309.85/291.47 Types: 309.85/291.47 from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 n__from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 s :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndspos :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 0' :: s:n__from:0':n__cons 309.85/291.47 rnil :: rnil:rcons 309.85/291.47 n__cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 rcons :: posrecip:negrecip -> rnil:rcons -> rnil:rcons 309.85/291.47 posrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 activate :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndsneg :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 negrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 pi :: s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 plus :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 times :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 square :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 hole_s:n__from:0':n__cons1_0 :: s:n__from:0':n__cons 309.85/291.47 hole_rnil:rcons2_0 :: rnil:rcons 309.85/291.47 hole_posrecip:negrecip3_0 :: posrecip:negrecip 309.85/291.47 gen_s:n__from:0':n__cons4_0 :: Nat -> s:n__from:0':n__cons 309.85/291.47 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (5) OrderProof (LOWER BOUND(ID)) 309.85/291.47 Heuristically decided to analyse the following defined symbols: 309.85/291.47 2ndspos, 2ndsneg, plus, times 309.85/291.47 309.85/291.47 They will be analysed ascendingly in the following order: 309.85/291.47 2ndspos = 2ndsneg 309.85/291.47 plus < times 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (6) 309.85/291.47 Obligation: 309.85/291.47 TRS: 309.85/291.47 Rules: 309.85/291.47 from(X) -> cons(X, n__from(s(X))) 309.85/291.47 2ndspos(0', Z) -> rnil 309.85/291.47 2ndspos(s(N), cons(X, n__cons(Y, Z))) -> rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z))) 309.85/291.47 2ndsneg(0', Z) -> rnil 309.85/291.47 2ndsneg(s(N), cons(X, n__cons(Y, Z))) -> rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z))) 309.85/291.47 pi(X) -> 2ndspos(X, from(0')) 309.85/291.47 plus(0', Y) -> Y 309.85/291.47 plus(s(X), Y) -> s(plus(X, Y)) 309.85/291.47 times(0', Y) -> 0' 309.85/291.47 times(s(X), Y) -> plus(Y, times(X, Y)) 309.85/291.47 square(X) -> times(X, X) 309.85/291.47 from(X) -> n__from(X) 309.85/291.47 cons(X1, X2) -> n__cons(X1, X2) 309.85/291.47 activate(n__from(X)) -> from(X) 309.85/291.47 activate(n__cons(X1, X2)) -> cons(X1, X2) 309.85/291.47 activate(X) -> X 309.85/291.47 309.85/291.47 Types: 309.85/291.47 from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 n__from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 s :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndspos :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 0' :: s:n__from:0':n__cons 309.85/291.47 rnil :: rnil:rcons 309.85/291.47 n__cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 rcons :: posrecip:negrecip -> rnil:rcons -> rnil:rcons 309.85/291.47 posrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 activate :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndsneg :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 negrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 pi :: s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 plus :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 times :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 square :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 hole_s:n__from:0':n__cons1_0 :: s:n__from:0':n__cons 309.85/291.47 hole_rnil:rcons2_0 :: rnil:rcons 309.85/291.47 hole_posrecip:negrecip3_0 :: posrecip:negrecip 309.85/291.47 gen_s:n__from:0':n__cons4_0 :: Nat -> s:n__from:0':n__cons 309.85/291.47 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 309.85/291.47 309.85/291.47 309.85/291.47 Generator Equations: 309.85/291.47 gen_s:n__from:0':n__cons4_0(0) <=> 0' 309.85/291.47 gen_s:n__from:0':n__cons4_0(+(x, 1)) <=> s(gen_s:n__from:0':n__cons4_0(x)) 309.85/291.47 gen_rnil:rcons5_0(0) <=> rnil 309.85/291.47 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(posrecip(0'), gen_rnil:rcons5_0(x)) 309.85/291.47 309.85/291.47 309.85/291.47 The following defined symbols remain to be analysed: 309.85/291.47 plus, 2ndspos, 2ndsneg, times 309.85/291.47 309.85/291.47 They will be analysed ascendingly in the following order: 309.85/291.47 2ndspos = 2ndsneg 309.85/291.47 plus < times 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (7) RewriteLemmaProof (LOWER BOUND(ID)) 309.85/291.47 Proved the following rewrite lemma: 309.85/291.47 plus(gen_s:n__from:0':n__cons4_0(n7_0), gen_s:n__from:0':n__cons4_0(b)) -> gen_s:n__from:0':n__cons4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 309.85/291.47 309.85/291.47 Induction Base: 309.85/291.47 plus(gen_s:n__from:0':n__cons4_0(0), gen_s:n__from:0':n__cons4_0(b)) ->_R^Omega(1) 309.85/291.47 gen_s:n__from:0':n__cons4_0(b) 309.85/291.47 309.85/291.47 Induction Step: 309.85/291.47 plus(gen_s:n__from:0':n__cons4_0(+(n7_0, 1)), gen_s:n__from:0':n__cons4_0(b)) ->_R^Omega(1) 309.85/291.47 s(plus(gen_s:n__from:0':n__cons4_0(n7_0), gen_s:n__from:0':n__cons4_0(b))) ->_IH 309.85/291.47 s(gen_s:n__from:0':n__cons4_0(+(b, c8_0))) 309.85/291.47 309.85/291.47 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (8) 309.85/291.47 Complex Obligation (BEST) 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (9) 309.85/291.47 Obligation: 309.85/291.47 Proved the lower bound n^1 for the following obligation: 309.85/291.47 309.85/291.47 TRS: 309.85/291.47 Rules: 309.85/291.47 from(X) -> cons(X, n__from(s(X))) 309.85/291.47 2ndspos(0', Z) -> rnil 309.85/291.47 2ndspos(s(N), cons(X, n__cons(Y, Z))) -> rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z))) 309.85/291.47 2ndsneg(0', Z) -> rnil 309.85/291.47 2ndsneg(s(N), cons(X, n__cons(Y, Z))) -> rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z))) 309.85/291.47 pi(X) -> 2ndspos(X, from(0')) 309.85/291.47 plus(0', Y) -> Y 309.85/291.47 plus(s(X), Y) -> s(plus(X, Y)) 309.85/291.47 times(0', Y) -> 0' 309.85/291.47 times(s(X), Y) -> plus(Y, times(X, Y)) 309.85/291.47 square(X) -> times(X, X) 309.85/291.47 from(X) -> n__from(X) 309.85/291.47 cons(X1, X2) -> n__cons(X1, X2) 309.85/291.47 activate(n__from(X)) -> from(X) 309.85/291.47 activate(n__cons(X1, X2)) -> cons(X1, X2) 309.85/291.47 activate(X) -> X 309.85/291.47 309.85/291.47 Types: 309.85/291.47 from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 n__from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 s :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndspos :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 0' :: s:n__from:0':n__cons 309.85/291.47 rnil :: rnil:rcons 309.85/291.47 n__cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 rcons :: posrecip:negrecip -> rnil:rcons -> rnil:rcons 309.85/291.47 posrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 activate :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndsneg :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 negrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 pi :: s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 plus :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 times :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 square :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 hole_s:n__from:0':n__cons1_0 :: s:n__from:0':n__cons 309.85/291.47 hole_rnil:rcons2_0 :: rnil:rcons 309.85/291.47 hole_posrecip:negrecip3_0 :: posrecip:negrecip 309.85/291.47 gen_s:n__from:0':n__cons4_0 :: Nat -> s:n__from:0':n__cons 309.85/291.47 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 309.85/291.47 309.85/291.47 309.85/291.47 Generator Equations: 309.85/291.47 gen_s:n__from:0':n__cons4_0(0) <=> 0' 309.85/291.47 gen_s:n__from:0':n__cons4_0(+(x, 1)) <=> s(gen_s:n__from:0':n__cons4_0(x)) 309.85/291.47 gen_rnil:rcons5_0(0) <=> rnil 309.85/291.47 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(posrecip(0'), gen_rnil:rcons5_0(x)) 309.85/291.47 309.85/291.47 309.85/291.47 The following defined symbols remain to be analysed: 309.85/291.47 plus, 2ndspos, 2ndsneg, times 309.85/291.47 309.85/291.47 They will be analysed ascendingly in the following order: 309.85/291.47 2ndspos = 2ndsneg 309.85/291.47 plus < times 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (10) LowerBoundPropagationProof (FINISHED) 309.85/291.47 Propagated lower bound. 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (11) 309.85/291.47 BOUNDS(n^1, INF) 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (12) 309.85/291.47 Obligation: 309.85/291.47 TRS: 309.85/291.47 Rules: 309.85/291.47 from(X) -> cons(X, n__from(s(X))) 309.85/291.47 2ndspos(0', Z) -> rnil 309.85/291.47 2ndspos(s(N), cons(X, n__cons(Y, Z))) -> rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z))) 309.85/291.47 2ndsneg(0', Z) -> rnil 309.85/291.47 2ndsneg(s(N), cons(X, n__cons(Y, Z))) -> rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z))) 309.85/291.47 pi(X) -> 2ndspos(X, from(0')) 309.85/291.47 plus(0', Y) -> Y 309.85/291.47 plus(s(X), Y) -> s(plus(X, Y)) 309.85/291.47 times(0', Y) -> 0' 309.85/291.47 times(s(X), Y) -> plus(Y, times(X, Y)) 309.85/291.47 square(X) -> times(X, X) 309.85/291.47 from(X) -> n__from(X) 309.85/291.47 cons(X1, X2) -> n__cons(X1, X2) 309.85/291.47 activate(n__from(X)) -> from(X) 309.85/291.47 activate(n__cons(X1, X2)) -> cons(X1, X2) 309.85/291.47 activate(X) -> X 309.85/291.47 309.85/291.47 Types: 309.85/291.47 from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 n__from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 s :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndspos :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 0' :: s:n__from:0':n__cons 309.85/291.47 rnil :: rnil:rcons 309.85/291.47 n__cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 rcons :: posrecip:negrecip -> rnil:rcons -> rnil:rcons 309.85/291.47 posrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 activate :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndsneg :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 negrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 pi :: s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 plus :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 times :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 square :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 hole_s:n__from:0':n__cons1_0 :: s:n__from:0':n__cons 309.85/291.47 hole_rnil:rcons2_0 :: rnil:rcons 309.85/291.47 hole_posrecip:negrecip3_0 :: posrecip:negrecip 309.85/291.47 gen_s:n__from:0':n__cons4_0 :: Nat -> s:n__from:0':n__cons 309.85/291.47 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 309.85/291.47 309.85/291.47 309.85/291.47 Lemmas: 309.85/291.47 plus(gen_s:n__from:0':n__cons4_0(n7_0), gen_s:n__from:0':n__cons4_0(b)) -> gen_s:n__from:0':n__cons4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 309.85/291.47 309.85/291.47 309.85/291.47 Generator Equations: 309.85/291.47 gen_s:n__from:0':n__cons4_0(0) <=> 0' 309.85/291.47 gen_s:n__from:0':n__cons4_0(+(x, 1)) <=> s(gen_s:n__from:0':n__cons4_0(x)) 309.85/291.47 gen_rnil:rcons5_0(0) <=> rnil 309.85/291.47 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(posrecip(0'), gen_rnil:rcons5_0(x)) 309.85/291.47 309.85/291.47 309.85/291.47 The following defined symbols remain to be analysed: 309.85/291.47 times, 2ndspos, 2ndsneg 309.85/291.47 309.85/291.47 They will be analysed ascendingly in the following order: 309.85/291.47 2ndspos = 2ndsneg 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (13) RewriteLemmaProof (LOWER BOUND(ID)) 309.85/291.47 Proved the following rewrite lemma: 309.85/291.47 times(gen_s:n__from:0':n__cons4_0(n724_0), gen_s:n__from:0':n__cons4_0(b)) -> gen_s:n__from:0':n__cons4_0(*(n724_0, b)), rt in Omega(1 + b*n724_0 + n724_0) 309.85/291.47 309.85/291.47 Induction Base: 309.85/291.47 times(gen_s:n__from:0':n__cons4_0(0), gen_s:n__from:0':n__cons4_0(b)) ->_R^Omega(1) 309.85/291.47 0' 309.85/291.47 309.85/291.47 Induction Step: 309.85/291.47 times(gen_s:n__from:0':n__cons4_0(+(n724_0, 1)), gen_s:n__from:0':n__cons4_0(b)) ->_R^Omega(1) 309.85/291.47 plus(gen_s:n__from:0':n__cons4_0(b), times(gen_s:n__from:0':n__cons4_0(n724_0), gen_s:n__from:0':n__cons4_0(b))) ->_IH 309.85/291.47 plus(gen_s:n__from:0':n__cons4_0(b), gen_s:n__from:0':n__cons4_0(*(c725_0, b))) ->_L^Omega(1 + b) 309.85/291.47 gen_s:n__from:0':n__cons4_0(+(b, *(n724_0, b))) 309.85/291.47 309.85/291.47 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (14) 309.85/291.47 Complex Obligation (BEST) 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (15) 309.85/291.47 Obligation: 309.85/291.47 Proved the lower bound n^2 for the following obligation: 309.85/291.47 309.85/291.47 TRS: 309.85/291.47 Rules: 309.85/291.47 from(X) -> cons(X, n__from(s(X))) 309.85/291.47 2ndspos(0', Z) -> rnil 309.85/291.47 2ndspos(s(N), cons(X, n__cons(Y, Z))) -> rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z))) 309.85/291.47 2ndsneg(0', Z) -> rnil 309.85/291.47 2ndsneg(s(N), cons(X, n__cons(Y, Z))) -> rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z))) 309.85/291.47 pi(X) -> 2ndspos(X, from(0')) 309.85/291.47 plus(0', Y) -> Y 309.85/291.47 plus(s(X), Y) -> s(plus(X, Y)) 309.85/291.47 times(0', Y) -> 0' 309.85/291.47 times(s(X), Y) -> plus(Y, times(X, Y)) 309.85/291.47 square(X) -> times(X, X) 309.85/291.47 from(X) -> n__from(X) 309.85/291.47 cons(X1, X2) -> n__cons(X1, X2) 309.85/291.47 activate(n__from(X)) -> from(X) 309.85/291.47 activate(n__cons(X1, X2)) -> cons(X1, X2) 309.85/291.47 activate(X) -> X 309.85/291.47 309.85/291.47 Types: 309.85/291.47 from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 n__from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 s :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndspos :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 0' :: s:n__from:0':n__cons 309.85/291.47 rnil :: rnil:rcons 309.85/291.47 n__cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 rcons :: posrecip:negrecip -> rnil:rcons -> rnil:rcons 309.85/291.47 posrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 activate :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndsneg :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 negrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.47 pi :: s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 plus :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 times :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 square :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 hole_s:n__from:0':n__cons1_0 :: s:n__from:0':n__cons 309.85/291.47 hole_rnil:rcons2_0 :: rnil:rcons 309.85/291.47 hole_posrecip:negrecip3_0 :: posrecip:negrecip 309.85/291.47 gen_s:n__from:0':n__cons4_0 :: Nat -> s:n__from:0':n__cons 309.85/291.47 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 309.85/291.47 309.85/291.47 309.85/291.47 Lemmas: 309.85/291.47 plus(gen_s:n__from:0':n__cons4_0(n7_0), gen_s:n__from:0':n__cons4_0(b)) -> gen_s:n__from:0':n__cons4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 309.85/291.47 309.85/291.47 309.85/291.47 Generator Equations: 309.85/291.47 gen_s:n__from:0':n__cons4_0(0) <=> 0' 309.85/291.47 gen_s:n__from:0':n__cons4_0(+(x, 1)) <=> s(gen_s:n__from:0':n__cons4_0(x)) 309.85/291.47 gen_rnil:rcons5_0(0) <=> rnil 309.85/291.47 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(posrecip(0'), gen_rnil:rcons5_0(x)) 309.85/291.47 309.85/291.47 309.85/291.47 The following defined symbols remain to be analysed: 309.85/291.47 times, 2ndspos, 2ndsneg 309.85/291.47 309.85/291.47 They will be analysed ascendingly in the following order: 309.85/291.47 2ndspos = 2ndsneg 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (16) LowerBoundPropagationProof (FINISHED) 309.85/291.47 Propagated lower bound. 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (17) 309.85/291.47 BOUNDS(n^2, INF) 309.85/291.47 309.85/291.47 ---------------------------------------- 309.85/291.47 309.85/291.47 (18) 309.85/291.47 Obligation: 309.85/291.47 TRS: 309.85/291.47 Rules: 309.85/291.47 from(X) -> cons(X, n__from(s(X))) 309.85/291.47 2ndspos(0', Z) -> rnil 309.85/291.47 2ndspos(s(N), cons(X, n__cons(Y, Z))) -> rcons(posrecip(activate(Y)), 2ndsneg(N, activate(Z))) 309.85/291.47 2ndsneg(0', Z) -> rnil 309.85/291.47 2ndsneg(s(N), cons(X, n__cons(Y, Z))) -> rcons(negrecip(activate(Y)), 2ndspos(N, activate(Z))) 309.85/291.47 pi(X) -> 2ndspos(X, from(0')) 309.85/291.47 plus(0', Y) -> Y 309.85/291.47 plus(s(X), Y) -> s(plus(X, Y)) 309.85/291.47 times(0', Y) -> 0' 309.85/291.47 times(s(X), Y) -> plus(Y, times(X, Y)) 309.85/291.47 square(X) -> times(X, X) 309.85/291.47 from(X) -> n__from(X) 309.85/291.47 cons(X1, X2) -> n__cons(X1, X2) 309.85/291.47 activate(n__from(X)) -> from(X) 309.85/291.47 activate(n__cons(X1, X2)) -> cons(X1, X2) 309.85/291.47 activate(X) -> X 309.85/291.47 309.85/291.47 Types: 309.85/291.47 from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 n__from :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 s :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.47 2ndspos :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.47 0' :: s:n__from:0':n__cons 309.85/291.48 rnil :: rnil:rcons 309.85/291.48 n__cons :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.48 rcons :: posrecip:negrecip -> rnil:rcons -> rnil:rcons 309.85/291.48 posrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.48 activate :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.48 2ndsneg :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> rnil:rcons 309.85/291.48 negrecip :: s:n__from:0':n__cons -> posrecip:negrecip 309.85/291.48 pi :: s:n__from:0':n__cons -> rnil:rcons 309.85/291.48 plus :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.48 times :: s:n__from:0':n__cons -> s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.48 square :: s:n__from:0':n__cons -> s:n__from:0':n__cons 309.85/291.48 hole_s:n__from:0':n__cons1_0 :: s:n__from:0':n__cons 309.85/291.48 hole_rnil:rcons2_0 :: rnil:rcons 309.85/291.48 hole_posrecip:negrecip3_0 :: posrecip:negrecip 309.85/291.48 gen_s:n__from:0':n__cons4_0 :: Nat -> s:n__from:0':n__cons 309.85/291.48 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 309.85/291.48 309.85/291.48 309.85/291.48 Lemmas: 309.85/291.48 plus(gen_s:n__from:0':n__cons4_0(n7_0), gen_s:n__from:0':n__cons4_0(b)) -> gen_s:n__from:0':n__cons4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 309.85/291.48 times(gen_s:n__from:0':n__cons4_0(n724_0), gen_s:n__from:0':n__cons4_0(b)) -> gen_s:n__from:0':n__cons4_0(*(n724_0, b)), rt in Omega(1 + b*n724_0 + n724_0) 309.85/291.48 309.85/291.48 309.85/291.48 Generator Equations: 309.85/291.48 gen_s:n__from:0':n__cons4_0(0) <=> 0' 309.85/291.48 gen_s:n__from:0':n__cons4_0(+(x, 1)) <=> s(gen_s:n__from:0':n__cons4_0(x)) 309.85/291.48 gen_rnil:rcons5_0(0) <=> rnil 309.85/291.48 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(posrecip(0'), gen_rnil:rcons5_0(x)) 309.85/291.48 309.85/291.48 309.85/291.48 The following defined symbols remain to be analysed: 309.85/291.48 2ndsneg, 2ndspos 309.85/291.48 309.85/291.48 They will be analysed ascendingly in the following order: 309.85/291.48 2ndspos = 2ndsneg 309.95/291.50 EOF