317.33/291.48 WORST_CASE(Omega(n^2), ?) 317.33/291.49 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 317.33/291.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 317.33/291.49 317.33/291.49 317.33/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 317.33/291.49 317.33/291.49 (0) CpxTRS 317.33/291.49 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 317.33/291.49 (2) CpxTRS 317.33/291.49 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 317.33/291.49 (4) typed CpxTrs 317.33/291.49 (5) OrderProof [LOWER BOUND(ID), 0 ms] 317.33/291.49 (6) typed CpxTrs 317.33/291.49 (7) RewriteLemmaProof [LOWER BOUND(ID), 303 ms] 317.33/291.49 (8) BEST 317.33/291.49 (9) proven lower bound 317.33/291.49 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 317.33/291.49 (11) BOUNDS(n^1, INF) 317.33/291.49 (12) typed CpxTrs 317.33/291.49 (13) RewriteLemmaProof [LOWER BOUND(ID), 36 ms] 317.33/291.49 (14) BEST 317.33/291.49 (15) proven lower bound 317.33/291.49 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 317.33/291.49 (17) BOUNDS(n^2, INF) 317.33/291.49 (18) typed CpxTrs 317.33/291.49 (19) RewriteLemmaProof [LOWER BOUND(ID), 34 ms] 317.33/291.49 (20) typed CpxTrs 317.33/291.49 (21) RewriteLemmaProof [LOWER BOUND(ID), 1859 ms] 317.33/291.49 (22) BOUNDS(1, INF) 317.33/291.49 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (0) 317.33/291.49 Obligation: 317.33/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 317.33/291.49 317.33/291.49 317.33/291.49 The TRS R consists of the following rules: 317.33/291.49 317.33/291.49 plus(x, 0) -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0, y) -> 0 317.33/291.49 times(x, 0) -> 0 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.49 p(s(s(x))) -> s(p(s(x))) 317.33/291.49 p(s(0)) -> 0 317.33/291.49 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.49 317.33/291.49 S is empty. 317.33/291.49 Rewrite Strategy: FULL 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 317.33/291.49 Renamed function symbols to avoid clashes with predefined symbol. 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (2) 317.33/291.49 Obligation: 317.33/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 317.33/291.49 317.33/291.49 317.33/291.49 The TRS R consists of the following rules: 317.33/291.49 317.33/291.49 plus(x, 0') -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0', y) -> 0' 317.33/291.49 times(x, 0') -> 0' 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.49 p(s(s(x))) -> s(p(s(x))) 317.33/291.49 p(s(0')) -> 0' 317.33/291.49 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.49 317.33/291.49 S is empty. 317.33/291.49 Rewrite Strategy: FULL 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 317.33/291.49 Infered types. 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (4) 317.33/291.49 Obligation: 317.33/291.49 TRS: 317.33/291.49 Rules: 317.33/291.49 plus(x, 0') -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0', y) -> 0' 317.33/291.49 times(x, 0') -> 0' 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.49 p(s(s(x))) -> s(p(s(x))) 317.33/291.49 p(s(0')) -> 0' 317.33/291.49 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.49 317.33/291.49 Types: 317.33/291.49 plus :: 0':s -> 0':s -> 0':s 317.33/291.49 0' :: 0':s 317.33/291.49 s :: 0':s -> 0':s 317.33/291.49 times :: 0':s -> 0':s -> 0':s 317.33/291.49 p :: 0':s -> 0':s 317.33/291.49 fac :: 0':s -> 0':s 317.33/291.49 hole_0':s1_0 :: 0':s 317.33/291.49 gen_0':s2_0 :: Nat -> 0':s 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (5) OrderProof (LOWER BOUND(ID)) 317.33/291.49 Heuristically decided to analyse the following defined symbols: 317.33/291.49 plus, times, p, fac 317.33/291.49 317.33/291.49 They will be analysed ascendingly in the following order: 317.33/291.49 plus < times 317.33/291.49 times < fac 317.33/291.49 p < fac 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (6) 317.33/291.49 Obligation: 317.33/291.49 TRS: 317.33/291.49 Rules: 317.33/291.49 plus(x, 0') -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0', y) -> 0' 317.33/291.49 times(x, 0') -> 0' 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.49 p(s(s(x))) -> s(p(s(x))) 317.33/291.49 p(s(0')) -> 0' 317.33/291.49 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.49 317.33/291.49 Types: 317.33/291.49 plus :: 0':s -> 0':s -> 0':s 317.33/291.49 0' :: 0':s 317.33/291.49 s :: 0':s -> 0':s 317.33/291.49 times :: 0':s -> 0':s -> 0':s 317.33/291.49 p :: 0':s -> 0':s 317.33/291.49 fac :: 0':s -> 0':s 317.33/291.49 hole_0':s1_0 :: 0':s 317.33/291.49 gen_0':s2_0 :: Nat -> 0':s 317.33/291.49 317.33/291.49 317.33/291.49 Generator Equations: 317.33/291.49 gen_0':s2_0(0) <=> 0' 317.33/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 317.33/291.49 317.33/291.49 317.33/291.49 The following defined symbols remain to be analysed: 317.33/291.49 plus, times, p, fac 317.33/291.49 317.33/291.49 They will be analysed ascendingly in the following order: 317.33/291.49 plus < times 317.33/291.49 times < fac 317.33/291.49 p < fac 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (7) RewriteLemmaProof (LOWER BOUND(ID)) 317.33/291.49 Proved the following rewrite lemma: 317.33/291.49 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 317.33/291.49 317.33/291.49 Induction Base: 317.33/291.49 plus(gen_0':s2_0(a), gen_0':s2_0(0)) ->_R^Omega(1) 317.33/291.49 gen_0':s2_0(a) 317.33/291.49 317.33/291.49 Induction Step: 317.33/291.49 plus(gen_0':s2_0(a), gen_0':s2_0(+(n4_0, 1))) ->_R^Omega(1) 317.33/291.49 s(plus(gen_0':s2_0(a), gen_0':s2_0(n4_0))) ->_IH 317.33/291.49 s(gen_0':s2_0(+(a, c5_0))) 317.33/291.49 317.33/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (8) 317.33/291.49 Complex Obligation (BEST) 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (9) 317.33/291.49 Obligation: 317.33/291.49 Proved the lower bound n^1 for the following obligation: 317.33/291.49 317.33/291.49 TRS: 317.33/291.49 Rules: 317.33/291.49 plus(x, 0') -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0', y) -> 0' 317.33/291.49 times(x, 0') -> 0' 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.49 p(s(s(x))) -> s(p(s(x))) 317.33/291.49 p(s(0')) -> 0' 317.33/291.49 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.49 317.33/291.49 Types: 317.33/291.49 plus :: 0':s -> 0':s -> 0':s 317.33/291.49 0' :: 0':s 317.33/291.49 s :: 0':s -> 0':s 317.33/291.49 times :: 0':s -> 0':s -> 0':s 317.33/291.49 p :: 0':s -> 0':s 317.33/291.49 fac :: 0':s -> 0':s 317.33/291.49 hole_0':s1_0 :: 0':s 317.33/291.49 gen_0':s2_0 :: Nat -> 0':s 317.33/291.49 317.33/291.49 317.33/291.49 Generator Equations: 317.33/291.49 gen_0':s2_0(0) <=> 0' 317.33/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 317.33/291.49 317.33/291.49 317.33/291.49 The following defined symbols remain to be analysed: 317.33/291.49 plus, times, p, fac 317.33/291.49 317.33/291.49 They will be analysed ascendingly in the following order: 317.33/291.49 plus < times 317.33/291.49 times < fac 317.33/291.49 p < fac 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (10) LowerBoundPropagationProof (FINISHED) 317.33/291.49 Propagated lower bound. 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (11) 317.33/291.49 BOUNDS(n^1, INF) 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (12) 317.33/291.49 Obligation: 317.33/291.49 TRS: 317.33/291.49 Rules: 317.33/291.49 plus(x, 0') -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0', y) -> 0' 317.33/291.49 times(x, 0') -> 0' 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.49 p(s(s(x))) -> s(p(s(x))) 317.33/291.49 p(s(0')) -> 0' 317.33/291.49 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.49 317.33/291.49 Types: 317.33/291.49 plus :: 0':s -> 0':s -> 0':s 317.33/291.49 0' :: 0':s 317.33/291.49 s :: 0':s -> 0':s 317.33/291.49 times :: 0':s -> 0':s -> 0':s 317.33/291.49 p :: 0':s -> 0':s 317.33/291.49 fac :: 0':s -> 0':s 317.33/291.49 hole_0':s1_0 :: 0':s 317.33/291.49 gen_0':s2_0 :: Nat -> 0':s 317.33/291.49 317.33/291.49 317.33/291.49 Lemmas: 317.33/291.49 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 317.33/291.49 317.33/291.49 317.33/291.49 Generator Equations: 317.33/291.49 gen_0':s2_0(0) <=> 0' 317.33/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 317.33/291.49 317.33/291.49 317.33/291.49 The following defined symbols remain to be analysed: 317.33/291.49 times, p, fac 317.33/291.49 317.33/291.49 They will be analysed ascendingly in the following order: 317.33/291.49 times < fac 317.33/291.49 p < fac 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (13) RewriteLemmaProof (LOWER BOUND(ID)) 317.33/291.49 Proved the following rewrite lemma: 317.33/291.49 times(gen_0':s2_0(n475_0), gen_0':s2_0(b)) -> gen_0':s2_0(*(n475_0, b)), rt in Omega(1 + b*n475_0 + n475_0) 317.33/291.49 317.33/291.49 Induction Base: 317.33/291.49 times(gen_0':s2_0(0), gen_0':s2_0(b)) ->_R^Omega(1) 317.33/291.49 0' 317.33/291.49 317.33/291.49 Induction Step: 317.33/291.49 times(gen_0':s2_0(+(n475_0, 1)), gen_0':s2_0(b)) ->_R^Omega(1) 317.33/291.49 plus(times(gen_0':s2_0(n475_0), gen_0':s2_0(b)), gen_0':s2_0(b)) ->_IH 317.33/291.49 plus(gen_0':s2_0(*(c476_0, b)), gen_0':s2_0(b)) ->_L^Omega(1 + b) 317.33/291.49 gen_0':s2_0(+(b, *(n475_0, b))) 317.33/291.49 317.33/291.49 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (14) 317.33/291.49 Complex Obligation (BEST) 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (15) 317.33/291.49 Obligation: 317.33/291.49 Proved the lower bound n^2 for the following obligation: 317.33/291.49 317.33/291.49 TRS: 317.33/291.49 Rules: 317.33/291.49 plus(x, 0') -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0', y) -> 0' 317.33/291.49 times(x, 0') -> 0' 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.49 p(s(s(x))) -> s(p(s(x))) 317.33/291.49 p(s(0')) -> 0' 317.33/291.49 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.49 317.33/291.49 Types: 317.33/291.49 plus :: 0':s -> 0':s -> 0':s 317.33/291.49 0' :: 0':s 317.33/291.49 s :: 0':s -> 0':s 317.33/291.49 times :: 0':s -> 0':s -> 0':s 317.33/291.49 p :: 0':s -> 0':s 317.33/291.49 fac :: 0':s -> 0':s 317.33/291.49 hole_0':s1_0 :: 0':s 317.33/291.49 gen_0':s2_0 :: Nat -> 0':s 317.33/291.49 317.33/291.49 317.33/291.49 Lemmas: 317.33/291.49 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 317.33/291.49 317.33/291.49 317.33/291.49 Generator Equations: 317.33/291.49 gen_0':s2_0(0) <=> 0' 317.33/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 317.33/291.49 317.33/291.49 317.33/291.49 The following defined symbols remain to be analysed: 317.33/291.49 times, p, fac 317.33/291.49 317.33/291.49 They will be analysed ascendingly in the following order: 317.33/291.49 times < fac 317.33/291.49 p < fac 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (16) LowerBoundPropagationProof (FINISHED) 317.33/291.49 Propagated lower bound. 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (17) 317.33/291.49 BOUNDS(n^2, INF) 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (18) 317.33/291.49 Obligation: 317.33/291.49 TRS: 317.33/291.49 Rules: 317.33/291.49 plus(x, 0') -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0', y) -> 0' 317.33/291.49 times(x, 0') -> 0' 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.49 p(s(s(x))) -> s(p(s(x))) 317.33/291.49 p(s(0')) -> 0' 317.33/291.49 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.49 317.33/291.49 Types: 317.33/291.49 plus :: 0':s -> 0':s -> 0':s 317.33/291.49 0' :: 0':s 317.33/291.49 s :: 0':s -> 0':s 317.33/291.49 times :: 0':s -> 0':s -> 0':s 317.33/291.49 p :: 0':s -> 0':s 317.33/291.49 fac :: 0':s -> 0':s 317.33/291.49 hole_0':s1_0 :: 0':s 317.33/291.49 gen_0':s2_0 :: Nat -> 0':s 317.33/291.49 317.33/291.49 317.33/291.49 Lemmas: 317.33/291.49 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 317.33/291.49 times(gen_0':s2_0(n475_0), gen_0':s2_0(b)) -> gen_0':s2_0(*(n475_0, b)), rt in Omega(1 + b*n475_0 + n475_0) 317.33/291.49 317.33/291.49 317.33/291.49 Generator Equations: 317.33/291.49 gen_0':s2_0(0) <=> 0' 317.33/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 317.33/291.49 317.33/291.49 317.33/291.49 The following defined symbols remain to be analysed: 317.33/291.49 p, fac 317.33/291.49 317.33/291.49 They will be analysed ascendingly in the following order: 317.33/291.49 p < fac 317.33/291.49 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (19) RewriteLemmaProof (LOWER BOUND(ID)) 317.33/291.49 Proved the following rewrite lemma: 317.33/291.49 p(gen_0':s2_0(+(1, n1092_0))) -> gen_0':s2_0(n1092_0), rt in Omega(1 + n1092_0) 317.33/291.49 317.33/291.49 Induction Base: 317.33/291.49 p(gen_0':s2_0(+(1, 0))) ->_R^Omega(1) 317.33/291.49 0' 317.33/291.49 317.33/291.49 Induction Step: 317.33/291.49 p(gen_0':s2_0(+(1, +(n1092_0, 1)))) ->_R^Omega(1) 317.33/291.49 s(p(s(gen_0':s2_0(n1092_0)))) ->_IH 317.33/291.49 s(gen_0':s2_0(c1093_0)) 317.33/291.49 317.33/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 317.33/291.49 ---------------------------------------- 317.33/291.49 317.33/291.49 (20) 317.33/291.49 Obligation: 317.33/291.49 TRS: 317.33/291.49 Rules: 317.33/291.49 plus(x, 0') -> x 317.33/291.49 plus(x, s(y)) -> s(plus(x, y)) 317.33/291.49 times(0', y) -> 0' 317.33/291.49 times(x, 0') -> 0' 317.33/291.49 times(s(x), y) -> plus(times(x, y), y) 317.33/291.50 p(s(s(x))) -> s(p(s(x))) 317.33/291.50 p(s(0')) -> 0' 317.33/291.50 fac(s(x)) -> times(fac(p(s(x))), s(x)) 317.33/291.50 317.33/291.50 Types: 317.33/291.50 plus :: 0':s -> 0':s -> 0':s 317.33/291.50 0' :: 0':s 317.33/291.50 s :: 0':s -> 0':s 317.33/291.50 times :: 0':s -> 0':s -> 0':s 317.33/291.50 p :: 0':s -> 0':s 317.33/291.50 fac :: 0':s -> 0':s 317.33/291.50 hole_0':s1_0 :: 0':s 317.33/291.50 gen_0':s2_0 :: Nat -> 0':s 317.33/291.50 317.33/291.50 317.33/291.50 Lemmas: 317.33/291.50 plus(gen_0':s2_0(a), gen_0':s2_0(n4_0)) -> gen_0':s2_0(+(n4_0, a)), rt in Omega(1 + n4_0) 317.33/291.50 times(gen_0':s2_0(n475_0), gen_0':s2_0(b)) -> gen_0':s2_0(*(n475_0, b)), rt in Omega(1 + b*n475_0 + n475_0) 317.33/291.50 p(gen_0':s2_0(+(1, n1092_0))) -> gen_0':s2_0(n1092_0), rt in Omega(1 + n1092_0) 317.33/291.50 317.33/291.50 317.33/291.50 Generator Equations: 317.33/291.50 gen_0':s2_0(0) <=> 0' 317.33/291.50 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 317.33/291.50 317.33/291.50 317.33/291.50 The following defined symbols remain to be analysed: 317.33/291.50 fac 317.33/291.50 ---------------------------------------- 317.33/291.50 317.33/291.50 (21) RewriteLemmaProof (LOWER BOUND(ID)) 317.33/291.50 Proved the following rewrite lemma: 317.33/291.50 fac(gen_0':s2_0(+(1, n1276_0))) -> *3_0, rt in Omega(n1276_0 + n1276_0^2) 317.33/291.50 317.33/291.50 Induction Base: 317.33/291.50 fac(gen_0':s2_0(+(1, 0))) 317.33/291.50 317.33/291.50 Induction Step: 317.33/291.50 fac(gen_0':s2_0(+(1, +(n1276_0, 1)))) ->_R^Omega(1) 317.33/291.50 times(fac(p(s(gen_0':s2_0(+(1, n1276_0))))), s(gen_0':s2_0(+(1, n1276_0)))) ->_L^Omega(2 + n1276_0) 317.33/291.50 times(fac(gen_0':s2_0(+(1, n1276_0))), s(gen_0':s2_0(+(1, n1276_0)))) ->_IH 317.33/291.50 times(*3_0, s(gen_0':s2_0(+(1, n1276_0)))) 317.33/291.50 317.33/291.50 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 317.33/291.50 ---------------------------------------- 317.33/291.50 317.33/291.50 (22) 317.33/291.50 BOUNDS(1, INF) 317.38/291.52 EOF