17.40/5.39 WORST_CASE(Omega(n^2), O(n^2)) 17.40/5.40 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 17.40/5.40 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 17.40/5.40 17.40/5.40 17.40/5.40 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 17.40/5.40 17.40/5.40 (0) CpxTRS 17.40/5.40 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 17.40/5.40 (2) CdtProblem 17.40/5.40 (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 17.40/5.40 (4) CdtProblem 17.40/5.40 (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 17.40/5.40 (6) CdtProblem 17.40/5.40 (7) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 17.40/5.40 (8) CdtProblem 17.40/5.40 (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 17.40/5.40 (10) CdtProblem 17.40/5.40 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 110 ms] 17.40/5.40 (12) CdtProblem 17.40/5.40 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 29 ms] 17.40/5.40 (14) CdtProblem 17.40/5.40 (15) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] 17.40/5.40 (16) CdtProblem 17.40/5.40 (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 114 ms] 17.40/5.40 (18) CdtProblem 17.40/5.40 (19) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 17.40/5.40 (20) BOUNDS(1, 1) 17.40/5.40 (21) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 17.40/5.40 (22) CpxTRS 17.40/5.40 (23) SlicingProof [LOWER BOUND(ID), 0 ms] 17.40/5.40 (24) CpxTRS 17.40/5.40 (25) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 17.40/5.40 (26) typed CpxTrs 17.40/5.40 (27) OrderProof [LOWER BOUND(ID), 0 ms] 17.40/5.40 (28) typed CpxTrs 17.40/5.40 (29) RewriteLemmaProof [LOWER BOUND(ID), 294 ms] 17.40/5.40 (30) BEST 17.40/5.40 (31) proven lower bound 17.40/5.40 (32) LowerBoundPropagationProof [FINISHED, 0 ms] 17.40/5.40 (33) BOUNDS(n^1, INF) 17.40/5.40 (34) typed CpxTrs 17.40/5.40 (35) RewriteLemmaProof [LOWER BOUND(ID), 106 ms] 17.40/5.40 (36) BEST 17.40/5.40 (37) proven lower bound 17.40/5.40 (38) LowerBoundPropagationProof [FINISHED, 0 ms] 17.40/5.40 (39) BOUNDS(n^2, INF) 17.40/5.40 (40) typed CpxTrs 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (0) 17.40/5.40 Obligation: 17.40/5.40 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 17.40/5.40 17.40/5.40 17.40/5.40 The TRS R consists of the following rules: 17.40/5.40 17.40/5.40 from(X) -> cons(X, n__from(s(X))) 17.40/5.40 2ndspos(0, Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0, Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from(0)) 17.40/5.40 plus(0, Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0, Y) -> 0 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from(X) -> n__from(X) 17.40/5.40 activate(n__from(X)) -> from(X) 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 S is empty. 17.40/5.40 Rewrite Strategy: INNERMOST 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 17.40/5.40 Converted Cpx (relative) TRS to CDT 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (2) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 2ndspos(0, z0) -> rnil 17.40/5.40 2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3))) 17.40/5.40 2ndsneg(0, z0) -> rnil 17.40/5.40 2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3))) 17.40/5.40 pi(z0) -> 2ndspos(z0, from(0)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 square(z0) -> times(z0, z0) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 Tuples: 17.40/5.40 FROM(z0) -> c 17.40/5.40 FROM(z0) -> c1 17.40/5.40 2NDSPOS(0, z0) -> c2 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2)) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)), ACTIVATE(z3)) 17.40/5.40 2NDSNEG(0, z0) -> c5 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2)) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)), ACTIVATE(z3)) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0)), FROM(0)) 17.40/5.40 PLUS(0, z0) -> c9 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(0, z0) -> c11 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 SQUARE(z0) -> c13(TIMES(z0, z0)) 17.40/5.40 ACTIVATE(n__from(z0)) -> c14(FROM(z0)) 17.40/5.40 ACTIVATE(z0) -> c15 17.40/5.40 S tuples: 17.40/5.40 FROM(z0) -> c 17.40/5.40 FROM(z0) -> c1 17.40/5.40 2NDSPOS(0, z0) -> c2 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2)) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)), ACTIVATE(z3)) 17.40/5.40 2NDSNEG(0, z0) -> c5 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2)) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)), ACTIVATE(z3)) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0)), FROM(0)) 17.40/5.40 PLUS(0, z0) -> c9 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(0, z0) -> c11 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 SQUARE(z0) -> c13(TIMES(z0, z0)) 17.40/5.40 ACTIVATE(n__from(z0)) -> c14(FROM(z0)) 17.40/5.40 ACTIVATE(z0) -> c15 17.40/5.40 K tuples:none 17.40/5.40 Defined Rule Symbols: from_1, 2ndspos_2, 2ndsneg_2, pi_1, plus_2, times_2, square_1, activate_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: FROM_1, 2NDSPOS_2, 2NDSNEG_2, PI_1, PLUS_2, TIMES_2, SQUARE_1, ACTIVATE_1 17.40/5.40 17.40/5.40 Compound Symbols: c, c1, c2, c3_2, c4_2, c5, c6_2, c7_2, c8_2, c9, c10_1, c11, c12_2, c13_1, c14_1, c15 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (3) CdtLeafRemovalProof (ComplexityIfPolyImplication) 17.40/5.40 Removed 1 leading nodes: 17.40/5.40 SQUARE(z0) -> c13(TIMES(z0, z0)) 17.40/5.40 Removed 8 trailing nodes: 17.40/5.40 ACTIVATE(z0) -> c15 17.40/5.40 ACTIVATE(n__from(z0)) -> c14(FROM(z0)) 17.40/5.40 FROM(z0) -> c1 17.40/5.40 TIMES(0, z0) -> c11 17.40/5.40 2NDSPOS(0, z0) -> c2 17.40/5.40 FROM(z0) -> c 17.40/5.40 PLUS(0, z0) -> c9 17.40/5.40 2NDSNEG(0, z0) -> c5 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (4) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 2ndspos(0, z0) -> rnil 17.40/5.40 2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3))) 17.40/5.40 2ndsneg(0, z0) -> rnil 17.40/5.40 2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3))) 17.40/5.40 pi(z0) -> 2ndspos(z0, from(0)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 square(z0) -> times(z0, z0) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 Tuples: 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2)) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)), ACTIVATE(z3)) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2)) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)), ACTIVATE(z3)) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0)), FROM(0)) 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 S tuples: 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2)) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3)), ACTIVATE(z3)) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2))), ACTIVATE(z2)) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3)), ACTIVATE(z3)) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0)), FROM(0)) 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 K tuples:none 17.40/5.40 Defined Rule Symbols: from_1, 2ndspos_2, 2ndsneg_2, pi_1, plus_2, times_2, square_1, activate_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: 2NDSPOS_2, 2NDSNEG_2, PI_1, PLUS_2, TIMES_2 17.40/5.40 17.40/5.40 Compound Symbols: c3_2, c4_2, c6_2, c7_2, c8_2, c10_1, c12_2 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 17.40/5.40 Removed 5 trailing tuple parts 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (6) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 2ndspos(0, z0) -> rnil 17.40/5.40 2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3))) 17.40/5.40 2ndsneg(0, z0) -> rnil 17.40/5.40 2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3))) 17.40/5.40 pi(z0) -> 2ndspos(z0, from(0)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 square(z0) -> times(z0, z0) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 S tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 K tuples:none 17.40/5.40 Defined Rule Symbols: from_1, 2ndspos_2, 2ndsneg_2, pi_1, plus_2, times_2, square_1, activate_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1 17.40/5.40 17.40/5.40 Compound Symbols: c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (7) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 17.40/5.40 The following tuples could be moved from S to K by knowledge propagation: 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (8) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 2ndspos(0, z0) -> rnil 17.40/5.40 2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3))) 17.40/5.40 2ndsneg(0, z0) -> rnil 17.40/5.40 2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3))) 17.40/5.40 pi(z0) -> 2ndspos(z0, from(0)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 square(z0) -> times(z0, z0) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 S tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 K tuples: 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 Defined Rule Symbols: from_1, 2ndspos_2, 2ndsneg_2, pi_1, plus_2, times_2, square_1, activate_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1 17.40/5.40 17.40/5.40 Compound Symbols: c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 17.40/5.40 The following rules are not usable and were removed: 17.40/5.40 2ndspos(0, z0) -> rnil 17.40/5.40 2ndspos(s(z0), cons(z1, z2)) -> 2ndspos(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndspos(s(z0), cons2(z1, cons(z2, z3))) -> rcons(posrecip(z2), 2ndsneg(z0, activate(z3))) 17.40/5.40 2ndsneg(0, z0) -> rnil 17.40/5.40 2ndsneg(s(z0), cons(z1, z2)) -> 2ndsneg(s(z0), cons2(z1, activate(z2))) 17.40/5.40 2ndsneg(s(z0), cons2(z1, cons(z2, z3))) -> rcons(negrecip(z2), 2ndspos(z0, activate(z3))) 17.40/5.40 pi(z0) -> 2ndspos(z0, from(0)) 17.40/5.40 square(z0) -> times(z0, z0) 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (10) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 S tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 K tuples: 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 Defined Rule Symbols: times_2, plus_2, activate_1, from_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1 17.40/5.40 17.40/5.40 Compound Symbols: c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 17.40/5.40 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 We considered the (Usable) Rules:none 17.40/5.40 And the Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 The order we found is given by the following interpretation: 17.40/5.40 17.40/5.40 Polynomial interpretation : 17.40/5.40 17.40/5.40 POL(0) = [1] 17.40/5.40 POL(2NDSNEG(x_1, x_2)) = 0 17.40/5.40 POL(2NDSPOS(x_1, x_2)) = 0 17.40/5.40 POL(PI(x_1)) = 0 17.40/5.40 POL(PLUS(x_1, x_2)) = 0 17.40/5.40 POL(TIMES(x_1, x_2)) = x_1 17.40/5.40 POL(activate(x_1)) = x_1 17.40/5.40 POL(c10(x_1)) = x_1 17.40/5.40 POL(c12(x_1, x_2)) = x_1 + x_2 17.40/5.40 POL(c3(x_1)) = x_1 17.40/5.40 POL(c4(x_1)) = x_1 17.40/5.40 POL(c6(x_1)) = x_1 17.40/5.40 POL(c7(x_1)) = x_1 17.40/5.40 POL(c8(x_1)) = x_1 17.40/5.40 POL(cons(x_1, x_2)) = [1] + x_1 17.40/5.40 POL(cons2(x_1, x_2)) = [1] + x_1 17.40/5.40 POL(from(x_1)) = [1] + x_1 17.40/5.40 POL(n__from(x_1)) = [1] + x_1 17.40/5.40 POL(plus(x_1, x_2)) = [1] + x_1 + x_2 17.40/5.40 POL(s(x_1)) = [1] + x_1 17.40/5.40 POL(times(x_1, x_2)) = [1] + x_1 + x_2 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (12) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 S tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 K tuples: 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 Defined Rule Symbols: times_2, plus_2, activate_1, from_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1 17.40/5.40 17.40/5.40 Compound Symbols: c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 17.40/5.40 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 We considered the (Usable) Rules:none 17.40/5.40 And the Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 The order we found is given by the following interpretation: 17.40/5.40 17.40/5.40 Polynomial interpretation : 17.40/5.40 17.40/5.40 POL(0) = [1] 17.40/5.40 POL(2NDSNEG(x_1, x_2)) = x_1 17.40/5.40 POL(2NDSPOS(x_1, x_2)) = x_1 17.40/5.40 POL(PI(x_1)) = x_1 17.40/5.40 POL(PLUS(x_1, x_2)) = [1] 17.40/5.40 POL(TIMES(x_1, x_2)) = x_1 17.40/5.40 POL(activate(x_1)) = x_1 17.40/5.40 POL(c10(x_1)) = x_1 17.40/5.40 POL(c12(x_1, x_2)) = x_1 + x_2 17.40/5.40 POL(c3(x_1)) = x_1 17.40/5.40 POL(c4(x_1)) = x_1 17.40/5.40 POL(c6(x_1)) = x_1 17.40/5.40 POL(c7(x_1)) = x_1 17.40/5.40 POL(c8(x_1)) = x_1 17.40/5.40 POL(cons(x_1, x_2)) = x_2 17.40/5.40 POL(cons2(x_1, x_2)) = [1] + x_1 17.40/5.40 POL(from(x_1)) = [1] 17.40/5.40 POL(n__from(x_1)) = [1] 17.40/5.40 POL(plus(x_1, x_2)) = [1] + x_1 + x_2 17.40/5.40 POL(s(x_1)) = [1] + x_1 17.40/5.40 POL(times(x_1, x_2)) = [1] + x_1 + x_2 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (14) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 S tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 K tuples: 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 Defined Rule Symbols: times_2, plus_2, activate_1, from_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1 17.40/5.40 17.40/5.40 Compound Symbols: c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (15) CdtKnowledgeProof (BOTH BOUNDS(ID, ID)) 17.40/5.40 The following tuples could be moved from S to K by knowledge propagation: 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (16) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 S tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 K tuples: 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 Defined Rule Symbols: times_2, plus_2, activate_1, from_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1 17.40/5.40 17.40/5.40 Compound Symbols: c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 17.40/5.40 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 We considered the (Usable) Rules:none 17.40/5.40 And the Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 The order we found is given by the following interpretation: 17.40/5.40 17.40/5.40 Polynomial interpretation : 17.40/5.40 17.40/5.40 POL(0) = 0 17.40/5.40 POL(2NDSNEG(x_1, x_2)) = 0 17.40/5.40 POL(2NDSPOS(x_1, x_2)) = 0 17.40/5.40 POL(PI(x_1)) = [2] + [2]x_1^2 17.40/5.40 POL(PLUS(x_1, x_2)) = x_1 17.40/5.40 POL(TIMES(x_1, x_2)) = x_1*x_2 17.40/5.40 POL(activate(x_1)) = 0 17.40/5.40 POL(c10(x_1)) = x_1 17.40/5.40 POL(c12(x_1, x_2)) = x_1 + x_2 17.40/5.40 POL(c3(x_1)) = x_1 17.40/5.40 POL(c4(x_1)) = x_1 17.40/5.40 POL(c6(x_1)) = x_1 17.40/5.40 POL(c7(x_1)) = x_1 17.40/5.40 POL(c8(x_1)) = x_1 17.40/5.40 POL(cons(x_1, x_2)) = 0 17.40/5.40 POL(cons2(x_1, x_2)) = 0 17.40/5.40 POL(from(x_1)) = 0 17.40/5.40 POL(n__from(x_1)) = 0 17.40/5.40 POL(plus(x_1, x_2)) = [1] + x_1^2 17.40/5.40 POL(s(x_1)) = [1] + x_1 17.40/5.40 POL(times(x_1, x_2)) = [2]x_2^2 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (18) 17.40/5.40 Obligation: 17.40/5.40 Complexity Dependency Tuples Problem 17.40/5.40 17.40/5.40 Rules: 17.40/5.40 times(0, z0) -> 0 17.40/5.40 times(s(z0), z1) -> plus(z1, times(z0, z1)) 17.40/5.40 plus(0, z0) -> z0 17.40/5.40 plus(s(z0), z1) -> s(plus(z0, z1)) 17.40/5.40 activate(n__from(z0)) -> from(z0) 17.40/5.40 activate(z0) -> z0 17.40/5.40 from(z0) -> cons(z0, n__from(s(z0))) 17.40/5.40 from(z0) -> n__from(z0) 17.40/5.40 Tuples: 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 S tuples:none 17.40/5.40 K tuples: 17.40/5.40 PI(z0) -> c8(2NDSPOS(z0, from(0))) 17.40/5.40 TIMES(s(z0), z1) -> c12(PLUS(z1, times(z0, z1)), TIMES(z0, z1)) 17.40/5.40 2NDSPOS(s(z0), cons2(z1, cons(z2, z3))) -> c4(2NDSNEG(z0, activate(z3))) 17.40/5.40 2NDSNEG(s(z0), cons2(z1, cons(z2, z3))) -> c7(2NDSPOS(z0, activate(z3))) 17.40/5.40 2NDSPOS(s(z0), cons(z1, z2)) -> c3(2NDSPOS(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 2NDSNEG(s(z0), cons(z1, z2)) -> c6(2NDSNEG(s(z0), cons2(z1, activate(z2)))) 17.40/5.40 PLUS(s(z0), z1) -> c10(PLUS(z0, z1)) 17.40/5.40 Defined Rule Symbols: times_2, plus_2, activate_1, from_1 17.40/5.40 17.40/5.40 Defined Pair Symbols: PLUS_2, TIMES_2, 2NDSPOS_2, 2NDSNEG_2, PI_1 17.40/5.40 17.40/5.40 Compound Symbols: c10_1, c12_2, c3_1, c4_1, c6_1, c7_1, c8_1 17.40/5.40 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (19) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 17.40/5.40 The set S is empty 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (20) 17.40/5.40 BOUNDS(1, 1) 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (21) RenamingProof (BOTH BOUNDS(ID, ID)) 17.40/5.40 Renamed function symbols to avoid clashes with predefined symbol. 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (22) 17.40/5.40 Obligation: 17.40/5.40 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 17.40/5.40 17.40/5.40 17.40/5.40 The TRS R consists of the following rules: 17.40/5.40 17.40/5.40 from(X) -> cons(X, n__from(s(X))) 17.40/5.40 2ndspos(0', Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(X, Z)) -> 2ndspos(s(N), cons2(X, activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(X, cons(Y, Z))) -> rcons(posrecip(Y), 2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0', Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(X, Z)) -> 2ndsneg(s(N), cons2(X, activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(X, cons(Y, Z))) -> rcons(negrecip(Y), 2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from(0')) 17.40/5.40 plus(0', Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0', Y) -> 0' 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from(X) -> n__from(X) 17.40/5.40 activate(n__from(X)) -> from(X) 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 S is empty. 17.40/5.40 Rewrite Strategy: INNERMOST 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (23) SlicingProof (LOWER BOUND(ID)) 17.40/5.40 Sliced the following arguments: 17.40/5.40 from/0 17.40/5.40 cons/0 17.40/5.40 n__from/0 17.40/5.40 cons2/0 17.40/5.40 rcons/0 17.40/5.40 posrecip/0 17.40/5.40 negrecip/0 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (24) 17.40/5.40 Obligation: 17.40/5.40 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 17.40/5.40 17.40/5.40 17.40/5.40 The TRS R consists of the following rules: 17.40/5.40 17.40/5.40 from -> cons(n__from) 17.40/5.40 2ndspos(0', Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0', Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from) 17.40/5.40 plus(0', Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0', Y) -> 0' 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from -> n__from 17.40/5.40 activate(n__from) -> from 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 S is empty. 17.40/5.40 Rewrite Strategy: INNERMOST 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (25) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 17.40/5.40 Infered types. 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (26) 17.40/5.40 Obligation: 17.40/5.40 Innermost TRS: 17.40/5.40 Rules: 17.40/5.40 from -> cons(n__from) 17.40/5.40 2ndspos(0', Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0', Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from) 17.40/5.40 plus(0', Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0', Y) -> 0' 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from -> n__from 17.40/5.40 activate(n__from) -> from 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 Types: 17.40/5.40 from :: n__from:cons:cons2 17.40/5.40 cons :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 n__from :: n__from:cons:cons2 17.40/5.40 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 0' :: 0':s 17.40/5.40 rnil :: rnil:rcons 17.40/5.40 s :: 0':s -> 0':s 17.40/5.40 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 activate :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 rcons :: rnil:rcons -> rnil:rcons 17.40/5.40 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 pi :: 0':s -> rnil:rcons 17.40/5.40 plus :: 0':s -> 0':s -> 0':s 17.40/5.40 times :: 0':s -> 0':s -> 0':s 17.40/5.40 square :: 0':s -> 0':s 17.40/5.40 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 17.40/5.40 hole_rnil:rcons2_0 :: rnil:rcons 17.40/5.40 hole_0':s3_0 :: 0':s 17.40/5.40 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 17.40/5.40 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 17.40/5.40 gen_0':s6_0 :: Nat -> 0':s 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (27) OrderProof (LOWER BOUND(ID)) 17.40/5.40 Heuristically decided to analyse the following defined symbols: 17.40/5.40 2ndspos, 2ndsneg, plus, times 17.40/5.40 17.40/5.40 They will be analysed ascendingly in the following order: 17.40/5.40 2ndspos = 2ndsneg 17.40/5.40 plus < times 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (28) 17.40/5.40 Obligation: 17.40/5.40 Innermost TRS: 17.40/5.40 Rules: 17.40/5.40 from -> cons(n__from) 17.40/5.40 2ndspos(0', Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0', Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from) 17.40/5.40 plus(0', Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0', Y) -> 0' 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from -> n__from 17.40/5.40 activate(n__from) -> from 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 Types: 17.40/5.40 from :: n__from:cons:cons2 17.40/5.40 cons :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 n__from :: n__from:cons:cons2 17.40/5.40 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 0' :: 0':s 17.40/5.40 rnil :: rnil:rcons 17.40/5.40 s :: 0':s -> 0':s 17.40/5.40 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 activate :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 rcons :: rnil:rcons -> rnil:rcons 17.40/5.40 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 pi :: 0':s -> rnil:rcons 17.40/5.40 plus :: 0':s -> 0':s -> 0':s 17.40/5.40 times :: 0':s -> 0':s -> 0':s 17.40/5.40 square :: 0':s -> 0':s 17.40/5.40 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 17.40/5.40 hole_rnil:rcons2_0 :: rnil:rcons 17.40/5.40 hole_0':s3_0 :: 0':s 17.40/5.40 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 17.40/5.40 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 17.40/5.40 gen_0':s6_0 :: Nat -> 0':s 17.40/5.40 17.40/5.40 17.40/5.40 Generator Equations: 17.40/5.40 gen_n__from:cons:cons24_0(0) <=> n__from 17.40/5.40 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 17.40/5.40 gen_rnil:rcons5_0(0) <=> rnil 17.40/5.40 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 17.40/5.40 gen_0':s6_0(0) <=> 0' 17.40/5.40 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 17.40/5.40 17.40/5.40 17.40/5.40 The following defined symbols remain to be analysed: 17.40/5.40 plus, 2ndspos, 2ndsneg, times 17.40/5.40 17.40/5.40 They will be analysed ascendingly in the following order: 17.40/5.40 2ndspos = 2ndsneg 17.40/5.40 plus < times 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (29) RewriteLemmaProof (LOWER BOUND(ID)) 17.40/5.40 Proved the following rewrite lemma: 17.40/5.40 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) 17.40/5.40 17.40/5.40 Induction Base: 17.40/5.40 plus(gen_0':s6_0(0), gen_0':s6_0(b)) ->_R^Omega(1) 17.40/5.40 gen_0':s6_0(b) 17.40/5.40 17.40/5.40 Induction Step: 17.40/5.40 plus(gen_0':s6_0(+(n8_0, 1)), gen_0':s6_0(b)) ->_R^Omega(1) 17.40/5.40 s(plus(gen_0':s6_0(n8_0), gen_0':s6_0(b))) ->_IH 17.40/5.40 s(gen_0':s6_0(+(b, c9_0))) 17.40/5.40 17.40/5.40 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (30) 17.40/5.40 Complex Obligation (BEST) 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (31) 17.40/5.40 Obligation: 17.40/5.40 Proved the lower bound n^1 for the following obligation: 17.40/5.40 17.40/5.40 Innermost TRS: 17.40/5.40 Rules: 17.40/5.40 from -> cons(n__from) 17.40/5.40 2ndspos(0', Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0', Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from) 17.40/5.40 plus(0', Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0', Y) -> 0' 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from -> n__from 17.40/5.40 activate(n__from) -> from 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 Types: 17.40/5.40 from :: n__from:cons:cons2 17.40/5.40 cons :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 n__from :: n__from:cons:cons2 17.40/5.40 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 0' :: 0':s 17.40/5.40 rnil :: rnil:rcons 17.40/5.40 s :: 0':s -> 0':s 17.40/5.40 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 activate :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 rcons :: rnil:rcons -> rnil:rcons 17.40/5.40 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 pi :: 0':s -> rnil:rcons 17.40/5.40 plus :: 0':s -> 0':s -> 0':s 17.40/5.40 times :: 0':s -> 0':s -> 0':s 17.40/5.40 square :: 0':s -> 0':s 17.40/5.40 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 17.40/5.40 hole_rnil:rcons2_0 :: rnil:rcons 17.40/5.40 hole_0':s3_0 :: 0':s 17.40/5.40 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 17.40/5.40 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 17.40/5.40 gen_0':s6_0 :: Nat -> 0':s 17.40/5.40 17.40/5.40 17.40/5.40 Generator Equations: 17.40/5.40 gen_n__from:cons:cons24_0(0) <=> n__from 17.40/5.40 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 17.40/5.40 gen_rnil:rcons5_0(0) <=> rnil 17.40/5.40 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 17.40/5.40 gen_0':s6_0(0) <=> 0' 17.40/5.40 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 17.40/5.40 17.40/5.40 17.40/5.40 The following defined symbols remain to be analysed: 17.40/5.40 plus, 2ndspos, 2ndsneg, times 17.40/5.40 17.40/5.40 They will be analysed ascendingly in the following order: 17.40/5.40 2ndspos = 2ndsneg 17.40/5.40 plus < times 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (32) LowerBoundPropagationProof (FINISHED) 17.40/5.40 Propagated lower bound. 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (33) 17.40/5.40 BOUNDS(n^1, INF) 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (34) 17.40/5.40 Obligation: 17.40/5.40 Innermost TRS: 17.40/5.40 Rules: 17.40/5.40 from -> cons(n__from) 17.40/5.40 2ndspos(0', Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0', Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from) 17.40/5.40 plus(0', Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0', Y) -> 0' 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from -> n__from 17.40/5.40 activate(n__from) -> from 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 Types: 17.40/5.40 from :: n__from:cons:cons2 17.40/5.40 cons :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 n__from :: n__from:cons:cons2 17.40/5.40 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 0' :: 0':s 17.40/5.40 rnil :: rnil:rcons 17.40/5.40 s :: 0':s -> 0':s 17.40/5.40 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 activate :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 rcons :: rnil:rcons -> rnil:rcons 17.40/5.40 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 pi :: 0':s -> rnil:rcons 17.40/5.40 plus :: 0':s -> 0':s -> 0':s 17.40/5.40 times :: 0':s -> 0':s -> 0':s 17.40/5.40 square :: 0':s -> 0':s 17.40/5.40 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 17.40/5.40 hole_rnil:rcons2_0 :: rnil:rcons 17.40/5.40 hole_0':s3_0 :: 0':s 17.40/5.40 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 17.40/5.40 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 17.40/5.40 gen_0':s6_0 :: Nat -> 0':s 17.40/5.40 17.40/5.40 17.40/5.40 Lemmas: 17.40/5.40 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) 17.40/5.40 17.40/5.40 17.40/5.40 Generator Equations: 17.40/5.40 gen_n__from:cons:cons24_0(0) <=> n__from 17.40/5.40 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 17.40/5.40 gen_rnil:rcons5_0(0) <=> rnil 17.40/5.40 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 17.40/5.40 gen_0':s6_0(0) <=> 0' 17.40/5.40 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 17.40/5.40 17.40/5.40 17.40/5.40 The following defined symbols remain to be analysed: 17.40/5.40 times, 2ndspos, 2ndsneg 17.40/5.40 17.40/5.40 They will be analysed ascendingly in the following order: 17.40/5.40 2ndspos = 2ndsneg 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (35) RewriteLemmaProof (LOWER BOUND(ID)) 17.40/5.40 Proved the following rewrite lemma: 17.40/5.40 times(gen_0':s6_0(n1067_0), gen_0':s6_0(b)) -> gen_0':s6_0(*(n1067_0, b)), rt in Omega(1 + b*n1067_0 + n1067_0) 17.40/5.40 17.40/5.40 Induction Base: 17.40/5.40 times(gen_0':s6_0(0), gen_0':s6_0(b)) ->_R^Omega(1) 17.40/5.40 0' 17.40/5.40 17.40/5.40 Induction Step: 17.40/5.40 times(gen_0':s6_0(+(n1067_0, 1)), gen_0':s6_0(b)) ->_R^Omega(1) 17.40/5.40 plus(gen_0':s6_0(b), times(gen_0':s6_0(n1067_0), gen_0':s6_0(b))) ->_IH 17.40/5.40 plus(gen_0':s6_0(b), gen_0':s6_0(*(c1068_0, b))) ->_L^Omega(1 + b) 17.40/5.40 gen_0':s6_0(+(b, *(n1067_0, b))) 17.40/5.40 17.40/5.40 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (36) 17.40/5.40 Complex Obligation (BEST) 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (37) 17.40/5.40 Obligation: 17.40/5.40 Proved the lower bound n^2 for the following obligation: 17.40/5.40 17.40/5.40 Innermost TRS: 17.40/5.40 Rules: 17.40/5.40 from -> cons(n__from) 17.40/5.40 2ndspos(0', Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0', Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from) 17.40/5.40 plus(0', Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0', Y) -> 0' 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from -> n__from 17.40/5.40 activate(n__from) -> from 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 Types: 17.40/5.40 from :: n__from:cons:cons2 17.40/5.40 cons :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 n__from :: n__from:cons:cons2 17.40/5.40 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 0' :: 0':s 17.40/5.40 rnil :: rnil:rcons 17.40/5.40 s :: 0':s -> 0':s 17.40/5.40 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 activate :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 rcons :: rnil:rcons -> rnil:rcons 17.40/5.40 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 pi :: 0':s -> rnil:rcons 17.40/5.40 plus :: 0':s -> 0':s -> 0':s 17.40/5.40 times :: 0':s -> 0':s -> 0':s 17.40/5.40 square :: 0':s -> 0':s 17.40/5.40 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 17.40/5.40 hole_rnil:rcons2_0 :: rnil:rcons 17.40/5.40 hole_0':s3_0 :: 0':s 17.40/5.40 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 17.40/5.40 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 17.40/5.40 gen_0':s6_0 :: Nat -> 0':s 17.40/5.40 17.40/5.40 17.40/5.40 Lemmas: 17.40/5.40 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) 17.40/5.40 17.40/5.40 17.40/5.40 Generator Equations: 17.40/5.40 gen_n__from:cons:cons24_0(0) <=> n__from 17.40/5.40 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 17.40/5.40 gen_rnil:rcons5_0(0) <=> rnil 17.40/5.40 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 17.40/5.40 gen_0':s6_0(0) <=> 0' 17.40/5.40 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 17.40/5.40 17.40/5.40 17.40/5.40 The following defined symbols remain to be analysed: 17.40/5.40 times, 2ndspos, 2ndsneg 17.40/5.40 17.40/5.40 They will be analysed ascendingly in the following order: 17.40/5.40 2ndspos = 2ndsneg 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (38) LowerBoundPropagationProof (FINISHED) 17.40/5.40 Propagated lower bound. 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (39) 17.40/5.40 BOUNDS(n^2, INF) 17.40/5.40 17.40/5.40 ---------------------------------------- 17.40/5.40 17.40/5.40 (40) 17.40/5.40 Obligation: 17.40/5.40 Innermost TRS: 17.40/5.40 Rules: 17.40/5.40 from -> cons(n__from) 17.40/5.40 2ndspos(0', Z) -> rnil 17.40/5.40 2ndspos(s(N), cons(Z)) -> 2ndspos(s(N), cons2(activate(Z))) 17.40/5.40 2ndspos(s(N), cons2(cons(Z))) -> rcons(2ndsneg(N, activate(Z))) 17.40/5.40 2ndsneg(0', Z) -> rnil 17.40/5.40 2ndsneg(s(N), cons(Z)) -> 2ndsneg(s(N), cons2(activate(Z))) 17.40/5.40 2ndsneg(s(N), cons2(cons(Z))) -> rcons(2ndspos(N, activate(Z))) 17.40/5.40 pi(X) -> 2ndspos(X, from) 17.40/5.40 plus(0', Y) -> Y 17.40/5.40 plus(s(X), Y) -> s(plus(X, Y)) 17.40/5.40 times(0', Y) -> 0' 17.40/5.40 times(s(X), Y) -> plus(Y, times(X, Y)) 17.40/5.40 square(X) -> times(X, X) 17.40/5.40 from -> n__from 17.40/5.40 activate(n__from) -> from 17.40/5.40 activate(X) -> X 17.40/5.40 17.40/5.40 Types: 17.40/5.40 from :: n__from:cons:cons2 17.40/5.40 cons :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 n__from :: n__from:cons:cons2 17.40/5.40 2ndspos :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 0' :: 0':s 17.40/5.40 rnil :: rnil:rcons 17.40/5.40 s :: 0':s -> 0':s 17.40/5.40 cons2 :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 activate :: n__from:cons:cons2 -> n__from:cons:cons2 17.40/5.40 rcons :: rnil:rcons -> rnil:rcons 17.40/5.40 2ndsneg :: 0':s -> n__from:cons:cons2 -> rnil:rcons 17.40/5.40 pi :: 0':s -> rnil:rcons 17.40/5.40 plus :: 0':s -> 0':s -> 0':s 17.40/5.40 times :: 0':s -> 0':s -> 0':s 17.40/5.40 square :: 0':s -> 0':s 17.40/5.40 hole_n__from:cons:cons21_0 :: n__from:cons:cons2 17.40/5.40 hole_rnil:rcons2_0 :: rnil:rcons 17.40/5.40 hole_0':s3_0 :: 0':s 17.40/5.40 gen_n__from:cons:cons24_0 :: Nat -> n__from:cons:cons2 17.40/5.40 gen_rnil:rcons5_0 :: Nat -> rnil:rcons 17.40/5.40 gen_0':s6_0 :: Nat -> 0':s 17.40/5.40 17.40/5.40 17.40/5.40 Lemmas: 17.40/5.40 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) 17.40/5.40 times(gen_0':s6_0(n1067_0), gen_0':s6_0(b)) -> gen_0':s6_0(*(n1067_0, b)), rt in Omega(1 + b*n1067_0 + n1067_0) 17.40/5.40 17.40/5.40 17.40/5.40 Generator Equations: 17.40/5.40 gen_n__from:cons:cons24_0(0) <=> n__from 17.40/5.40 gen_n__from:cons:cons24_0(+(x, 1)) <=> cons(gen_n__from:cons:cons24_0(x)) 17.40/5.40 gen_rnil:rcons5_0(0) <=> rnil 17.40/5.40 gen_rnil:rcons5_0(+(x, 1)) <=> rcons(gen_rnil:rcons5_0(x)) 17.40/5.40 gen_0':s6_0(0) <=> 0' 17.40/5.40 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 17.40/5.40 17.40/5.40 17.40/5.40 The following defined symbols remain to be analysed: 17.40/5.40 2ndsneg, 2ndspos 17.40/5.40 17.40/5.40 They will be analysed ascendingly in the following order: 17.40/5.40 2ndspos = 2ndsneg 17.70/5.49 EOF