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