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