734.15/291.52 WORST_CASE(Omega(n^2), ?) 734.15/291.54 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 734.15/291.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 734.15/291.54 734.15/291.54 734.15/291.54 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^2, INF). 734.15/291.54 734.15/291.54 (0) CpxRelTRS 734.15/291.54 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 155 ms] 734.15/291.54 (2) CpxRelTRS 734.15/291.54 (3) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 734.15/291.54 (4) CpxRelTRS 734.15/291.54 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 734.15/291.54 (6) typed CpxTrs 734.15/291.54 (7) OrderProof [LOWER BOUND(ID), 0 ms] 734.15/291.54 (8) typed CpxTrs 734.15/291.54 (9) RewriteLemmaProof [LOWER BOUND(ID), 285 ms] 734.15/291.54 (10) BEST 734.15/291.54 (11) proven lower bound 734.15/291.54 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 734.15/291.54 (13) BOUNDS(n^1, INF) 734.15/291.54 (14) typed CpxTrs 734.15/291.54 (15) RewriteLemmaProof [LOWER BOUND(ID), 40 ms] 734.15/291.54 (16) BEST 734.15/291.54 (17) proven lower bound 734.15/291.54 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 734.15/291.54 (19) BOUNDS(n^2, INF) 734.15/291.54 (20) typed CpxTrs 734.15/291.54 (21) RewriteLemmaProof [LOWER BOUND(ID), 54 ms] 734.15/291.54 (22) BOUNDS(1, INF) 734.15/291.54 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (0) 734.15/291.54 Obligation: 734.15/291.54 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^2, INF). 734.15/291.54 734.15/291.54 734.15/291.54 The TRS R consists of the following rules: 734.15/291.54 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +(S(0), add0(x', x)) 734.15/291.54 power(x, 0) -> S(0) 734.15/291.54 mult(x, 0) -> 0 734.15/291.54 add0(x, 0) -> x 734.15/291.54 734.15/291.54 The (relative) TRS S consists of the following rules: 734.15/291.54 734.15/291.54 +(x, S(0)) -> S(x) 734.15/291.54 +(S(0), y) -> S(y) 734.15/291.54 734.15/291.54 Rewrite Strategy: INNERMOST 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 734.15/291.54 proved termination of relative rules 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (2) 734.15/291.54 Obligation: 734.15/291.54 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^2, INF). 734.15/291.54 734.15/291.54 734.15/291.54 The TRS R consists of the following rules: 734.15/291.54 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +(S(0), add0(x', x)) 734.15/291.54 power(x, 0) -> S(0) 734.15/291.54 mult(x, 0) -> 0 734.15/291.54 add0(x, 0) -> x 734.15/291.54 734.15/291.54 The (relative) TRS S consists of the following rules: 734.15/291.54 734.15/291.54 +(x, S(0)) -> S(x) 734.15/291.54 +(S(0), y) -> S(y) 734.15/291.54 734.15/291.54 Rewrite Strategy: INNERMOST 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (3) RenamingProof (BOTH BOUNDS(ID, ID)) 734.15/291.54 Renamed function symbols to avoid clashes with predefined symbol. 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (4) 734.15/291.54 Obligation: 734.15/291.54 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^2, INF). 734.15/291.54 734.15/291.54 734.15/291.54 The TRS R consists of the following rules: 734.15/291.54 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +'(S(0'), add0(x', x)) 734.15/291.54 power(x, 0') -> S(0') 734.15/291.54 mult(x, 0') -> 0' 734.15/291.54 add0(x, 0') -> x 734.15/291.54 734.15/291.54 The (relative) TRS S consists of the following rules: 734.15/291.54 734.15/291.54 +'(x, S(0')) -> S(x) 734.15/291.54 +'(S(0'), y) -> S(y) 734.15/291.54 734.15/291.54 Rewrite Strategy: INNERMOST 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 734.15/291.54 Infered types. 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (6) 734.15/291.54 Obligation: 734.15/291.54 Innermost TRS: 734.15/291.54 Rules: 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +'(S(0'), add0(x', x)) 734.15/291.54 power(x, 0') -> S(0') 734.15/291.54 mult(x, 0') -> 0' 734.15/291.54 add0(x, 0') -> x 734.15/291.54 +'(x, S(0')) -> S(x) 734.15/291.54 +'(S(0'), y) -> S(y) 734.15/291.54 734.15/291.54 Types: 734.15/291.54 power :: S:0' -> S:0' -> S:0' 734.15/291.54 S :: S:0' -> S:0' 734.15/291.54 mult :: S:0' -> S:0' -> S:0' 734.15/291.54 add0 :: S:0' -> S:0' -> S:0' 734.15/291.54 +' :: S:0' -> S:0' -> S:0' 734.15/291.54 0' :: S:0' 734.15/291.54 hole_S:0'1_1 :: S:0' 734.15/291.54 gen_S:0'2_1 :: Nat -> S:0' 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (7) OrderProof (LOWER BOUND(ID)) 734.15/291.54 Heuristically decided to analyse the following defined symbols: 734.15/291.54 power, mult, add0 734.15/291.54 734.15/291.54 They will be analysed ascendingly in the following order: 734.15/291.54 mult < power 734.15/291.54 add0 < mult 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (8) 734.15/291.54 Obligation: 734.15/291.54 Innermost TRS: 734.15/291.54 Rules: 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +'(S(0'), add0(x', x)) 734.15/291.54 power(x, 0') -> S(0') 734.15/291.54 mult(x, 0') -> 0' 734.15/291.54 add0(x, 0') -> x 734.15/291.54 +'(x, S(0')) -> S(x) 734.15/291.54 +'(S(0'), y) -> S(y) 734.15/291.54 734.15/291.54 Types: 734.15/291.54 power :: S:0' -> S:0' -> S:0' 734.15/291.54 S :: S:0' -> S:0' 734.15/291.54 mult :: S:0' -> S:0' -> S:0' 734.15/291.54 add0 :: S:0' -> S:0' -> S:0' 734.15/291.54 +' :: S:0' -> S:0' -> S:0' 734.15/291.54 0' :: S:0' 734.15/291.54 hole_S:0'1_1 :: S:0' 734.15/291.54 gen_S:0'2_1 :: Nat -> S:0' 734.15/291.54 734.15/291.54 734.15/291.54 Generator Equations: 734.15/291.54 gen_S:0'2_1(0) <=> 0' 734.15/291.54 gen_S:0'2_1(+(x, 1)) <=> S(gen_S:0'2_1(x)) 734.15/291.54 734.15/291.54 734.15/291.54 The following defined symbols remain to be analysed: 734.15/291.54 add0, power, mult 734.15/291.54 734.15/291.54 They will be analysed ascendingly in the following order: 734.15/291.54 mult < power 734.15/291.54 add0 < mult 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (9) RewriteLemmaProof (LOWER BOUND(ID)) 734.15/291.54 Proved the following rewrite lemma: 734.15/291.54 add0(gen_S:0'2_1(1), gen_S:0'2_1(n4_1)) -> gen_S:0'2_1(+(1, n4_1)), rt in Omega(1 + n4_1) 734.15/291.54 734.15/291.54 Induction Base: 734.15/291.54 add0(gen_S:0'2_1(1), gen_S:0'2_1(0)) ->_R^Omega(1) 734.15/291.54 gen_S:0'2_1(1) 734.15/291.54 734.15/291.54 Induction Step: 734.15/291.54 add0(gen_S:0'2_1(1), gen_S:0'2_1(+(n4_1, 1))) ->_R^Omega(1) 734.15/291.54 +'(S(0'), add0(gen_S:0'2_1(1), gen_S:0'2_1(n4_1))) ->_IH 734.15/291.54 +'(S(0'), gen_S:0'2_1(+(1, c5_1))) ->_R^Omega(0) 734.15/291.54 S(gen_S:0'2_1(+(1, n4_1))) 734.15/291.54 734.15/291.54 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (10) 734.15/291.54 Complex Obligation (BEST) 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (11) 734.15/291.54 Obligation: 734.15/291.54 Proved the lower bound n^1 for the following obligation: 734.15/291.54 734.15/291.54 Innermost TRS: 734.15/291.54 Rules: 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +'(S(0'), add0(x', x)) 734.15/291.54 power(x, 0') -> S(0') 734.15/291.54 mult(x, 0') -> 0' 734.15/291.54 add0(x, 0') -> x 734.15/291.54 +'(x, S(0')) -> S(x) 734.15/291.54 +'(S(0'), y) -> S(y) 734.15/291.54 734.15/291.54 Types: 734.15/291.54 power :: S:0' -> S:0' -> S:0' 734.15/291.54 S :: S:0' -> S:0' 734.15/291.54 mult :: S:0' -> S:0' -> S:0' 734.15/291.54 add0 :: S:0' -> S:0' -> S:0' 734.15/291.54 +' :: S:0' -> S:0' -> S:0' 734.15/291.54 0' :: S:0' 734.15/291.54 hole_S:0'1_1 :: S:0' 734.15/291.54 gen_S:0'2_1 :: Nat -> S:0' 734.15/291.54 734.15/291.54 734.15/291.54 Generator Equations: 734.15/291.54 gen_S:0'2_1(0) <=> 0' 734.15/291.54 gen_S:0'2_1(+(x, 1)) <=> S(gen_S:0'2_1(x)) 734.15/291.54 734.15/291.54 734.15/291.54 The following defined symbols remain to be analysed: 734.15/291.54 add0, power, mult 734.15/291.54 734.15/291.54 They will be analysed ascendingly in the following order: 734.15/291.54 mult < power 734.15/291.54 add0 < mult 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (12) LowerBoundPropagationProof (FINISHED) 734.15/291.54 Propagated lower bound. 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (13) 734.15/291.54 BOUNDS(n^1, INF) 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (14) 734.15/291.54 Obligation: 734.15/291.54 Innermost TRS: 734.15/291.54 Rules: 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +'(S(0'), add0(x', x)) 734.15/291.54 power(x, 0') -> S(0') 734.15/291.54 mult(x, 0') -> 0' 734.15/291.54 add0(x, 0') -> x 734.15/291.54 +'(x, S(0')) -> S(x) 734.15/291.54 +'(S(0'), y) -> S(y) 734.15/291.54 734.15/291.54 Types: 734.15/291.54 power :: S:0' -> S:0' -> S:0' 734.15/291.54 S :: S:0' -> S:0' 734.15/291.54 mult :: S:0' -> S:0' -> S:0' 734.15/291.54 add0 :: S:0' -> S:0' -> S:0' 734.15/291.54 +' :: S:0' -> S:0' -> S:0' 734.15/291.54 0' :: S:0' 734.15/291.54 hole_S:0'1_1 :: S:0' 734.15/291.54 gen_S:0'2_1 :: Nat -> S:0' 734.15/291.54 734.15/291.54 734.15/291.54 Lemmas: 734.15/291.54 add0(gen_S:0'2_1(1), gen_S:0'2_1(n4_1)) -> gen_S:0'2_1(+(1, n4_1)), rt in Omega(1 + n4_1) 734.15/291.54 734.15/291.54 734.15/291.54 Generator Equations: 734.15/291.54 gen_S:0'2_1(0) <=> 0' 734.15/291.54 gen_S:0'2_1(+(x, 1)) <=> S(gen_S:0'2_1(x)) 734.15/291.54 734.15/291.54 734.15/291.54 The following defined symbols remain to be analysed: 734.15/291.54 mult, power 734.15/291.54 734.15/291.54 They will be analysed ascendingly in the following order: 734.15/291.54 mult < power 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (15) RewriteLemmaProof (LOWER BOUND(ID)) 734.15/291.54 Proved the following rewrite lemma: 734.15/291.54 mult(gen_S:0'2_1(1), gen_S:0'2_1(n487_1)) -> gen_S:0'2_1(n487_1), rt in Omega(1 + n487_1 + n487_1^2) 734.15/291.54 734.15/291.54 Induction Base: 734.15/291.54 mult(gen_S:0'2_1(1), gen_S:0'2_1(0)) ->_R^Omega(1) 734.15/291.54 0' 734.15/291.54 734.15/291.54 Induction Step: 734.15/291.54 mult(gen_S:0'2_1(1), gen_S:0'2_1(+(n487_1, 1))) ->_R^Omega(1) 734.15/291.54 add0(gen_S:0'2_1(1), mult(gen_S:0'2_1(1), gen_S:0'2_1(n487_1))) ->_IH 734.15/291.54 add0(gen_S:0'2_1(1), gen_S:0'2_1(c488_1)) ->_L^Omega(1 + n487_1) 734.15/291.54 gen_S:0'2_1(+(1, n487_1)) 734.15/291.54 734.15/291.54 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (16) 734.15/291.54 Complex Obligation (BEST) 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (17) 734.15/291.54 Obligation: 734.15/291.54 Proved the lower bound n^2 for the following obligation: 734.15/291.54 734.15/291.54 Innermost TRS: 734.15/291.54 Rules: 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +'(S(0'), add0(x', x)) 734.15/291.54 power(x, 0') -> S(0') 734.15/291.54 mult(x, 0') -> 0' 734.15/291.54 add0(x, 0') -> x 734.15/291.54 +'(x, S(0')) -> S(x) 734.15/291.54 +'(S(0'), y) -> S(y) 734.15/291.54 734.15/291.54 Types: 734.15/291.54 power :: S:0' -> S:0' -> S:0' 734.15/291.54 S :: S:0' -> S:0' 734.15/291.54 mult :: S:0' -> S:0' -> S:0' 734.15/291.54 add0 :: S:0' -> S:0' -> S:0' 734.15/291.54 +' :: S:0' -> S:0' -> S:0' 734.15/291.54 0' :: S:0' 734.15/291.54 hole_S:0'1_1 :: S:0' 734.15/291.54 gen_S:0'2_1 :: Nat -> S:0' 734.15/291.54 734.15/291.54 734.15/291.54 Lemmas: 734.15/291.54 add0(gen_S:0'2_1(1), gen_S:0'2_1(n4_1)) -> gen_S:0'2_1(+(1, n4_1)), rt in Omega(1 + n4_1) 734.15/291.54 734.15/291.54 734.15/291.54 Generator Equations: 734.15/291.54 gen_S:0'2_1(0) <=> 0' 734.15/291.54 gen_S:0'2_1(+(x, 1)) <=> S(gen_S:0'2_1(x)) 734.15/291.54 734.15/291.54 734.15/291.54 The following defined symbols remain to be analysed: 734.15/291.54 mult, power 734.15/291.54 734.15/291.54 They will be analysed ascendingly in the following order: 734.15/291.54 mult < power 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (18) LowerBoundPropagationProof (FINISHED) 734.15/291.54 Propagated lower bound. 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (19) 734.15/291.54 BOUNDS(n^2, INF) 734.15/291.54 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (20) 734.15/291.54 Obligation: 734.15/291.54 Innermost TRS: 734.15/291.54 Rules: 734.15/291.54 power(x', S(x)) -> mult(x', power(x', x)) 734.15/291.54 mult(x', S(x)) -> add0(x', mult(x', x)) 734.15/291.54 add0(x', S(x)) -> +'(S(0'), add0(x', x)) 734.15/291.54 power(x, 0') -> S(0') 734.15/291.54 mult(x, 0') -> 0' 734.15/291.54 add0(x, 0') -> x 734.15/291.54 +'(x, S(0')) -> S(x) 734.15/291.54 +'(S(0'), y) -> S(y) 734.15/291.54 734.15/291.54 Types: 734.15/291.54 power :: S:0' -> S:0' -> S:0' 734.15/291.54 S :: S:0' -> S:0' 734.15/291.54 mult :: S:0' -> S:0' -> S:0' 734.15/291.54 add0 :: S:0' -> S:0' -> S:0' 734.15/291.54 +' :: S:0' -> S:0' -> S:0' 734.15/291.54 0' :: S:0' 734.15/291.54 hole_S:0'1_1 :: S:0' 734.15/291.54 gen_S:0'2_1 :: Nat -> S:0' 734.15/291.54 734.15/291.54 734.15/291.54 Lemmas: 734.15/291.54 add0(gen_S:0'2_1(1), gen_S:0'2_1(n4_1)) -> gen_S:0'2_1(+(1, n4_1)), rt in Omega(1 + n4_1) 734.15/291.54 mult(gen_S:0'2_1(1), gen_S:0'2_1(n487_1)) -> gen_S:0'2_1(n487_1), rt in Omega(1 + n487_1 + n487_1^2) 734.15/291.54 734.15/291.54 734.15/291.54 Generator Equations: 734.15/291.54 gen_S:0'2_1(0) <=> 0' 734.15/291.54 gen_S:0'2_1(+(x, 1)) <=> S(gen_S:0'2_1(x)) 734.15/291.54 734.15/291.54 734.15/291.54 The following defined symbols remain to be analysed: 734.15/291.54 power 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (21) RewriteLemmaProof (LOWER BOUND(ID)) 734.15/291.54 Proved the following rewrite lemma: 734.15/291.54 power(gen_S:0'2_1(1), gen_S:0'2_1(n780_1)) -> gen_S:0'2_1(1), rt in Omega(1 + n780_1) 734.15/291.54 734.15/291.54 Induction Base: 734.15/291.54 power(gen_S:0'2_1(1), gen_S:0'2_1(0)) ->_R^Omega(1) 734.15/291.54 S(0') 734.15/291.54 734.15/291.54 Induction Step: 734.15/291.54 power(gen_S:0'2_1(1), gen_S:0'2_1(+(n780_1, 1))) ->_R^Omega(1) 734.15/291.54 mult(gen_S:0'2_1(1), power(gen_S:0'2_1(1), gen_S:0'2_1(n780_1))) ->_IH 734.15/291.54 mult(gen_S:0'2_1(1), gen_S:0'2_1(1)) ->_L^Omega(3) 734.15/291.54 gen_S:0'2_1(1) 734.15/291.54 734.15/291.54 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 734.15/291.54 ---------------------------------------- 734.15/291.54 734.15/291.54 (22) 734.15/291.54 BOUNDS(1, INF) 734.28/291.58 EOF