1113.72/291.71 WORST_CASE(Omega(n^1), O(n^2)) 1113.72/291.73 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1113.72/291.73 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1113.72/291.73 1113.72/291.73 1113.72/291.73 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1113.72/291.73 1113.72/291.73 (0) CpxTRS 1113.72/291.73 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1113.72/291.73 (2) CpxWeightedTrs 1113.72/291.73 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1113.72/291.73 (4) CpxTypedWeightedTrs 1113.72/291.73 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1113.72/291.73 (6) CpxTypedWeightedCompleteTrs 1113.72/291.73 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 6 ms] 1113.72/291.73 (8) CpxRNTS 1113.72/291.73 (9) CompleteCoflocoProof [FINISHED, 1823 ms] 1113.72/291.73 (10) BOUNDS(1, n^2) 1113.72/291.73 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1113.72/291.73 (12) CpxTRS 1113.72/291.73 (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1113.72/291.73 (14) typed CpxTrs 1113.72/291.73 (15) OrderProof [LOWER BOUND(ID), 0 ms] 1113.72/291.73 (16) typed CpxTrs 1113.72/291.73 (17) RewriteLemmaProof [LOWER BOUND(ID), 355 ms] 1113.72/291.73 (18) BEST 1113.72/291.73 (19) proven lower bound 1113.72/291.73 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 1113.72/291.73 (21) BOUNDS(n^1, INF) 1113.72/291.73 (22) typed CpxTrs 1113.72/291.73 (23) RewriteLemmaProof [LOWER BOUND(ID), 37 ms] 1113.72/291.73 (24) typed CpxTrs 1113.72/291.73 (25) RewriteLemmaProof [LOWER BOUND(ID), 59 ms] 1113.72/291.73 (26) typed CpxTrs 1113.72/291.73 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (0) 1113.72/291.73 Obligation: 1113.72/291.73 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1113.72/291.73 1113.72/291.73 1113.72/291.73 The TRS R consists of the following rules: 1113.72/291.73 1113.72/291.73 half(0) -> 0 1113.72/291.73 half(s(0)) -> 0 1113.72/291.73 half(s(s(x))) -> s(half(x)) 1113.72/291.73 le(0, y) -> true 1113.72/291.73 le(s(x), 0) -> false 1113.72/291.73 le(s(x), s(y)) -> le(x, y) 1113.72/291.73 inc(s(x)) -> s(inc(x)) 1113.72/291.73 inc(0) -> s(0) 1113.72/291.73 logarithm(x) -> logIter(x, 0) 1113.72/291.73 logIter(x, y) -> if(le(s(0), x), le(s(s(0)), x), half(x), inc(y)) 1113.72/291.73 if(false, b, x, y) -> logZeroError 1113.72/291.73 if(true, false, x, s(y)) -> y 1113.72/291.73 if(true, true, x, y) -> logIter(x, y) 1113.72/291.73 f -> g 1113.72/291.73 f -> h 1113.72/291.73 1113.72/291.73 S is empty. 1113.72/291.73 Rewrite Strategy: INNERMOST 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1113.72/291.73 Transformed relative TRS to weighted TRS 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (2) 1113.72/291.73 Obligation: 1113.72/291.73 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1113.72/291.73 1113.72/291.73 1113.72/291.73 The TRS R consists of the following rules: 1113.72/291.73 1113.72/291.73 half(0) -> 0 [1] 1113.72/291.73 half(s(0)) -> 0 [1] 1113.72/291.73 half(s(s(x))) -> s(half(x)) [1] 1113.72/291.73 le(0, y) -> true [1] 1113.72/291.73 le(s(x), 0) -> false [1] 1113.72/291.73 le(s(x), s(y)) -> le(x, y) [1] 1113.72/291.73 inc(s(x)) -> s(inc(x)) [1] 1113.72/291.73 inc(0) -> s(0) [1] 1113.72/291.73 logarithm(x) -> logIter(x, 0) [1] 1113.72/291.73 logIter(x, y) -> if(le(s(0), x), le(s(s(0)), x), half(x), inc(y)) [1] 1113.72/291.73 if(false, b, x, y) -> logZeroError [1] 1113.72/291.73 if(true, false, x, s(y)) -> y [1] 1113.72/291.73 if(true, true, x, y) -> logIter(x, y) [1] 1113.72/291.73 f -> g [1] 1113.72/291.73 f -> h [1] 1113.72/291.73 1113.72/291.73 Rewrite Strategy: INNERMOST 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1113.72/291.73 Infered types. 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (4) 1113.72/291.73 Obligation: 1113.72/291.73 Runtime Complexity Weighted TRS with Types. 1113.72/291.73 The TRS R consists of the following rules: 1113.72/291.73 1113.72/291.73 half(0) -> 0 [1] 1113.72/291.73 half(s(0)) -> 0 [1] 1113.72/291.73 half(s(s(x))) -> s(half(x)) [1] 1113.72/291.73 le(0, y) -> true [1] 1113.72/291.73 le(s(x), 0) -> false [1] 1113.72/291.73 le(s(x), s(y)) -> le(x, y) [1] 1113.72/291.73 inc(s(x)) -> s(inc(x)) [1] 1113.72/291.73 inc(0) -> s(0) [1] 1113.72/291.73 logarithm(x) -> logIter(x, 0) [1] 1113.72/291.73 logIter(x, y) -> if(le(s(0), x), le(s(s(0)), x), half(x), inc(y)) [1] 1113.72/291.73 if(false, b, x, y) -> logZeroError [1] 1113.72/291.73 if(true, false, x, s(y)) -> y [1] 1113.72/291.73 if(true, true, x, y) -> logIter(x, y) [1] 1113.72/291.73 f -> g [1] 1113.72/291.73 f -> h [1] 1113.72/291.73 1113.72/291.73 The TRS has the following type information: 1113.72/291.73 half :: 0:s:logZeroError -> 0:s:logZeroError 1113.72/291.73 0 :: 0:s:logZeroError 1113.72/291.73 s :: 0:s:logZeroError -> 0:s:logZeroError 1113.72/291.73 le :: 0:s:logZeroError -> 0:s:logZeroError -> true:false 1113.72/291.73 true :: true:false 1113.72/291.73 false :: true:false 1113.72/291.73 inc :: 0:s:logZeroError -> 0:s:logZeroError 1113.72/291.73 logarithm :: 0:s:logZeroError -> 0:s:logZeroError 1113.72/291.73 logIter :: 0:s:logZeroError -> 0:s:logZeroError -> 0:s:logZeroError 1113.72/291.73 if :: true:false -> true:false -> 0:s:logZeroError -> 0:s:logZeroError -> 0:s:logZeroError 1113.72/291.73 logZeroError :: 0:s:logZeroError 1113.72/291.73 f :: g:h 1113.72/291.73 g :: g:h 1113.72/291.73 h :: g:h 1113.72/291.73 1113.72/291.73 Rewrite Strategy: INNERMOST 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (5) CompletionProof (UPPER BOUND(ID)) 1113.72/291.73 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 1113.72/291.73 1113.72/291.73 half(v0) -> null_half [0] 1113.72/291.73 le(v0, v1) -> null_le [0] 1113.72/291.73 inc(v0) -> null_inc [0] 1113.72/291.73 if(v0, v1, v2, v3) -> null_if [0] 1113.72/291.73 1113.72/291.73 And the following fresh constants: null_half, null_le, null_inc, null_if 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (6) 1113.72/291.73 Obligation: 1113.72/291.73 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 1113.72/291.73 1113.72/291.73 Runtime Complexity Weighted TRS with Types. 1113.72/291.73 The TRS R consists of the following rules: 1113.72/291.73 1113.72/291.73 half(0) -> 0 [1] 1113.72/291.73 half(s(0)) -> 0 [1] 1113.72/291.73 half(s(s(x))) -> s(half(x)) [1] 1113.72/291.73 le(0, y) -> true [1] 1113.72/291.73 le(s(x), 0) -> false [1] 1113.72/291.73 le(s(x), s(y)) -> le(x, y) [1] 1113.72/291.73 inc(s(x)) -> s(inc(x)) [1] 1113.72/291.73 inc(0) -> s(0) [1] 1113.72/291.73 logarithm(x) -> logIter(x, 0) [1] 1113.72/291.73 logIter(x, y) -> if(le(s(0), x), le(s(s(0)), x), half(x), inc(y)) [1] 1113.72/291.73 if(false, b, x, y) -> logZeroError [1] 1113.72/291.73 if(true, false, x, s(y)) -> y [1] 1113.72/291.73 if(true, true, x, y) -> logIter(x, y) [1] 1113.72/291.73 f -> g [1] 1113.72/291.73 f -> h [1] 1113.72/291.73 half(v0) -> null_half [0] 1113.72/291.73 le(v0, v1) -> null_le [0] 1113.72/291.73 inc(v0) -> null_inc [0] 1113.72/291.73 if(v0, v1, v2, v3) -> null_if [0] 1113.72/291.73 1113.72/291.73 The TRS has the following type information: 1113.72/291.73 half :: 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 0 :: 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 s :: 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 le :: 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if -> true:false:null_le 1113.72/291.73 true :: true:false:null_le 1113.72/291.73 false :: true:false:null_le 1113.72/291.73 inc :: 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 logarithm :: 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 logIter :: 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 if :: true:false:null_le -> true:false:null_le -> 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if -> 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 logZeroError :: 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 f :: g:h 1113.72/291.73 g :: g:h 1113.72/291.73 h :: g:h 1113.72/291.73 null_half :: 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 null_le :: true:false:null_le 1113.72/291.73 null_inc :: 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 null_if :: 0:s:logZeroError:null_half:null_inc:null_if 1113.72/291.73 1113.72/291.73 Rewrite Strategy: INNERMOST 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1113.72/291.73 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1113.72/291.73 The constant constructors are abstracted as follows: 1113.72/291.73 1113.72/291.73 0 => 0 1113.72/291.73 true => 2 1113.72/291.73 false => 1 1113.72/291.73 logZeroError => 1 1113.72/291.73 g => 0 1113.72/291.73 h => 1 1113.72/291.73 null_half => 0 1113.72/291.73 null_le => 0 1113.72/291.73 null_inc => 0 1113.72/291.73 null_if => 0 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (8) 1113.72/291.73 Obligation: 1113.72/291.73 Complexity RNTS consisting of the following rules: 1113.72/291.73 1113.72/291.73 f -{ 1 }-> 1 :|: 1113.72/291.73 f -{ 1 }-> 0 :|: 1113.72/291.73 half(z) -{ 1 }-> 0 :|: z = 0 1113.72/291.73 half(z) -{ 1 }-> 0 :|: z = 1 + 0 1113.72/291.73 half(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 1113.72/291.73 half(z) -{ 1 }-> 1 + half(x) :|: x >= 0, z = 1 + (1 + x) 1113.72/291.73 if(z, z', z'', z1) -{ 1 }-> y :|: z = 2, x >= 0, y >= 0, z'' = x, z1 = 1 + y, z' = 1 1113.72/291.73 if(z, z', z'', z1) -{ 1 }-> logIter(x, y) :|: z = 2, z1 = y, z' = 2, x >= 0, y >= 0, z'' = x 1113.72/291.73 if(z, z', z'', z1) -{ 1 }-> 1 :|: b >= 0, z1 = y, z = 1, x >= 0, y >= 0, z' = b, z'' = x 1113.72/291.73 if(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 1113.72/291.73 inc(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 1113.72/291.73 inc(z) -{ 1 }-> 1 + inc(x) :|: x >= 0, z = 1 + x 1113.72/291.73 inc(z) -{ 1 }-> 1 + 0 :|: z = 0 1113.72/291.73 le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1113.72/291.73 le(z, z') -{ 1 }-> 2 :|: y >= 0, z = 0, z' = y 1113.72/291.73 le(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0 1113.72/291.73 le(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1113.72/291.73 logIter(z, z') -{ 1 }-> if(le(1 + 0, x), le(1 + (1 + 0), x), half(x), inc(y)) :|: x >= 0, y >= 0, z = x, z' = y 1113.72/291.73 logarithm(z) -{ 1 }-> logIter(x, 0) :|: x >= 0, z = x 1113.72/291.73 1113.72/291.73 Only complete derivations are relevant for the runtime complexity. 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (9) CompleteCoflocoProof (FINISHED) 1113.72/291.73 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 1113.72/291.73 1113.72/291.73 eq(start(V, V2, V12, V15),0,[half(V, Out)],[V >= 0]). 1113.72/291.73 eq(start(V, V2, V12, V15),0,[le(V, V2, Out)],[V >= 0,V2 >= 0]). 1113.72/291.73 eq(start(V, V2, V12, V15),0,[inc(V, Out)],[V >= 0]). 1113.72/291.73 eq(start(V, V2, V12, V15),0,[logarithm(V, Out)],[V >= 0]). 1113.72/291.73 eq(start(V, V2, V12, V15),0,[logIter(V, V2, Out)],[V >= 0,V2 >= 0]). 1113.72/291.73 eq(start(V, V2, V12, V15),0,[if(V, V2, V12, V15, Out)],[V >= 0,V2 >= 0,V12 >= 0,V15 >= 0]). 1113.72/291.73 eq(start(V, V2, V12, V15),0,[f(Out)],[]). 1113.72/291.73 eq(half(V, Out),1,[],[Out = 0,V = 0]). 1113.72/291.73 eq(half(V, Out),1,[],[Out = 0,V = 1]). 1113.72/291.73 eq(half(V, Out),1,[half(V1, Ret1)],[Out = 1 + Ret1,V1 >= 0,V = 2 + V1]). 1113.72/291.73 eq(le(V, V2, Out),1,[],[Out = 2,V3 >= 0,V = 0,V2 = V3]). 1113.72/291.73 eq(le(V, V2, Out),1,[],[Out = 1,V4 >= 0,V = 1 + V4,V2 = 0]). 1113.72/291.73 eq(le(V, V2, Out),1,[le(V5, V6, Ret)],[Out = Ret,V2 = 1 + V6,V5 >= 0,V6 >= 0,V = 1 + V5]). 1113.72/291.73 eq(inc(V, Out),1,[inc(V7, Ret11)],[Out = 1 + Ret11,V7 >= 0,V = 1 + V7]). 1113.72/291.73 eq(inc(V, Out),1,[],[Out = 1,V = 0]). 1113.72/291.73 eq(logarithm(V, Out),1,[logIter(V8, 0, Ret2)],[Out = Ret2,V8 >= 0,V = V8]). 1113.72/291.73 eq(logIter(V, V2, Out),1,[le(1 + 0, V10, Ret0),le(1 + (1 + 0), V10, Ret12),half(V10, Ret21),inc(V9, Ret3),if(Ret0, Ret12, Ret21, Ret3, Ret4)],[Out = Ret4,V10 >= 0,V9 >= 0,V = V10,V2 = V9]). 1113.72/291.73 eq(if(V, V2, V12, V15, Out),1,[],[Out = 1,V13 >= 0,V15 = V11,V = 1,V14 >= 0,V11 >= 0,V2 = V13,V12 = V14]). 1113.72/291.73 eq(if(V, V2, V12, V15, Out),1,[],[Out = V16,V = 2,V17 >= 0,V16 >= 0,V12 = V17,V15 = 1 + V16,V2 = 1]). 1113.72/291.73 eq(if(V, V2, V12, V15, Out),1,[logIter(V19, V18, Ret5)],[Out = Ret5,V = 2,V15 = V18,V2 = 2,V19 >= 0,V18 >= 0,V12 = V19]). 1113.72/291.73 eq(f(Out),1,[],[Out = 0]). 1113.72/291.73 eq(f(Out),1,[],[Out = 1]). 1113.72/291.73 eq(half(V, Out),0,[],[Out = 0,V20 >= 0,V = V20]). 1113.72/291.73 eq(le(V, V2, Out),0,[],[Out = 0,V22 >= 0,V21 >= 0,V = V22,V2 = V21]). 1113.72/291.73 eq(inc(V, Out),0,[],[Out = 0,V23 >= 0,V = V23]). 1113.72/291.73 eq(if(V, V2, V12, V15, Out),0,[],[Out = 0,V15 = V26,V24 >= 0,V12 = V27,V25 >= 0,V = V24,V2 = V25,V27 >= 0,V26 >= 0]). 1113.72/291.73 input_output_vars(half(V,Out),[V],[Out]). 1113.72/291.73 input_output_vars(le(V,V2,Out),[V,V2],[Out]). 1113.72/291.73 input_output_vars(inc(V,Out),[V],[Out]). 1113.72/291.73 input_output_vars(logarithm(V,Out),[V],[Out]). 1113.72/291.73 input_output_vars(logIter(V,V2,Out),[V,V2],[Out]). 1113.72/291.73 input_output_vars(if(V,V2,V12,V15,Out),[V,V2,V12,V15],[Out]). 1113.72/291.73 input_output_vars(f(Out),[],[Out]). 1113.72/291.73 1113.72/291.73 1113.72/291.73 CoFloCo proof output: 1113.72/291.73 Preprocessing Cost Relations 1113.72/291.73 ===================================== 1113.72/291.73 1113.72/291.73 #### Computed strongly connected components 1113.72/291.73 0. non_recursive : [f/1] 1113.72/291.73 1. recursive : [half/2] 1113.72/291.73 2. recursive : [inc/2] 1113.72/291.73 3. recursive : [le/3] 1113.72/291.73 4. recursive : [if/5,logIter/3] 1113.72/291.73 5. non_recursive : [logarithm/2] 1113.72/291.73 6. non_recursive : [start/4] 1113.72/291.73 1113.72/291.73 #### Obtained direct recursion through partial evaluation 1113.72/291.73 0. SCC is partially evaluated into f/1 1113.72/291.73 1. SCC is partially evaluated into half/2 1113.72/291.73 2. SCC is partially evaluated into inc/2 1113.72/291.73 3. SCC is partially evaluated into le/3 1113.72/291.73 4. SCC is partially evaluated into logIter/3 1113.72/291.73 5. SCC is completely evaluated into other SCCs 1113.72/291.73 6. SCC is partially evaluated into start/4 1113.72/291.73 1113.72/291.73 Control-Flow Refinement of Cost Relations 1113.72/291.73 ===================================== 1113.72/291.73 1113.72/291.73 ### Specialization of cost equations f/1 1113.72/291.73 * CE 27 is refined into CE [28] 1113.72/291.73 * CE 26 is refined into CE [29] 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Cost equations --> "Loop" of f/1 1113.72/291.73 * CEs [28] --> Loop 17 1113.72/291.73 * CEs [29] --> Loop 18 1113.72/291.73 1113.72/291.73 ### Ranking functions of CR f(Out) 1113.72/291.73 1113.72/291.73 #### Partial ranking functions of CR f(Out) 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Specialization of cost equations half/2 1113.72/291.73 * CE 16 is refined into CE [30] 1113.72/291.73 * CE 15 is refined into CE [31] 1113.72/291.73 * CE 18 is refined into CE [32] 1113.72/291.73 * CE 17 is refined into CE [33] 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Cost equations --> "Loop" of half/2 1113.72/291.73 * CEs [33] --> Loop 19 1113.72/291.73 * CEs [30] --> Loop 20 1113.72/291.73 * CEs [31,32] --> Loop 21 1113.72/291.73 1113.72/291.73 ### Ranking functions of CR half(V,Out) 1113.72/291.73 * RF of phase [19]: [V-1] 1113.72/291.73 1113.72/291.73 #### Partial ranking functions of CR half(V,Out) 1113.72/291.73 * Partial RF of phase [19]: 1113.72/291.73 - RF of loop [19:1]: 1113.72/291.73 V-1 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Specialization of cost equations inc/2 1113.72/291.73 * CE 25 is refined into CE [34] 1113.72/291.73 * CE 24 is refined into CE [35] 1113.72/291.73 * CE 23 is refined into CE [36] 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Cost equations --> "Loop" of inc/2 1113.72/291.73 * CEs [36] --> Loop 22 1113.72/291.73 * CEs [34] --> Loop 23 1113.72/291.73 * CEs [35] --> Loop 24 1113.72/291.73 1113.72/291.73 ### Ranking functions of CR inc(V,Out) 1113.72/291.73 * RF of phase [22]: [V] 1113.72/291.73 1113.72/291.73 #### Partial ranking functions of CR inc(V,Out) 1113.72/291.73 * Partial RF of phase [22]: 1113.72/291.73 - RF of loop [22:1]: 1113.72/291.73 V 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Specialization of cost equations le/3 1113.72/291.73 * CE 22 is refined into CE [37] 1113.72/291.73 * CE 20 is refined into CE [38] 1113.72/291.73 * CE 19 is refined into CE [39] 1113.72/291.73 * CE 21 is refined into CE [40] 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Cost equations --> "Loop" of le/3 1113.72/291.73 * CEs [40] --> Loop 25 1113.72/291.73 * CEs [37] --> Loop 26 1113.72/291.73 * CEs [38] --> Loop 27 1113.72/291.73 * CEs [39] --> Loop 28 1113.72/291.73 1113.72/291.73 ### Ranking functions of CR le(V,V2,Out) 1113.72/291.73 * RF of phase [25]: [V,V2] 1113.72/291.73 1113.72/291.73 #### Partial ranking functions of CR le(V,V2,Out) 1113.72/291.73 * Partial RF of phase [25]: 1113.72/291.73 - RF of loop [25:1]: 1113.72/291.73 V 1113.72/291.73 V2 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Specialization of cost equations logIter/3 1113.72/291.73 * CE 14 is refined into CE [41,42,43,44,45,46,47,48] 1113.72/291.73 * CE 11 is refined into CE [49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100] 1113.72/291.73 * CE 13 is refined into CE [101,102,103] 1113.72/291.73 * CE 12 is refined into CE [104,105,106,107,108,109,110,111] 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Cost equations --> "Loop" of logIter/3 1113.72/291.73 * CEs [111] --> Loop 29 1113.72/291.73 * CEs [110] --> Loop 30 1113.72/291.73 * CEs [109] --> Loop 31 1113.72/291.73 * CEs [107] --> Loop 32 1113.72/291.73 * CEs [106] --> Loop 33 1113.72/291.73 * CEs [105] --> Loop 34 1113.72/291.73 * CEs [108] --> Loop 35 1113.72/291.73 * CEs [104] --> Loop 36 1113.72/291.73 * CEs [61,65,73,77,81,85,93,97] --> Loop 37 1113.72/291.73 * CEs [103] --> Loop 38 1113.72/291.73 * CEs [102] --> Loop 39 1113.72/291.73 * CEs [69,70,71,72,89,90,91,92,101] --> Loop 40 1113.72/291.73 * CEs [41,42,43,44,45,46,47,48] --> Loop 41 1113.72/291.73 * CEs [49,50,51,52,53,54,55,56,57,58,59,60,62,63,64,66,67,68,74,75,76,78,79,80,82,83,84,86,87,88,94,95,96,98,99,100] --> Loop 42 1113.72/291.73 1113.72/291.73 ### Ranking functions of CR logIter(V,V2,Out) 1113.72/291.73 * RF of phase [29,30,31,35]: [V-1] 1113.72/291.73 1113.72/291.73 #### Partial ranking functions of CR logIter(V,V2,Out) 1113.72/291.73 * Partial RF of phase [29,30,31,35]: 1113.72/291.73 - RF of loop [29:1,30:1,31:1,35:1]: 1113.72/291.73 V-1 1113.72/291.73 - RF of loop [35:1]: 1113.72/291.73 -V2+1 depends on loops [29:1,31:1] 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Specialization of cost equations start/4 1113.72/291.73 * CE 1 is refined into CE [112] 1113.72/291.73 * CE 2 is refined into CE [113,114,115,116,117,118,119] 1113.72/291.73 * CE 3 is refined into CE [120] 1113.72/291.73 * CE 4 is refined into CE [121] 1113.72/291.73 * CE 5 is refined into CE [122,123] 1113.72/291.73 * CE 6 is refined into CE [124,125,126,127,128] 1113.72/291.73 * CE 7 is refined into CE [129,130,131,132] 1113.72/291.73 * CE 8 is refined into CE [133,134,135,136,137] 1113.72/291.73 * CE 9 is refined into CE [138,139,140,141,142,143,144] 1113.72/291.73 * CE 10 is refined into CE [145,146] 1113.72/291.73 1113.72/291.73 1113.72/291.73 ### Cost equations --> "Loop" of start/4 1113.72/291.73 * CEs [112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146] --> Loop 43 1113.72/291.73 1113.72/291.73 ### Ranking functions of CR start(V,V2,V12,V15) 1113.72/291.73 1113.72/291.73 #### Partial ranking functions of CR start(V,V2,V12,V15) 1113.72/291.73 1113.72/291.73 1113.72/291.73 Computing Bounds 1113.72/291.73 ===================================== 1113.72/291.73 1113.72/291.73 #### Cost of chains of f(Out): 1113.72/291.73 * Chain [18]: 1 1113.72/291.73 with precondition: [Out=0] 1113.72/291.73 1113.72/291.73 * Chain [17]: 1 1113.72/291.73 with precondition: [Out=1] 1113.72/291.73 1113.72/291.73 1113.72/291.73 #### Cost of chains of half(V,Out): 1113.72/291.73 * Chain [[19],21]: 1*it(19)+1 1113.72/291.73 Such that:it(19) =< 2*Out 1113.72/291.73 1113.72/291.73 with precondition: [Out>=1,V>=2*Out] 1113.72/291.73 1113.72/291.73 * Chain [[19],20]: 1*it(19)+1 1113.72/291.73 Such that:it(19) =< 2*Out 1113.72/291.73 1113.72/291.73 with precondition: [V=2*Out+1,V>=3] 1113.72/291.73 1113.72/291.73 * Chain [21]: 1 1113.72/291.73 with precondition: [Out=0,V>=0] 1113.72/291.73 1113.72/291.73 * Chain [20]: 1 1113.72/291.73 with precondition: [V=1,Out=0] 1113.72/291.73 1113.72/291.73 1113.72/291.73 #### Cost of chains of inc(V,Out): 1113.72/291.73 * Chain [[22],24]: 1*it(22)+1 1113.72/291.73 Such that:it(22) =< Out 1113.72/291.73 1113.72/291.73 with precondition: [V+1=Out,V>=1] 1113.72/291.73 1113.72/291.73 * Chain [[22],23]: 1*it(22)+0 1113.72/291.73 Such that:it(22) =< Out 1113.72/291.73 1113.72/291.73 with precondition: [Out>=1,V>=Out] 1113.72/291.73 1113.72/291.73 * Chain [24]: 1 1113.72/291.73 with precondition: [V=0,Out=1] 1113.72/291.73 1113.72/291.73 * Chain [23]: 0 1113.72/291.73 with precondition: [Out=0,V>=0] 1113.72/291.73 1113.72/291.73 1113.72/291.73 #### Cost of chains of le(V,V2,Out): 1113.72/291.73 * Chain [[25],28]: 1*it(25)+1 1113.72/291.73 Such that:it(25) =< V 1113.72/291.73 1113.72/291.73 with precondition: [Out=2,V>=1,V2>=V] 1113.72/291.73 1113.72/291.73 * Chain [[25],27]: 1*it(25)+1 1113.72/291.73 Such that:it(25) =< V2 1113.72/291.73 1113.72/291.73 with precondition: [Out=1,V2>=1,V>=V2+1] 1113.72/291.73 1113.72/291.73 * Chain [[25],26]: 1*it(25)+0 1113.72/291.73 Such that:it(25) =< V2 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=1,V2>=1] 1113.72/291.73 1113.72/291.73 * Chain [28]: 1 1113.72/291.73 with precondition: [V=0,Out=2,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [27]: 1 1113.72/291.73 with precondition: [V2=0,Out=1,V>=1] 1113.72/291.73 1113.72/291.73 * Chain [26]: 0 1113.72/291.73 with precondition: [Out=0,V>=0,V2>=0] 1113.72/291.73 1113.72/291.73 1113.72/291.73 #### Cost of chains of logIter(V,V2,Out): 1113.72/291.73 * Chain [[29,30,31,35],42]: 8*it(29)+11*it(30)+6*it(35)+11*s(4)+11*s(5)+56*s(18)+12*s(41)+12*s(62)+3*s(143)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+5 1113.72/291.73 Such that:aux(14) =< 1 1113.72/291.73 aux(15) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(17) =< V/2+V2+1 1113.72/291.73 aux(18) =< V/2+V2+2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(37) =< V 1113.72/291.73 aux(38) =< 2*V 1113.72/291.73 s(62) =< aux(14) 1113.72/291.73 s(41) =< aux(15) 1113.72/291.73 s(18) =< aux(38) 1113.72/291.73 s(5) =< aux(17) 1113.72/291.73 s(4) =< aux(18) 1113.72/291.73 aux(31) =< aux(37) 1113.72/291.73 it(29) =< aux(37) 1113.72/291.73 it(30) =< aux(37) 1113.72/291.73 it(35) =< aux(37) 1113.72/291.73 it(30) =< aux(38) 1113.72/291.73 it(35) =< aux(38) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(37)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(37)+aux(29) 1113.72/291.73 it(35) =< aux(37)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=2,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],40]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+18*s(160)+2*s(166)+2*s(169)+6 1113.72/291.73 Such that:aux(48) =< 1 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(49) =< V/2+V2 1113.72/291.73 aux(50) =< V/2+V2+1 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(51) =< V 1113.72/291.73 aux(52) =< 2*V 1113.72/291.73 s(169) =< aux(49) 1113.72/291.73 s(166) =< aux(50) 1113.72/291.73 s(160) =< aux(48) 1113.72/291.73 aux(31) =< aux(51) 1113.72/291.73 it(29) =< aux(51) 1113.72/291.73 it(30) =< aux(51) 1113.72/291.73 it(35) =< aux(51) 1113.72/291.73 it(30) =< aux(52) 1113.72/291.73 it(35) =< aux(52) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(51)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(51)+aux(29) 1113.72/291.73 it(35) =< aux(51)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(52) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=2,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],39]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+2*s(182)+1*s(184)+6 1113.72/291.73 Such that:aux(53) =< 1 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 s(184) =< Out+1 1113.72/291.73 aux(54) =< V 1113.72/291.73 aux(55) =< 2*V 1113.72/291.73 s(182) =< aux(53) 1113.72/291.73 aux(31) =< aux(54) 1113.72/291.73 it(29) =< aux(54) 1113.72/291.73 it(30) =< aux(54) 1113.72/291.73 it(35) =< aux(54) 1113.72/291.73 it(30) =< aux(55) 1113.72/291.73 it(35) =< aux(55) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(54)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(54)+aux(29) 1113.72/291.73 it(35) =< aux(54)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(55) 1113.72/291.73 1113.72/291.73 with precondition: [V>=2,V2>=0,Out>=1,V+2*V2>=2*Out] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],38]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+2*s(185)+1*s(187)+5 1113.72/291.73 Such that:aux(56) =< 1 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 s(187) =< V/2+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(57) =< V 1113.72/291.73 aux(58) =< 2*V 1113.72/291.73 s(185) =< aux(56) 1113.72/291.73 aux(31) =< aux(57) 1113.72/291.73 it(29) =< aux(57) 1113.72/291.73 it(30) =< aux(57) 1113.72/291.73 it(35) =< aux(57) 1113.72/291.73 it(30) =< aux(58) 1113.72/291.73 it(35) =< aux(58) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(57)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(57)+aux(29) 1113.72/291.73 it(35) =< aux(57)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(58) 1113.72/291.73 1113.72/291.73 with precondition: [V>=2,V2>=0,Out>=0,V+2*V2>=2*Out+2] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],37]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+24*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+4*s(195)+4*s(200)+5 1113.72/291.73 Such that:aux(63) =< 1 1113.72/291.73 aux(64) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(66) =< V 1113.72/291.73 aux(67) =< 2*V 1113.72/291.73 s(200) =< aux(63) 1113.72/291.73 s(195) =< aux(64) 1113.72/291.73 s(144) =< aux(67) 1113.72/291.73 aux(31) =< aux(66) 1113.72/291.73 it(29) =< aux(66) 1113.72/291.73 it(30) =< aux(66) 1113.72/291.73 it(35) =< aux(66) 1113.72/291.73 it(30) =< aux(67) 1113.72/291.73 it(35) =< aux(67) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(66)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(66)+aux(29) 1113.72/291.73 it(35) =< aux(66)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=2,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],36,42]: 8*it(29)+11*it(30)+6*it(35)+24*s(4)+24*s(5)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+11 1113.72/291.73 Such that:aux(68) =< 1 1113.72/291.73 aux(69) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(70) =< V 1113.72/291.73 aux(71) =< 2*V 1113.72/291.73 s(5) =< aux(68) 1113.72/291.73 s(4) =< aux(69) 1113.72/291.73 aux(31) =< aux(70) 1113.72/291.73 it(29) =< aux(70) 1113.72/291.73 it(30) =< aux(70) 1113.72/291.73 it(35) =< aux(70) 1113.72/291.73 it(30) =< aux(71) 1113.72/291.73 it(35) =< aux(71) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(70)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(70)+aux(29) 1113.72/291.73 it(35) =< aux(70)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(71) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],36,41]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+3*s(212)+3*s(213)+12 1113.72/291.73 Such that:aux(74) =< 1 1113.72/291.73 aux(75) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(76) =< V 1113.72/291.73 aux(77) =< 2*V 1113.72/291.73 s(212) =< aux(74) 1113.72/291.73 s(213) =< aux(75) 1113.72/291.73 aux(31) =< aux(76) 1113.72/291.73 it(29) =< aux(76) 1113.72/291.73 it(30) =< aux(76) 1113.72/291.73 it(35) =< aux(76) 1113.72/291.73 it(30) =< aux(77) 1113.72/291.73 it(35) =< aux(77) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(76)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(76)+aux(29) 1113.72/291.73 it(35) =< aux(76)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(77) 1113.72/291.73 1113.72/291.73 with precondition: [Out=1,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],34,42]: 8*it(29)+11*it(30)+6*it(35)+24*s(4)+13*s(41)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+10 1113.72/291.73 Such that:aux(79) =< 1 1113.72/291.73 aux(80) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(81) =< V 1113.72/291.73 aux(82) =< 2*V 1113.72/291.73 s(4) =< aux(79) 1113.72/291.73 s(41) =< aux(80) 1113.72/291.73 aux(31) =< aux(81) 1113.72/291.73 it(29) =< aux(81) 1113.72/291.73 it(30) =< aux(81) 1113.72/291.73 it(35) =< aux(81) 1113.72/291.73 it(30) =< aux(82) 1113.72/291.73 it(35) =< aux(82) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(81)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(81)+aux(29) 1113.72/291.73 it(35) =< aux(81)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(82) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],34,41]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+3*s(214)+1*s(223)+11 1113.72/291.73 Such that:aux(83) =< 1 1113.72/291.73 s(223) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(84) =< V 1113.72/291.73 aux(85) =< 2*V 1113.72/291.73 s(214) =< aux(83) 1113.72/291.73 aux(31) =< aux(84) 1113.72/291.73 it(29) =< aux(84) 1113.72/291.73 it(30) =< aux(84) 1113.72/291.73 it(35) =< aux(84) 1113.72/291.73 it(30) =< aux(85) 1113.72/291.73 it(35) =< aux(85) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(84)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(84)+aux(29) 1113.72/291.73 it(35) =< aux(84)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(85) 1113.72/291.73 1113.72/291.73 with precondition: [Out=1,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],34,37]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+5*s(195)+5*s(200)+10 1113.72/291.73 Such that:aux(86) =< 1 1113.72/291.73 aux(87) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(88) =< V 1113.72/291.73 aux(89) =< 2*V 1113.72/291.73 s(200) =< aux(86) 1113.72/291.73 s(195) =< aux(87) 1113.72/291.73 aux(31) =< aux(88) 1113.72/291.73 it(29) =< aux(88) 1113.72/291.73 it(30) =< aux(88) 1113.72/291.73 it(35) =< aux(88) 1113.72/291.73 it(30) =< aux(89) 1113.72/291.73 it(35) =< aux(89) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(88)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(88)+aux(29) 1113.72/291.73 it(35) =< aux(88)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(89) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],33,42]: 8*it(29)+11*it(30)+6*it(35)+11*s(4)+12*s(5)+13*s(41)+13*s(62)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+11 1113.72/291.73 Such that:aux(90) =< 1 1113.72/291.73 aux(91) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(92) =< V/2+V2 1113.72/291.73 aux(18) =< V/2+V2+1 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(93) =< V 1113.72/291.73 aux(94) =< 2*V 1113.72/291.73 s(62) =< aux(90) 1113.72/291.73 s(41) =< aux(91) 1113.72/291.73 s(5) =< aux(92) 1113.72/291.73 s(4) =< aux(18) 1113.72/291.73 aux(31) =< aux(93) 1113.72/291.73 it(29) =< aux(93) 1113.72/291.73 it(30) =< aux(93) 1113.72/291.73 it(35) =< aux(93) 1113.72/291.73 it(30) =< aux(94) 1113.72/291.73 it(35) =< aux(94) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(93)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(93)+aux(29) 1113.72/291.73 it(35) =< aux(93)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(94) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],33,41]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+2*s(214)+3*s(215)+1*s(224)+1*s(225)+12 1113.72/291.73 Such that:s(224) =< 1 1113.72/291.73 s(225) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(95) =< V/2+V2 1113.72/291.73 aux(73) =< V/2+V2+1 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(96) =< V 1113.72/291.73 aux(97) =< 2*V 1113.72/291.73 s(215) =< aux(95) 1113.72/291.73 s(214) =< aux(73) 1113.72/291.73 aux(31) =< aux(96) 1113.72/291.73 it(29) =< aux(96) 1113.72/291.73 it(30) =< aux(96) 1113.72/291.73 it(35) =< aux(96) 1113.72/291.73 it(30) =< aux(97) 1113.72/291.73 it(35) =< aux(97) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(96)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(96)+aux(29) 1113.72/291.73 it(35) =< aux(96)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(97) 1113.72/291.73 1113.72/291.73 with precondition: [Out=1,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],32,42]: 8*it(29)+11*it(30)+6*it(35)+23*s(4)+13*s(41)+13*s(62)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+10 1113.72/291.73 Such that:aux(98) =< 1 1113.72/291.73 aux(99) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(101) =< V 1113.72/291.73 aux(102) =< 2*V 1113.72/291.73 aux(103) =< V/2+V2 1113.72/291.73 s(62) =< aux(98) 1113.72/291.73 s(41) =< aux(99) 1113.72/291.73 s(4) =< aux(103) 1113.72/291.73 aux(31) =< aux(101) 1113.72/291.73 it(29) =< aux(101) 1113.72/291.73 it(30) =< aux(101) 1113.72/291.73 it(35) =< aux(101) 1113.72/291.73 it(30) =< aux(102) 1113.72/291.73 it(35) =< aux(102) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(101)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(101)+aux(29) 1113.72/291.73 it(35) =< aux(101)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(102) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [[29,30,31,35],32,41]: 8*it(29)+11*it(30)+6*it(35)+3*s(143)+8*s(144)+1*s(145)+1*s(150)+1*s(156)+1*s(157)+5*s(214)+1*s(227)+1*s(228)+11 1113.72/291.73 Such that:s(227) =< 1 1113.72/291.73 s(228) =< 2 1113.72/291.73 aux(21) =< V+V2 1113.72/291.73 aux(29) =< -V2+1 1113.72/291.73 aux(105) =< V 1113.72/291.73 aux(106) =< 2*V 1113.72/291.73 aux(107) =< V/2+V2 1113.72/291.73 s(214) =< aux(107) 1113.72/291.73 aux(31) =< aux(105) 1113.72/291.73 it(29) =< aux(105) 1113.72/291.73 it(30) =< aux(105) 1113.72/291.73 it(35) =< aux(105) 1113.72/291.73 it(30) =< aux(106) 1113.72/291.73 it(35) =< aux(106) 1113.72/291.73 aux(24) =< aux(21)+1 1113.72/291.73 s(143) =< aux(105)*2 1113.72/291.73 s(145) =< it(29)*aux(21) 1113.72/291.73 aux(31) =< aux(105)+aux(29) 1113.72/291.73 it(35) =< aux(105)+aux(29) 1113.72/291.73 s(150) =< it(30)*aux(24) 1113.72/291.73 s(157) =< aux(31)*2 1113.72/291.73 s(156) =< aux(31) 1113.72/291.73 s(144) =< aux(106) 1113.72/291.73 1113.72/291.73 with precondition: [Out=1,V>=4,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [42]: 11*s(4)+11*s(5)+48*s(18)+12*s(41)+12*s(62)+5 1113.72/291.73 Such that:aux(14) =< 1 1113.72/291.73 aux(15) =< 2 1113.72/291.73 aux(16) =< V 1113.72/291.73 aux(17) =< V2 1113.72/291.73 aux(18) =< V2+1 1113.72/291.73 s(62) =< aux(14) 1113.72/291.73 s(41) =< aux(15) 1113.72/291.73 s(18) =< aux(16) 1113.72/291.73 s(5) =< aux(17) 1113.72/291.73 s(4) =< aux(18) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=0,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [41]: 2*s(214)+2*s(215)+6 1113.72/291.73 Such that:aux(72) =< V2 1113.72/291.73 aux(73) =< V2+1 1113.72/291.73 s(215) =< aux(72) 1113.72/291.73 s(214) =< aux(73) 1113.72/291.73 1113.72/291.73 with precondition: [V=0,Out=1,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [40]: 18*s(160)+2*s(166)+2*s(169)+6 1113.72/291.73 Such that:aux(48) =< 1 1113.72/291.73 aux(49) =< V2 1113.72/291.73 aux(50) =< V2+1 1113.72/291.73 s(169) =< aux(49) 1113.72/291.73 s(166) =< aux(50) 1113.72/291.73 s(160) =< aux(48) 1113.72/291.73 1113.72/291.73 with precondition: [V=1,Out=0,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [39]: 2*s(182)+1*s(184)+6 1113.72/291.73 Such that:s(184) =< V2+1 1113.72/291.73 aux(53) =< 1 1113.72/291.73 s(182) =< aux(53) 1113.72/291.73 1113.72/291.73 with precondition: [V=1,V2=Out,V2>=1] 1113.72/291.73 1113.72/291.73 * Chain [38]: 2*s(185)+1*s(187)+5 1113.72/291.73 Such that:s(187) =< V2 1113.72/291.73 aux(56) =< 1 1113.72/291.73 s(185) =< aux(56) 1113.72/291.73 1113.72/291.73 with precondition: [V=1,Out>=0,V2>=Out+1] 1113.72/291.73 1113.72/291.73 * Chain [37]: 16*s(188)+4*s(195)+4*s(200)+5 1113.72/291.73 Such that:aux(63) =< 1 1113.72/291.73 aux(64) =< 2 1113.72/291.73 aux(65) =< V 1113.72/291.73 s(200) =< aux(63) 1113.72/291.73 s(195) =< aux(64) 1113.72/291.73 s(188) =< aux(65) 1113.72/291.73 1113.72/291.73 with precondition: [V2=0,Out=0,V>=0] 1113.72/291.73 1113.72/291.73 * Chain [36,42]: 24*s(4)+24*s(5)+11 1113.72/291.73 Such that:aux(68) =< 1 1113.72/291.73 aux(69) =< 2 1113.72/291.73 s(5) =< aux(68) 1113.72/291.73 s(4) =< aux(69) 1113.72/291.73 1113.72/291.73 with precondition: [V2=0,Out=0,V>=2] 1113.72/291.73 1113.72/291.73 * Chain [36,41]: 3*s(212)+3*s(213)+12 1113.72/291.73 Such that:aux(74) =< 1 1113.72/291.73 aux(75) =< 2 1113.72/291.73 s(212) =< aux(74) 1113.72/291.73 s(213) =< aux(75) 1113.72/291.73 1113.72/291.73 with precondition: [V2=0,Out=1,V>=2] 1113.72/291.73 1113.72/291.73 * Chain [34,42]: 24*s(4)+13*s(41)+10 1113.72/291.73 Such that:aux(79) =< 1 1113.72/291.73 aux(80) =< 2 1113.72/291.73 s(4) =< aux(79) 1113.72/291.73 s(41) =< aux(80) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=2,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [34,41]: 3*s(214)+1*s(223)+11 1113.72/291.73 Such that:s(223) =< 2 1113.72/291.73 aux(83) =< 1 1113.72/291.73 s(214) =< aux(83) 1113.72/291.73 1113.72/291.73 with precondition: [Out=1,V>=2,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [34,37]: 5*s(195)+5*s(200)+10 1113.72/291.73 Such that:aux(86) =< 1 1113.72/291.73 aux(87) =< 2 1113.72/291.73 s(200) =< aux(86) 1113.72/291.73 s(195) =< aux(87) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=2,V2>=0] 1113.72/291.73 1113.72/291.73 * Chain [33,42]: 11*s(4)+12*s(5)+13*s(41)+13*s(62)+11 1113.72/291.73 Such that:aux(18) =< V2+2 1113.72/291.73 aux(90) =< 1 1113.72/291.73 aux(91) =< 2 1113.72/291.73 aux(92) =< V2+1 1113.72/291.73 s(62) =< aux(90) 1113.72/291.73 s(41) =< aux(91) 1113.72/291.73 s(5) =< aux(92) 1113.72/291.73 s(4) =< aux(18) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=2,V2>=1] 1113.72/291.73 1113.72/291.73 * Chain [33,41]: 2*s(214)+3*s(215)+1*s(224)+1*s(225)+12 1113.72/291.73 Such that:s(224) =< 1 1113.72/291.73 s(225) =< 2 1113.72/291.73 aux(73) =< V2+2 1113.72/291.73 aux(95) =< V2+1 1113.72/291.73 s(215) =< aux(95) 1113.72/291.73 s(214) =< aux(73) 1113.72/291.73 1113.72/291.73 with precondition: [Out=1,V>=2,V2>=1] 1113.72/291.73 1113.72/291.73 * Chain [32,42]: 11*s(4)+12*s(5)+13*s(41)+13*s(62)+10 1113.72/291.73 Such that:aux(18) =< V2+1 1113.72/291.73 aux(98) =< 1 1113.72/291.73 aux(99) =< 2 1113.72/291.73 aux(100) =< V2 1113.72/291.73 s(62) =< aux(98) 1113.72/291.73 s(41) =< aux(99) 1113.72/291.73 s(5) =< aux(100) 1113.72/291.73 s(4) =< aux(18) 1113.72/291.73 1113.72/291.73 with precondition: [Out=0,V>=2,V2>=1] 1113.72/291.73 1113.72/291.73 * Chain [32,41]: 2*s(214)+3*s(215)+1*s(227)+1*s(228)+11 1113.72/291.73 Such that:s(227) =< 1 1113.72/291.73 s(228) =< 2 1113.72/291.73 aux(73) =< V2+1 1113.72/291.73 aux(104) =< V2 1113.72/291.73 s(215) =< aux(104) 1113.72/291.73 s(214) =< aux(73) 1113.72/291.73 1113.72/291.73 with precondition: [Out=1,V>=2,V2>=1] 1113.72/291.73 1113.72/291.73 1113.72/291.73 #### Cost of chains of start(V,V2,V12,V15): 1113.72/291.73 * Chain [43]: 31*s(560)+44*s(561)+789*s(574)+553*s(575)+176*s(578)+46*s(579)+154*s(581)+84*s(582)+42*s(584)+14*s(585)+14*s(586)+14*s(587)+14*s(588)+176*s(589)+27*s(590)+11*s(591)+13*s(592)+356*s(654)+33*s(655)+1*s(658)+46*s(681)+308*s(683)+84*s(684)+84*s(686)+14*s(687)+14*s(688)+14*s(689)+14*s(690)+352*s(691)+27*s(692)+11*s(693)+44*s(752)+46*s(770)+84*s(773)+14*s(776)+14*s(777)+14*s(778)+14*s(779)+27*s(781)+11*s(782)+13*s(783)+13 1113.72/291.73 Such that:s(658) =< V+1 1113.72/291.73 s(664) =< V/2+2 1113.72/291.73 s(753) =< V/2+V2+2 1113.72/291.73 s(562) =< V12/2+V15+2 1113.72/291.73 aux(139) =< 1 1113.72/291.73 aux(140) =< 2 1113.72/291.73 aux(141) =< V 1113.72/291.73 aux(142) =< V+V2 1113.72/291.73 aux(143) =< 2*V 1113.72/291.73 aux(144) =< V/2 1113.72/291.73 aux(145) =< V/2+1 1113.72/291.73 aux(146) =< V/2+V2 1113.72/291.73 aux(147) =< V/2+V2+1 1113.72/291.73 aux(148) =< -V2+1 1113.72/291.73 aux(149) =< V2 1113.72/291.73 aux(150) =< V2+1 1113.72/291.73 aux(151) =< V2+2 1113.72/291.73 aux(152) =< V12 1113.72/291.73 aux(153) =< V12+V15 1113.72/291.73 aux(154) =< 2*V12 1113.72/291.73 aux(155) =< V12/2+V15 1113.72/291.73 aux(156) =< V12/2+V15+1 1113.72/291.73 aux(157) =< -V15+1 1113.72/291.73 aux(158) =< V15 1113.72/291.73 aux(159) =< V15+1 1113.72/291.73 aux(160) =< V15+2 1113.72/291.73 s(654) =< aux(141) 1113.72/291.73 s(681) =< aux(144) 1113.72/291.73 s(770) =< aux(146) 1113.72/291.73 s(655) =< aux(149) 1113.72/291.73 s(752) =< aux(150) 1113.72/291.73 s(579) =< aux(155) 1113.72/291.73 s(560) =< aux(158) 1113.72/291.73 s(561) =< aux(159) 1113.72/291.73 s(574) =< aux(139) 1113.72/291.73 s(575) =< aux(140) 1113.72/291.73 s(578) =< aux(152) 1113.72/291.73 s(580) =< aux(152) 1113.72/291.73 s(581) =< aux(152) 1113.72/291.73 s(582) =< aux(152) 1113.72/291.73 s(581) =< aux(154) 1113.72/291.73 s(582) =< aux(154) 1113.72/291.73 s(583) =< aux(153)+1 1113.72/291.73 s(584) =< aux(152)*2 1113.72/291.73 s(585) =< s(578)*aux(153) 1113.72/291.73 s(580) =< aux(152)+aux(157) 1113.72/291.73 s(582) =< aux(152)+aux(157) 1113.72/291.73 s(586) =< s(581)*s(583) 1113.72/291.73 s(587) =< s(580)*2 1113.72/291.73 s(588) =< s(580) 1113.72/291.73 s(589) =< aux(154) 1113.72/291.73 s(590) =< aux(156) 1113.72/291.73 s(591) =< s(562) 1113.72/291.73 s(592) =< aux(160) 1113.72/291.73 s(771) =< aux(141) 1113.72/291.73 s(683) =< aux(141) 1113.72/291.73 s(773) =< aux(141) 1113.72/291.73 s(683) =< aux(143) 1113.72/291.73 s(773) =< aux(143) 1113.72/291.73 s(774) =< aux(142)+1 1113.72/291.73 s(686) =< aux(141)*2 1113.72/291.73 s(776) =< s(654)*aux(142) 1113.72/291.73 s(771) =< aux(141)+aux(148) 1113.72/291.73 s(773) =< aux(141)+aux(148) 1113.72/291.73 s(777) =< s(683)*s(774) 1113.72/291.73 s(778) =< s(771)*2 1113.72/291.73 s(779) =< s(771) 1113.72/291.73 s(691) =< aux(143) 1113.72/291.73 s(781) =< aux(147) 1113.72/291.73 s(782) =< s(753) 1113.72/291.73 s(783) =< aux(151) 1113.72/291.73 s(682) =< aux(141) 1113.72/291.73 s(684) =< aux(141) 1113.72/291.73 s(684) =< aux(143) 1113.72/291.73 s(685) =< aux(141)+1 1113.72/291.73 s(687) =< s(654)*aux(141) 1113.72/291.73 s(682) =< aux(141)+aux(139) 1113.72/291.73 s(684) =< aux(141)+aux(139) 1113.72/291.73 s(688) =< s(683)*s(685) 1113.72/291.73 s(689) =< s(682)*2 1113.72/291.73 s(690) =< s(682) 1113.72/291.73 s(692) =< aux(145) 1113.72/291.73 s(693) =< s(664) 1113.72/291.73 1113.72/291.73 with precondition: [] 1113.72/291.73 1113.72/291.73 1113.72/291.73 Closed-form bounds of start(V,V2,V12,V15): 1113.72/291.73 ------------------------------------- 1113.72/291.73 * Chain [43] with precondition: [] 1113.72/291.73 - Upper bound: nat(V)*1112+1908+nat(V)*28*nat(V)+nat(V)*28*nat(V+V2)+nat(V2)*33+nat(V12)*554+nat(V12)*28*nat(V12+V15)+nat(V15)*31+nat(2*V)*352+nat(2*V12)*176+nat(V+1)+nat(V2+1)*44+nat(V2+2)*13+nat(V15+1)*44+nat(V15+2)*13+nat(V/2+V2+1)*27+nat(V/2+V2+2)*11+nat(V12/2+V15+1)*27+nat(V12/2+V15+2)*11+nat(V/2+V2)*46+nat(V/2+1)*27+nat(V/2+2)*11+nat(V12/2+V15)*46+nat(V/2)*46 1113.72/291.73 - Complexity: n^2 1113.72/291.73 1113.72/291.73 ### Maximum cost of start(V,V2,V12,V15): nat(V)*1112+1908+nat(V)*28*nat(V)+nat(V)*28*nat(V+V2)+nat(V2)*33+nat(V12)*554+nat(V12)*28*nat(V12+V15)+nat(V15)*31+nat(2*V)*352+nat(2*V12)*176+nat(V+1)+nat(V2+1)*44+nat(V2+2)*13+nat(V15+1)*44+nat(V15+2)*13+nat(V/2+V2+1)*27+nat(V/2+V2+2)*11+nat(V12/2+V15+1)*27+nat(V12/2+V15+2)*11+nat(V/2+V2)*46+nat(V/2+1)*27+nat(V/2+2)*11+nat(V12/2+V15)*46+nat(V/2)*46 1113.72/291.73 Asymptotic class: n^2 1113.72/291.73 * Total analysis performed in 1573 ms. 1113.72/291.73 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (10) 1113.72/291.73 BOUNDS(1, n^2) 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 1113.72/291.73 Renamed function symbols to avoid clashes with predefined symbol. 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (12) 1113.72/291.73 Obligation: 1113.72/291.73 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1113.72/291.73 1113.72/291.73 1113.72/291.73 The TRS R consists of the following rules: 1113.72/291.73 1113.72/291.73 half(0') -> 0' 1113.72/291.73 half(s(0')) -> 0' 1113.72/291.73 half(s(s(x))) -> s(half(x)) 1113.72/291.73 le(0', y) -> true 1113.72/291.73 le(s(x), 0') -> false 1113.72/291.73 le(s(x), s(y)) -> le(x, y) 1113.72/291.73 inc(s(x)) -> s(inc(x)) 1113.72/291.73 inc(0') -> s(0') 1113.72/291.73 logarithm(x) -> logIter(x, 0') 1113.72/291.73 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), half(x), inc(y)) 1113.72/291.73 if(false, b, x, y) -> logZeroError 1113.72/291.73 if(true, false, x, s(y)) -> y 1113.72/291.73 if(true, true, x, y) -> logIter(x, y) 1113.72/291.73 f -> g 1113.72/291.73 f -> h 1113.72/291.73 1113.72/291.73 S is empty. 1113.72/291.73 Rewrite Strategy: INNERMOST 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (13) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1113.72/291.73 Infered types. 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (14) 1113.72/291.73 Obligation: 1113.72/291.73 Innermost TRS: 1113.72/291.73 Rules: 1113.72/291.73 half(0') -> 0' 1113.72/291.73 half(s(0')) -> 0' 1113.72/291.73 half(s(s(x))) -> s(half(x)) 1113.72/291.73 le(0', y) -> true 1113.72/291.73 le(s(x), 0') -> false 1113.72/291.73 le(s(x), s(y)) -> le(x, y) 1113.72/291.73 inc(s(x)) -> s(inc(x)) 1113.72/291.73 inc(0') -> s(0') 1113.72/291.73 logarithm(x) -> logIter(x, 0') 1113.72/291.73 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), half(x), inc(y)) 1113.72/291.73 if(false, b, x, y) -> logZeroError 1113.72/291.73 if(true, false, x, s(y)) -> y 1113.72/291.73 if(true, true, x, y) -> logIter(x, y) 1113.72/291.73 f -> g 1113.72/291.73 f -> h 1113.72/291.73 1113.72/291.73 Types: 1113.72/291.73 half :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 0' :: 0':s:logZeroError 1113.72/291.73 s :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 1113.72/291.73 true :: true:false 1113.72/291.73 false :: true:false 1113.72/291.73 inc :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logarithm :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logZeroError :: 0':s:logZeroError 1113.72/291.73 f :: g:h 1113.72/291.73 g :: g:h 1113.72/291.73 h :: g:h 1113.72/291.73 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 1113.72/291.73 hole_true:false2_0 :: true:false 1113.72/291.73 hole_g:h3_0 :: g:h 1113.72/291.73 gen_0':s:logZeroError4_0 :: Nat -> 0':s:logZeroError 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (15) OrderProof (LOWER BOUND(ID)) 1113.72/291.73 Heuristically decided to analyse the following defined symbols: 1113.72/291.73 half, le, inc, logIter 1113.72/291.73 1113.72/291.73 They will be analysed ascendingly in the following order: 1113.72/291.73 half < logIter 1113.72/291.73 le < logIter 1113.72/291.73 inc < logIter 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (16) 1113.72/291.73 Obligation: 1113.72/291.73 Innermost TRS: 1113.72/291.73 Rules: 1113.72/291.73 half(0') -> 0' 1113.72/291.73 half(s(0')) -> 0' 1113.72/291.73 half(s(s(x))) -> s(half(x)) 1113.72/291.73 le(0', y) -> true 1113.72/291.73 le(s(x), 0') -> false 1113.72/291.73 le(s(x), s(y)) -> le(x, y) 1113.72/291.73 inc(s(x)) -> s(inc(x)) 1113.72/291.73 inc(0') -> s(0') 1113.72/291.73 logarithm(x) -> logIter(x, 0') 1113.72/291.73 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), half(x), inc(y)) 1113.72/291.73 if(false, b, x, y) -> logZeroError 1113.72/291.73 if(true, false, x, s(y)) -> y 1113.72/291.73 if(true, true, x, y) -> logIter(x, y) 1113.72/291.73 f -> g 1113.72/291.73 f -> h 1113.72/291.73 1113.72/291.73 Types: 1113.72/291.73 half :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 0' :: 0':s:logZeroError 1113.72/291.73 s :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 1113.72/291.73 true :: true:false 1113.72/291.73 false :: true:false 1113.72/291.73 inc :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logarithm :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logZeroError :: 0':s:logZeroError 1113.72/291.73 f :: g:h 1113.72/291.73 g :: g:h 1113.72/291.73 h :: g:h 1113.72/291.73 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 1113.72/291.73 hole_true:false2_0 :: true:false 1113.72/291.73 hole_g:h3_0 :: g:h 1113.72/291.73 gen_0':s:logZeroError4_0 :: Nat -> 0':s:logZeroError 1113.72/291.73 1113.72/291.73 1113.72/291.73 Generator Equations: 1113.72/291.73 gen_0':s:logZeroError4_0(0) <=> 0' 1113.72/291.73 gen_0':s:logZeroError4_0(+(x, 1)) <=> s(gen_0':s:logZeroError4_0(x)) 1113.72/291.73 1113.72/291.73 1113.72/291.73 The following defined symbols remain to be analysed: 1113.72/291.73 half, le, inc, logIter 1113.72/291.73 1113.72/291.73 They will be analysed ascendingly in the following order: 1113.72/291.73 half < logIter 1113.72/291.73 le < logIter 1113.72/291.73 inc < logIter 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1113.72/291.73 Proved the following rewrite lemma: 1113.72/291.73 half(gen_0':s:logZeroError4_0(*(2, n6_0))) -> gen_0':s:logZeroError4_0(n6_0), rt in Omega(1 + n6_0) 1113.72/291.73 1113.72/291.73 Induction Base: 1113.72/291.73 half(gen_0':s:logZeroError4_0(*(2, 0))) ->_R^Omega(1) 1113.72/291.73 0' 1113.72/291.73 1113.72/291.73 Induction Step: 1113.72/291.73 half(gen_0':s:logZeroError4_0(*(2, +(n6_0, 1)))) ->_R^Omega(1) 1113.72/291.73 s(half(gen_0':s:logZeroError4_0(*(2, n6_0)))) ->_IH 1113.72/291.73 s(gen_0':s:logZeroError4_0(c7_0)) 1113.72/291.73 1113.72/291.73 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (18) 1113.72/291.73 Complex Obligation (BEST) 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (19) 1113.72/291.73 Obligation: 1113.72/291.73 Proved the lower bound n^1 for the following obligation: 1113.72/291.73 1113.72/291.73 Innermost TRS: 1113.72/291.73 Rules: 1113.72/291.73 half(0') -> 0' 1113.72/291.73 half(s(0')) -> 0' 1113.72/291.73 half(s(s(x))) -> s(half(x)) 1113.72/291.73 le(0', y) -> true 1113.72/291.73 le(s(x), 0') -> false 1113.72/291.73 le(s(x), s(y)) -> le(x, y) 1113.72/291.73 inc(s(x)) -> s(inc(x)) 1113.72/291.73 inc(0') -> s(0') 1113.72/291.73 logarithm(x) -> logIter(x, 0') 1113.72/291.73 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), half(x), inc(y)) 1113.72/291.73 if(false, b, x, y) -> logZeroError 1113.72/291.73 if(true, false, x, s(y)) -> y 1113.72/291.73 if(true, true, x, y) -> logIter(x, y) 1113.72/291.73 f -> g 1113.72/291.73 f -> h 1113.72/291.73 1113.72/291.73 Types: 1113.72/291.73 half :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 0' :: 0':s:logZeroError 1113.72/291.73 s :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 1113.72/291.73 true :: true:false 1113.72/291.73 false :: true:false 1113.72/291.73 inc :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logarithm :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.73 logZeroError :: 0':s:logZeroError 1113.72/291.73 f :: g:h 1113.72/291.73 g :: g:h 1113.72/291.73 h :: g:h 1113.72/291.73 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 1113.72/291.73 hole_true:false2_0 :: true:false 1113.72/291.73 hole_g:h3_0 :: g:h 1113.72/291.73 gen_0':s:logZeroError4_0 :: Nat -> 0':s:logZeroError 1113.72/291.73 1113.72/291.73 1113.72/291.73 Generator Equations: 1113.72/291.73 gen_0':s:logZeroError4_0(0) <=> 0' 1113.72/291.73 gen_0':s:logZeroError4_0(+(x, 1)) <=> s(gen_0':s:logZeroError4_0(x)) 1113.72/291.73 1113.72/291.73 1113.72/291.73 The following defined symbols remain to be analysed: 1113.72/291.73 half, le, inc, logIter 1113.72/291.73 1113.72/291.73 They will be analysed ascendingly in the following order: 1113.72/291.73 half < logIter 1113.72/291.73 le < logIter 1113.72/291.73 inc < logIter 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (20) LowerBoundPropagationProof (FINISHED) 1113.72/291.73 Propagated lower bound. 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (21) 1113.72/291.73 BOUNDS(n^1, INF) 1113.72/291.73 1113.72/291.73 ---------------------------------------- 1113.72/291.73 1113.72/291.73 (22) 1113.72/291.73 Obligation: 1113.72/291.73 Innermost TRS: 1113.72/291.73 Rules: 1113.72/291.73 half(0') -> 0' 1113.72/291.73 half(s(0')) -> 0' 1113.72/291.73 half(s(s(x))) -> s(half(x)) 1113.72/291.73 le(0', y) -> true 1113.72/291.73 le(s(x), 0') -> false 1113.72/291.73 le(s(x), s(y)) -> le(x, y) 1113.72/291.73 inc(s(x)) -> s(inc(x)) 1113.72/291.73 inc(0') -> s(0') 1113.72/291.73 logarithm(x) -> logIter(x, 0') 1113.72/291.73 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), half(x), inc(y)) 1113.72/291.74 if(false, b, x, y) -> logZeroError 1113.72/291.74 if(true, false, x, s(y)) -> y 1113.72/291.74 if(true, true, x, y) -> logIter(x, y) 1113.72/291.74 f -> g 1113.72/291.74 f -> h 1113.72/291.74 1113.72/291.74 Types: 1113.72/291.74 half :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 0' :: 0':s:logZeroError 1113.72/291.74 s :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 1113.72/291.74 true :: true:false 1113.72/291.74 false :: true:false 1113.72/291.74 inc :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logarithm :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logZeroError :: 0':s:logZeroError 1113.72/291.74 f :: g:h 1113.72/291.74 g :: g:h 1113.72/291.74 h :: g:h 1113.72/291.74 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 1113.72/291.74 hole_true:false2_0 :: true:false 1113.72/291.74 hole_g:h3_0 :: g:h 1113.72/291.74 gen_0':s:logZeroError4_0 :: Nat -> 0':s:logZeroError 1113.72/291.74 1113.72/291.74 1113.72/291.74 Lemmas: 1113.72/291.74 half(gen_0':s:logZeroError4_0(*(2, n6_0))) -> gen_0':s:logZeroError4_0(n6_0), rt in Omega(1 + n6_0) 1113.72/291.74 1113.72/291.74 1113.72/291.74 Generator Equations: 1113.72/291.74 gen_0':s:logZeroError4_0(0) <=> 0' 1113.72/291.74 gen_0':s:logZeroError4_0(+(x, 1)) <=> s(gen_0':s:logZeroError4_0(x)) 1113.72/291.74 1113.72/291.74 1113.72/291.74 The following defined symbols remain to be analysed: 1113.72/291.74 le, inc, logIter 1113.72/291.74 1113.72/291.74 They will be analysed ascendingly in the following order: 1113.72/291.74 le < logIter 1113.72/291.74 inc < logIter 1113.72/291.74 1113.72/291.74 ---------------------------------------- 1113.72/291.74 1113.72/291.74 (23) RewriteLemmaProof (LOWER BOUND(ID)) 1113.72/291.74 Proved the following rewrite lemma: 1113.72/291.74 le(gen_0':s:logZeroError4_0(n360_0), gen_0':s:logZeroError4_0(n360_0)) -> true, rt in Omega(1 + n360_0) 1113.72/291.74 1113.72/291.74 Induction Base: 1113.72/291.74 le(gen_0':s:logZeroError4_0(0), gen_0':s:logZeroError4_0(0)) ->_R^Omega(1) 1113.72/291.74 true 1113.72/291.74 1113.72/291.74 Induction Step: 1113.72/291.74 le(gen_0':s:logZeroError4_0(+(n360_0, 1)), gen_0':s:logZeroError4_0(+(n360_0, 1))) ->_R^Omega(1) 1113.72/291.74 le(gen_0':s:logZeroError4_0(n360_0), gen_0':s:logZeroError4_0(n360_0)) ->_IH 1113.72/291.74 true 1113.72/291.74 1113.72/291.74 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1113.72/291.74 ---------------------------------------- 1113.72/291.74 1113.72/291.74 (24) 1113.72/291.74 Obligation: 1113.72/291.74 Innermost TRS: 1113.72/291.74 Rules: 1113.72/291.74 half(0') -> 0' 1113.72/291.74 half(s(0')) -> 0' 1113.72/291.74 half(s(s(x))) -> s(half(x)) 1113.72/291.74 le(0', y) -> true 1113.72/291.74 le(s(x), 0') -> false 1113.72/291.74 le(s(x), s(y)) -> le(x, y) 1113.72/291.74 inc(s(x)) -> s(inc(x)) 1113.72/291.74 inc(0') -> s(0') 1113.72/291.74 logarithm(x) -> logIter(x, 0') 1113.72/291.74 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), half(x), inc(y)) 1113.72/291.74 if(false, b, x, y) -> logZeroError 1113.72/291.74 if(true, false, x, s(y)) -> y 1113.72/291.74 if(true, true, x, y) -> logIter(x, y) 1113.72/291.74 f -> g 1113.72/291.74 f -> h 1113.72/291.74 1113.72/291.74 Types: 1113.72/291.74 half :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 0' :: 0':s:logZeroError 1113.72/291.74 s :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 1113.72/291.74 true :: true:false 1113.72/291.74 false :: true:false 1113.72/291.74 inc :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logarithm :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logZeroError :: 0':s:logZeroError 1113.72/291.74 f :: g:h 1113.72/291.74 g :: g:h 1113.72/291.74 h :: g:h 1113.72/291.74 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 1113.72/291.74 hole_true:false2_0 :: true:false 1113.72/291.74 hole_g:h3_0 :: g:h 1113.72/291.74 gen_0':s:logZeroError4_0 :: Nat -> 0':s:logZeroError 1113.72/291.74 1113.72/291.74 1113.72/291.74 Lemmas: 1113.72/291.74 half(gen_0':s:logZeroError4_0(*(2, n6_0))) -> gen_0':s:logZeroError4_0(n6_0), rt in Omega(1 + n6_0) 1113.72/291.74 le(gen_0':s:logZeroError4_0(n360_0), gen_0':s:logZeroError4_0(n360_0)) -> true, rt in Omega(1 + n360_0) 1113.72/291.74 1113.72/291.74 1113.72/291.74 Generator Equations: 1113.72/291.74 gen_0':s:logZeroError4_0(0) <=> 0' 1113.72/291.74 gen_0':s:logZeroError4_0(+(x, 1)) <=> s(gen_0':s:logZeroError4_0(x)) 1113.72/291.74 1113.72/291.74 1113.72/291.74 The following defined symbols remain to be analysed: 1113.72/291.74 inc, logIter 1113.72/291.74 1113.72/291.74 They will be analysed ascendingly in the following order: 1113.72/291.74 inc < logIter 1113.72/291.74 1113.72/291.74 ---------------------------------------- 1113.72/291.74 1113.72/291.74 (25) RewriteLemmaProof (LOWER BOUND(ID)) 1113.72/291.74 Proved the following rewrite lemma: 1113.72/291.74 inc(gen_0':s:logZeroError4_0(n703_0)) -> gen_0':s:logZeroError4_0(+(1, n703_0)), rt in Omega(1 + n703_0) 1113.72/291.74 1113.72/291.74 Induction Base: 1113.72/291.74 inc(gen_0':s:logZeroError4_0(0)) ->_R^Omega(1) 1113.72/291.74 s(0') 1113.72/291.74 1113.72/291.74 Induction Step: 1113.72/291.74 inc(gen_0':s:logZeroError4_0(+(n703_0, 1))) ->_R^Omega(1) 1113.72/291.74 s(inc(gen_0':s:logZeroError4_0(n703_0))) ->_IH 1113.72/291.74 s(gen_0':s:logZeroError4_0(+(1, c704_0))) 1113.72/291.74 1113.72/291.74 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1113.72/291.74 ---------------------------------------- 1113.72/291.74 1113.72/291.74 (26) 1113.72/291.74 Obligation: 1113.72/291.74 Innermost TRS: 1113.72/291.74 Rules: 1113.72/291.74 half(0') -> 0' 1113.72/291.74 half(s(0')) -> 0' 1113.72/291.74 half(s(s(x))) -> s(half(x)) 1113.72/291.74 le(0', y) -> true 1113.72/291.74 le(s(x), 0') -> false 1113.72/291.74 le(s(x), s(y)) -> le(x, y) 1113.72/291.74 inc(s(x)) -> s(inc(x)) 1113.72/291.74 inc(0') -> s(0') 1113.72/291.74 logarithm(x) -> logIter(x, 0') 1113.72/291.74 logIter(x, y) -> if(le(s(0'), x), le(s(s(0')), x), half(x), inc(y)) 1113.72/291.74 if(false, b, x, y) -> logZeroError 1113.72/291.74 if(true, false, x, s(y)) -> y 1113.72/291.74 if(true, true, x, y) -> logIter(x, y) 1113.72/291.74 f -> g 1113.72/291.74 f -> h 1113.72/291.74 1113.72/291.74 Types: 1113.72/291.74 half :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 0' :: 0':s:logZeroError 1113.72/291.74 s :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 le :: 0':s:logZeroError -> 0':s:logZeroError -> true:false 1113.72/291.74 true :: true:false 1113.72/291.74 false :: true:false 1113.72/291.74 inc :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logarithm :: 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logIter :: 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 if :: true:false -> true:false -> 0':s:logZeroError -> 0':s:logZeroError -> 0':s:logZeroError 1113.72/291.74 logZeroError :: 0':s:logZeroError 1113.72/291.74 f :: g:h 1113.72/291.74 g :: g:h 1113.72/291.74 h :: g:h 1113.72/291.74 hole_0':s:logZeroError1_0 :: 0':s:logZeroError 1113.72/291.74 hole_true:false2_0 :: true:false 1113.72/291.74 hole_g:h3_0 :: g:h 1113.72/291.74 gen_0':s:logZeroError4_0 :: Nat -> 0':s:logZeroError 1113.72/291.74 1113.72/291.74 1113.72/291.74 Lemmas: 1113.72/291.74 half(gen_0':s:logZeroError4_0(*(2, n6_0))) -> gen_0':s:logZeroError4_0(n6_0), rt in Omega(1 + n6_0) 1113.72/291.74 le(gen_0':s:logZeroError4_0(n360_0), gen_0':s:logZeroError4_0(n360_0)) -> true, rt in Omega(1 + n360_0) 1113.72/291.74 inc(gen_0':s:logZeroError4_0(n703_0)) -> gen_0':s:logZeroError4_0(+(1, n703_0)), rt in Omega(1 + n703_0) 1113.72/291.74 1113.72/291.74 1113.72/291.74 Generator Equations: 1113.72/291.74 gen_0':s:logZeroError4_0(0) <=> 0' 1113.72/291.74 gen_0':s:logZeroError4_0(+(x, 1)) <=> s(gen_0':s:logZeroError4_0(x)) 1113.72/291.74 1113.72/291.74 1113.72/291.74 The following defined symbols remain to be analysed: 1113.72/291.74 logIter 1113.94/291.80 EOF