20.92/7.46 WORST_CASE(Omega(n^3), O(n^3)) 20.92/7.48 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 20.92/7.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 20.92/7.48 20.92/7.48 20.92/7.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 20.92/7.48 20.92/7.48 (0) CpxTRS 20.92/7.48 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 20.92/7.48 (2) CdtProblem 20.92/7.48 (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] 20.92/7.48 (4) CdtProblem 20.92/7.48 (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 20.92/7.48 (6) CdtProblem 20.92/7.48 (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 39 ms] 20.92/7.48 (8) CdtProblem 20.92/7.48 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 150 ms] 20.92/7.48 (10) CdtProblem 20.92/7.48 (11) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 20.92/7.48 (12) BOUNDS(1, 1) 20.92/7.48 (13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 20.92/7.48 (14) CpxTRS 20.92/7.48 (15) SlicingProof [LOWER BOUND(ID), 0 ms] 20.92/7.48 (16) CpxTRS 20.92/7.48 (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 20.92/7.48 (18) typed CpxTrs 20.92/7.48 (19) OrderProof [LOWER BOUND(ID), 0 ms] 20.92/7.48 (20) typed CpxTrs 20.92/7.48 (21) RewriteLemmaProof [LOWER BOUND(ID), 290 ms] 20.92/7.48 (22) BEST 20.92/7.48 (23) proven lower bound 20.92/7.48 (24) LowerBoundPropagationProof [FINISHED, 0 ms] 20.92/7.48 (25) BOUNDS(n^1, INF) 20.92/7.48 (26) typed CpxTrs 20.92/7.48 (27) RewriteLemmaProof [LOWER BOUND(ID), 64 ms] 20.92/7.48 (28) proven lower bound 20.92/7.48 (29) LowerBoundPropagationProof [FINISHED, 0 ms] 20.92/7.48 (30) BOUNDS(n^3, INF) 20.92/7.48 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (0) 20.92/7.48 Obligation: 20.92/7.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3). 20.92/7.48 20.92/7.48 20.92/7.48 The TRS R consists of the following rules: 20.92/7.48 20.92/7.48 mul0(C(x, y), y') -> add0(mul0(y, y'), y') 20.92/7.48 mul0(Z, y) -> Z 20.92/7.48 add0(C(x, y), y') -> add0(y, C(S, y')) 20.92/7.48 add0(Z, y) -> y 20.92/7.48 second(C(x, y)) -> y 20.92/7.48 isZero(C(x, y)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(xs, ys) -> mul0(xs, ys) 20.92/7.48 20.92/7.48 S is empty. 20.92/7.48 Rewrite Strategy: INNERMOST 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 20.92/7.48 Converted Cpx (relative) TRS to CDT 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (2) 20.92/7.48 Obligation: 20.92/7.48 Complexity Dependency Tuples Problem 20.92/7.48 20.92/7.48 Rules: 20.92/7.48 mul0(C(z0, z1), z2) -> add0(mul0(z1, z2), z2) 20.92/7.48 mul0(Z, z0) -> Z 20.92/7.48 add0(C(z0, z1), z2) -> add0(z1, C(S, z2)) 20.92/7.48 add0(Z, z0) -> z0 20.92/7.48 second(C(z0, z1)) -> z1 20.92/7.48 isZero(C(z0, z1)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(z0, z1) -> mul0(z0, z1) 20.92/7.48 Tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 MUL0(Z, z0) -> c1 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 ADD0(Z, z0) -> c3 20.92/7.48 SECOND(C(z0, z1)) -> c4 20.92/7.48 ISZERO(C(z0, z1)) -> c5 20.92/7.48 ISZERO(Z) -> c6 20.92/7.48 GOAL(z0, z1) -> c7(MUL0(z0, z1)) 20.92/7.48 S tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 MUL0(Z, z0) -> c1 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 ADD0(Z, z0) -> c3 20.92/7.48 SECOND(C(z0, z1)) -> c4 20.92/7.48 ISZERO(C(z0, z1)) -> c5 20.92/7.48 ISZERO(Z) -> c6 20.92/7.48 GOAL(z0, z1) -> c7(MUL0(z0, z1)) 20.92/7.48 K tuples:none 20.92/7.48 Defined Rule Symbols: mul0_2, add0_2, second_1, isZero_1, goal_2 20.92/7.48 20.92/7.48 Defined Pair Symbols: MUL0_2, ADD0_2, SECOND_1, ISZERO_1, GOAL_2 20.92/7.48 20.92/7.48 Compound Symbols: c_2, c1, c2_1, c3, c4, c5, c6, c7_1 20.92/7.48 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (3) CdtLeafRemovalProof (ComplexityIfPolyImplication) 20.92/7.48 Removed 1 leading nodes: 20.92/7.48 GOAL(z0, z1) -> c7(MUL0(z0, z1)) 20.92/7.48 Removed 5 trailing nodes: 20.92/7.48 ADD0(Z, z0) -> c3 20.92/7.48 ISZERO(Z) -> c6 20.92/7.48 SECOND(C(z0, z1)) -> c4 20.92/7.48 MUL0(Z, z0) -> c1 20.92/7.48 ISZERO(C(z0, z1)) -> c5 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (4) 20.92/7.48 Obligation: 20.92/7.48 Complexity Dependency Tuples Problem 20.92/7.48 20.92/7.48 Rules: 20.92/7.48 mul0(C(z0, z1), z2) -> add0(mul0(z1, z2), z2) 20.92/7.48 mul0(Z, z0) -> Z 20.92/7.48 add0(C(z0, z1), z2) -> add0(z1, C(S, z2)) 20.92/7.48 add0(Z, z0) -> z0 20.92/7.48 second(C(z0, z1)) -> z1 20.92/7.48 isZero(C(z0, z1)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(z0, z1) -> mul0(z0, z1) 20.92/7.48 Tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 S tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 K tuples:none 20.92/7.48 Defined Rule Symbols: mul0_2, add0_2, second_1, isZero_1, goal_2 20.92/7.48 20.92/7.48 Defined Pair Symbols: MUL0_2, ADD0_2 20.92/7.48 20.92/7.48 Compound Symbols: c_2, c2_1 20.92/7.48 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 20.92/7.48 The following rules are not usable and were removed: 20.92/7.48 second(C(z0, z1)) -> z1 20.92/7.48 isZero(C(z0, z1)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(z0, z1) -> mul0(z0, z1) 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (6) 20.92/7.48 Obligation: 20.92/7.48 Complexity Dependency Tuples Problem 20.92/7.48 20.92/7.48 Rules: 20.92/7.48 mul0(C(z0, z1), z2) -> add0(mul0(z1, z2), z2) 20.92/7.48 mul0(Z, z0) -> Z 20.92/7.48 add0(C(z0, z1), z2) -> add0(z1, C(S, z2)) 20.92/7.48 add0(Z, z0) -> z0 20.92/7.48 Tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 S tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 K tuples:none 20.92/7.48 Defined Rule Symbols: mul0_2, add0_2 20.92/7.48 20.92/7.48 Defined Pair Symbols: MUL0_2, ADD0_2 20.92/7.48 20.92/7.48 Compound Symbols: c_2, c2_1 20.92/7.48 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 20.92/7.48 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 We considered the (Usable) Rules:none 20.92/7.48 And the Tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 The order we found is given by the following interpretation: 20.92/7.48 20.92/7.48 Polynomial interpretation : 20.92/7.48 20.92/7.48 POL(ADD0(x_1, x_2)) = [1] 20.92/7.48 POL(C(x_1, x_2)) = [2] + x_1 + x_2 20.92/7.48 POL(MUL0(x_1, x_2)) = [2]x_1 20.92/7.48 POL(S) = [3] 20.92/7.48 POL(Z) = [3] 20.92/7.48 POL(add0(x_1, x_2)) = [3] 20.92/7.48 POL(c(x_1, x_2)) = x_1 + x_2 20.92/7.48 POL(c2(x_1)) = x_1 20.92/7.48 POL(mul0(x_1, x_2)) = [3] + [3]x_2 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (8) 20.92/7.48 Obligation: 20.92/7.48 Complexity Dependency Tuples Problem 20.92/7.48 20.92/7.48 Rules: 20.92/7.48 mul0(C(z0, z1), z2) -> add0(mul0(z1, z2), z2) 20.92/7.48 mul0(Z, z0) -> Z 20.92/7.48 add0(C(z0, z1), z2) -> add0(z1, C(S, z2)) 20.92/7.48 add0(Z, z0) -> z0 20.92/7.48 Tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 S tuples: 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 K tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 Defined Rule Symbols: mul0_2, add0_2 20.92/7.48 20.92/7.48 Defined Pair Symbols: MUL0_2, ADD0_2 20.92/7.48 20.92/7.48 Compound Symbols: c_2, c2_1 20.92/7.48 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^3))) 20.92/7.48 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 We considered the (Usable) Rules: 20.92/7.48 mul0(Z, z0) -> Z 20.92/7.48 add0(Z, z0) -> z0 20.92/7.48 add0(C(z0, z1), z2) -> add0(z1, C(S, z2)) 20.92/7.48 mul0(C(z0, z1), z2) -> add0(mul0(z1, z2), z2) 20.92/7.48 And the Tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 The order we found is given by the following interpretation: 20.92/7.48 20.92/7.48 Polynomial interpretation : 20.92/7.48 20.92/7.48 POL(ADD0(x_1, x_2)) = x_1 20.92/7.48 POL(C(x_1, x_2)) = [1] + x_2 20.92/7.48 POL(MUL0(x_1, x_2)) = x_1^2*x_2 + x_1*x_2^2 20.92/7.48 POL(S) = 0 20.92/7.48 POL(Z) = 0 20.92/7.48 POL(add0(x_1, x_2)) = x_1 + x_2 20.92/7.48 POL(c(x_1, x_2)) = x_1 + x_2 20.92/7.48 POL(c2(x_1)) = x_1 20.92/7.48 POL(mul0(x_1, x_2)) = x_2 + x_1*x_2 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (10) 20.92/7.48 Obligation: 20.92/7.48 Complexity Dependency Tuples Problem 20.92/7.48 20.92/7.48 Rules: 20.92/7.48 mul0(C(z0, z1), z2) -> add0(mul0(z1, z2), z2) 20.92/7.48 mul0(Z, z0) -> Z 20.92/7.48 add0(C(z0, z1), z2) -> add0(z1, C(S, z2)) 20.92/7.48 add0(Z, z0) -> z0 20.92/7.48 Tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 S tuples:none 20.92/7.48 K tuples: 20.92/7.48 MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2)) 20.92/7.48 ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2))) 20.92/7.48 Defined Rule Symbols: mul0_2, add0_2 20.92/7.48 20.92/7.48 Defined Pair Symbols: MUL0_2, ADD0_2 20.92/7.48 20.92/7.48 Compound Symbols: c_2, c2_1 20.92/7.48 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (11) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 20.92/7.48 The set S is empty 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (12) 20.92/7.48 BOUNDS(1, 1) 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (13) RenamingProof (BOTH BOUNDS(ID, ID)) 20.92/7.48 Renamed function symbols to avoid clashes with predefined symbol. 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (14) 20.92/7.48 Obligation: 20.92/7.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 20.92/7.48 20.92/7.48 20.92/7.48 The TRS R consists of the following rules: 20.92/7.48 20.92/7.48 mul0(C(x, y), y') -> add0(mul0(y, y'), y') 20.92/7.48 mul0(Z, y) -> Z 20.92/7.48 add0(C(x, y), y') -> add0(y, C(S, y')) 20.92/7.48 add0(Z, y) -> y 20.92/7.48 second(C(x, y)) -> y 20.92/7.48 isZero(C(x, y)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(xs, ys) -> mul0(xs, ys) 20.92/7.48 20.92/7.48 S is empty. 20.92/7.48 Rewrite Strategy: INNERMOST 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (15) SlicingProof (LOWER BOUND(ID)) 20.92/7.48 Sliced the following arguments: 20.92/7.48 C/0 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (16) 20.92/7.48 Obligation: 20.92/7.48 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 20.92/7.48 20.92/7.48 20.92/7.48 The TRS R consists of the following rules: 20.92/7.48 20.92/7.48 mul0(C(y), y') -> add0(mul0(y, y'), y') 20.92/7.48 mul0(Z, y) -> Z 20.92/7.48 add0(C(y), y') -> add0(y, C(y')) 20.92/7.48 add0(Z, y) -> y 20.92/7.48 second(C(y)) -> y 20.92/7.48 isZero(C(y)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(xs, ys) -> mul0(xs, ys) 20.92/7.48 20.92/7.48 S is empty. 20.92/7.48 Rewrite Strategy: INNERMOST 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 20.92/7.48 Infered types. 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (18) 20.92/7.48 Obligation: 20.92/7.48 Innermost TRS: 20.92/7.48 Rules: 20.92/7.48 mul0(C(y), y') -> add0(mul0(y, y'), y') 20.92/7.48 mul0(Z, y) -> Z 20.92/7.48 add0(C(y), y') -> add0(y, C(y')) 20.92/7.48 add0(Z, y) -> y 20.92/7.48 second(C(y)) -> y 20.92/7.48 isZero(C(y)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(xs, ys) -> mul0(xs, ys) 20.92/7.48 20.92/7.48 Types: 20.92/7.48 mul0 :: C:Z -> C:Z -> C:Z 20.92/7.48 C :: C:Z -> C:Z 20.92/7.48 add0 :: C:Z -> C:Z -> C:Z 20.92/7.48 Z :: C:Z 20.92/7.48 second :: C:Z -> C:Z 20.92/7.48 isZero :: C:Z -> False:True 20.92/7.48 False :: False:True 20.92/7.48 True :: False:True 20.92/7.48 goal :: C:Z -> C:Z -> C:Z 20.92/7.48 hole_C:Z1_1 :: C:Z 20.92/7.48 hole_False:True2_1 :: False:True 20.92/7.48 gen_C:Z3_1 :: Nat -> C:Z 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (19) OrderProof (LOWER BOUND(ID)) 20.92/7.48 Heuristically decided to analyse the following defined symbols: 20.92/7.48 mul0, add0 20.92/7.48 20.92/7.48 They will be analysed ascendingly in the following order: 20.92/7.48 add0 < mul0 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (20) 20.92/7.48 Obligation: 20.92/7.48 Innermost TRS: 20.92/7.48 Rules: 20.92/7.48 mul0(C(y), y') -> add0(mul0(y, y'), y') 20.92/7.48 mul0(Z, y) -> Z 20.92/7.48 add0(C(y), y') -> add0(y, C(y')) 20.92/7.48 add0(Z, y) -> y 20.92/7.48 second(C(y)) -> y 20.92/7.48 isZero(C(y)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(xs, ys) -> mul0(xs, ys) 20.92/7.48 20.92/7.48 Types: 20.92/7.48 mul0 :: C:Z -> C:Z -> C:Z 20.92/7.48 C :: C:Z -> C:Z 20.92/7.48 add0 :: C:Z -> C:Z -> C:Z 20.92/7.48 Z :: C:Z 20.92/7.48 second :: C:Z -> C:Z 20.92/7.48 isZero :: C:Z -> False:True 20.92/7.48 False :: False:True 20.92/7.48 True :: False:True 20.92/7.48 goal :: C:Z -> C:Z -> C:Z 20.92/7.48 hole_C:Z1_1 :: C:Z 20.92/7.48 hole_False:True2_1 :: False:True 20.92/7.48 gen_C:Z3_1 :: Nat -> C:Z 20.92/7.48 20.92/7.48 20.92/7.48 Generator Equations: 20.92/7.48 gen_C:Z3_1(0) <=> Z 20.92/7.48 gen_C:Z3_1(+(x, 1)) <=> C(gen_C:Z3_1(x)) 20.92/7.48 20.92/7.48 20.92/7.48 The following defined symbols remain to be analysed: 20.92/7.48 add0, mul0 20.92/7.48 20.92/7.48 They will be analysed ascendingly in the following order: 20.92/7.48 add0 < mul0 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (21) RewriteLemmaProof (LOWER BOUND(ID)) 20.92/7.48 Proved the following rewrite lemma: 20.92/7.48 add0(gen_C:Z3_1(n5_1), gen_C:Z3_1(b)) -> gen_C:Z3_1(+(n5_1, b)), rt in Omega(1 + n5_1) 20.92/7.48 20.92/7.48 Induction Base: 20.92/7.48 add0(gen_C:Z3_1(0), gen_C:Z3_1(b)) ->_R^Omega(1) 20.92/7.48 gen_C:Z3_1(b) 20.92/7.48 20.92/7.48 Induction Step: 20.92/7.48 add0(gen_C:Z3_1(+(n5_1, 1)), gen_C:Z3_1(b)) ->_R^Omega(1) 20.92/7.48 add0(gen_C:Z3_1(n5_1), C(gen_C:Z3_1(b))) ->_IH 20.92/7.48 gen_C:Z3_1(+(+(b, 1), c6_1)) 20.92/7.48 20.92/7.48 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (22) 20.92/7.48 Complex Obligation (BEST) 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (23) 20.92/7.48 Obligation: 20.92/7.48 Proved the lower bound n^1 for the following obligation: 20.92/7.48 20.92/7.48 Innermost TRS: 20.92/7.48 Rules: 20.92/7.48 mul0(C(y), y') -> add0(mul0(y, y'), y') 20.92/7.48 mul0(Z, y) -> Z 20.92/7.48 add0(C(y), y') -> add0(y, C(y')) 20.92/7.48 add0(Z, y) -> y 20.92/7.48 second(C(y)) -> y 20.92/7.48 isZero(C(y)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(xs, ys) -> mul0(xs, ys) 20.92/7.48 20.92/7.48 Types: 20.92/7.48 mul0 :: C:Z -> C:Z -> C:Z 20.92/7.48 C :: C:Z -> C:Z 20.92/7.48 add0 :: C:Z -> C:Z -> C:Z 20.92/7.48 Z :: C:Z 20.92/7.48 second :: C:Z -> C:Z 20.92/7.48 isZero :: C:Z -> False:True 20.92/7.48 False :: False:True 20.92/7.48 True :: False:True 20.92/7.48 goal :: C:Z -> C:Z -> C:Z 20.92/7.48 hole_C:Z1_1 :: C:Z 20.92/7.48 hole_False:True2_1 :: False:True 20.92/7.48 gen_C:Z3_1 :: Nat -> C:Z 20.92/7.48 20.92/7.48 20.92/7.48 Generator Equations: 20.92/7.48 gen_C:Z3_1(0) <=> Z 20.92/7.48 gen_C:Z3_1(+(x, 1)) <=> C(gen_C:Z3_1(x)) 20.92/7.48 20.92/7.48 20.92/7.48 The following defined symbols remain to be analysed: 20.92/7.48 add0, mul0 20.92/7.48 20.92/7.48 They will be analysed ascendingly in the following order: 20.92/7.48 add0 < mul0 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (24) LowerBoundPropagationProof (FINISHED) 20.92/7.48 Propagated lower bound. 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (25) 20.92/7.48 BOUNDS(n^1, INF) 20.92/7.48 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (26) 20.92/7.48 Obligation: 20.92/7.48 Innermost TRS: 20.92/7.48 Rules: 20.92/7.48 mul0(C(y), y') -> add0(mul0(y, y'), y') 20.92/7.48 mul0(Z, y) -> Z 20.92/7.48 add0(C(y), y') -> add0(y, C(y')) 20.92/7.48 add0(Z, y) -> y 20.92/7.48 second(C(y)) -> y 20.92/7.48 isZero(C(y)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(xs, ys) -> mul0(xs, ys) 20.92/7.48 20.92/7.48 Types: 20.92/7.48 mul0 :: C:Z -> C:Z -> C:Z 20.92/7.48 C :: C:Z -> C:Z 20.92/7.48 add0 :: C:Z -> C:Z -> C:Z 20.92/7.48 Z :: C:Z 20.92/7.48 second :: C:Z -> C:Z 20.92/7.48 isZero :: C:Z -> False:True 20.92/7.48 False :: False:True 20.92/7.48 True :: False:True 20.92/7.48 goal :: C:Z -> C:Z -> C:Z 20.92/7.48 hole_C:Z1_1 :: C:Z 20.92/7.48 hole_False:True2_1 :: False:True 20.92/7.48 gen_C:Z3_1 :: Nat -> C:Z 20.92/7.48 20.92/7.48 20.92/7.48 Lemmas: 20.92/7.48 add0(gen_C:Z3_1(n5_1), gen_C:Z3_1(b)) -> gen_C:Z3_1(+(n5_1, b)), rt in Omega(1 + n5_1) 20.92/7.48 20.92/7.48 20.92/7.48 Generator Equations: 20.92/7.48 gen_C:Z3_1(0) <=> Z 20.92/7.48 gen_C:Z3_1(+(x, 1)) <=> C(gen_C:Z3_1(x)) 20.92/7.48 20.92/7.48 20.92/7.48 The following defined symbols remain to be analysed: 20.92/7.48 mul0 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (27) RewriteLemmaProof (LOWER BOUND(ID)) 20.92/7.48 Proved the following rewrite lemma: 20.92/7.48 mul0(gen_C:Z3_1(n523_1), gen_C:Z3_1(b)) -> gen_C:Z3_1(*(n523_1, b)), rt in Omega(1 + b*n523_1^2 + n523_1) 20.92/7.48 20.92/7.48 Induction Base: 20.92/7.48 mul0(gen_C:Z3_1(0), gen_C:Z3_1(b)) ->_R^Omega(1) 20.92/7.48 Z 20.92/7.48 20.92/7.48 Induction Step: 20.92/7.48 mul0(gen_C:Z3_1(+(n523_1, 1)), gen_C:Z3_1(b)) ->_R^Omega(1) 20.92/7.48 add0(mul0(gen_C:Z3_1(n523_1), gen_C:Z3_1(b)), gen_C:Z3_1(b)) ->_IH 20.92/7.48 add0(gen_C:Z3_1(*(c524_1, b)), gen_C:Z3_1(b)) ->_L^Omega(1 + b*n523_1) 20.92/7.48 gen_C:Z3_1(+(*(n523_1, b), b)) 20.92/7.48 20.92/7.48 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (28) 20.92/7.48 Obligation: 20.92/7.48 Proved the lower bound n^3 for the following obligation: 20.92/7.48 20.92/7.48 Innermost TRS: 20.92/7.48 Rules: 20.92/7.48 mul0(C(y), y') -> add0(mul0(y, y'), y') 20.92/7.48 mul0(Z, y) -> Z 20.92/7.48 add0(C(y), y') -> add0(y, C(y')) 20.92/7.48 add0(Z, y) -> y 20.92/7.48 second(C(y)) -> y 20.92/7.48 isZero(C(y)) -> False 20.92/7.48 isZero(Z) -> True 20.92/7.48 goal(xs, ys) -> mul0(xs, ys) 20.92/7.48 20.92/7.48 Types: 20.92/7.48 mul0 :: C:Z -> C:Z -> C:Z 20.92/7.48 C :: C:Z -> C:Z 20.92/7.48 add0 :: C:Z -> C:Z -> C:Z 20.92/7.48 Z :: C:Z 20.92/7.48 second :: C:Z -> C:Z 20.92/7.48 isZero :: C:Z -> False:True 20.92/7.48 False :: False:True 20.92/7.48 True :: False:True 20.92/7.48 goal :: C:Z -> C:Z -> C:Z 20.92/7.48 hole_C:Z1_1 :: C:Z 20.92/7.48 hole_False:True2_1 :: False:True 20.92/7.48 gen_C:Z3_1 :: Nat -> C:Z 20.92/7.48 20.92/7.48 20.92/7.48 Lemmas: 20.92/7.48 add0(gen_C:Z3_1(n5_1), gen_C:Z3_1(b)) -> gen_C:Z3_1(+(n5_1, b)), rt in Omega(1 + n5_1) 20.92/7.48 20.92/7.48 20.92/7.48 Generator Equations: 20.92/7.48 gen_C:Z3_1(0) <=> Z 20.92/7.48 gen_C:Z3_1(+(x, 1)) <=> C(gen_C:Z3_1(x)) 20.92/7.48 20.92/7.48 20.92/7.48 The following defined symbols remain to be analysed: 20.92/7.48 mul0 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (29) LowerBoundPropagationProof (FINISHED) 20.92/7.48 Propagated lower bound. 20.92/7.48 ---------------------------------------- 20.92/7.48 20.92/7.48 (30) 20.92/7.48 BOUNDS(n^3, INF) 20.92/7.52 EOF