32.48/10.60 WORST_CASE(Omega(n^1), O(n^1)) 32.48/10.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 32.48/10.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 32.48/10.61 32.48/10.61 32.48/10.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 32.48/10.61 32.48/10.61 (0) CpxTRS 32.48/10.61 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 32.48/10.61 (2) CpxWeightedTrs 32.48/10.61 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 32.48/10.61 (4) CpxTypedWeightedTrs 32.48/10.61 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 32.48/10.61 (6) CpxTypedWeightedCompleteTrs 32.48/10.61 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 32.48/10.61 (8) CpxRNTS 32.48/10.61 (9) CompleteCoflocoProof [FINISHED, 783 ms] 32.48/10.61 (10) BOUNDS(1, n^1) 32.48/10.61 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 32.48/10.61 (12) CpxTRS 32.48/10.61 (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 32.48/10.61 (14) typed CpxTrs 32.48/10.61 (15) OrderProof [LOWER BOUND(ID), 0 ms] 32.48/10.61 (16) typed CpxTrs 32.48/10.61 (17) RewriteLemmaProof [LOWER BOUND(ID), 275 ms] 32.48/10.61 (18) BEST 32.48/10.61 (19) proven lower bound 32.48/10.61 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 32.48/10.61 (21) BOUNDS(n^1, INF) 32.48/10.61 (22) typed CpxTrs 32.48/10.61 (23) RewriteLemmaProof [LOWER BOUND(ID), 47 ms] 32.48/10.61 (24) typed CpxTrs 32.48/10.61 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (0) 32.48/10.61 Obligation: 32.48/10.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 32.48/10.61 32.48/10.61 32.48/10.61 The TRS R consists of the following rules: 32.48/10.61 32.48/10.61 lt(0, s(x)) -> true 32.48/10.61 lt(x, 0) -> false 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) 32.48/10.61 logarithm(x) -> ifa(lt(0, x), x) 32.48/10.61 ifa(true, x) -> help(x, 1) 32.48/10.61 ifa(false, x) -> logZeroError 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) 32.48/10.61 ifb(false, x, y) -> y 32.48/10.61 half(0) -> 0 32.48/10.61 half(s(0)) -> 0 32.48/10.61 half(s(s(x))) -> s(half(x)) 32.48/10.61 32.48/10.61 S is empty. 32.48/10.61 Rewrite Strategy: INNERMOST 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 32.48/10.61 Transformed relative TRS to weighted TRS 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (2) 32.48/10.61 Obligation: 32.48/10.61 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 32.48/10.61 32.48/10.61 32.48/10.61 The TRS R consists of the following rules: 32.48/10.61 32.48/10.61 lt(0, s(x)) -> true [1] 32.48/10.61 lt(x, 0) -> false [1] 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) [1] 32.48/10.61 logarithm(x) -> ifa(lt(0, x), x) [1] 32.48/10.61 ifa(true, x) -> help(x, 1) [1] 32.48/10.61 ifa(false, x) -> logZeroError [1] 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) [1] 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) [1] 32.48/10.61 ifb(false, x, y) -> y [1] 32.48/10.61 half(0) -> 0 [1] 32.48/10.61 half(s(0)) -> 0 [1] 32.48/10.61 half(s(s(x))) -> s(half(x)) [1] 32.48/10.61 32.48/10.61 Rewrite Strategy: INNERMOST 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 32.48/10.61 Infered types. 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (4) 32.48/10.61 Obligation: 32.48/10.61 Runtime Complexity Weighted TRS with Types. 32.48/10.61 The TRS R consists of the following rules: 32.48/10.61 32.48/10.61 lt(0, s(x)) -> true [1] 32.48/10.61 lt(x, 0) -> false [1] 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) [1] 32.48/10.61 logarithm(x) -> ifa(lt(0, x), x) [1] 32.48/10.61 ifa(true, x) -> help(x, 1) [1] 32.48/10.61 ifa(false, x) -> logZeroError [1] 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) [1] 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) [1] 32.48/10.61 ifb(false, x, y) -> y [1] 32.48/10.61 half(0) -> 0 [1] 32.48/10.61 half(s(0)) -> 0 [1] 32.48/10.61 half(s(s(x))) -> s(half(x)) [1] 32.48/10.61 32.48/10.61 The TRS has the following type information: 32.48/10.61 lt :: 0:s:1:logZeroError -> 0:s:1:logZeroError -> true:false 32.48/10.61 0 :: 0:s:1:logZeroError 32.48/10.61 s :: 0:s:1:logZeroError -> 0:s:1:logZeroError 32.48/10.61 true :: true:false 32.48/10.61 false :: true:false 32.48/10.61 logarithm :: 0:s:1:logZeroError -> 0:s:1:logZeroError 32.48/10.61 ifa :: true:false -> 0:s:1:logZeroError -> 0:s:1:logZeroError 32.48/10.61 help :: 0:s:1:logZeroError -> 0:s:1:logZeroError -> 0:s:1:logZeroError 32.48/10.61 1 :: 0:s:1:logZeroError 32.48/10.61 logZeroError :: 0:s:1:logZeroError 32.48/10.61 ifb :: true:false -> 0:s:1:logZeroError -> 0:s:1:logZeroError -> 0:s:1:logZeroError 32.48/10.61 half :: 0:s:1:logZeroError -> 0:s:1:logZeroError 32.48/10.61 32.48/10.61 Rewrite Strategy: INNERMOST 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (5) CompletionProof (UPPER BOUND(ID)) 32.48/10.61 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 32.48/10.61 32.48/10.61 lt(v0, v1) -> null_lt [0] 32.48/10.61 half(v0) -> null_half [0] 32.48/10.61 ifa(v0, v1) -> null_ifa [0] 32.48/10.61 ifb(v0, v1, v2) -> null_ifb [0] 32.48/10.61 32.48/10.61 And the following fresh constants: null_lt, null_half, null_ifa, null_ifb 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (6) 32.48/10.61 Obligation: 32.48/10.61 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 32.48/10.61 32.48/10.61 Runtime Complexity Weighted TRS with Types. 32.48/10.61 The TRS R consists of the following rules: 32.48/10.61 32.48/10.61 lt(0, s(x)) -> true [1] 32.48/10.61 lt(x, 0) -> false [1] 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) [1] 32.48/10.61 logarithm(x) -> ifa(lt(0, x), x) [1] 32.48/10.61 ifa(true, x) -> help(x, 1) [1] 32.48/10.61 ifa(false, x) -> logZeroError [1] 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) [1] 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) [1] 32.48/10.61 ifb(false, x, y) -> y [1] 32.48/10.61 half(0) -> 0 [1] 32.48/10.61 half(s(0)) -> 0 [1] 32.48/10.61 half(s(s(x))) -> s(half(x)) [1] 32.48/10.61 lt(v0, v1) -> null_lt [0] 32.48/10.61 half(v0) -> null_half [0] 32.48/10.61 ifa(v0, v1) -> null_ifa [0] 32.48/10.61 ifb(v0, v1, v2) -> null_ifb [0] 32.48/10.61 32.48/10.61 The TRS has the following type information: 32.48/10.61 lt :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> true:false:null_lt 32.48/10.61 0 :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 s :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 true :: true:false:null_lt 32.48/10.61 false :: true:false:null_lt 32.48/10.61 logarithm :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 ifa :: true:false:null_lt -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 help :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 1 :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 logZeroError :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 ifb :: true:false:null_lt -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 half :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb -> 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 null_lt :: true:false:null_lt 32.48/10.61 null_half :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 null_ifa :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 null_ifb :: 0:s:1:logZeroError:null_half:null_ifa:null_ifb 32.48/10.61 32.48/10.61 Rewrite Strategy: INNERMOST 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 32.48/10.61 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 32.48/10.61 The constant constructors are abstracted as follows: 32.48/10.61 32.48/10.61 0 => 0 32.48/10.61 true => 2 32.48/10.61 false => 1 32.48/10.61 1 => 1 32.48/10.61 logZeroError => 2 32.48/10.61 null_lt => 0 32.48/10.61 null_half => 0 32.48/10.61 null_ifa => 0 32.48/10.61 null_ifb => 0 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (8) 32.48/10.61 Obligation: 32.48/10.61 Complexity RNTS consisting of the following rules: 32.48/10.61 32.48/10.61 half(z) -{ 1 }-> 0 :|: z = 0 32.48/10.61 half(z) -{ 1 }-> 0 :|: z = 1 + 0 32.48/10.61 half(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 32.48/10.61 half(z) -{ 1 }-> 1 + half(x) :|: x >= 0, z = 1 + (1 + x) 32.48/10.61 help(z, z') -{ 1 }-> ifb(lt(y, x), x, y) :|: x >= 0, y >= 0, z = x, z' = y 32.48/10.61 ifa(z, z') -{ 1 }-> help(x, 1) :|: z = 2, z' = x, x >= 0 32.48/10.61 ifa(z, z') -{ 1 }-> 2 :|: z' = x, z = 1, x >= 0 32.48/10.61 ifa(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 32.48/10.61 ifb(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 32.48/10.61 ifb(z, z', z'') -{ 1 }-> help(half(x), 1 + y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 32.48/10.61 ifb(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 32.48/10.61 logarithm(z) -{ 1 }-> ifa(lt(0, x), x) :|: x >= 0, z = x 32.48/10.61 lt(z, z') -{ 1 }-> lt(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 32.48/10.61 lt(z, z') -{ 1 }-> 2 :|: z' = 1 + x, x >= 0, z = 0 32.48/10.61 lt(z, z') -{ 1 }-> 1 :|: x >= 0, z = x, z' = 0 32.48/10.61 lt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 32.48/10.61 32.48/10.61 Only complete derivations are relevant for the runtime complexity. 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (9) CompleteCoflocoProof (FINISHED) 32.48/10.61 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 32.48/10.61 32.48/10.61 eq(start(V1, V, V12),0,[lt(V1, V, Out)],[V1 >= 0,V >= 0]). 32.48/10.61 eq(start(V1, V, V12),0,[logarithm(V1, Out)],[V1 >= 0]). 32.48/10.61 eq(start(V1, V, V12),0,[ifa(V1, V, Out)],[V1 >= 0,V >= 0]). 32.48/10.61 eq(start(V1, V, V12),0,[help(V1, V, Out)],[V1 >= 0,V >= 0]). 32.48/10.61 eq(start(V1, V, V12),0,[ifb(V1, V, V12, Out)],[V1 >= 0,V >= 0,V12 >= 0]). 32.48/10.61 eq(start(V1, V, V12),0,[half(V1, Out)],[V1 >= 0]). 32.48/10.61 eq(lt(V1, V, Out),1,[],[Out = 2,V = 1 + V2,V2 >= 0,V1 = 0]). 32.48/10.61 eq(lt(V1, V, Out),1,[],[Out = 1,V3 >= 0,V1 = V3,V = 0]). 32.48/10.61 eq(lt(V1, V, Out),1,[lt(V4, V5, Ret)],[Out = Ret,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]). 32.48/10.61 eq(logarithm(V1, Out),1,[lt(0, V6, Ret0),ifa(Ret0, V6, Ret1)],[Out = Ret1,V6 >= 0,V1 = V6]). 32.48/10.61 eq(ifa(V1, V, Out),1,[help(V7, 1, Ret2)],[Out = Ret2,V1 = 2,V = V7,V7 >= 0]). 32.48/10.61 eq(ifa(V1, V, Out),1,[],[Out = 2,V = V8,V1 = 1,V8 >= 0]). 32.48/10.61 eq(help(V1, V, Out),1,[lt(V10, V9, Ret01),ifb(Ret01, V9, V10, Ret3)],[Out = Ret3,V9 >= 0,V10 >= 0,V1 = V9,V = V10]). 32.48/10.61 eq(ifb(V1, V, V12, Out),1,[half(V13, Ret02),help(Ret02, 1 + V11, Ret4)],[Out = Ret4,V1 = 2,V = V13,V12 = V11,V13 >= 0,V11 >= 0]). 32.48/10.61 eq(ifb(V1, V, V12, Out),1,[],[Out = V14,V = V15,V12 = V14,V1 = 1,V15 >= 0,V14 >= 0]). 32.48/10.61 eq(half(V1, Out),1,[],[Out = 0,V1 = 0]). 32.48/10.61 eq(half(V1, Out),1,[],[Out = 0,V1 = 1]). 32.48/10.61 eq(half(V1, Out),1,[half(V16, Ret11)],[Out = 1 + Ret11,V16 >= 0,V1 = 2 + V16]). 32.48/10.61 eq(lt(V1, V, Out),0,[],[Out = 0,V18 >= 0,V17 >= 0,V1 = V18,V = V17]). 32.48/10.61 eq(half(V1, Out),0,[],[Out = 0,V19 >= 0,V1 = V19]). 32.48/10.61 eq(ifa(V1, V, Out),0,[],[Out = 0,V21 >= 0,V20 >= 0,V1 = V21,V = V20]). 32.48/10.61 eq(ifb(V1, V, V12, Out),0,[],[Out = 0,V22 >= 0,V12 = V24,V23 >= 0,V1 = V22,V = V23,V24 >= 0]). 32.48/10.61 input_output_vars(lt(V1,V,Out),[V1,V],[Out]). 32.48/10.61 input_output_vars(logarithm(V1,Out),[V1],[Out]). 32.48/10.61 input_output_vars(ifa(V1,V,Out),[V1,V],[Out]). 32.48/10.61 input_output_vars(help(V1,V,Out),[V1,V],[Out]). 32.48/10.61 input_output_vars(ifb(V1,V,V12,Out),[V1,V,V12],[Out]). 32.48/10.61 input_output_vars(half(V1,Out),[V1],[Out]). 32.48/10.61 32.48/10.61 32.48/10.61 CoFloCo proof output: 32.48/10.61 Preprocessing Cost Relations 32.48/10.61 ===================================== 32.48/10.61 32.48/10.61 #### Computed strongly connected components 32.48/10.61 0. recursive : [half/2] 32.48/10.61 1. recursive : [lt/3] 32.48/10.61 2. recursive : [help/3,ifb/4] 32.48/10.61 3. non_recursive : [ifa/3] 32.48/10.61 4. non_recursive : [logarithm/2] 32.48/10.61 5. non_recursive : [start/3] 32.48/10.61 32.48/10.61 #### Obtained direct recursion through partial evaluation 32.48/10.61 0. SCC is partially evaluated into half/2 32.48/10.61 1. SCC is partially evaluated into lt/3 32.48/10.61 2. SCC is partially evaluated into help/3 32.48/10.61 3. SCC is partially evaluated into ifa/3 32.48/10.61 4. SCC is partially evaluated into logarithm/2 32.48/10.61 5. SCC is partially evaluated into start/3 32.48/10.61 32.48/10.61 Control-Flow Refinement of Cost Relations 32.48/10.61 ===================================== 32.48/10.61 32.48/10.61 ### Specialization of cost equations half/2 32.48/10.61 * CE 10 is refined into CE [24] 32.48/10.61 * CE 9 is refined into CE [25] 32.48/10.61 * CE 12 is refined into CE [26] 32.48/10.61 * CE 11 is refined into CE [27] 32.48/10.61 32.48/10.61 32.48/10.61 ### Cost equations --> "Loop" of half/2 32.48/10.61 * CEs [27] --> Loop 17 32.48/10.61 * CEs [24] --> Loop 18 32.48/10.61 * CEs [25,26] --> Loop 19 32.48/10.61 32.48/10.61 ### Ranking functions of CR half(V1,Out) 32.48/10.61 * RF of phase [17]: [V1-1] 32.48/10.61 32.48/10.61 #### Partial ranking functions of CR half(V1,Out) 32.48/10.61 * Partial RF of phase [17]: 32.48/10.61 - RF of loop [17:1]: 32.48/10.61 V1-1 32.48/10.61 32.48/10.61 32.48/10.61 ### Specialization of cost equations lt/3 32.48/10.61 * CE 19 is refined into CE [28] 32.48/10.61 * CE 17 is refined into CE [29] 32.48/10.61 * CE 16 is refined into CE [30] 32.48/10.61 * CE 18 is refined into CE [31] 32.48/10.61 32.48/10.61 32.48/10.61 ### Cost equations --> "Loop" of lt/3 32.48/10.61 * CEs [31] --> Loop 20 32.48/10.61 * CEs [28] --> Loop 21 32.48/10.61 * CEs [29] --> Loop 22 32.48/10.61 * CEs [30] --> Loop 23 32.48/10.61 32.48/10.61 ### Ranking functions of CR lt(V1,V,Out) 32.48/10.61 * RF of phase [20]: [V,V1] 32.48/10.61 32.48/10.61 #### Partial ranking functions of CR lt(V1,V,Out) 32.48/10.61 * Partial RF of phase [20]: 32.48/10.61 - RF of loop [20:1]: 32.48/10.61 V 32.48/10.61 V1 32.48/10.61 32.48/10.61 32.48/10.61 ### Specialization of cost equations help/3 32.48/10.61 * CE 15 is refined into CE [32,33,34,35] 32.48/10.61 * CE 14 is refined into CE [36,37] 32.48/10.61 * CE 13 is refined into CE [38,39,40,41,42] 32.48/10.61 32.48/10.61 32.48/10.61 ### Cost equations --> "Loop" of help/3 32.48/10.61 * CEs [37] --> Loop 24 32.48/10.61 * CEs [38] --> Loop 25 32.48/10.61 * CEs [36] --> Loop 26 32.48/10.61 * CEs [39,40,41,42] --> Loop 27 32.48/10.61 * CEs [35] --> Loop 28 32.48/10.61 * CEs [34] --> Loop 29 32.48/10.61 * CEs [33] --> Loop 30 32.48/10.61 * CEs [32] --> Loop 31 32.48/10.61 32.48/10.61 ### Ranking functions of CR help(V1,V,Out) 32.48/10.61 * RF of phase [28]: [V1-1,V1/2-V/2] 32.48/10.61 32.48/10.61 #### Partial ranking functions of CR help(V1,V,Out) 32.48/10.61 * Partial RF of phase [28]: 32.48/10.61 - RF of loop [28:1]: 32.48/10.61 V1-1 32.48/10.61 V1/2-V/2 32.48/10.61 32.48/10.61 32.48/10.61 ### Specialization of cost equations ifa/3 32.48/10.61 * CE 23 is refined into CE [43] 32.48/10.61 * CE 21 is refined into CE [44,45,46,47] 32.48/10.61 * CE 22 is refined into CE [48] 32.48/10.61 32.48/10.61 32.48/10.61 ### Cost equations --> "Loop" of ifa/3 32.48/10.61 * CEs [46] --> Loop 32 32.48/10.61 * CEs [43,45] --> Loop 33 32.48/10.61 * CEs [47] --> Loop 34 32.48/10.61 * CEs [44] --> Loop 35 32.48/10.61 * CEs [48] --> Loop 36 32.48/10.61 32.48/10.61 ### Ranking functions of CR ifa(V1,V,Out) 32.48/10.61 32.48/10.61 #### Partial ranking functions of CR ifa(V1,V,Out) 32.48/10.61 32.48/10.61 32.48/10.61 ### Specialization of cost equations logarithm/2 32.48/10.61 * CE 20 is refined into CE [49,50,51,52,53,54] 32.48/10.61 32.48/10.61 32.48/10.61 ### Cost equations --> "Loop" of logarithm/2 32.48/10.61 * CEs [50] --> Loop 37 32.48/10.61 * CEs [49] --> Loop 38 32.48/10.61 * CEs [52] --> Loop 39 32.48/10.61 * CEs [51,53,54] --> Loop 40 32.48/10.61 32.48/10.61 ### Ranking functions of CR logarithm(V1,Out) 32.48/10.61 32.48/10.61 #### Partial ranking functions of CR logarithm(V1,Out) 32.48/10.61 32.48/10.61 32.48/10.61 ### Specialization of cost equations start/3 32.48/10.61 * CE 3 is refined into CE [55,56,57,58,59] 32.48/10.61 * CE 1 is refined into CE [60] 32.48/10.61 * CE 2 is refined into CE [61] 32.48/10.61 * CE 4 is refined into CE [62,63,64,65,66] 32.48/10.61 * CE 5 is refined into CE [67,68,69,70] 32.48/10.61 * CE 6 is refined into CE [71,72,73,74,75] 32.48/10.61 * CE 7 is refined into CE [76,77,78,79,80,81] 32.48/10.61 * CE 8 is refined into CE [82,83] 32.48/10.61 32.48/10.61 32.48/10.61 ### Cost equations --> "Loop" of start/3 32.48/10.61 * CEs [74] --> Loop 41 32.48/10.61 * CEs [55,56,57,58,59] --> Loop 42 32.48/10.61 * CEs [73] --> Loop 43 32.48/10.61 * CEs [63,72,78,79] --> Loop 44 32.48/10.61 * CEs [61,68,71] --> Loop 45 32.48/10.61 * CEs [60,62,64,65,66,67,69,70,75,76,77,80,81,82,83] --> Loop 46 32.48/10.61 32.48/10.61 ### Ranking functions of CR start(V1,V,V12) 32.48/10.61 32.48/10.61 #### Partial ranking functions of CR start(V1,V,V12) 32.48/10.61 32.48/10.61 32.48/10.61 Computing Bounds 32.48/10.61 ===================================== 32.48/10.61 32.48/10.61 #### Cost of chains of half(V1,Out): 32.48/10.61 * Chain [[17],19]: 1*it(17)+1 32.48/10.61 Such that:it(17) =< 2*Out 32.48/10.61 32.48/10.61 with precondition: [Out>=1,V1>=2*Out] 32.48/10.61 32.48/10.61 * Chain [[17],18]: 1*it(17)+1 32.48/10.61 Such that:it(17) =< 2*Out 32.48/10.61 32.48/10.61 with precondition: [V1=2*Out+1,V1>=3] 32.48/10.61 32.48/10.61 * Chain [19]: 1 32.48/10.61 with precondition: [Out=0,V1>=0] 32.48/10.61 32.48/10.61 * Chain [18]: 1 32.48/10.61 with precondition: [V1=1,Out=0] 32.48/10.61 32.48/10.61 32.48/10.61 #### Cost of chains of lt(V1,V,Out): 32.48/10.61 * Chain [[20],23]: 1*it(20)+1 32.48/10.61 Such that:it(20) =< V1 32.48/10.61 32.48/10.61 with precondition: [Out=2,V1>=1,V>=V1+1] 32.48/10.61 32.48/10.61 * Chain [[20],22]: 1*it(20)+1 32.48/10.61 Such that:it(20) =< V 32.48/10.61 32.48/10.61 with precondition: [Out=1,V>=1,V1>=V] 32.48/10.61 32.48/10.61 * Chain [[20],21]: 1*it(20)+0 32.48/10.61 Such that:it(20) =< V 32.48/10.61 32.48/10.61 with precondition: [Out=0,V1>=1,V>=1] 32.48/10.61 32.48/10.61 * Chain [23]: 1 32.48/10.61 with precondition: [V1=0,Out=2,V>=1] 32.48/10.61 32.48/10.61 * Chain [22]: 1 32.48/10.61 with precondition: [V=0,Out=1,V1>=0] 32.48/10.61 32.48/10.61 * Chain [21]: 0 32.48/10.61 with precondition: [Out=0,V1>=0,V>=0] 32.48/10.61 32.48/10.61 32.48/10.61 #### Cost of chains of help(V1,V,Out): 32.48/10.61 * Chain [[28],29,27]: 4*it(28)+4*s(6)+1*s(14)+6 32.48/10.61 Such that:s(14) =< 3*V1+V+1 32.48/10.61 it(28) =< V1/2-V/2 32.48/10.61 aux(4) =< 2*V1-V 32.48/10.61 s(6) =< aux(4) 32.48/10.61 32.48/10.61 with precondition: [Out=0,V>=1,V1>=2*V+4] 32.48/10.61 32.48/10.61 * Chain [[28],29,26]: 4*it(28)+1*s(7)+1*s(14)+2*s(15)+7 32.48/10.61 Such that:s(16) =< 2*V1-V-Out 32.48/10.61 s(14) =< 3*V1+V-4*Out+1 32.48/10.61 it(28) =< V1/2-V/2 32.48/10.61 s(7) =< Out 32.48/10.61 s(15) =< s(16) 32.48/10.61 32.48/10.61 with precondition: [V>=1,Out>=V+2,V1+8*V+16>=10*Out] 32.48/10.61 32.48/10.61 * Chain [[28],27]: 4*it(28)+4*s(4)+2*s(15)+2 32.48/10.61 Such that:it(28) =< 4*V1 32.48/10.61 s(16) =< 5*V1 32.48/10.61 aux(5) =< 3*V1+V 32.48/10.61 s(4) =< aux(5) 32.48/10.61 s(15) =< s(16) 32.48/10.61 32.48/10.61 with precondition: [Out=0,V>=1,V1>=V+1] 32.48/10.61 32.48/10.61 * Chain [[28],24]: 4*it(28)+2*s(14)+2*s(15)+3 32.48/10.61 Such that:s(16) =< 2*V1-V+Out 32.48/10.61 it(28) =< V1/2-V/2 32.48/10.61 aux(6) =< 3*V1+V-Out 32.48/10.61 s(14) =< aux(6) 32.48/10.61 s(15) =< s(16) 32.48/10.61 32.48/10.61 with precondition: [V>=1,Out>=V+1,V1+3*V+3>=4*Out] 32.48/10.61 32.48/10.61 * Chain [31,27]: 1*s(6)+6 32.48/10.61 Such that:s(6) =< 1 32.48/10.61 32.48/10.61 with precondition: [V=0,Out=0,V1>=1] 32.48/10.61 32.48/10.61 * Chain [31,26]: 7 32.48/10.61 with precondition: [V=0,Out=1,V1>=1] 32.48/10.61 32.48/10.61 * Chain [30,[28],29,27]: 4*it(28)+6*s(6)+1*s(14)+10 32.48/10.61 Such that:it(28) =< V1/4 32.48/10.61 s(14) =< 3/2*V1+2 32.48/10.61 aux(7) =< V1 32.48/10.61 s(6) =< aux(7) 32.48/10.61 32.48/10.61 with precondition: [V=0,Out=0,V1>=12] 32.48/10.61 32.48/10.61 * Chain [30,[28],29,26]: 4*it(28)+1*s(7)+1*s(14)+2*s(15)+2*s(19)+11 32.48/10.61 Such that:s(18) =< V1 32.48/10.61 s(16) =< V1-Out 32.48/10.61 it(28) =< V1/4 32.48/10.61 s(14) =< 3/2*V1-4*Out+2 32.48/10.61 s(7) =< Out 32.48/10.61 s(15) =< s(16) 32.48/10.61 s(19) =< s(18) 32.48/10.61 32.48/10.61 with precondition: [V=0,Out>=3,V1+48>=20*Out] 32.48/10.61 32.48/10.61 * Chain [30,[28],27]: 4*it(28)+4*s(4)+2*s(15)+2*s(19)+6 32.48/10.61 Such that:s(18) =< V1 32.48/10.61 it(28) =< 2*V1 32.48/10.61 aux(5) =< 3/2*V1+1 32.48/10.61 s(16) =< 5/2*V1 32.48/10.61 s(4) =< aux(5) 32.48/10.61 s(15) =< s(16) 32.48/10.61 s(19) =< s(18) 32.48/10.61 32.48/10.61 with precondition: [V=0,Out=0,V1>=4] 32.48/10.61 32.48/10.61 * Chain [30,[28],24]: 4*it(28)+2*s(14)+2*s(15)+2*s(19)+7 32.48/10.61 Such that:s(18) =< V1 32.48/10.61 s(16) =< V1+Out 32.48/10.61 it(28) =< V1/4 32.48/10.61 aux(6) =< 3/2*V1-Out+1 32.48/10.61 s(14) =< aux(6) 32.48/10.61 s(15) =< s(16) 32.48/10.61 s(19) =< s(18) 32.48/10.61 32.48/10.61 with precondition: [V=0,Out>=2,V1+12>=8*Out] 32.48/10.61 32.48/10.61 * Chain [30,29,27]: 2*s(6)+2*s(19)+10 32.48/10.61 Such that:aux(3) =< 2 32.48/10.61 s(18) =< V1 32.48/10.61 s(6) =< aux(3) 32.48/10.61 s(19) =< s(18) 32.48/10.61 32.48/10.61 with precondition: [V=0,Out=0,V1>=4] 32.48/10.61 32.48/10.61 * Chain [30,29,26]: 1*s(7)+2*s(19)+11 32.48/10.61 Such that:s(7) =< 2 32.48/10.61 s(18) =< V1 32.48/10.61 s(19) =< s(18) 32.48/10.61 32.48/10.61 with precondition: [V=0,Out=2,V1>=4] 32.48/10.61 32.48/10.61 * Chain [30,27]: 2*s(4)+1*s(6)+2*s(19)+6 32.48/10.61 Such that:s(6) =< 1 32.48/10.61 s(18) =< V1 32.48/10.61 aux(2) =< V1/2 32.48/10.61 s(4) =< aux(2) 32.48/10.61 s(19) =< s(18) 32.48/10.61 32.48/10.61 with precondition: [V=0,Out=0,V1>=2] 32.48/10.61 32.48/10.61 * Chain [30,24]: 1*s(17)+2*s(19)+7 32.48/10.61 Such that:s(17) =< 1 32.48/10.61 s(18) =< 2 32.48/10.61 s(19) =< s(18) 32.48/10.61 32.48/10.61 with precondition: [V=0,Out=1,V1>=2] 32.48/10.61 32.48/10.61 * Chain [29,27]: 2*s(6)+6 32.48/10.61 Such that:aux(3) =< V+1 32.48/10.61 s(6) =< aux(3) 32.48/10.61 32.48/10.61 with precondition: [Out=0,V>=1,V1>=V+1] 32.48/10.61 32.48/10.61 * Chain [29,26]: 1*s(7)+7 32.48/10.61 Such that:s(7) =< Out 32.48/10.61 32.48/10.61 with precondition: [V+1=Out,V>=1,V1>=V+1] 32.48/10.61 32.48/10.61 * Chain [27]: 2*s(4)+1*s(6)+2 32.48/10.61 Such that:s(6) =< V 32.48/10.61 aux(2) =< V1 32.48/10.61 s(4) =< aux(2) 32.48/10.61 32.48/10.61 with precondition: [Out=0,V1>=0,V>=0] 32.48/10.61 32.48/10.61 * Chain [26]: 3 32.48/10.61 with precondition: [V1=0,V=Out,V>=0] 32.48/10.61 32.48/10.61 * Chain [25]: 2 32.48/10.61 with precondition: [V=0,Out=0,V1>=1] 32.48/10.61 32.48/10.61 * Chain [24]: 1*s(17)+3 32.48/10.61 Such that:s(17) =< V1 32.48/10.61 32.48/10.61 with precondition: [V=Out,V1>=1,V>=V1] 32.48/10.61 32.48/10.61 32.48/10.61 #### Cost of chains of ifa(V1,V,Out): 32.48/10.61 * Chain [36]: 1 32.48/10.61 with precondition: [V1=1,Out=2,V>=0] 32.48/10.61 32.48/10.61 * Chain [35]: 4 32.48/10.61 with precondition: [V1=2,V=0,Out=1] 32.48/10.61 32.48/10.61 * Chain [34]: 1*s(86)+4 32.48/10.61 Such that:s(86) =< 1 32.48/10.61 32.48/10.61 with precondition: [V1=2,V=1,Out=1] 32.48/10.61 32.48/10.61 * Chain [33]: 8*s(88)+1*s(91)+4*s(92)+6*s(95)+4*s(96)+1*s(98)+3*s(100)+14*s(106)+4*s(107)+4*s(108)+2*s(109)+4*s(111)+2*s(112)+11 32.48/10.61 Such that:aux(14) =< 1 32.48/10.61 aux(15) =< 2 32.48/10.61 s(103) =< V 32.48/10.61 aux(16) =< 2*V 32.48/10.61 s(90) =< 3*V+1 32.48/10.61 s(91) =< 3*V+2 32.48/10.61 s(92) =< 4*V 32.48/10.61 s(93) =< 5*V 32.48/10.61 aux(17) =< V/2 32.48/10.61 s(96) =< V/4 32.48/10.61 s(97) =< 3/2*V+1 32.48/10.61 s(98) =< 3/2*V+2 32.48/10.61 s(99) =< 5/2*V 32.48/10.61 s(100) =< aux(14) 32.48/10.61 s(88) =< aux(16) 32.48/10.61 s(95) =< aux(17) 32.48/10.61 s(106) =< s(103) 32.48/10.61 s(107) =< aux(15) 32.48/10.61 s(108) =< s(97) 32.48/10.61 s(109) =< s(99) 32.48/10.61 s(111) =< s(90) 32.48/10.61 s(112) =< s(93) 32.48/10.61 32.48/10.61 with precondition: [Out=0,V1>=0,V>=0] 32.48/10.61 32.48/10.61 * Chain [32]: 3*s(116)+8*s(120)+2*s(122)+2*s(123)+2*s(124)+8 32.48/10.61 Such that:s(114) =< 4*V 32.48/10.61 s(117) =< 5*V 32.48/10.61 s(115) =< 11*V 32.48/10.61 s(118) =< V/2 32.48/10.61 aux(18) =< 3*V+2 32.48/10.61 s(116) =< aux(18) 32.48/10.61 s(120) =< s(118) 32.48/10.61 s(122) =< s(114) 32.48/10.61 s(123) =< s(117) 32.48/10.61 s(124) =< s(115) 32.48/10.61 32.48/10.61 with precondition: [V1=2,Out>=2,V+6>=4*Out] 32.48/10.61 32.48/10.61 32.48/10.61 #### Cost of chains of logarithm(V1,Out): 32.48/10.61 * Chain [40]: 2*s(130)+8*s(131)+8*s(134)+2*s(136)+17*s(138)+16*s(139)+12*s(140)+29*s(141)+14*s(142)+8*s(143)+4*s(144)+8*s(145)+4*s(146)+13 32.48/10.61 Such that:aux(23) =< 1 32.48/10.61 aux(24) =< 2 32.48/10.61 aux(25) =< V1 32.48/10.61 aux(26) =< 2*V1 32.48/10.61 aux(27) =< 3*V1+1 32.48/10.61 aux(28) =< 3*V1+2 32.48/10.61 aux(29) =< 4*V1 32.48/10.61 aux(30) =< 5*V1 32.48/10.61 aux(31) =< V1/2 32.48/10.61 aux(32) =< V1/4 32.48/10.61 aux(33) =< 3/2*V1+1 32.48/10.61 aux(34) =< 3/2*V1+2 32.48/10.61 aux(35) =< 5/2*V1 32.48/10.61 s(130) =< aux(28) 32.48/10.61 s(131) =< aux(29) 32.48/10.61 s(134) =< aux(32) 32.48/10.61 s(136) =< aux(34) 32.48/10.61 s(142) =< aux(24) 32.48/10.61 s(138) =< aux(23) 32.48/10.61 s(139) =< aux(26) 32.48/10.61 s(140) =< aux(31) 32.48/10.61 s(141) =< aux(25) 32.48/10.61 s(143) =< aux(33) 32.48/10.61 s(144) =< aux(35) 32.48/10.61 s(145) =< aux(27) 32.48/10.61 s(146) =< aux(30) 32.48/10.61 32.48/10.61 with precondition: [Out=0,V1>=0] 32.48/10.61 32.48/10.61 * Chain [39]: 3 32.48/10.61 with precondition: [V1=0,Out=2] 32.48/10.61 32.48/10.61 * Chain [38]: 1*s(192)+6 32.48/10.61 Such that:s(192) =< 1 32.48/10.61 32.48/10.61 with precondition: [V1=1,Out=1] 32.48/10.61 32.48/10.61 * Chain [37]: 3*s(198)+8*s(199)+2*s(200)+2*s(201)+2*s(202)+10 32.48/10.61 Such that:s(197) =< 3*V1+2 32.48/10.61 s(193) =< 4*V1 32.48/10.61 s(194) =< 5*V1 32.48/10.61 s(195) =< 11*V1 32.48/10.61 s(196) =< V1/2 32.48/10.61 s(198) =< s(197) 32.48/10.61 s(199) =< s(196) 32.48/10.61 s(200) =< s(193) 32.48/10.61 s(201) =< s(194) 32.48/10.61 s(202) =< s(195) 32.48/10.61 32.48/10.61 with precondition: [Out>=2,V1+6>=4*Out] 32.48/10.61 32.48/10.61 32.48/10.61 #### Cost of chains of start(V1,V,V12): 32.48/10.61 * Chain [46]: 17*s(203)+47*s(205)+5*s(219)+14*s(220)+12*s(221)+3*s(222)+20*s(223)+22*s(224)+20*s(225)+22*s(226)+12*s(228)+6*s(229)+8*s(230)+10*s(231)+2*s(241)+1*s(247)+4*s(248)+4*s(251)+1*s(253)+8*s(256)+6*s(257)+4*s(260)+2*s(261)+4*s(262)+2*s(263)+4*s(268)+12*s(272)+4*s(287)+4*s(288)+2*s(290)+2*s(299)+2*s(301)+13 32.48/10.61 Such that:s(266) =< 2*V1-V 32.48/10.61 s(210) =< 3*V1+1 32.48/10.61 s(267) =< 3*V1+V 32.48/10.61 s(291) =< 4*V1-2*V 32.48/10.61 s(235) =< 11*V1 32.48/10.61 s(292) =< 11*V1-3*V+1 32.48/10.61 s(278) =< V+1 32.48/10.61 s(245) =< 2*V 32.48/10.61 s(246) =< 3*V+1 32.48/10.61 s(247) =< 3*V+2 32.48/10.61 s(248) =< 4*V 32.48/10.61 s(249) =< 5*V 32.48/10.61 s(250) =< V/2 32.48/10.61 s(251) =< V/4 32.48/10.61 s(252) =< 3/2*V+1 32.48/10.61 s(253) =< 3/2*V+2 32.48/10.61 s(254) =< 5/2*V 32.48/10.61 aux(37) =< 1 32.48/10.61 aux(38) =< 2 32.48/10.61 aux(39) =< V1 32.48/10.61 aux(40) =< 2*V1 32.48/10.61 aux(41) =< 3*V1+2 32.48/10.61 aux(42) =< 3*V1+V+1 32.48/10.61 aux(43) =< 4*V1 32.48/10.61 aux(44) =< 5*V1 32.48/10.61 aux(45) =< V1/2 32.48/10.61 aux(46) =< V1/2-V/2 32.48/10.61 aux(47) =< V1/4 32.48/10.61 aux(48) =< 3/2*V1+1 32.48/10.61 aux(49) =< 3/2*V1+2 32.48/10.61 aux(50) =< 5/2*V1 32.48/10.61 aux(51) =< V 32.48/10.61 s(205) =< aux(39) 32.48/10.61 s(225) =< aux(40) 32.48/10.61 s(268) =< aux(42) 32.48/10.61 s(220) =< aux(43) 32.48/10.61 s(272) =< aux(46) 32.48/10.61 s(221) =< aux(47) 32.48/10.61 s(222) =< aux(49) 32.48/10.61 s(203) =< aux(51) 32.48/10.61 s(219) =< aux(41) 32.48/10.61 s(223) =< aux(38) 32.48/10.61 s(224) =< aux(37) 32.48/10.61 s(226) =< aux(45) 32.48/10.61 s(228) =< aux(48) 32.48/10.61 s(229) =< aux(50) 32.48/10.61 s(230) =< s(210) 32.48/10.61 s(231) =< aux(44) 32.48/10.61 s(256) =< s(245) 32.48/10.61 s(257) =< s(250) 32.48/10.61 s(260) =< s(252) 32.48/10.61 s(261) =< s(254) 32.48/10.61 s(262) =< s(246) 32.48/10.61 s(263) =< s(249) 32.48/10.61 s(287) =< s(266) 32.48/10.61 s(288) =< s(267) 32.48/10.61 s(290) =< s(278) 32.48/10.61 s(241) =< s(235) 32.48/10.61 s(299) =< s(291) 32.48/10.61 s(301) =< s(292) 32.48/10.61 32.48/10.61 with precondition: [V1>=0] 32.48/10.61 32.48/10.61 * Chain [45]: 7 32.48/10.61 with precondition: [V1=1] 32.48/10.61 32.48/10.61 * Chain [44]: 1*s(306)+2*s(309)+8*s(314)+6*s(315)+2*s(316)+2*s(317)+2*s(318)+12 32.48/10.61 Such that:s(306) =< 2 32.48/10.61 s(312) =< V1 32.48/10.61 s(307) =< 2*V1 32.48/10.61 s(313) =< V1/4 32.48/10.61 aux(52) =< 3/2*V1+2 32.48/10.61 s(310) =< 5/2*V1+1 32.48/10.61 s(308) =< 11/2*V1+2 32.48/10.61 s(309) =< aux(52) 32.48/10.61 s(314) =< s(313) 32.48/10.61 s(315) =< s(312) 32.48/10.61 s(316) =< s(310) 32.48/10.61 s(317) =< s(308) 32.48/10.61 s(318) =< s(307) 32.48/10.61 32.48/10.61 with precondition: [V=0,V1>=0] 32.48/10.61 32.48/10.61 * Chain [43]: 1*s(319)+4 32.48/10.61 Such that:s(319) =< 1 32.48/10.61 32.48/10.61 with precondition: [V1=2,V=1] 32.48/10.61 32.48/10.61 * Chain [42]: 5*s(324)+4*s(328)+5*s(331)+7*s(333)+8*s(337)+4*s(343)+8*s(348)+4*s(353)+4*s(354)+12*s(357)+4*s(358)+1*s(360)+2*s(367)+14*s(368)+4*s(370)+2*s(371)+4*s(372)+4*s(373)+4*s(374)+2*s(386)+2*s(388)+2*s(390)+12 32.48/10.61 Such that:s(351) =< V-V12 32.48/10.61 s(354) =< 2*V 32.48/10.61 s(378) =< 2*V-2*V12 32.48/10.61 s(365) =< V/2 32.48/10.61 s(356) =< V/4 32.48/10.61 s(358) =< V/8 32.48/10.61 s(352) =< 3/2*V+V12+1 32.48/10.61 s(359) =< 3/4*V+1 32.48/10.61 s(360) =< 3/4*V+2 32.48/10.61 s(361) =< 5/4*V 32.48/10.61 s(379) =< 11/2*V-3*V12 32.48/10.61 s(322) =< -V12 32.48/10.61 s(389) =< 2*V12+2 32.48/10.61 s(328) =< -V12/2 32.48/10.61 aux(60) =< 1 32.48/10.61 aux(61) =< 2 32.48/10.61 aux(62) =< V 32.48/10.61 aux(63) =< V/4-V12/2 32.48/10.61 aux(64) =< 3/2*V+V12+2 32.48/10.61 aux(65) =< 5/2*V 32.48/10.61 aux(66) =< V12+1 32.48/10.61 aux(67) =< V12+2 32.48/10.61 s(357) =< aux(63) 32.48/10.61 s(353) =< aux(64) 32.48/10.61 s(333) =< aux(66) 32.48/10.61 s(348) =< aux(62) 32.48/10.61 s(337) =< aux(60) 32.48/10.61 s(367) =< s(356) 32.48/10.61 s(368) =< s(365) 32.48/10.61 s(331) =< aux(61) 32.48/10.61 s(370) =< s(359) 32.48/10.61 s(371) =< s(361) 32.48/10.61 s(372) =< s(351) 32.48/10.61 s(373) =< s(352) 32.48/10.61 s(374) =< aux(65) 32.48/10.61 s(324) =< aux(67) 32.48/10.61 s(386) =< s(378) 32.48/10.61 s(388) =< s(379) 32.48/10.61 s(343) =< s(322) 32.48/10.61 s(390) =< s(389) 32.48/10.61 32.48/10.61 with precondition: [V1=2,V>=0,V12>=0] 32.48/10.61 32.48/10.61 * Chain [41]: 3*s(397)+8*s(398)+2*s(399)+2*s(400)+2*s(401)+8 32.48/10.61 Such that:s(396) =< 3*V+2 32.48/10.61 s(392) =< 4*V 32.48/10.61 s(393) =< 5*V 32.48/10.61 s(394) =< 11*V 32.48/10.61 s(395) =< V/2 32.48/10.61 s(397) =< s(396) 32.48/10.61 s(398) =< s(395) 32.48/10.61 s(399) =< s(392) 32.48/10.61 s(400) =< s(393) 32.48/10.61 s(401) =< s(394) 32.48/10.61 32.48/10.61 with precondition: [V1=2,V>=2] 32.48/10.61 32.48/10.61 32.48/10.61 Closed-form bounds of start(V1,V,V12): 32.48/10.61 ------------------------------------- 32.48/10.61 * Chain [46] with precondition: [V1>=0] 32.48/10.61 - Upper bound: 47*V1+75+nat(V)*17+40*V1+nat(2*V)*8+56*V1+nat(4*V)*4+50*V1+nat(5*V)*2+22*V1+15*V1+nat(5/2*V)*2+nat(V+1)*2+nat(3*V1+V)*4+(24*V1+8)+(15*V1+10)+nat(3*V+1)*4+nat(3*V+2)+(18*V1+12)+(9/2*V1+6)+nat(3/2*V+1)*4+nat(3/2*V+2)+nat(3*V1+V+1)*4+nat(11*V1-3*V+1)*2+nat(2*V1-V)*4+nat(4*V1-2*V)*2+nat(V1/2-V/2)*12+11*V1+3*V1+nat(V/2)*6+nat(V/4)*4 32.48/10.61 - Complexity: n 32.48/10.61 * Chain [45] with precondition: [V1=1] 32.48/10.61 - Upper bound: 7 32.48/10.61 - Complexity: constant 32.48/10.61 * Chain [44] with precondition: [V=0,V1>=0] 32.48/10.61 - Upper bound: 31*V1+24 32.48/10.61 - Complexity: n 32.48/10.61 * Chain [43] with precondition: [V1=2,V=1] 32.48/10.61 - Upper bound: 5 32.48/10.61 - Complexity: constant 32.48/10.61 * Chain [42] with precondition: [V1=2,V>=0,V12>=0] 32.48/10.61 - Upper bound: V/2+(V/2+(177/4*V+24*V12+69+nat(V-V12)*4+nat(2*V-2*V12)*2+nat(11/2*V-3*V12)*2+nat(V/4-V12/2)*12+7*V)) 32.48/10.61 - Complexity: n 32.48/10.61 * Chain [41] with precondition: [V1=2,V>=2] 32.48/10.61 - Upper bound: 53*V+14 32.48/10.61 - Complexity: n 32.48/10.61 32.48/10.61 ### Maximum cost of start(V1,V,V12): max([31*V1+19,nat(V/2)*6+3+max([nat(5*V)*2+nat(4*V)*2+nat(11*V)*2+nat(3*V+2)*3+nat(V/2)*2,nat(V)*8+22+nat(2*V)*4+nat(5/2*V)*2+nat(V/4)*2+max([nat(5/4*V)*2+nat(5/2*V)*2+nat(V12+1)*7+nat(V12+2)*5+nat(2*V12+2)*2+nat(3/4*V+1)*4+nat(3/4*V+2)+nat(3/2*V+V12+1)*4+nat(3/2*V+V12+2)*4+nat(V-V12)*4+nat(2*V-2*V12)*2+nat(11/2*V-3*V12)*2+nat(V/4-V12/2)*12+nat(V/2)*8+nat(V/8)*4,47*V1+45+nat(V)*9+40*V1+nat(2*V)*4+56*V1+nat(4*V)*4+50*V1+nat(5*V)*2+22*V1+15*V1+nat(V+1)*2+nat(3*V1+V)*4+(24*V1+8)+(15*V1+10)+nat(3*V+1)*4+nat(3*V+2)+(18*V1+12)+(9/2*V1+6)+nat(3/2*V+1)*4+nat(3/2*V+2)+nat(3*V1+V+1)*4+nat(11*V1-3*V+1)*2+nat(2*V1-V)*4+nat(4*V1-2*V)*2+nat(V1/2-V/2)*12+11*V1+3*V1+nat(V/4)*2])])])+5 32.48/10.61 Asymptotic class: n 32.48/10.61 * Total analysis performed in 682 ms. 32.48/10.61 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (10) 32.48/10.61 BOUNDS(1, n^1) 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 32.48/10.61 Renamed function symbols to avoid clashes with predefined symbol. 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (12) 32.48/10.61 Obligation: 32.48/10.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 32.48/10.61 32.48/10.61 32.48/10.61 The TRS R consists of the following rules: 32.48/10.61 32.48/10.61 lt(0', s(x)) -> true 32.48/10.61 lt(x, 0') -> false 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) 32.48/10.61 logarithm(x) -> ifa(lt(0', x), x) 32.48/10.61 ifa(true, x) -> help(x, 1') 32.48/10.61 ifa(false, x) -> logZeroError 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) 32.48/10.61 ifb(false, x, y) -> y 32.48/10.61 half(0') -> 0' 32.48/10.61 half(s(0')) -> 0' 32.48/10.61 half(s(s(x))) -> s(half(x)) 32.48/10.61 32.48/10.61 S is empty. 32.48/10.61 Rewrite Strategy: INNERMOST 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (13) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 32.48/10.61 Infered types. 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (14) 32.48/10.61 Obligation: 32.48/10.61 Innermost TRS: 32.48/10.61 Rules: 32.48/10.61 lt(0', s(x)) -> true 32.48/10.61 lt(x, 0') -> false 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) 32.48/10.61 logarithm(x) -> ifa(lt(0', x), x) 32.48/10.61 ifa(true, x) -> help(x, 1') 32.48/10.61 ifa(false, x) -> logZeroError 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) 32.48/10.61 ifb(false, x, y) -> y 32.48/10.61 half(0') -> 0' 32.48/10.61 half(s(0')) -> 0' 32.48/10.61 half(s(s(x))) -> s(half(x)) 32.48/10.61 32.48/10.61 Types: 32.48/10.61 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 32.48/10.61 0' :: 0':s:1':logZeroError 32.48/10.61 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 true :: true:false 32.48/10.61 false :: true:false 32.48/10.61 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 1' :: 0':s:1':logZeroError 32.48/10.61 logZeroError :: 0':s:1':logZeroError 32.48/10.61 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 hole_true:false1_0 :: true:false 32.48/10.61 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 32.48/10.61 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (15) OrderProof (LOWER BOUND(ID)) 32.48/10.61 Heuristically decided to analyse the following defined symbols: 32.48/10.61 lt, help, half 32.48/10.61 32.48/10.61 They will be analysed ascendingly in the following order: 32.48/10.61 lt < help 32.48/10.61 half < help 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (16) 32.48/10.61 Obligation: 32.48/10.61 Innermost TRS: 32.48/10.61 Rules: 32.48/10.61 lt(0', s(x)) -> true 32.48/10.61 lt(x, 0') -> false 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) 32.48/10.61 logarithm(x) -> ifa(lt(0', x), x) 32.48/10.61 ifa(true, x) -> help(x, 1') 32.48/10.61 ifa(false, x) -> logZeroError 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) 32.48/10.61 ifb(false, x, y) -> y 32.48/10.61 half(0') -> 0' 32.48/10.61 half(s(0')) -> 0' 32.48/10.61 half(s(s(x))) -> s(half(x)) 32.48/10.61 32.48/10.61 Types: 32.48/10.61 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 32.48/10.61 0' :: 0':s:1':logZeroError 32.48/10.61 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 true :: true:false 32.48/10.61 false :: true:false 32.48/10.61 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 1' :: 0':s:1':logZeroError 32.48/10.61 logZeroError :: 0':s:1':logZeroError 32.48/10.61 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 hole_true:false1_0 :: true:false 32.48/10.61 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 32.48/10.61 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 32.48/10.61 32.48/10.61 32.48/10.61 Generator Equations: 32.48/10.61 gen_0':s:1':logZeroError3_0(0) <=> 0' 32.48/10.61 gen_0':s:1':logZeroError3_0(+(x, 1)) <=> s(gen_0':s:1':logZeroError3_0(x)) 32.48/10.61 32.48/10.61 32.48/10.61 The following defined symbols remain to be analysed: 32.48/10.61 lt, help, half 32.48/10.61 32.48/10.61 They will be analysed ascendingly in the following order: 32.48/10.61 lt < help 32.48/10.61 half < help 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (17) RewriteLemmaProof (LOWER BOUND(ID)) 32.48/10.61 Proved the following rewrite lemma: 32.48/10.61 lt(gen_0':s:1':logZeroError3_0(n5_0), gen_0':s:1':logZeroError3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 32.48/10.61 32.48/10.61 Induction Base: 32.48/10.61 lt(gen_0':s:1':logZeroError3_0(0), gen_0':s:1':logZeroError3_0(+(1, 0))) ->_R^Omega(1) 32.48/10.61 true 32.48/10.61 32.48/10.61 Induction Step: 32.48/10.61 lt(gen_0':s:1':logZeroError3_0(+(n5_0, 1)), gen_0':s:1':logZeroError3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1) 32.48/10.61 lt(gen_0':s:1':logZeroError3_0(n5_0), gen_0':s:1':logZeroError3_0(+(1, n5_0))) ->_IH 32.48/10.61 true 32.48/10.61 32.48/10.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (18) 32.48/10.61 Complex Obligation (BEST) 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (19) 32.48/10.61 Obligation: 32.48/10.61 Proved the lower bound n^1 for the following obligation: 32.48/10.61 32.48/10.61 Innermost TRS: 32.48/10.61 Rules: 32.48/10.61 lt(0', s(x)) -> true 32.48/10.61 lt(x, 0') -> false 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) 32.48/10.61 logarithm(x) -> ifa(lt(0', x), x) 32.48/10.61 ifa(true, x) -> help(x, 1') 32.48/10.61 ifa(false, x) -> logZeroError 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) 32.48/10.61 ifb(false, x, y) -> y 32.48/10.61 half(0') -> 0' 32.48/10.61 half(s(0')) -> 0' 32.48/10.61 half(s(s(x))) -> s(half(x)) 32.48/10.61 32.48/10.61 Types: 32.48/10.61 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 32.48/10.61 0' :: 0':s:1':logZeroError 32.48/10.61 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 true :: true:false 32.48/10.61 false :: true:false 32.48/10.61 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 1' :: 0':s:1':logZeroError 32.48/10.61 logZeroError :: 0':s:1':logZeroError 32.48/10.61 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 hole_true:false1_0 :: true:false 32.48/10.61 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 32.48/10.61 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 32.48/10.61 32.48/10.61 32.48/10.61 Generator Equations: 32.48/10.61 gen_0':s:1':logZeroError3_0(0) <=> 0' 32.48/10.61 gen_0':s:1':logZeroError3_0(+(x, 1)) <=> s(gen_0':s:1':logZeroError3_0(x)) 32.48/10.61 32.48/10.61 32.48/10.61 The following defined symbols remain to be analysed: 32.48/10.61 lt, help, half 32.48/10.61 32.48/10.61 They will be analysed ascendingly in the following order: 32.48/10.61 lt < help 32.48/10.61 half < help 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (20) LowerBoundPropagationProof (FINISHED) 32.48/10.61 Propagated lower bound. 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (21) 32.48/10.61 BOUNDS(n^1, INF) 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (22) 32.48/10.61 Obligation: 32.48/10.61 Innermost TRS: 32.48/10.61 Rules: 32.48/10.61 lt(0', s(x)) -> true 32.48/10.61 lt(x, 0') -> false 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) 32.48/10.61 logarithm(x) -> ifa(lt(0', x), x) 32.48/10.61 ifa(true, x) -> help(x, 1') 32.48/10.61 ifa(false, x) -> logZeroError 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) 32.48/10.61 ifb(false, x, y) -> y 32.48/10.61 half(0') -> 0' 32.48/10.61 half(s(0')) -> 0' 32.48/10.61 half(s(s(x))) -> s(half(x)) 32.48/10.61 32.48/10.61 Types: 32.48/10.61 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 32.48/10.61 0' :: 0':s:1':logZeroError 32.48/10.61 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 true :: true:false 32.48/10.61 false :: true:false 32.48/10.61 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 1' :: 0':s:1':logZeroError 32.48/10.61 logZeroError :: 0':s:1':logZeroError 32.48/10.61 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 hole_true:false1_0 :: true:false 32.48/10.61 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 32.48/10.61 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 32.48/10.61 32.48/10.61 32.48/10.61 Lemmas: 32.48/10.61 lt(gen_0':s:1':logZeroError3_0(n5_0), gen_0':s:1':logZeroError3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 32.48/10.61 32.48/10.61 32.48/10.61 Generator Equations: 32.48/10.61 gen_0':s:1':logZeroError3_0(0) <=> 0' 32.48/10.61 gen_0':s:1':logZeroError3_0(+(x, 1)) <=> s(gen_0':s:1':logZeroError3_0(x)) 32.48/10.61 32.48/10.61 32.48/10.61 The following defined symbols remain to be analysed: 32.48/10.61 half, help 32.48/10.61 32.48/10.61 They will be analysed ascendingly in the following order: 32.48/10.61 half < help 32.48/10.61 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (23) RewriteLemmaProof (LOWER BOUND(ID)) 32.48/10.61 Proved the following rewrite lemma: 32.48/10.61 half(gen_0':s:1':logZeroError3_0(*(2, n317_0))) -> gen_0':s:1':logZeroError3_0(n317_0), rt in Omega(1 + n317_0) 32.48/10.61 32.48/10.61 Induction Base: 32.48/10.61 half(gen_0':s:1':logZeroError3_0(*(2, 0))) ->_R^Omega(1) 32.48/10.61 0' 32.48/10.61 32.48/10.61 Induction Step: 32.48/10.61 half(gen_0':s:1':logZeroError3_0(*(2, +(n317_0, 1)))) ->_R^Omega(1) 32.48/10.61 s(half(gen_0':s:1':logZeroError3_0(*(2, n317_0)))) ->_IH 32.48/10.61 s(gen_0':s:1':logZeroError3_0(c318_0)) 32.48/10.61 32.48/10.61 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 32.48/10.61 ---------------------------------------- 32.48/10.61 32.48/10.61 (24) 32.48/10.61 Obligation: 32.48/10.61 Innermost TRS: 32.48/10.61 Rules: 32.48/10.61 lt(0', s(x)) -> true 32.48/10.61 lt(x, 0') -> false 32.48/10.61 lt(s(x), s(y)) -> lt(x, y) 32.48/10.61 logarithm(x) -> ifa(lt(0', x), x) 32.48/10.61 ifa(true, x) -> help(x, 1') 32.48/10.61 ifa(false, x) -> logZeroError 32.48/10.61 help(x, y) -> ifb(lt(y, x), x, y) 32.48/10.61 ifb(true, x, y) -> help(half(x), s(y)) 32.48/10.61 ifb(false, x, y) -> y 32.48/10.61 half(0') -> 0' 32.48/10.61 half(s(0')) -> 0' 32.48/10.61 half(s(s(x))) -> s(half(x)) 32.48/10.61 32.48/10.61 Types: 32.48/10.61 lt :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> true:false 32.48/10.61 0' :: 0':s:1':logZeroError 32.48/10.61 s :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 true :: true:false 32.48/10.61 false :: true:false 32.48/10.61 logarithm :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 ifa :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 help :: 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 1' :: 0':s:1':logZeroError 32.48/10.61 logZeroError :: 0':s:1':logZeroError 32.48/10.61 ifb :: true:false -> 0':s:1':logZeroError -> 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 half :: 0':s:1':logZeroError -> 0':s:1':logZeroError 32.48/10.61 hole_true:false1_0 :: true:false 32.48/10.61 hole_0':s:1':logZeroError2_0 :: 0':s:1':logZeroError 32.48/10.61 gen_0':s:1':logZeroError3_0 :: Nat -> 0':s:1':logZeroError 32.48/10.61 32.48/10.61 32.48/10.61 Lemmas: 32.48/10.61 lt(gen_0':s:1':logZeroError3_0(n5_0), gen_0':s:1':logZeroError3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 32.48/10.61 half(gen_0':s:1':logZeroError3_0(*(2, n317_0))) -> gen_0':s:1':logZeroError3_0(n317_0), rt in Omega(1 + n317_0) 32.48/10.61 32.48/10.61 32.48/10.61 Generator Equations: 32.48/10.61 gen_0':s:1':logZeroError3_0(0) <=> 0' 32.48/10.61 gen_0':s:1':logZeroError3_0(+(x, 1)) <=> s(gen_0':s:1':logZeroError3_0(x)) 32.48/10.61 32.48/10.61 32.48/10.61 The following defined symbols remain to be analysed: 32.48/10.61 help 32.63/10.71 EOF