321.65/291.52 WORST_CASE(Omega(n^2), ?) 321.65/291.53 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 321.65/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 321.65/291.53 321.65/291.53 321.65/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 321.65/291.53 321.65/291.53 (0) CpxTRS 321.65/291.53 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 321.65/291.53 (2) CpxTRS 321.65/291.53 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 321.65/291.53 (4) CpxTRS 321.65/291.53 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 321.65/291.53 (6) typed CpxTrs 321.65/291.53 (7) OrderProof [LOWER BOUND(ID), 0 ms] 321.65/291.53 (8) typed CpxTrs 321.65/291.53 (9) RewriteLemmaProof [LOWER BOUND(ID), 290 ms] 321.65/291.53 (10) BEST 321.65/291.53 (11) proven lower bound 321.65/291.53 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 321.65/291.53 (13) BOUNDS(n^1, INF) 321.65/291.53 (14) typed CpxTrs 321.65/291.53 (15) RewriteLemmaProof [LOWER BOUND(ID), 1609 ms] 321.65/291.53 (16) proven lower bound 321.65/291.53 (17) LowerBoundPropagationProof [FINISHED, 0 ms] 321.65/291.53 (18) BOUNDS(n^2, INF) 321.65/291.53 321.65/291.53 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (0) 321.65/291.53 Obligation: 321.65/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 321.65/291.53 321.65/291.53 321.65/291.53 The TRS R consists of the following rules: 321.65/291.53 321.65/291.53 fac(s(x)) -> *(fac(p(s(x))), s(x)) 321.65/291.53 p(s(0)) -> 0 321.65/291.53 p(s(s(x))) -> s(p(s(x))) 321.65/291.53 321.65/291.53 S is empty. 321.65/291.53 Rewrite Strategy: FULL 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 321.65/291.53 Renamed function symbols to avoid clashes with predefined symbol. 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (2) 321.65/291.53 Obligation: 321.65/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 321.65/291.53 321.65/291.53 321.65/291.53 The TRS R consists of the following rules: 321.65/291.53 321.65/291.53 fac(s(x)) -> *'(fac(p(s(x))), s(x)) 321.65/291.53 p(s(0')) -> 0' 321.65/291.53 p(s(s(x))) -> s(p(s(x))) 321.65/291.53 321.65/291.53 S is empty. 321.65/291.53 Rewrite Strategy: FULL 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (3) SlicingProof (LOWER BOUND(ID)) 321.65/291.53 Sliced the following arguments: 321.65/291.53 *'/1 321.65/291.53 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (4) 321.65/291.53 Obligation: 321.65/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 321.65/291.53 321.65/291.53 321.65/291.53 The TRS R consists of the following rules: 321.65/291.53 321.65/291.53 fac(s(x)) -> *'(fac(p(s(x)))) 321.65/291.53 p(s(0')) -> 0' 321.65/291.53 p(s(s(x))) -> s(p(s(x))) 321.65/291.53 321.65/291.53 S is empty. 321.65/291.53 Rewrite Strategy: FULL 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 321.65/291.53 Infered types. 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (6) 321.65/291.53 Obligation: 321.65/291.53 TRS: 321.65/291.53 Rules: 321.65/291.53 fac(s(x)) -> *'(fac(p(s(x)))) 321.65/291.53 p(s(0')) -> 0' 321.65/291.53 p(s(s(x))) -> s(p(s(x))) 321.65/291.53 321.65/291.53 Types: 321.65/291.53 fac :: s:0' -> *' 321.65/291.53 s :: s:0' -> s:0' 321.65/291.53 *' :: *' -> *' 321.65/291.53 p :: s:0' -> s:0' 321.65/291.53 0' :: s:0' 321.65/291.53 hole_*'1_0 :: *' 321.65/291.53 hole_s:0'2_0 :: s:0' 321.65/291.53 gen_*'3_0 :: Nat -> *' 321.65/291.53 gen_s:0'4_0 :: Nat -> s:0' 321.65/291.53 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (7) OrderProof (LOWER BOUND(ID)) 321.65/291.53 Heuristically decided to analyse the following defined symbols: 321.65/291.53 fac, p 321.65/291.53 321.65/291.53 They will be analysed ascendingly in the following order: 321.65/291.53 p < fac 321.65/291.53 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (8) 321.65/291.53 Obligation: 321.65/291.53 TRS: 321.65/291.53 Rules: 321.65/291.53 fac(s(x)) -> *'(fac(p(s(x)))) 321.65/291.53 p(s(0')) -> 0' 321.65/291.53 p(s(s(x))) -> s(p(s(x))) 321.65/291.53 321.65/291.53 Types: 321.65/291.53 fac :: s:0' -> *' 321.65/291.53 s :: s:0' -> s:0' 321.65/291.53 *' :: *' -> *' 321.65/291.53 p :: s:0' -> s:0' 321.65/291.53 0' :: s:0' 321.65/291.53 hole_*'1_0 :: *' 321.65/291.53 hole_s:0'2_0 :: s:0' 321.65/291.53 gen_*'3_0 :: Nat -> *' 321.65/291.53 gen_s:0'4_0 :: Nat -> s:0' 321.65/291.53 321.65/291.53 321.65/291.53 Generator Equations: 321.65/291.53 gen_*'3_0(0) <=> hole_*'1_0 321.65/291.53 gen_*'3_0(+(x, 1)) <=> *'(gen_*'3_0(x)) 321.65/291.53 gen_s:0'4_0(0) <=> 0' 321.65/291.53 gen_s:0'4_0(+(x, 1)) <=> s(gen_s:0'4_0(x)) 321.65/291.53 321.65/291.53 321.65/291.53 The following defined symbols remain to be analysed: 321.65/291.53 p, fac 321.65/291.53 321.65/291.53 They will be analysed ascendingly in the following order: 321.65/291.53 p < fac 321.65/291.53 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (9) RewriteLemmaProof (LOWER BOUND(ID)) 321.65/291.53 Proved the following rewrite lemma: 321.65/291.53 p(gen_s:0'4_0(+(1, n6_0))) -> gen_s:0'4_0(n6_0), rt in Omega(1 + n6_0) 321.65/291.53 321.65/291.53 Induction Base: 321.65/291.53 p(gen_s:0'4_0(+(1, 0))) ->_R^Omega(1) 321.65/291.53 0' 321.65/291.53 321.65/291.53 Induction Step: 321.65/291.53 p(gen_s:0'4_0(+(1, +(n6_0, 1)))) ->_R^Omega(1) 321.65/291.53 s(p(s(gen_s:0'4_0(n6_0)))) ->_IH 321.65/291.53 s(gen_s:0'4_0(c7_0)) 321.65/291.53 321.65/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (10) 321.65/291.53 Complex Obligation (BEST) 321.65/291.53 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (11) 321.65/291.53 Obligation: 321.65/291.53 Proved the lower bound n^1 for the following obligation: 321.65/291.53 321.65/291.53 TRS: 321.65/291.53 Rules: 321.65/291.53 fac(s(x)) -> *'(fac(p(s(x)))) 321.65/291.53 p(s(0')) -> 0' 321.65/291.53 p(s(s(x))) -> s(p(s(x))) 321.65/291.53 321.65/291.53 Types: 321.65/291.53 fac :: s:0' -> *' 321.65/291.53 s :: s:0' -> s:0' 321.65/291.53 *' :: *' -> *' 321.65/291.53 p :: s:0' -> s:0' 321.65/291.53 0' :: s:0' 321.65/291.53 hole_*'1_0 :: *' 321.65/291.53 hole_s:0'2_0 :: s:0' 321.65/291.53 gen_*'3_0 :: Nat -> *' 321.65/291.53 gen_s:0'4_0 :: Nat -> s:0' 321.65/291.53 321.65/291.53 321.65/291.53 Generator Equations: 321.65/291.53 gen_*'3_0(0) <=> hole_*'1_0 321.65/291.53 gen_*'3_0(+(x, 1)) <=> *'(gen_*'3_0(x)) 321.65/291.53 gen_s:0'4_0(0) <=> 0' 321.65/291.53 gen_s:0'4_0(+(x, 1)) <=> s(gen_s:0'4_0(x)) 321.65/291.53 321.65/291.53 321.65/291.53 The following defined symbols remain to be analysed: 321.65/291.53 p, fac 321.65/291.53 321.65/291.53 They will be analysed ascendingly in the following order: 321.65/291.53 p < fac 321.65/291.53 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (12) LowerBoundPropagationProof (FINISHED) 321.65/291.53 Propagated lower bound. 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (13) 321.65/291.53 BOUNDS(n^1, INF) 321.65/291.53 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (14) 321.65/291.53 Obligation: 321.65/291.53 TRS: 321.65/291.53 Rules: 321.65/291.53 fac(s(x)) -> *'(fac(p(s(x)))) 321.65/291.53 p(s(0')) -> 0' 321.65/291.53 p(s(s(x))) -> s(p(s(x))) 321.65/291.53 321.65/291.53 Types: 321.65/291.53 fac :: s:0' -> *' 321.65/291.53 s :: s:0' -> s:0' 321.65/291.53 *' :: *' -> *' 321.65/291.53 p :: s:0' -> s:0' 321.65/291.53 0' :: s:0' 321.65/291.53 hole_*'1_0 :: *' 321.65/291.53 hole_s:0'2_0 :: s:0' 321.65/291.53 gen_*'3_0 :: Nat -> *' 321.65/291.53 gen_s:0'4_0 :: Nat -> s:0' 321.65/291.53 321.65/291.53 321.65/291.53 Lemmas: 321.65/291.53 p(gen_s:0'4_0(+(1, n6_0))) -> gen_s:0'4_0(n6_0), rt in Omega(1 + n6_0) 321.65/291.53 321.65/291.53 321.65/291.53 Generator Equations: 321.65/291.53 gen_*'3_0(0) <=> hole_*'1_0 321.65/291.53 gen_*'3_0(+(x, 1)) <=> *'(gen_*'3_0(x)) 321.65/291.53 gen_s:0'4_0(0) <=> 0' 321.65/291.53 gen_s:0'4_0(+(x, 1)) <=> s(gen_s:0'4_0(x)) 321.65/291.53 321.65/291.53 321.65/291.53 The following defined symbols remain to be analysed: 321.65/291.53 fac 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (15) RewriteLemmaProof (LOWER BOUND(ID)) 321.65/291.53 Proved the following rewrite lemma: 321.65/291.53 fac(gen_s:0'4_0(+(1, n213_0))) -> *5_0, rt in Omega(n213_0 + n213_0^2) 321.65/291.53 321.65/291.53 Induction Base: 321.65/291.53 fac(gen_s:0'4_0(+(1, 0))) 321.65/291.53 321.65/291.53 Induction Step: 321.65/291.53 fac(gen_s:0'4_0(+(1, +(n213_0, 1)))) ->_R^Omega(1) 321.65/291.53 *'(fac(p(s(gen_s:0'4_0(+(1, n213_0)))))) ->_L^Omega(2 + n213_0) 321.65/291.53 *'(fac(gen_s:0'4_0(+(1, n213_0)))) ->_IH 321.65/291.53 *'(*5_0) 321.65/291.53 321.65/291.53 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (16) 321.65/291.53 Obligation: 321.65/291.53 Proved the lower bound n^2 for the following obligation: 321.65/291.53 321.65/291.53 TRS: 321.65/291.53 Rules: 321.65/291.53 fac(s(x)) -> *'(fac(p(s(x)))) 321.65/291.53 p(s(0')) -> 0' 321.65/291.53 p(s(s(x))) -> s(p(s(x))) 321.65/291.53 321.65/291.53 Types: 321.65/291.53 fac :: s:0' -> *' 321.65/291.53 s :: s:0' -> s:0' 321.65/291.53 *' :: *' -> *' 321.65/291.53 p :: s:0' -> s:0' 321.65/291.53 0' :: s:0' 321.65/291.53 hole_*'1_0 :: *' 321.65/291.53 hole_s:0'2_0 :: s:0' 321.65/291.53 gen_*'3_0 :: Nat -> *' 321.65/291.53 gen_s:0'4_0 :: Nat -> s:0' 321.65/291.53 321.65/291.53 321.65/291.53 Lemmas: 321.65/291.53 p(gen_s:0'4_0(+(1, n6_0))) -> gen_s:0'4_0(n6_0), rt in Omega(1 + n6_0) 321.65/291.53 321.65/291.53 321.65/291.53 Generator Equations: 321.65/291.53 gen_*'3_0(0) <=> hole_*'1_0 321.65/291.53 gen_*'3_0(+(x, 1)) <=> *'(gen_*'3_0(x)) 321.65/291.53 gen_s:0'4_0(0) <=> 0' 321.65/291.53 gen_s:0'4_0(+(x, 1)) <=> s(gen_s:0'4_0(x)) 321.65/291.53 321.65/291.53 321.65/291.53 The following defined symbols remain to be analysed: 321.65/291.53 fac 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (17) LowerBoundPropagationProof (FINISHED) 321.65/291.53 Propagated lower bound. 321.65/291.53 ---------------------------------------- 321.65/291.53 321.65/291.53 (18) 321.65/291.53 BOUNDS(n^2, INF) 321.65/291.56 EOF