305.88/292.10 WORST_CASE(Omega(n^1), ?) 305.88/292.11 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 305.88/292.11 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 305.88/292.11 305.88/292.11 305.88/292.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 305.88/292.11 305.88/292.11 (0) CpxTRS 305.88/292.11 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 305.88/292.11 (2) CpxTRS 305.88/292.11 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 305.88/292.11 (4) CpxTRS 305.88/292.11 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 305.88/292.11 (6) typed CpxTrs 305.88/292.11 (7) OrderProof [LOWER BOUND(ID), 0 ms] 305.88/292.11 (8) typed CpxTrs 305.88/292.11 (9) RewriteLemmaProof [LOWER BOUND(ID), 331 ms] 305.88/292.11 (10) BEST 305.88/292.11 (11) proven lower bound 305.88/292.11 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 305.88/292.11 (13) BOUNDS(n^1, INF) 305.88/292.11 (14) typed CpxTrs 305.88/292.11 (15) RewriteLemmaProof [LOWER BOUND(ID), 43 ms] 305.88/292.11 (16) typed CpxTrs 305.88/292.11 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (0) 305.88/292.11 Obligation: 305.88/292.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 305.88/292.11 305.88/292.11 305.88/292.11 The TRS R consists of the following rules: 305.88/292.11 305.88/292.11 half(0) -> 0 305.88/292.11 half(s(0)) -> 0 305.88/292.11 half(s(s(x))) -> s(half(x)) 305.88/292.11 lastbit(0) -> 0 305.88/292.11 lastbit(s(0)) -> s(0) 305.88/292.11 lastbit(s(s(x))) -> lastbit(x) 305.88/292.11 zero(0) -> true 305.88/292.11 zero(s(x)) -> false 305.88/292.11 conv(x) -> conviter(x, cons(0, nil)) 305.88/292.11 conviter(x, l) -> if(zero(x), x, l) 305.88/292.11 if(true, x, l) -> l 305.88/292.11 if(false, x, l) -> conviter(half(x), cons(lastbit(x), l)) 305.88/292.11 305.88/292.11 S is empty. 305.88/292.11 Rewrite Strategy: FULL 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 305.88/292.11 Renamed function symbols to avoid clashes with predefined symbol. 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (2) 305.88/292.11 Obligation: 305.88/292.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 305.88/292.11 305.88/292.11 305.88/292.11 The TRS R consists of the following rules: 305.88/292.11 305.88/292.11 half(0') -> 0' 305.88/292.11 half(s(0')) -> 0' 305.88/292.11 half(s(s(x))) -> s(half(x)) 305.88/292.11 lastbit(0') -> 0' 305.88/292.11 lastbit(s(0')) -> s(0') 305.88/292.11 lastbit(s(s(x))) -> lastbit(x) 305.88/292.11 zero(0') -> true 305.88/292.11 zero(s(x)) -> false 305.88/292.11 conv(x) -> conviter(x, cons(0', nil)) 305.88/292.11 conviter(x, l) -> if(zero(x), x, l) 305.88/292.11 if(true, x, l) -> l 305.88/292.11 if(false, x, l) -> conviter(half(x), cons(lastbit(x), l)) 305.88/292.11 305.88/292.11 S is empty. 305.88/292.11 Rewrite Strategy: FULL 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (3) SlicingProof (LOWER BOUND(ID)) 305.88/292.11 Sliced the following arguments: 305.88/292.11 cons/1 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (4) 305.88/292.11 Obligation: 305.88/292.11 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 305.88/292.11 305.88/292.11 305.88/292.11 The TRS R consists of the following rules: 305.88/292.11 305.88/292.11 half(0') -> 0' 305.88/292.11 half(s(0')) -> 0' 305.88/292.11 half(s(s(x))) -> s(half(x)) 305.88/292.11 lastbit(0') -> 0' 305.88/292.11 lastbit(s(0')) -> s(0') 305.88/292.11 lastbit(s(s(x))) -> lastbit(x) 305.88/292.11 zero(0') -> true 305.88/292.11 zero(s(x)) -> false 305.88/292.11 conv(x) -> conviter(x, cons(0')) 305.88/292.11 conviter(x, l) -> if(zero(x), x, l) 305.88/292.11 if(true, x, l) -> l 305.88/292.11 if(false, x, l) -> conviter(half(x), cons(lastbit(x))) 305.88/292.11 305.88/292.11 S is empty. 305.88/292.11 Rewrite Strategy: FULL 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 305.88/292.11 Infered types. 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (6) 305.88/292.11 Obligation: 305.88/292.11 TRS: 305.88/292.11 Rules: 305.88/292.11 half(0') -> 0' 305.88/292.11 half(s(0')) -> 0' 305.88/292.11 half(s(s(x))) -> s(half(x)) 305.88/292.11 lastbit(0') -> 0' 305.88/292.11 lastbit(s(0')) -> s(0') 305.88/292.11 lastbit(s(s(x))) -> lastbit(x) 305.88/292.11 zero(0') -> true 305.88/292.11 zero(s(x)) -> false 305.88/292.11 conv(x) -> conviter(x, cons(0')) 305.88/292.11 conviter(x, l) -> if(zero(x), x, l) 305.88/292.11 if(true, x, l) -> l 305.88/292.11 if(false, x, l) -> conviter(half(x), cons(lastbit(x))) 305.88/292.11 305.88/292.11 Types: 305.88/292.11 half :: 0':s -> 0':s 305.88/292.11 0' :: 0':s 305.88/292.11 s :: 0':s -> 0':s 305.88/292.11 lastbit :: 0':s -> 0':s 305.88/292.11 zero :: 0':s -> true:false 305.88/292.11 true :: true:false 305.88/292.11 false :: true:false 305.88/292.11 conv :: 0':s -> cons 305.88/292.11 conviter :: 0':s -> cons -> cons 305.88/292.11 cons :: 0':s -> cons 305.88/292.11 if :: true:false -> 0':s -> cons -> cons 305.88/292.11 hole_0':s1_0 :: 0':s 305.88/292.11 hole_true:false2_0 :: true:false 305.88/292.11 hole_cons3_0 :: cons 305.88/292.11 gen_0':s4_0 :: Nat -> 0':s 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (7) OrderProof (LOWER BOUND(ID)) 305.88/292.11 Heuristically decided to analyse the following defined symbols: 305.88/292.11 half, lastbit, conviter 305.88/292.11 305.88/292.11 They will be analysed ascendingly in the following order: 305.88/292.11 half < conviter 305.88/292.11 lastbit < conviter 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (8) 305.88/292.11 Obligation: 305.88/292.11 TRS: 305.88/292.11 Rules: 305.88/292.11 half(0') -> 0' 305.88/292.11 half(s(0')) -> 0' 305.88/292.11 half(s(s(x))) -> s(half(x)) 305.88/292.11 lastbit(0') -> 0' 305.88/292.11 lastbit(s(0')) -> s(0') 305.88/292.11 lastbit(s(s(x))) -> lastbit(x) 305.88/292.11 zero(0') -> true 305.88/292.11 zero(s(x)) -> false 305.88/292.11 conv(x) -> conviter(x, cons(0')) 305.88/292.11 conviter(x, l) -> if(zero(x), x, l) 305.88/292.11 if(true, x, l) -> l 305.88/292.11 if(false, x, l) -> conviter(half(x), cons(lastbit(x))) 305.88/292.11 305.88/292.11 Types: 305.88/292.11 half :: 0':s -> 0':s 305.88/292.11 0' :: 0':s 305.88/292.11 s :: 0':s -> 0':s 305.88/292.11 lastbit :: 0':s -> 0':s 305.88/292.11 zero :: 0':s -> true:false 305.88/292.11 true :: true:false 305.88/292.11 false :: true:false 305.88/292.11 conv :: 0':s -> cons 305.88/292.11 conviter :: 0':s -> cons -> cons 305.88/292.11 cons :: 0':s -> cons 305.88/292.11 if :: true:false -> 0':s -> cons -> cons 305.88/292.11 hole_0':s1_0 :: 0':s 305.88/292.11 hole_true:false2_0 :: true:false 305.88/292.11 hole_cons3_0 :: cons 305.88/292.11 gen_0':s4_0 :: Nat -> 0':s 305.88/292.11 305.88/292.11 305.88/292.11 Generator Equations: 305.88/292.11 gen_0':s4_0(0) <=> 0' 305.88/292.11 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 305.88/292.11 305.88/292.11 305.88/292.11 The following defined symbols remain to be analysed: 305.88/292.11 half, lastbit, conviter 305.88/292.11 305.88/292.11 They will be analysed ascendingly in the following order: 305.88/292.11 half < conviter 305.88/292.11 lastbit < conviter 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (9) RewriteLemmaProof (LOWER BOUND(ID)) 305.88/292.11 Proved the following rewrite lemma: 305.88/292.11 half(gen_0':s4_0(*(2, n6_0))) -> gen_0':s4_0(n6_0), rt in Omega(1 + n6_0) 305.88/292.11 305.88/292.11 Induction Base: 305.88/292.11 half(gen_0':s4_0(*(2, 0))) ->_R^Omega(1) 305.88/292.11 0' 305.88/292.11 305.88/292.11 Induction Step: 305.88/292.11 half(gen_0':s4_0(*(2, +(n6_0, 1)))) ->_R^Omega(1) 305.88/292.11 s(half(gen_0':s4_0(*(2, n6_0)))) ->_IH 305.88/292.11 s(gen_0':s4_0(c7_0)) 305.88/292.11 305.88/292.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (10) 305.88/292.11 Complex Obligation (BEST) 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (11) 305.88/292.11 Obligation: 305.88/292.11 Proved the lower bound n^1 for the following obligation: 305.88/292.11 305.88/292.11 TRS: 305.88/292.11 Rules: 305.88/292.11 half(0') -> 0' 305.88/292.11 half(s(0')) -> 0' 305.88/292.11 half(s(s(x))) -> s(half(x)) 305.88/292.11 lastbit(0') -> 0' 305.88/292.11 lastbit(s(0')) -> s(0') 305.88/292.11 lastbit(s(s(x))) -> lastbit(x) 305.88/292.11 zero(0') -> true 305.88/292.11 zero(s(x)) -> false 305.88/292.11 conv(x) -> conviter(x, cons(0')) 305.88/292.11 conviter(x, l) -> if(zero(x), x, l) 305.88/292.11 if(true, x, l) -> l 305.88/292.11 if(false, x, l) -> conviter(half(x), cons(lastbit(x))) 305.88/292.11 305.88/292.11 Types: 305.88/292.11 half :: 0':s -> 0':s 305.88/292.11 0' :: 0':s 305.88/292.11 s :: 0':s -> 0':s 305.88/292.11 lastbit :: 0':s -> 0':s 305.88/292.11 zero :: 0':s -> true:false 305.88/292.11 true :: true:false 305.88/292.11 false :: true:false 305.88/292.11 conv :: 0':s -> cons 305.88/292.11 conviter :: 0':s -> cons -> cons 305.88/292.11 cons :: 0':s -> cons 305.88/292.11 if :: true:false -> 0':s -> cons -> cons 305.88/292.11 hole_0':s1_0 :: 0':s 305.88/292.11 hole_true:false2_0 :: true:false 305.88/292.11 hole_cons3_0 :: cons 305.88/292.11 gen_0':s4_0 :: Nat -> 0':s 305.88/292.11 305.88/292.11 305.88/292.11 Generator Equations: 305.88/292.11 gen_0':s4_0(0) <=> 0' 305.88/292.11 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 305.88/292.11 305.88/292.11 305.88/292.11 The following defined symbols remain to be analysed: 305.88/292.11 half, lastbit, conviter 305.88/292.11 305.88/292.11 They will be analysed ascendingly in the following order: 305.88/292.11 half < conviter 305.88/292.11 lastbit < conviter 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (12) LowerBoundPropagationProof (FINISHED) 305.88/292.11 Propagated lower bound. 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (13) 305.88/292.11 BOUNDS(n^1, INF) 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (14) 305.88/292.11 Obligation: 305.88/292.11 TRS: 305.88/292.11 Rules: 305.88/292.11 half(0') -> 0' 305.88/292.11 half(s(0')) -> 0' 305.88/292.11 half(s(s(x))) -> s(half(x)) 305.88/292.11 lastbit(0') -> 0' 305.88/292.11 lastbit(s(0')) -> s(0') 305.88/292.11 lastbit(s(s(x))) -> lastbit(x) 305.88/292.11 zero(0') -> true 305.88/292.11 zero(s(x)) -> false 305.88/292.11 conv(x) -> conviter(x, cons(0')) 305.88/292.11 conviter(x, l) -> if(zero(x), x, l) 305.88/292.11 if(true, x, l) -> l 305.88/292.11 if(false, x, l) -> conviter(half(x), cons(lastbit(x))) 305.88/292.11 305.88/292.11 Types: 305.88/292.11 half :: 0':s -> 0':s 305.88/292.11 0' :: 0':s 305.88/292.11 s :: 0':s -> 0':s 305.88/292.11 lastbit :: 0':s -> 0':s 305.88/292.11 zero :: 0':s -> true:false 305.88/292.11 true :: true:false 305.88/292.11 false :: true:false 305.88/292.11 conv :: 0':s -> cons 305.88/292.11 conviter :: 0':s -> cons -> cons 305.88/292.11 cons :: 0':s -> cons 305.88/292.11 if :: true:false -> 0':s -> cons -> cons 305.88/292.11 hole_0':s1_0 :: 0':s 305.88/292.11 hole_true:false2_0 :: true:false 305.88/292.11 hole_cons3_0 :: cons 305.88/292.11 gen_0':s4_0 :: Nat -> 0':s 305.88/292.11 305.88/292.11 305.88/292.11 Lemmas: 305.88/292.11 half(gen_0':s4_0(*(2, n6_0))) -> gen_0':s4_0(n6_0), rt in Omega(1 + n6_0) 305.88/292.11 305.88/292.11 305.88/292.11 Generator Equations: 305.88/292.11 gen_0':s4_0(0) <=> 0' 305.88/292.11 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 305.88/292.11 305.88/292.11 305.88/292.11 The following defined symbols remain to be analysed: 305.88/292.11 lastbit, conviter 305.88/292.11 305.88/292.11 They will be analysed ascendingly in the following order: 305.88/292.11 lastbit < conviter 305.88/292.11 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (15) RewriteLemmaProof (LOWER BOUND(ID)) 305.88/292.11 Proved the following rewrite lemma: 305.88/292.11 lastbit(gen_0':s4_0(*(2, n308_0))) -> gen_0':s4_0(0), rt in Omega(1 + n308_0) 305.88/292.11 305.88/292.11 Induction Base: 305.88/292.11 lastbit(gen_0':s4_0(*(2, 0))) ->_R^Omega(1) 305.88/292.11 0' 305.88/292.11 305.88/292.11 Induction Step: 305.88/292.11 lastbit(gen_0':s4_0(*(2, +(n308_0, 1)))) ->_R^Omega(1) 305.88/292.11 lastbit(gen_0':s4_0(*(2, n308_0))) ->_IH 305.88/292.11 gen_0':s4_0(0) 305.88/292.11 305.88/292.11 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 305.88/292.11 ---------------------------------------- 305.88/292.11 305.88/292.11 (16) 305.88/292.11 Obligation: 305.88/292.11 TRS: 305.88/292.11 Rules: 305.88/292.11 half(0') -> 0' 305.88/292.11 half(s(0')) -> 0' 305.88/292.11 half(s(s(x))) -> s(half(x)) 305.88/292.11 lastbit(0') -> 0' 305.88/292.11 lastbit(s(0')) -> s(0') 305.88/292.11 lastbit(s(s(x))) -> lastbit(x) 305.88/292.11 zero(0') -> true 305.88/292.11 zero(s(x)) -> false 305.88/292.11 conv(x) -> conviter(x, cons(0')) 305.88/292.11 conviter(x, l) -> if(zero(x), x, l) 305.88/292.11 if(true, x, l) -> l 305.88/292.11 if(false, x, l) -> conviter(half(x), cons(lastbit(x))) 305.88/292.11 305.88/292.11 Types: 305.88/292.11 half :: 0':s -> 0':s 305.88/292.11 0' :: 0':s 305.88/292.11 s :: 0':s -> 0':s 305.88/292.11 lastbit :: 0':s -> 0':s 305.88/292.11 zero :: 0':s -> true:false 305.88/292.11 true :: true:false 305.88/292.11 false :: true:false 305.88/292.11 conv :: 0':s -> cons 305.88/292.11 conviter :: 0':s -> cons -> cons 305.88/292.11 cons :: 0':s -> cons 305.88/292.11 if :: true:false -> 0':s -> cons -> cons 305.88/292.11 hole_0':s1_0 :: 0':s 305.88/292.11 hole_true:false2_0 :: true:false 305.88/292.11 hole_cons3_0 :: cons 305.88/292.11 gen_0':s4_0 :: Nat -> 0':s 305.88/292.11 305.88/292.11 305.88/292.11 Lemmas: 305.88/292.11 half(gen_0':s4_0(*(2, n6_0))) -> gen_0':s4_0(n6_0), rt in Omega(1 + n6_0) 305.88/292.11 lastbit(gen_0':s4_0(*(2, n308_0))) -> gen_0':s4_0(0), rt in Omega(1 + n308_0) 305.88/292.11 305.88/292.11 305.88/292.11 Generator Equations: 305.88/292.11 gen_0':s4_0(0) <=> 0' 305.88/292.11 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 305.88/292.11 305.88/292.11 305.88/292.11 The following defined symbols remain to be analysed: 305.88/292.11 conviter 305.98/292.15 EOF