746.47/291.64 WORST_CASE(Omega(n^3), ?) 746.47/291.65 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 746.47/291.65 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 746.47/291.65 746.47/291.65 746.47/291.65 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 746.47/291.65 746.47/291.65 (0) CpxTRS 746.47/291.65 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 746.47/291.65 (2) CpxTRS 746.47/291.65 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 746.47/291.65 (4) CpxTRS 746.47/291.65 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 746.47/291.65 (6) typed CpxTrs 746.47/291.65 (7) OrderProof [LOWER BOUND(ID), 0 ms] 746.47/291.65 (8) typed CpxTrs 746.47/291.65 (9) RewriteLemmaProof [LOWER BOUND(ID), 321 ms] 746.47/291.65 (10) BEST 746.47/291.65 (11) proven lower bound 746.47/291.65 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 746.47/291.65 (13) BOUNDS(n^1, INF) 746.47/291.65 (14) typed CpxTrs 746.47/291.65 (15) RewriteLemmaProof [LOWER BOUND(ID), 113 ms] 746.47/291.65 (16) BEST 746.47/291.65 (17) proven lower bound 746.47/291.65 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 746.47/291.65 (19) BOUNDS(n^3, INF) 746.47/291.65 (20) typed CpxTrs 746.47/291.65 (21) RewriteLemmaProof [LOWER BOUND(ID), 610 ms] 746.47/291.65 (22) BOUNDS(1, INF) 746.47/291.65 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (0) 746.47/291.65 Obligation: 746.47/291.65 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 746.47/291.65 746.47/291.65 746.47/291.65 The TRS R consists of the following rules: 746.47/291.65 746.47/291.65 power(x', Cons(x, xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(x, xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(x, xs)) -> Cons(Cons(Nil, Nil), add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil, Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 S is empty. 746.47/291.65 Rewrite Strategy: INNERMOST 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 746.47/291.65 Renamed function symbols to avoid clashes with predefined symbol. 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (2) 746.47/291.65 Obligation: 746.47/291.65 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 746.47/291.65 746.47/291.65 746.47/291.65 The TRS R consists of the following rules: 746.47/291.65 746.47/291.65 power(x', Cons(x, xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(x, xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(x, xs)) -> Cons(Cons(Nil, Nil), add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil, Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 S is empty. 746.47/291.65 Rewrite Strategy: INNERMOST 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (3) SlicingProof (LOWER BOUND(ID)) 746.47/291.65 Sliced the following arguments: 746.47/291.65 Cons/0 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (4) 746.47/291.65 Obligation: 746.47/291.65 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF). 746.47/291.65 746.47/291.65 746.47/291.65 The TRS R consists of the following rules: 746.47/291.65 746.47/291.65 power(x', Cons(xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(xs)) -> Cons(add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 S is empty. 746.47/291.65 Rewrite Strategy: INNERMOST 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 746.47/291.65 Infered types. 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (6) 746.47/291.65 Obligation: 746.47/291.65 Innermost TRS: 746.47/291.65 Rules: 746.47/291.65 power(x', Cons(xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(xs)) -> Cons(add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 Types: 746.47/291.65 power :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Cons :: Cons:Nil -> Cons:Nil 746.47/291.65 mult :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 add0 :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Nil :: Cons:Nil 746.47/291.65 goal :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 hole_Cons:Nil1_1 :: Cons:Nil 746.47/291.65 gen_Cons:Nil2_1 :: Nat -> Cons:Nil 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (7) OrderProof (LOWER BOUND(ID)) 746.47/291.65 Heuristically decided to analyse the following defined symbols: 746.47/291.65 power, mult, add0 746.47/291.65 746.47/291.65 They will be analysed ascendingly in the following order: 746.47/291.65 mult < power 746.47/291.65 add0 < mult 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (8) 746.47/291.65 Obligation: 746.47/291.65 Innermost TRS: 746.47/291.65 Rules: 746.47/291.65 power(x', Cons(xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(xs)) -> Cons(add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 Types: 746.47/291.65 power :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Cons :: Cons:Nil -> Cons:Nil 746.47/291.65 mult :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 add0 :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Nil :: Cons:Nil 746.47/291.65 goal :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 hole_Cons:Nil1_1 :: Cons:Nil 746.47/291.65 gen_Cons:Nil2_1 :: Nat -> Cons:Nil 746.47/291.65 746.47/291.65 746.47/291.65 Generator Equations: 746.47/291.65 gen_Cons:Nil2_1(0) <=> Nil 746.47/291.65 gen_Cons:Nil2_1(+(x, 1)) <=> Cons(gen_Cons:Nil2_1(x)) 746.47/291.65 746.47/291.65 746.47/291.65 The following defined symbols remain to be analysed: 746.47/291.65 add0, power, mult 746.47/291.65 746.47/291.65 They will be analysed ascendingly in the following order: 746.47/291.65 mult < power 746.47/291.65 add0 < mult 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (9) RewriteLemmaProof (LOWER BOUND(ID)) 746.47/291.65 Proved the following rewrite lemma: 746.47/291.65 add0(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(n4_1)) -> gen_Cons:Nil2_1(+(n4_1, a)), rt in Omega(1 + n4_1) 746.47/291.65 746.47/291.65 Induction Base: 746.47/291.65 add0(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(0)) ->_R^Omega(1) 746.47/291.65 gen_Cons:Nil2_1(a) 746.47/291.65 746.47/291.65 Induction Step: 746.47/291.65 add0(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(+(n4_1, 1))) ->_R^Omega(1) 746.47/291.65 Cons(add0(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(n4_1))) ->_IH 746.47/291.65 Cons(gen_Cons:Nil2_1(+(a, c5_1))) 746.47/291.65 746.47/291.65 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (10) 746.47/291.65 Complex Obligation (BEST) 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (11) 746.47/291.65 Obligation: 746.47/291.65 Proved the lower bound n^1 for the following obligation: 746.47/291.65 746.47/291.65 Innermost TRS: 746.47/291.65 Rules: 746.47/291.65 power(x', Cons(xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(xs)) -> Cons(add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 Types: 746.47/291.65 power :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Cons :: Cons:Nil -> Cons:Nil 746.47/291.65 mult :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 add0 :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Nil :: Cons:Nil 746.47/291.65 goal :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 hole_Cons:Nil1_1 :: Cons:Nil 746.47/291.65 gen_Cons:Nil2_1 :: Nat -> Cons:Nil 746.47/291.65 746.47/291.65 746.47/291.65 Generator Equations: 746.47/291.65 gen_Cons:Nil2_1(0) <=> Nil 746.47/291.65 gen_Cons:Nil2_1(+(x, 1)) <=> Cons(gen_Cons:Nil2_1(x)) 746.47/291.65 746.47/291.65 746.47/291.65 The following defined symbols remain to be analysed: 746.47/291.65 add0, power, mult 746.47/291.65 746.47/291.65 They will be analysed ascendingly in the following order: 746.47/291.65 mult < power 746.47/291.65 add0 < mult 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (12) LowerBoundPropagationProof (FINISHED) 746.47/291.65 Propagated lower bound. 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (13) 746.47/291.65 BOUNDS(n^1, INF) 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (14) 746.47/291.65 Obligation: 746.47/291.65 Innermost TRS: 746.47/291.65 Rules: 746.47/291.65 power(x', Cons(xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(xs)) -> Cons(add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 Types: 746.47/291.65 power :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Cons :: Cons:Nil -> Cons:Nil 746.47/291.65 mult :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 add0 :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Nil :: Cons:Nil 746.47/291.65 goal :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 hole_Cons:Nil1_1 :: Cons:Nil 746.47/291.65 gen_Cons:Nil2_1 :: Nat -> Cons:Nil 746.47/291.65 746.47/291.65 746.47/291.65 Lemmas: 746.47/291.65 add0(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(n4_1)) -> gen_Cons:Nil2_1(+(n4_1, a)), rt in Omega(1 + n4_1) 746.47/291.65 746.47/291.65 746.47/291.65 Generator Equations: 746.47/291.65 gen_Cons:Nil2_1(0) <=> Nil 746.47/291.65 gen_Cons:Nil2_1(+(x, 1)) <=> Cons(gen_Cons:Nil2_1(x)) 746.47/291.65 746.47/291.65 746.47/291.65 The following defined symbols remain to be analysed: 746.47/291.65 mult, power 746.47/291.65 746.47/291.65 They will be analysed ascendingly in the following order: 746.47/291.65 mult < power 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (15) RewriteLemmaProof (LOWER BOUND(ID)) 746.47/291.65 Proved the following rewrite lemma: 746.47/291.65 mult(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(n504_1)) -> gen_Cons:Nil2_1(*(n504_1, a)), rt in Omega(1 + a*n504_1^2 + n504_1) 746.47/291.65 746.47/291.65 Induction Base: 746.47/291.65 mult(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(0)) ->_R^Omega(1) 746.47/291.65 Nil 746.47/291.65 746.47/291.65 Induction Step: 746.47/291.65 mult(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(+(n504_1, 1))) ->_R^Omega(1) 746.47/291.65 add0(gen_Cons:Nil2_1(a), mult(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(n504_1))) ->_IH 746.47/291.65 add0(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(*(c505_1, a))) ->_L^Omega(1 + a*n504_1) 746.47/291.65 gen_Cons:Nil2_1(+(*(n504_1, a), a)) 746.47/291.65 746.47/291.65 We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (16) 746.47/291.65 Complex Obligation (BEST) 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (17) 746.47/291.65 Obligation: 746.47/291.65 Proved the lower bound n^3 for the following obligation: 746.47/291.65 746.47/291.65 Innermost TRS: 746.47/291.65 Rules: 746.47/291.65 power(x', Cons(xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(xs)) -> Cons(add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 Types: 746.47/291.65 power :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Cons :: Cons:Nil -> Cons:Nil 746.47/291.65 mult :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 add0 :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Nil :: Cons:Nil 746.47/291.65 goal :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 hole_Cons:Nil1_1 :: Cons:Nil 746.47/291.65 gen_Cons:Nil2_1 :: Nat -> Cons:Nil 746.47/291.65 746.47/291.65 746.47/291.65 Lemmas: 746.47/291.65 add0(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(n4_1)) -> gen_Cons:Nil2_1(+(n4_1, a)), rt in Omega(1 + n4_1) 746.47/291.65 746.47/291.65 746.47/291.65 Generator Equations: 746.47/291.65 gen_Cons:Nil2_1(0) <=> Nil 746.47/291.65 gen_Cons:Nil2_1(+(x, 1)) <=> Cons(gen_Cons:Nil2_1(x)) 746.47/291.65 746.47/291.65 746.47/291.65 The following defined symbols remain to be analysed: 746.47/291.65 mult, power 746.47/291.65 746.47/291.65 They will be analysed ascendingly in the following order: 746.47/291.65 mult < power 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (18) LowerBoundPropagationProof (FINISHED) 746.47/291.65 Propagated lower bound. 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (19) 746.47/291.65 BOUNDS(n^3, INF) 746.47/291.65 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (20) 746.47/291.65 Obligation: 746.47/291.65 Innermost TRS: 746.47/291.65 Rules: 746.47/291.65 power(x', Cons(xs)) -> mult(x', power(x', xs)) 746.47/291.65 mult(x', Cons(xs)) -> add0(x', mult(x', xs)) 746.47/291.65 add0(x', Cons(xs)) -> Cons(add0(x', xs)) 746.47/291.65 power(x, Nil) -> Cons(Nil) 746.47/291.65 mult(x, Nil) -> Nil 746.47/291.65 add0(x, Nil) -> x 746.47/291.65 goal(x, y) -> power(x, y) 746.47/291.65 746.47/291.65 Types: 746.47/291.65 power :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Cons :: Cons:Nil -> Cons:Nil 746.47/291.65 mult :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 add0 :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 Nil :: Cons:Nil 746.47/291.65 goal :: Cons:Nil -> Cons:Nil -> Cons:Nil 746.47/291.65 hole_Cons:Nil1_1 :: Cons:Nil 746.47/291.65 gen_Cons:Nil2_1 :: Nat -> Cons:Nil 746.47/291.65 746.47/291.65 746.47/291.65 Lemmas: 746.47/291.65 add0(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(n4_1)) -> gen_Cons:Nil2_1(+(n4_1, a)), rt in Omega(1 + n4_1) 746.47/291.65 mult(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(n504_1)) -> gen_Cons:Nil2_1(*(n504_1, a)), rt in Omega(1 + a*n504_1^2 + n504_1) 746.47/291.65 746.47/291.65 746.47/291.65 Generator Equations: 746.47/291.65 gen_Cons:Nil2_1(0) <=> Nil 746.47/291.65 gen_Cons:Nil2_1(+(x, 1)) <=> Cons(gen_Cons:Nil2_1(x)) 746.47/291.65 746.47/291.65 746.47/291.65 The following defined symbols remain to be analysed: 746.47/291.65 power 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (21) RewriteLemmaProof (LOWER BOUND(ID)) 746.47/291.65 Proved the following rewrite lemma: 746.47/291.65 power(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(+(1, n1128_1))) -> *3_1, rt in Omega(n1128_1) 746.47/291.65 746.47/291.65 Induction Base: 746.47/291.65 power(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(+(1, 0))) 746.47/291.65 746.47/291.65 Induction Step: 746.47/291.65 power(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(+(1, +(n1128_1, 1)))) ->_R^Omega(1) 746.47/291.65 mult(gen_Cons:Nil2_1(a), power(gen_Cons:Nil2_1(a), gen_Cons:Nil2_1(+(1, n1128_1)))) ->_IH 746.47/291.65 mult(gen_Cons:Nil2_1(a), *3_1) 746.47/291.65 746.47/291.65 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 746.47/291.65 ---------------------------------------- 746.47/291.65 746.47/291.65 (22) 746.47/291.65 BOUNDS(1, INF) 746.47/291.70 EOF