304.58/291.47 WORST_CASE(Omega(n^1), ?) 304.58/291.48 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 304.58/291.48 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 304.58/291.48 304.58/291.48 304.58/291.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 304.58/291.48 304.58/291.48 (0) CpxTRS 304.58/291.48 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 304.58/291.48 (2) CpxTRS 304.58/291.48 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 304.58/291.48 (4) typed CpxTrs 304.58/291.48 (5) OrderProof [LOWER BOUND(ID), 0 ms] 304.58/291.48 (6) typed CpxTrs 304.58/291.48 (7) RewriteLemmaProof [LOWER BOUND(ID), 317 ms] 304.58/291.48 (8) BEST 304.58/291.48 (9) proven lower bound 304.58/291.48 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 304.58/291.48 (11) BOUNDS(n^1, INF) 304.58/291.48 (12) typed CpxTrs 304.58/291.48 304.58/291.48 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (0) 304.58/291.48 Obligation: 304.58/291.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 304.58/291.48 304.58/291.48 304.58/291.48 The TRS R consists of the following rules: 304.58/291.48 304.58/291.48 p(s(x)) -> x 304.58/291.48 p(0) -> 0 304.58/291.48 le(0, y) -> true 304.58/291.48 le(s(x), 0) -> false 304.58/291.48 le(s(x), s(y)) -> le(x, y) 304.58/291.48 average(x, y) -> if(le(x, 0), le(y, 0), le(y, s(0)), le(y, s(s(0))), x, y) 304.58/291.48 if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) 304.58/291.48 if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) 304.58/291.48 if2(true, b2, b3, x, y) -> 0 304.58/291.48 if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) 304.58/291.48 if3(true, b3, x, y) -> 0 304.58/291.48 if3(false, b3, x, y) -> if4(b3, x, y) 304.58/291.48 if4(true, x, y) -> s(0) 304.58/291.48 if4(false, x, y) -> average(s(x), p(p(y))) 304.58/291.48 304.58/291.48 S is empty. 304.58/291.48 Rewrite Strategy: FULL 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 304.58/291.48 Renamed function symbols to avoid clashes with predefined symbol. 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (2) 304.58/291.48 Obligation: 304.58/291.48 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 304.58/291.48 304.58/291.48 304.58/291.48 The TRS R consists of the following rules: 304.58/291.48 304.58/291.48 p(s(x)) -> x 304.58/291.48 p(0') -> 0' 304.58/291.48 le(0', y) -> true 304.58/291.48 le(s(x), 0') -> false 304.58/291.48 le(s(x), s(y)) -> le(x, y) 304.58/291.48 average(x, y) -> if(le(x, 0'), le(y, 0'), le(y, s(0')), le(y, s(s(0'))), x, y) 304.58/291.48 if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) 304.58/291.48 if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) 304.58/291.48 if2(true, b2, b3, x, y) -> 0' 304.58/291.48 if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) 304.58/291.48 if3(true, b3, x, y) -> 0' 304.58/291.48 if3(false, b3, x, y) -> if4(b3, x, y) 304.58/291.48 if4(true, x, y) -> s(0') 304.58/291.48 if4(false, x, y) -> average(s(x), p(p(y))) 304.58/291.48 304.58/291.48 S is empty. 304.58/291.48 Rewrite Strategy: FULL 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 304.58/291.48 Infered types. 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (4) 304.58/291.48 Obligation: 304.58/291.48 TRS: 304.58/291.48 Rules: 304.58/291.48 p(s(x)) -> x 304.58/291.48 p(0') -> 0' 304.58/291.48 le(0', y) -> true 304.58/291.48 le(s(x), 0') -> false 304.58/291.48 le(s(x), s(y)) -> le(x, y) 304.58/291.48 average(x, y) -> if(le(x, 0'), le(y, 0'), le(y, s(0')), le(y, s(s(0'))), x, y) 304.58/291.48 if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) 304.58/291.48 if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) 304.58/291.48 if2(true, b2, b3, x, y) -> 0' 304.58/291.48 if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) 304.58/291.48 if3(true, b3, x, y) -> 0' 304.58/291.48 if3(false, b3, x, y) -> if4(b3, x, y) 304.58/291.48 if4(true, x, y) -> s(0') 304.58/291.48 if4(false, x, y) -> average(s(x), p(p(y))) 304.58/291.48 304.58/291.48 Types: 304.58/291.48 p :: s:0' -> s:0' 304.58/291.48 s :: s:0' -> s:0' 304.58/291.48 0' :: s:0' 304.58/291.48 le :: s:0' -> s:0' -> true:false 304.58/291.48 true :: true:false 304.58/291.48 false :: true:false 304.58/291.48 average :: s:0' -> s:0' -> s:0' 304.58/291.48 if :: true:false -> true:false -> true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if2 :: true:false -> true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if3 :: true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if4 :: true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 hole_s:0'1_0 :: s:0' 304.58/291.48 hole_true:false2_0 :: true:false 304.58/291.48 gen_s:0'3_0 :: Nat -> s:0' 304.58/291.48 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (5) OrderProof (LOWER BOUND(ID)) 304.58/291.48 Heuristically decided to analyse the following defined symbols: 304.58/291.48 le, average 304.58/291.48 304.58/291.48 They will be analysed ascendingly in the following order: 304.58/291.48 le < average 304.58/291.48 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (6) 304.58/291.48 Obligation: 304.58/291.48 TRS: 304.58/291.48 Rules: 304.58/291.48 p(s(x)) -> x 304.58/291.48 p(0') -> 0' 304.58/291.48 le(0', y) -> true 304.58/291.48 le(s(x), 0') -> false 304.58/291.48 le(s(x), s(y)) -> le(x, y) 304.58/291.48 average(x, y) -> if(le(x, 0'), le(y, 0'), le(y, s(0')), le(y, s(s(0'))), x, y) 304.58/291.48 if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) 304.58/291.48 if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) 304.58/291.48 if2(true, b2, b3, x, y) -> 0' 304.58/291.48 if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) 304.58/291.48 if3(true, b3, x, y) -> 0' 304.58/291.48 if3(false, b3, x, y) -> if4(b3, x, y) 304.58/291.48 if4(true, x, y) -> s(0') 304.58/291.48 if4(false, x, y) -> average(s(x), p(p(y))) 304.58/291.48 304.58/291.48 Types: 304.58/291.48 p :: s:0' -> s:0' 304.58/291.48 s :: s:0' -> s:0' 304.58/291.48 0' :: s:0' 304.58/291.48 le :: s:0' -> s:0' -> true:false 304.58/291.48 true :: true:false 304.58/291.48 false :: true:false 304.58/291.48 average :: s:0' -> s:0' -> s:0' 304.58/291.48 if :: true:false -> true:false -> true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if2 :: true:false -> true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if3 :: true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if4 :: true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 hole_s:0'1_0 :: s:0' 304.58/291.48 hole_true:false2_0 :: true:false 304.58/291.48 gen_s:0'3_0 :: Nat -> s:0' 304.58/291.48 304.58/291.48 304.58/291.48 Generator Equations: 304.58/291.48 gen_s:0'3_0(0) <=> 0' 304.58/291.48 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 304.58/291.48 304.58/291.48 304.58/291.48 The following defined symbols remain to be analysed: 304.58/291.48 le, average 304.58/291.48 304.58/291.48 They will be analysed ascendingly in the following order: 304.58/291.48 le < average 304.58/291.48 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (7) RewriteLemmaProof (LOWER BOUND(ID)) 304.58/291.48 Proved the following rewrite lemma: 304.58/291.48 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 304.58/291.48 304.58/291.48 Induction Base: 304.58/291.48 le(gen_s:0'3_0(0), gen_s:0'3_0(0)) ->_R^Omega(1) 304.58/291.48 true 304.58/291.48 304.58/291.48 Induction Step: 304.58/291.48 le(gen_s:0'3_0(+(n5_0, 1)), gen_s:0'3_0(+(n5_0, 1))) ->_R^Omega(1) 304.58/291.48 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) ->_IH 304.58/291.48 true 304.58/291.48 304.58/291.48 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (8) 304.58/291.48 Complex Obligation (BEST) 304.58/291.48 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (9) 304.58/291.48 Obligation: 304.58/291.48 Proved the lower bound n^1 for the following obligation: 304.58/291.48 304.58/291.48 TRS: 304.58/291.48 Rules: 304.58/291.48 p(s(x)) -> x 304.58/291.48 p(0') -> 0' 304.58/291.48 le(0', y) -> true 304.58/291.48 le(s(x), 0') -> false 304.58/291.48 le(s(x), s(y)) -> le(x, y) 304.58/291.48 average(x, y) -> if(le(x, 0'), le(y, 0'), le(y, s(0')), le(y, s(s(0'))), x, y) 304.58/291.48 if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) 304.58/291.48 if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) 304.58/291.48 if2(true, b2, b3, x, y) -> 0' 304.58/291.48 if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) 304.58/291.48 if3(true, b3, x, y) -> 0' 304.58/291.48 if3(false, b3, x, y) -> if4(b3, x, y) 304.58/291.48 if4(true, x, y) -> s(0') 304.58/291.48 if4(false, x, y) -> average(s(x), p(p(y))) 304.58/291.48 304.58/291.48 Types: 304.58/291.48 p :: s:0' -> s:0' 304.58/291.48 s :: s:0' -> s:0' 304.58/291.48 0' :: s:0' 304.58/291.48 le :: s:0' -> s:0' -> true:false 304.58/291.48 true :: true:false 304.58/291.48 false :: true:false 304.58/291.48 average :: s:0' -> s:0' -> s:0' 304.58/291.48 if :: true:false -> true:false -> true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if2 :: true:false -> true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if3 :: true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if4 :: true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 hole_s:0'1_0 :: s:0' 304.58/291.48 hole_true:false2_0 :: true:false 304.58/291.48 gen_s:0'3_0 :: Nat -> s:0' 304.58/291.48 304.58/291.48 304.58/291.48 Generator Equations: 304.58/291.48 gen_s:0'3_0(0) <=> 0' 304.58/291.48 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 304.58/291.48 304.58/291.48 304.58/291.48 The following defined symbols remain to be analysed: 304.58/291.48 le, average 304.58/291.48 304.58/291.48 They will be analysed ascendingly in the following order: 304.58/291.48 le < average 304.58/291.48 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (10) LowerBoundPropagationProof (FINISHED) 304.58/291.48 Propagated lower bound. 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (11) 304.58/291.48 BOUNDS(n^1, INF) 304.58/291.48 304.58/291.48 ---------------------------------------- 304.58/291.48 304.58/291.48 (12) 304.58/291.48 Obligation: 304.58/291.48 TRS: 304.58/291.48 Rules: 304.58/291.48 p(s(x)) -> x 304.58/291.48 p(0') -> 0' 304.58/291.48 le(0', y) -> true 304.58/291.48 le(s(x), 0') -> false 304.58/291.48 le(s(x), s(y)) -> le(x, y) 304.58/291.48 average(x, y) -> if(le(x, 0'), le(y, 0'), le(y, s(0')), le(y, s(s(0'))), x, y) 304.58/291.48 if(true, b1, b2, b3, x, y) -> if2(b1, b2, b3, x, y) 304.58/291.48 if(false, b1, b2, b3, x, y) -> average(p(x), s(y)) 304.58/291.48 if2(true, b2, b3, x, y) -> 0' 304.58/291.48 if2(false, b2, b3, x, y) -> if3(b2, b3, x, y) 304.58/291.48 if3(true, b3, x, y) -> 0' 304.58/291.48 if3(false, b3, x, y) -> if4(b3, x, y) 304.58/291.48 if4(true, x, y) -> s(0') 304.58/291.48 if4(false, x, y) -> average(s(x), p(p(y))) 304.58/291.48 304.58/291.48 Types: 304.58/291.48 p :: s:0' -> s:0' 304.58/291.48 s :: s:0' -> s:0' 304.58/291.48 0' :: s:0' 304.58/291.48 le :: s:0' -> s:0' -> true:false 304.58/291.48 true :: true:false 304.58/291.48 false :: true:false 304.58/291.48 average :: s:0' -> s:0' -> s:0' 304.58/291.48 if :: true:false -> true:false -> true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if2 :: true:false -> true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if3 :: true:false -> true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 if4 :: true:false -> s:0' -> s:0' -> s:0' 304.58/291.48 hole_s:0'1_0 :: s:0' 304.58/291.48 hole_true:false2_0 :: true:false 304.58/291.48 gen_s:0'3_0 :: Nat -> s:0' 304.58/291.48 304.58/291.48 304.58/291.48 Lemmas: 304.58/291.48 le(gen_s:0'3_0(n5_0), gen_s:0'3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 304.58/291.48 304.58/291.48 304.58/291.48 Generator Equations: 304.58/291.48 gen_s:0'3_0(0) <=> 0' 304.58/291.48 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 304.58/291.48 304.58/291.48 304.58/291.48 The following defined symbols remain to be analysed: 304.58/291.48 average 304.58/291.51 EOF