307.80/291.52 WORST_CASE(Omega(n^2), ?) 307.80/291.53 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 307.80/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 307.80/291.53 307.80/291.53 307.80/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 307.80/291.53 307.80/291.53 (0) CpxTRS 307.80/291.53 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 307.80/291.53 (2) CpxTRS 307.80/291.53 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 307.80/291.53 (4) typed CpxTrs 307.80/291.53 (5) OrderProof [LOWER BOUND(ID), 0 ms] 307.80/291.53 (6) typed CpxTrs 307.80/291.53 (7) RewriteLemmaProof [LOWER BOUND(ID), 284 ms] 307.80/291.53 (8) BEST 307.80/291.53 (9) proven lower bound 307.80/291.53 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 307.80/291.53 (11) BOUNDS(n^1, INF) 307.80/291.53 (12) typed CpxTrs 307.80/291.53 (13) RewriteLemmaProof [LOWER BOUND(ID), 41 ms] 307.80/291.53 (14) proven lower bound 307.80/291.53 (15) LowerBoundPropagationProof [FINISHED, 0 ms] 307.80/291.53 (16) BOUNDS(n^2, INF) 307.80/291.53 307.80/291.53 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (0) 307.80/291.53 Obligation: 307.80/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 307.80/291.53 307.80/291.53 307.80/291.53 The TRS R consists of the following rules: 307.80/291.53 307.80/291.53 nonZero(0) -> false 307.80/291.53 nonZero(s(x)) -> true 307.80/291.53 p(s(0)) -> 0 307.80/291.53 p(s(s(x))) -> s(p(s(x))) 307.80/291.53 id_inc(x) -> x 307.80/291.53 id_inc(x) -> s(x) 307.80/291.53 random(x) -> rand(x, 0) 307.80/291.53 rand(x, y) -> if(nonZero(x), x, y) 307.80/291.53 if(false, x, y) -> y 307.80/291.53 if(true, x, y) -> rand(p(x), id_inc(y)) 307.80/291.53 307.80/291.53 S is empty. 307.80/291.53 Rewrite Strategy: FULL 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 307.80/291.53 Renamed function symbols to avoid clashes with predefined symbol. 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (2) 307.80/291.53 Obligation: 307.80/291.53 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 307.80/291.53 307.80/291.53 307.80/291.53 The TRS R consists of the following rules: 307.80/291.53 307.80/291.53 nonZero(0') -> false 307.80/291.53 nonZero(s(x)) -> true 307.80/291.53 p(s(0')) -> 0' 307.80/291.53 p(s(s(x))) -> s(p(s(x))) 307.80/291.53 id_inc(x) -> x 307.80/291.53 id_inc(x) -> s(x) 307.80/291.53 random(x) -> rand(x, 0') 307.80/291.53 rand(x, y) -> if(nonZero(x), x, y) 307.80/291.53 if(false, x, y) -> y 307.80/291.53 if(true, x, y) -> rand(p(x), id_inc(y)) 307.80/291.53 307.80/291.53 S is empty. 307.80/291.53 Rewrite Strategy: FULL 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 307.80/291.53 Infered types. 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (4) 307.80/291.53 Obligation: 307.80/291.53 TRS: 307.80/291.53 Rules: 307.80/291.53 nonZero(0') -> false 307.80/291.53 nonZero(s(x)) -> true 307.80/291.53 p(s(0')) -> 0' 307.80/291.53 p(s(s(x))) -> s(p(s(x))) 307.80/291.53 id_inc(x) -> x 307.80/291.53 id_inc(x) -> s(x) 307.80/291.53 random(x) -> rand(x, 0') 307.80/291.53 rand(x, y) -> if(nonZero(x), x, y) 307.80/291.53 if(false, x, y) -> y 307.80/291.53 if(true, x, y) -> rand(p(x), id_inc(y)) 307.80/291.53 307.80/291.53 Types: 307.80/291.53 nonZero :: 0':s -> false:true 307.80/291.53 0' :: 0':s 307.80/291.53 false :: false:true 307.80/291.53 s :: 0':s -> 0':s 307.80/291.53 true :: false:true 307.80/291.53 p :: 0':s -> 0':s 307.80/291.53 id_inc :: 0':s -> 0':s 307.80/291.53 random :: 0':s -> 0':s 307.80/291.53 rand :: 0':s -> 0':s -> 0':s 307.80/291.53 if :: false:true -> 0':s -> 0':s -> 0':s 307.80/291.53 hole_false:true1_0 :: false:true 307.80/291.53 hole_0':s2_0 :: 0':s 307.80/291.53 gen_0':s3_0 :: Nat -> 0':s 307.80/291.53 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (5) OrderProof (LOWER BOUND(ID)) 307.80/291.53 Heuristically decided to analyse the following defined symbols: 307.80/291.53 p, rand 307.80/291.53 307.80/291.53 They will be analysed ascendingly in the following order: 307.80/291.53 p < rand 307.80/291.53 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (6) 307.80/291.53 Obligation: 307.80/291.53 TRS: 307.80/291.53 Rules: 307.80/291.53 nonZero(0') -> false 307.80/291.53 nonZero(s(x)) -> true 307.80/291.53 p(s(0')) -> 0' 307.80/291.53 p(s(s(x))) -> s(p(s(x))) 307.80/291.53 id_inc(x) -> x 307.80/291.53 id_inc(x) -> s(x) 307.80/291.53 random(x) -> rand(x, 0') 307.80/291.53 rand(x, y) -> if(nonZero(x), x, y) 307.80/291.53 if(false, x, y) -> y 307.80/291.53 if(true, x, y) -> rand(p(x), id_inc(y)) 307.80/291.53 307.80/291.53 Types: 307.80/291.53 nonZero :: 0':s -> false:true 307.80/291.53 0' :: 0':s 307.80/291.53 false :: false:true 307.80/291.53 s :: 0':s -> 0':s 307.80/291.53 true :: false:true 307.80/291.53 p :: 0':s -> 0':s 307.80/291.53 id_inc :: 0':s -> 0':s 307.80/291.53 random :: 0':s -> 0':s 307.80/291.53 rand :: 0':s -> 0':s -> 0':s 307.80/291.53 if :: false:true -> 0':s -> 0':s -> 0':s 307.80/291.53 hole_false:true1_0 :: false:true 307.80/291.53 hole_0':s2_0 :: 0':s 307.80/291.53 gen_0':s3_0 :: Nat -> 0':s 307.80/291.53 307.80/291.53 307.80/291.53 Generator Equations: 307.80/291.53 gen_0':s3_0(0) <=> 0' 307.80/291.53 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 307.80/291.53 307.80/291.53 307.80/291.53 The following defined symbols remain to be analysed: 307.80/291.53 p, rand 307.80/291.53 307.80/291.53 They will be analysed ascendingly in the following order: 307.80/291.53 p < rand 307.80/291.53 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (7) RewriteLemmaProof (LOWER BOUND(ID)) 307.80/291.53 Proved the following rewrite lemma: 307.80/291.53 p(gen_0':s3_0(+(1, n5_0))) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0) 307.80/291.53 307.80/291.53 Induction Base: 307.80/291.53 p(gen_0':s3_0(+(1, 0))) ->_R^Omega(1) 307.80/291.53 0' 307.80/291.53 307.80/291.53 Induction Step: 307.80/291.53 p(gen_0':s3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1) 307.80/291.53 s(p(s(gen_0':s3_0(n5_0)))) ->_IH 307.80/291.53 s(gen_0':s3_0(c6_0)) 307.80/291.53 307.80/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (8) 307.80/291.53 Complex Obligation (BEST) 307.80/291.53 307.80/291.53 ---------------------------------------- 307.80/291.53 307.80/291.53 (9) 307.80/291.53 Obligation: 307.80/291.53 Proved the lower bound n^1 for the following obligation: 307.80/291.53 307.80/291.53 TRS: 307.80/291.53 Rules: 307.80/291.53 nonZero(0') -> false 307.80/291.53 nonZero(s(x)) -> true 307.80/291.53 p(s(0')) -> 0' 307.80/291.53 p(s(s(x))) -> s(p(s(x))) 307.80/291.53 id_inc(x) -> x 307.80/291.53 id_inc(x) -> s(x) 307.80/291.53 random(x) -> rand(x, 0') 307.80/291.53 rand(x, y) -> if(nonZero(x), x, y) 307.80/291.53 if(false, x, y) -> y 307.80/291.53 if(true, x, y) -> rand(p(x), id_inc(y)) 307.80/291.53 307.80/291.53 Types: 307.80/291.53 nonZero :: 0':s -> false:true 307.80/291.53 0' :: 0':s 307.80/291.53 false :: false:true 307.80/291.53 s :: 0':s -> 0':s 307.80/291.53 true :: false:true 307.80/291.53 p :: 0':s -> 0':s 307.80/291.53 id_inc :: 0':s -> 0':s 307.80/291.53 random :: 0':s -> 0':s 307.80/291.53 rand :: 0':s -> 0':s -> 0':s 307.80/291.53 if :: false:true -> 0':s -> 0':s -> 0':s 307.80/291.53 hole_false:true1_0 :: false:true 307.80/291.53 hole_0':s2_0 :: 0':s 307.80/291.53 gen_0':s3_0 :: Nat -> 0':s 307.80/291.53 307.80/291.53 307.80/291.53 Generator Equations: 307.80/291.53 gen_0':s3_0(0) <=> 0' 307.80/291.53 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 307.80/291.53 307.80/291.53 307.80/291.53 The following defined symbols remain to be analysed: 307.80/291.53 p, rand 307.80/291.53 307.80/291.53 They will be analysed ascendingly in the following order: 307.92/291.53 p < rand 307.92/291.53 307.92/291.53 ---------------------------------------- 307.92/291.53 307.92/291.53 (10) LowerBoundPropagationProof (FINISHED) 307.92/291.53 Propagated lower bound. 307.92/291.53 ---------------------------------------- 307.92/291.53 307.92/291.53 (11) 307.92/291.53 BOUNDS(n^1, INF) 307.92/291.53 307.92/291.53 ---------------------------------------- 307.92/291.53 307.92/291.53 (12) 307.92/291.53 Obligation: 307.92/291.53 TRS: 307.92/291.53 Rules: 307.92/291.53 nonZero(0') -> false 307.92/291.53 nonZero(s(x)) -> true 307.92/291.53 p(s(0')) -> 0' 307.92/291.53 p(s(s(x))) -> s(p(s(x))) 307.92/291.53 id_inc(x) -> x 307.92/291.53 id_inc(x) -> s(x) 307.92/291.53 random(x) -> rand(x, 0') 307.92/291.53 rand(x, y) -> if(nonZero(x), x, y) 307.92/291.53 if(false, x, y) -> y 307.92/291.53 if(true, x, y) -> rand(p(x), id_inc(y)) 307.92/291.53 307.92/291.53 Types: 307.92/291.53 nonZero :: 0':s -> false:true 307.92/291.53 0' :: 0':s 307.92/291.53 false :: false:true 307.92/291.53 s :: 0':s -> 0':s 307.92/291.53 true :: false:true 307.92/291.53 p :: 0':s -> 0':s 307.92/291.53 id_inc :: 0':s -> 0':s 307.92/291.53 random :: 0':s -> 0':s 307.92/291.53 rand :: 0':s -> 0':s -> 0':s 307.92/291.53 if :: false:true -> 0':s -> 0':s -> 0':s 307.92/291.53 hole_false:true1_0 :: false:true 307.92/291.53 hole_0':s2_0 :: 0':s 307.92/291.53 gen_0':s3_0 :: Nat -> 0':s 307.92/291.53 307.92/291.53 307.92/291.53 Lemmas: 307.92/291.53 p(gen_0':s3_0(+(1, n5_0))) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0) 307.92/291.53 307.92/291.53 307.92/291.53 Generator Equations: 307.92/291.53 gen_0':s3_0(0) <=> 0' 307.92/291.53 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 307.92/291.53 307.92/291.53 307.92/291.53 The following defined symbols remain to be analysed: 307.92/291.53 rand 307.92/291.53 ---------------------------------------- 307.92/291.53 307.92/291.53 (13) RewriteLemmaProof (LOWER BOUND(ID)) 307.92/291.53 Proved the following rewrite lemma: 307.92/291.53 rand(gen_0':s3_0(n198_0), gen_0':s3_0(b)) -> gen_0':s3_0(b), rt in Omega(1 + n198_0 + n198_0^2) 307.92/291.53 307.92/291.53 Induction Base: 307.92/291.53 rand(gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1) 307.92/291.53 if(nonZero(gen_0':s3_0(0)), gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1) 307.92/291.53 if(false, gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1) 307.92/291.53 gen_0':s3_0(b) 307.92/291.53 307.92/291.53 Induction Step: 307.92/291.53 rand(gen_0':s3_0(+(n198_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1) 307.92/291.53 if(nonZero(gen_0':s3_0(+(n198_0, 1))), gen_0':s3_0(+(n198_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1) 307.92/291.53 if(true, gen_0':s3_0(+(1, n198_0)), gen_0':s3_0(b)) ->_R^Omega(1) 307.92/291.53 rand(p(gen_0':s3_0(+(1, n198_0))), id_inc(gen_0':s3_0(b))) ->_L^Omega(1 + n198_0) 307.92/291.53 rand(gen_0':s3_0(n198_0), id_inc(gen_0':s3_0(b))) ->_R^Omega(1) 307.92/291.53 rand(gen_0':s3_0(n198_0), gen_0':s3_0(b)) ->_IH 307.92/291.53 gen_0':s3_0(b) 307.92/291.53 307.92/291.53 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 307.92/291.53 ---------------------------------------- 307.92/291.53 307.92/291.53 (14) 307.92/291.53 Obligation: 307.92/291.53 Proved the lower bound n^2 for the following obligation: 307.92/291.53 307.92/291.53 TRS: 307.92/291.53 Rules: 307.92/291.53 nonZero(0') -> false 307.92/291.53 nonZero(s(x)) -> true 307.92/291.53 p(s(0')) -> 0' 307.92/291.53 p(s(s(x))) -> s(p(s(x))) 307.92/291.53 id_inc(x) -> x 307.92/291.53 id_inc(x) -> s(x) 307.92/291.53 random(x) -> rand(x, 0') 307.92/291.53 rand(x, y) -> if(nonZero(x), x, y) 307.92/291.53 if(false, x, y) -> y 307.92/291.53 if(true, x, y) -> rand(p(x), id_inc(y)) 307.92/291.53 307.92/291.53 Types: 307.92/291.53 nonZero :: 0':s -> false:true 307.92/291.53 0' :: 0':s 307.92/291.53 false :: false:true 307.92/291.53 s :: 0':s -> 0':s 307.92/291.53 true :: false:true 307.92/291.53 p :: 0':s -> 0':s 307.92/291.53 id_inc :: 0':s -> 0':s 307.92/291.53 random :: 0':s -> 0':s 307.92/291.53 rand :: 0':s -> 0':s -> 0':s 307.92/291.53 if :: false:true -> 0':s -> 0':s -> 0':s 307.92/291.53 hole_false:true1_0 :: false:true 307.92/291.53 hole_0':s2_0 :: 0':s 307.92/291.53 gen_0':s3_0 :: Nat -> 0':s 307.92/291.53 307.92/291.53 307.92/291.53 Lemmas: 307.92/291.53 p(gen_0':s3_0(+(1, n5_0))) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0) 307.92/291.53 307.92/291.53 307.92/291.53 Generator Equations: 307.92/291.53 gen_0':s3_0(0) <=> 0' 307.92/291.53 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 307.92/291.53 307.92/291.53 307.92/291.53 The following defined symbols remain to be analysed: 307.92/291.53 rand 307.92/291.53 ---------------------------------------- 307.92/291.53 307.92/291.53 (15) LowerBoundPropagationProof (FINISHED) 307.92/291.53 Propagated lower bound. 307.92/291.53 ---------------------------------------- 307.92/291.53 307.92/291.53 (16) 307.92/291.53 BOUNDS(n^2, INF) 307.92/291.56 EOF