25.84/8.83 WORST_CASE(Omega(n^2), O(n^2)) 25.84/8.85 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 25.84/8.85 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.84/8.85 25.84/8.85 25.84/8.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 25.84/8.85 25.84/8.85 (0) CpxTRS 25.84/8.85 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 25.84/8.85 (2) CpxTRS 25.84/8.85 (3) CpxTrsToCdtProof [UPPER BOUND(ID), 7 ms] 25.84/8.85 (4) CdtProblem 25.84/8.85 (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 25.84/8.85 (6) CdtProblem 25.84/8.85 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 94 ms] 25.84/8.85 (8) CdtProblem 25.84/8.85 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 55 ms] 25.84/8.85 (10) CdtProblem 25.84/8.85 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 49 ms] 25.84/8.85 (12) CdtProblem 25.84/8.85 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 25.84/8.85 (14) BOUNDS(1, 1) 25.84/8.85 (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 25.84/8.85 (16) CpxTRS 25.84/8.85 (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 25.84/8.85 (18) typed CpxTrs 25.84/8.85 (19) OrderProof [LOWER BOUND(ID), 0 ms] 25.84/8.85 (20) typed CpxTrs 25.84/8.85 (21) RewriteLemmaProof [LOWER BOUND(ID), 292 ms] 25.84/8.85 (22) BEST 25.84/8.85 (23) proven lower bound 25.84/8.85 (24) LowerBoundPropagationProof [FINISHED, 0 ms] 25.84/8.85 (25) BOUNDS(n^1, INF) 25.84/8.85 (26) typed CpxTrs 25.84/8.85 (27) RewriteLemmaProof [LOWER BOUND(ID), 78 ms] 25.84/8.85 (28) typed CpxTrs 25.84/8.85 (29) RewriteLemmaProof [LOWER BOUND(ID), 134 ms] 25.84/8.85 (30) proven lower bound 25.84/8.85 (31) LowerBoundPropagationProof [FINISHED, 0 ms] 25.84/8.85 (32) BOUNDS(n^2, INF) 25.84/8.85 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (0) 25.84/8.85 Obligation: 25.84/8.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 25.84/8.85 25.84/8.85 25.84/8.85 The TRS R consists of the following rules: 25.84/8.85 25.84/8.85 sqr(0) -> 0 25.84/8.85 sqr(s(x)) -> +(sqr(x), s(double(x))) 25.84/8.85 double(0) -> 0 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +(x, 0) -> x 25.84/8.85 +(x, s(y)) -> s(+(x, y)) 25.84/8.85 sqr(s(x)) -> s(+(sqr(x), double(x))) 25.84/8.85 25.84/8.85 S is empty. 25.84/8.85 Rewrite Strategy: FULL 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 25.84/8.85 Converted rc-obligation to irc-obligation. 25.84/8.85 25.84/8.85 The duplicating contexts are: 25.84/8.85 sqr(s([])) 25.84/8.85 25.84/8.85 25.84/8.85 The defined contexts are: 25.84/8.85 +([], x1) 25.84/8.85 +(x0, []) 25.84/8.85 +([], s(x1)) 25.84/8.85 +(x0, s([])) 25.84/8.85 25.84/8.85 25.84/8.85 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (2) 25.84/8.85 Obligation: 25.84/8.85 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 25.84/8.85 25.84/8.85 25.84/8.85 The TRS R consists of the following rules: 25.84/8.85 25.84/8.85 sqr(0) -> 0 25.84/8.85 sqr(s(x)) -> +(sqr(x), s(double(x))) 25.84/8.85 double(0) -> 0 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +(x, 0) -> x 25.84/8.85 +(x, s(y)) -> s(+(x, y)) 25.84/8.85 sqr(s(x)) -> s(+(sqr(x), double(x))) 25.84/8.85 25.84/8.85 S is empty. 25.84/8.85 Rewrite Strategy: INNERMOST 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (3) CpxTrsToCdtProof (UPPER BOUND(ID)) 25.84/8.85 Converted Cpx (relative) TRS to CDT 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (4) 25.84/8.85 Obligation: 25.84/8.85 Complexity Dependency Tuples Problem 25.84/8.85 25.84/8.85 Rules: 25.84/8.85 sqr(0) -> 0 25.84/8.85 sqr(s(z0)) -> +(sqr(z0), s(double(z0))) 25.84/8.85 sqr(s(z0)) -> s(+(sqr(z0), double(z0))) 25.84/8.85 double(0) -> 0 25.84/8.85 double(s(z0)) -> s(s(double(z0))) 25.84/8.85 +(z0, 0) -> z0 25.84/8.85 +(z0, s(z1)) -> s(+(z0, z1)) 25.84/8.85 Tuples: 25.84/8.85 SQR(0) -> c 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(0) -> c3 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, 0) -> c5 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 S tuples: 25.84/8.85 SQR(0) -> c 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(0) -> c3 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, 0) -> c5 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 K tuples:none 25.84/8.85 Defined Rule Symbols: sqr_1, double_1, +_2 25.84/8.85 25.84/8.85 Defined Pair Symbols: SQR_1, DOUBLE_1, +'_2 25.84/8.85 25.84/8.85 Compound Symbols: c, c1_3, c2_3, c3, c4_1, c5, c6_1 25.84/8.85 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 25.84/8.85 Removed 3 trailing nodes: 25.84/8.85 +'(z0, 0) -> c5 25.84/8.85 DOUBLE(0) -> c3 25.84/8.85 SQR(0) -> c 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (6) 25.84/8.85 Obligation: 25.84/8.85 Complexity Dependency Tuples Problem 25.84/8.85 25.84/8.85 Rules: 25.84/8.85 sqr(0) -> 0 25.84/8.85 sqr(s(z0)) -> +(sqr(z0), s(double(z0))) 25.84/8.85 sqr(s(z0)) -> s(+(sqr(z0), double(z0))) 25.84/8.85 double(0) -> 0 25.84/8.85 double(s(z0)) -> s(s(double(z0))) 25.84/8.85 +(z0, 0) -> z0 25.84/8.85 +(z0, s(z1)) -> s(+(z0, z1)) 25.84/8.85 Tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 S tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 K tuples:none 25.84/8.85 Defined Rule Symbols: sqr_1, double_1, +_2 25.84/8.85 25.84/8.85 Defined Pair Symbols: SQR_1, DOUBLE_1, +'_2 25.84/8.85 25.84/8.85 Compound Symbols: c1_3, c2_3, c4_1, c6_1 25.84/8.85 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 25.84/8.85 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 We considered the (Usable) Rules:none 25.84/8.85 And the Tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 The order we found is given by the following interpretation: 25.84/8.85 25.84/8.85 Polynomial interpretation : 25.84/8.85 25.84/8.85 POL(+(x_1, x_2)) = [1] + x_2 25.84/8.85 POL(+'(x_1, x_2)) = 0 25.84/8.85 POL(0) = [1] 25.84/8.85 POL(DOUBLE(x_1)) = 0 25.84/8.85 POL(SQR(x_1)) = x_1 25.84/8.85 POL(c1(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.84/8.85 POL(c2(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.84/8.85 POL(c4(x_1)) = x_1 25.84/8.85 POL(c6(x_1)) = x_1 25.84/8.85 POL(double(x_1)) = x_1 25.84/8.85 POL(s(x_1)) = [1] + x_1 25.84/8.85 POL(sqr(x_1)) = [1] + x_1 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (8) 25.84/8.85 Obligation: 25.84/8.85 Complexity Dependency Tuples Problem 25.84/8.85 25.84/8.85 Rules: 25.84/8.85 sqr(0) -> 0 25.84/8.85 sqr(s(z0)) -> +(sqr(z0), s(double(z0))) 25.84/8.85 sqr(s(z0)) -> s(+(sqr(z0), double(z0))) 25.84/8.85 double(0) -> 0 25.84/8.85 double(s(z0)) -> s(s(double(z0))) 25.84/8.85 +(z0, 0) -> z0 25.84/8.85 +(z0, s(z1)) -> s(+(z0, z1)) 25.84/8.85 Tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 S tuples: 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 K tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 Defined Rule Symbols: sqr_1, double_1, +_2 25.84/8.85 25.84/8.85 Defined Pair Symbols: SQR_1, DOUBLE_1, +'_2 25.84/8.85 25.84/8.85 Compound Symbols: c1_3, c2_3, c4_1, c6_1 25.84/8.85 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 25.84/8.85 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 We considered the (Usable) Rules:none 25.84/8.85 And the Tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 The order we found is given by the following interpretation: 25.84/8.85 25.84/8.85 Polynomial interpretation : 25.84/8.85 25.84/8.85 POL(+(x_1, x_2)) = [2] 25.84/8.85 POL(+'(x_1, x_2)) = 0 25.84/8.85 POL(0) = 0 25.84/8.85 POL(DOUBLE(x_1)) = x_1 25.84/8.85 POL(SQR(x_1)) = x_1^2 25.84/8.85 POL(c1(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.84/8.85 POL(c2(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.84/8.85 POL(c4(x_1)) = x_1 25.84/8.85 POL(c6(x_1)) = x_1 25.84/8.85 POL(double(x_1)) = 0 25.84/8.85 POL(s(x_1)) = [1] + x_1 25.84/8.85 POL(sqr(x_1)) = 0 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (10) 25.84/8.85 Obligation: 25.84/8.85 Complexity Dependency Tuples Problem 25.84/8.85 25.84/8.85 Rules: 25.84/8.85 sqr(0) -> 0 25.84/8.85 sqr(s(z0)) -> +(sqr(z0), s(double(z0))) 25.84/8.85 sqr(s(z0)) -> s(+(sqr(z0), double(z0))) 25.84/8.85 double(0) -> 0 25.84/8.85 double(s(z0)) -> s(s(double(z0))) 25.84/8.85 +(z0, 0) -> z0 25.84/8.85 +(z0, s(z1)) -> s(+(z0, z1)) 25.84/8.85 Tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 S tuples: 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 K tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 Defined Rule Symbols: sqr_1, double_1, +_2 25.84/8.85 25.84/8.85 Defined Pair Symbols: SQR_1, DOUBLE_1, +'_2 25.84/8.85 25.84/8.85 Compound Symbols: c1_3, c2_3, c4_1, c6_1 25.84/8.85 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2))) 25.84/8.85 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 We considered the (Usable) Rules: 25.84/8.85 double(0) -> 0 25.84/8.85 double(s(z0)) -> s(s(double(z0))) 25.84/8.85 And the Tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 The order we found is given by the following interpretation: 25.84/8.85 25.84/8.85 Polynomial interpretation : 25.84/8.85 25.84/8.85 POL(+(x_1, x_2)) = [2] + [2]x_2 25.84/8.85 POL(+'(x_1, x_2)) = x_2 25.84/8.85 POL(0) = 0 25.84/8.85 POL(DOUBLE(x_1)) = 0 25.84/8.85 POL(SQR(x_1)) = x_1^2 25.84/8.85 POL(c1(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.84/8.85 POL(c2(x_1, x_2, x_3)) = x_1 + x_2 + x_3 25.84/8.85 POL(c4(x_1)) = x_1 25.84/8.85 POL(c6(x_1)) = x_1 25.84/8.85 POL(double(x_1)) = [2]x_1 25.84/8.85 POL(s(x_1)) = [1] + x_1 25.84/8.85 POL(sqr(x_1)) = [2] + [2]x_1^2 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (12) 25.84/8.85 Obligation: 25.84/8.85 Complexity Dependency Tuples Problem 25.84/8.85 25.84/8.85 Rules: 25.84/8.85 sqr(0) -> 0 25.84/8.85 sqr(s(z0)) -> +(sqr(z0), s(double(z0))) 25.84/8.85 sqr(s(z0)) -> s(+(sqr(z0), double(z0))) 25.84/8.85 double(0) -> 0 25.84/8.85 double(s(z0)) -> s(s(double(z0))) 25.84/8.85 +(z0, 0) -> z0 25.84/8.85 +(z0, s(z1)) -> s(+(z0, z1)) 25.84/8.85 Tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 S tuples:none 25.84/8.85 K tuples: 25.84/8.85 SQR(s(z0)) -> c1(+'(sqr(z0), s(double(z0))), SQR(z0), DOUBLE(z0)) 25.84/8.85 SQR(s(z0)) -> c2(+'(sqr(z0), double(z0)), SQR(z0), DOUBLE(z0)) 25.84/8.85 DOUBLE(s(z0)) -> c4(DOUBLE(z0)) 25.84/8.85 +'(z0, s(z1)) -> c6(+'(z0, z1)) 25.84/8.85 Defined Rule Symbols: sqr_1, double_1, +_2 25.84/8.85 25.84/8.85 Defined Pair Symbols: SQR_1, DOUBLE_1, +'_2 25.84/8.85 25.84/8.85 Compound Symbols: c1_3, c2_3, c4_1, c6_1 25.84/8.85 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 25.84/8.85 The set S is empty 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (14) 25.84/8.85 BOUNDS(1, 1) 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (15) RenamingProof (BOTH BOUNDS(ID, ID)) 25.84/8.85 Renamed function symbols to avoid clashes with predefined symbol. 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (16) 25.84/8.85 Obligation: 25.84/8.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 25.84/8.85 25.84/8.85 25.84/8.85 The TRS R consists of the following rules: 25.84/8.85 25.84/8.85 sqr(0') -> 0' 25.84/8.85 sqr(s(x)) -> +'(sqr(x), s(double(x))) 25.84/8.85 double(0') -> 0' 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +'(x, 0') -> x 25.84/8.85 +'(x, s(y)) -> s(+'(x, y)) 25.84/8.85 sqr(s(x)) -> s(+'(sqr(x), double(x))) 25.84/8.85 25.84/8.85 S is empty. 25.84/8.85 Rewrite Strategy: FULL 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 25.84/8.85 Infered types. 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (18) 25.84/8.85 Obligation: 25.84/8.85 TRS: 25.84/8.85 Rules: 25.84/8.85 sqr(0') -> 0' 25.84/8.85 sqr(s(x)) -> +'(sqr(x), s(double(x))) 25.84/8.85 double(0') -> 0' 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +'(x, 0') -> x 25.84/8.85 +'(x, s(y)) -> s(+'(x, y)) 25.84/8.85 sqr(s(x)) -> s(+'(sqr(x), double(x))) 25.84/8.85 25.84/8.85 Types: 25.84/8.85 sqr :: 0':s -> 0':s 25.84/8.85 0' :: 0':s 25.84/8.85 s :: 0':s -> 0':s 25.84/8.85 +' :: 0':s -> 0':s -> 0':s 25.84/8.85 double :: 0':s -> 0':s 25.84/8.85 hole_0':s1_0 :: 0':s 25.84/8.85 gen_0':s2_0 :: Nat -> 0':s 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (19) OrderProof (LOWER BOUND(ID)) 25.84/8.85 Heuristically decided to analyse the following defined symbols: 25.84/8.85 sqr, +', double 25.84/8.85 25.84/8.85 They will be analysed ascendingly in the following order: 25.84/8.85 +' < sqr 25.84/8.85 double < sqr 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (20) 25.84/8.85 Obligation: 25.84/8.85 TRS: 25.84/8.85 Rules: 25.84/8.85 sqr(0') -> 0' 25.84/8.85 sqr(s(x)) -> +'(sqr(x), s(double(x))) 25.84/8.85 double(0') -> 0' 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +'(x, 0') -> x 25.84/8.85 +'(x, s(y)) -> s(+'(x, y)) 25.84/8.85 sqr(s(x)) -> s(+'(sqr(x), double(x))) 25.84/8.85 25.84/8.85 Types: 25.84/8.85 sqr :: 0':s -> 0':s 25.84/8.85 0' :: 0':s 25.84/8.85 s :: 0':s -> 0':s 25.84/8.85 +' :: 0':s -> 0':s -> 0':s 25.84/8.85 double :: 0':s -> 0':s 25.84/8.85 hole_0':s1_0 :: 0':s 25.84/8.85 gen_0':s2_0 :: Nat -> 0':s 25.84/8.85 25.84/8.85 25.84/8.85 Generator Equations: 25.84/8.85 gen_0':s2_0(0) <=> 0' 25.84/8.85 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 25.84/8.85 25.84/8.85 25.84/8.85 The following defined symbols remain to be analysed: 25.84/8.85 +', sqr, double 25.84/8.85 25.84/8.85 They will be analysed ascendingly in the following order: 25.84/8.85 +' < sqr 25.84/8.85 double < sqr 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (21) RewriteLemmaProof (LOWER BOUND(ID)) 25.84/8.85 Proved the following rewrite lemma: 25.84/8.85 +'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 25.84/8.85 25.84/8.85 Induction Base: 25.84/8.85 +'(gen_0':s2_0(a), gen_0':s2_0(0)) ->_R^Omega(1) 25.84/8.85 gen_0':s2_0(a) 25.84/8.85 25.84/8.85 Induction Step: 25.84/8.85 +'(gen_0':s2_0(a), gen_0':s2_0(+(n4_0, 1))) ->_R^Omega(1) 25.84/8.85 s(+'(gen_0':s2_0(a), gen_0':s2_0(n4_0))) ->_IH 25.84/8.85 s(gen_0':s2_0(+(a, c5_0))) 25.84/8.85 25.84/8.85 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (22) 25.84/8.85 Complex Obligation (BEST) 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (23) 25.84/8.85 Obligation: 25.84/8.85 Proved the lower bound n^1 for the following obligation: 25.84/8.85 25.84/8.85 TRS: 25.84/8.85 Rules: 25.84/8.85 sqr(0') -> 0' 25.84/8.85 sqr(s(x)) -> +'(sqr(x), s(double(x))) 25.84/8.85 double(0') -> 0' 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +'(x, 0') -> x 25.84/8.85 +'(x, s(y)) -> s(+'(x, y)) 25.84/8.85 sqr(s(x)) -> s(+'(sqr(x), double(x))) 25.84/8.85 25.84/8.85 Types: 25.84/8.85 sqr :: 0':s -> 0':s 25.84/8.85 0' :: 0':s 25.84/8.85 s :: 0':s -> 0':s 25.84/8.85 +' :: 0':s -> 0':s -> 0':s 25.84/8.85 double :: 0':s -> 0':s 25.84/8.85 hole_0':s1_0 :: 0':s 25.84/8.85 gen_0':s2_0 :: Nat -> 0':s 25.84/8.85 25.84/8.85 25.84/8.85 Generator Equations: 25.84/8.85 gen_0':s2_0(0) <=> 0' 25.84/8.85 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 25.84/8.85 25.84/8.85 25.84/8.85 The following defined symbols remain to be analysed: 25.84/8.85 +', sqr, double 25.84/8.85 25.84/8.85 They will be analysed ascendingly in the following order: 25.84/8.85 +' < sqr 25.84/8.85 double < sqr 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (24) LowerBoundPropagationProof (FINISHED) 25.84/8.85 Propagated lower bound. 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (25) 25.84/8.85 BOUNDS(n^1, INF) 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (26) 25.84/8.85 Obligation: 25.84/8.85 TRS: 25.84/8.85 Rules: 25.84/8.85 sqr(0') -> 0' 25.84/8.85 sqr(s(x)) -> +'(sqr(x), s(double(x))) 25.84/8.85 double(0') -> 0' 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +'(x, 0') -> x 25.84/8.85 +'(x, s(y)) -> s(+'(x, y)) 25.84/8.85 sqr(s(x)) -> s(+'(sqr(x), double(x))) 25.84/8.85 25.84/8.85 Types: 25.84/8.85 sqr :: 0':s -> 0':s 25.84/8.85 0' :: 0':s 25.84/8.85 s :: 0':s -> 0':s 25.84/8.85 +' :: 0':s -> 0':s -> 0':s 25.84/8.85 double :: 0':s -> 0':s 25.84/8.85 hole_0':s1_0 :: 0':s 25.84/8.85 gen_0':s2_0 :: Nat -> 0':s 25.84/8.85 25.84/8.85 25.84/8.85 Lemmas: 25.84/8.85 +'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 25.84/8.85 25.84/8.85 25.84/8.85 Generator Equations: 25.84/8.85 gen_0':s2_0(0) <=> 0' 25.84/8.85 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 25.84/8.85 25.84/8.85 25.84/8.85 The following defined symbols remain to be analysed: 25.84/8.85 double, sqr 25.84/8.85 25.84/8.85 They will be analysed ascendingly in the following order: 25.84/8.85 double < sqr 25.84/8.85 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (27) RewriteLemmaProof (LOWER BOUND(ID)) 25.84/8.85 Proved the following rewrite lemma: 25.84/8.85 double(gen_0':s2_0(n457_0)) -> gen_0':s2_0(*(2, n457_0)), rt in Omega(1 + n457_0) 25.84/8.85 25.84/8.85 Induction Base: 25.84/8.85 double(gen_0':s2_0(0)) ->_R^Omega(1) 25.84/8.85 0' 25.84/8.85 25.84/8.85 Induction Step: 25.84/8.85 double(gen_0':s2_0(+(n457_0, 1))) ->_R^Omega(1) 25.84/8.85 s(s(double(gen_0':s2_0(n457_0)))) ->_IH 25.84/8.85 s(s(gen_0':s2_0(*(2, c458_0)))) 25.84/8.85 25.84/8.85 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (28) 25.84/8.85 Obligation: 25.84/8.85 TRS: 25.84/8.85 Rules: 25.84/8.85 sqr(0') -> 0' 25.84/8.85 sqr(s(x)) -> +'(sqr(x), s(double(x))) 25.84/8.85 double(0') -> 0' 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +'(x, 0') -> x 25.84/8.85 +'(x, s(y)) -> s(+'(x, y)) 25.84/8.85 sqr(s(x)) -> s(+'(sqr(x), double(x))) 25.84/8.85 25.84/8.85 Types: 25.84/8.85 sqr :: 0':s -> 0':s 25.84/8.85 0' :: 0':s 25.84/8.85 s :: 0':s -> 0':s 25.84/8.85 +' :: 0':s -> 0':s -> 0':s 25.84/8.85 double :: 0':s -> 0':s 25.84/8.85 hole_0':s1_0 :: 0':s 25.84/8.85 gen_0':s2_0 :: Nat -> 0':s 25.84/8.85 25.84/8.85 25.84/8.85 Lemmas: 25.84/8.85 +'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 25.84/8.85 double(gen_0':s2_0(n457_0)) -> gen_0':s2_0(*(2, n457_0)), rt in Omega(1 + n457_0) 25.84/8.85 25.84/8.85 25.84/8.85 Generator Equations: 25.84/8.85 gen_0':s2_0(0) <=> 0' 25.84/8.85 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 25.84/8.85 25.84/8.85 25.84/8.85 The following defined symbols remain to be analysed: 25.84/8.85 sqr 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (29) RewriteLemmaProof (LOWER BOUND(ID)) 25.84/8.85 Proved the following rewrite lemma: 25.84/8.85 sqr(gen_0':s2_0(n693_0)) -> gen_0':s2_0(*(n693_0, n693_0)), rt in Omega(1 + n693_0 + n693_0^2) 25.84/8.85 25.84/8.85 Induction Base: 25.84/8.85 sqr(gen_0':s2_0(0)) ->_R^Omega(1) 25.84/8.85 0' 25.84/8.85 25.84/8.85 Induction Step: 25.84/8.85 sqr(gen_0':s2_0(+(n693_0, 1))) ->_R^Omega(1) 25.84/8.85 +'(sqr(gen_0':s2_0(n693_0)), s(double(gen_0':s2_0(n693_0)))) ->_IH 25.84/8.85 +'(gen_0':s2_0(*(c694_0, c694_0)), s(double(gen_0':s2_0(n693_0)))) ->_L^Omega(1 + n693_0) 25.84/8.85 +'(gen_0':s2_0(*(n693_0, n693_0)), s(gen_0':s2_0(*(2, n693_0)))) ->_L^Omega(2 + 2*n693_0) 25.84/8.85 gen_0':s2_0(+(+(*(2, n693_0), 1), *(n693_0, n693_0))) 25.84/8.85 25.84/8.85 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (30) 25.84/8.85 Obligation: 25.84/8.85 Proved the lower bound n^2 for the following obligation: 25.84/8.85 25.84/8.85 TRS: 25.84/8.85 Rules: 25.84/8.85 sqr(0') -> 0' 25.84/8.85 sqr(s(x)) -> +'(sqr(x), s(double(x))) 25.84/8.85 double(0') -> 0' 25.84/8.85 double(s(x)) -> s(s(double(x))) 25.84/8.85 +'(x, 0') -> x 25.84/8.85 +'(x, s(y)) -> s(+'(x, y)) 25.84/8.85 sqr(s(x)) -> s(+'(sqr(x), double(x))) 25.84/8.85 25.84/8.85 Types: 25.84/8.85 sqr :: 0':s -> 0':s 25.84/8.85 0' :: 0':s 25.84/8.85 s :: 0':s -> 0':s 25.84/8.85 +' :: 0':s -> 0':s -> 0':s 25.84/8.85 double :: 0':s -> 0':s 25.84/8.85 hole_0':s1_0 :: 0':s 25.84/8.85 gen_0':s2_0 :: Nat -> 0':s 25.84/8.85 25.84/8.85 25.84/8.85 Lemmas: 25.84/8.85 +'(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 25.84/8.85 double(gen_0':s2_0(n457_0)) -> gen_0':s2_0(*(2, n457_0)), rt in Omega(1 + n457_0) 25.84/8.85 25.84/8.85 25.84/8.85 Generator Equations: 25.84/8.85 gen_0':s2_0(0) <=> 0' 25.84/8.85 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 25.84/8.85 25.84/8.85 25.84/8.85 The following defined symbols remain to be analysed: 25.84/8.85 sqr 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (31) LowerBoundPropagationProof (FINISHED) 25.84/8.85 Propagated lower bound. 25.84/8.85 ---------------------------------------- 25.84/8.85 25.84/8.85 (32) 25.84/8.85 BOUNDS(n^2, INF) 25.92/8.89 EOF