49.43/14.02 WORST_CASE(Omega(n^1), O(n^1)) 49.43/14.02 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 49.43/14.02 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 49.43/14.02 49.43/14.02 49.43/14.02 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 49.43/14.02 49.43/14.02 (0) CpxTRS 49.43/14.02 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 49.43/14.02 (2) CpxWeightedTrs 49.43/14.02 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 49.43/14.02 (4) CpxTypedWeightedTrs 49.43/14.02 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 49.43/14.02 (6) CpxTypedWeightedCompleteTrs 49.43/14.02 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 3 ms] 49.43/14.02 (8) CpxRNTS 49.43/14.02 (9) CompleteCoflocoProof [FINISHED, 1332 ms] 49.43/14.02 (10) BOUNDS(1, n^1) 49.43/14.02 (11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 49.43/14.02 (12) TRS for Loop Detection 49.43/14.02 (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 49.43/14.02 (14) BEST 49.43/14.02 (15) proven lower bound 49.43/14.02 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 49.43/14.02 (17) BOUNDS(n^1, INF) 49.43/14.02 (18) TRS for Loop Detection 49.43/14.02 49.43/14.02 49.43/14.02 ---------------------------------------- 49.43/14.03 49.43/14.03 (0) 49.43/14.03 Obligation: 49.43/14.03 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 49.43/14.03 49.43/14.03 49.43/14.03 The TRS R consists of the following rules: 49.43/14.03 49.43/14.03 minus(0, x) -> 0 49.43/14.03 minus(s(x), 0) -> s(x) 49.43/14.03 minus(s(x), s(y)) -> minus(x, y) 49.43/14.03 mod(x, 0) -> 0 49.43/14.03 mod(x, s(y)) -> if(lt(x, s(y)), x, s(y)) 49.43/14.03 if(true, x, y) -> x 49.43/14.03 if(false, x, y) -> mod(minus(x, y), y) 49.43/14.03 gcd(x, 0) -> x 49.43/14.03 gcd(0, s(y)) -> s(y) 49.43/14.03 gcd(s(x), s(y)) -> gcd(mod(s(x), s(y)), mod(s(y), s(x))) 49.43/14.03 lt(x, 0) -> false 49.43/14.03 lt(0, s(x)) -> true 49.43/14.03 lt(s(x), s(y)) -> lt(x, y) 49.43/14.03 49.43/14.03 S is empty. 49.43/14.03 Rewrite Strategy: INNERMOST 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 49.43/14.03 Transformed relative TRS to weighted TRS 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (2) 49.43/14.03 Obligation: 49.43/14.03 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 49.43/14.03 49.43/14.03 49.43/14.03 The TRS R consists of the following rules: 49.43/14.03 49.43/14.03 minus(0, x) -> 0 [1] 49.43/14.03 minus(s(x), 0) -> s(x) [1] 49.43/14.03 minus(s(x), s(y)) -> minus(x, y) [1] 49.43/14.03 mod(x, 0) -> 0 [1] 49.43/14.03 mod(x, s(y)) -> if(lt(x, s(y)), x, s(y)) [1] 49.43/14.03 if(true, x, y) -> x [1] 49.43/14.03 if(false, x, y) -> mod(minus(x, y), y) [1] 49.43/14.03 gcd(x, 0) -> x [1] 49.43/14.03 gcd(0, s(y)) -> s(y) [1] 49.43/14.03 gcd(s(x), s(y)) -> gcd(mod(s(x), s(y)), mod(s(y), s(x))) [1] 49.43/14.03 lt(x, 0) -> false [1] 49.43/14.03 lt(0, s(x)) -> true [1] 49.43/14.03 lt(s(x), s(y)) -> lt(x, y) [1] 49.43/14.03 49.43/14.03 Rewrite Strategy: INNERMOST 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 49.43/14.03 Infered types. 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (4) 49.43/14.03 Obligation: 49.43/14.03 Runtime Complexity Weighted TRS with Types. 49.43/14.03 The TRS R consists of the following rules: 49.43/14.03 49.43/14.03 minus(0, x) -> 0 [1] 49.43/14.03 minus(s(x), 0) -> s(x) [1] 49.43/14.03 minus(s(x), s(y)) -> minus(x, y) [1] 49.43/14.03 mod(x, 0) -> 0 [1] 49.43/14.03 mod(x, s(y)) -> if(lt(x, s(y)), x, s(y)) [1] 49.43/14.03 if(true, x, y) -> x [1] 49.43/14.03 if(false, x, y) -> mod(minus(x, y), y) [1] 49.43/14.03 gcd(x, 0) -> x [1] 49.43/14.03 gcd(0, s(y)) -> s(y) [1] 49.43/14.03 gcd(s(x), s(y)) -> gcd(mod(s(x), s(y)), mod(s(y), s(x))) [1] 49.43/14.03 lt(x, 0) -> false [1] 49.43/14.03 lt(0, s(x)) -> true [1] 49.43/14.03 lt(s(x), s(y)) -> lt(x, y) [1] 49.43/14.03 49.43/14.03 The TRS has the following type information: 49.43/14.03 minus :: 0:s -> 0:s -> 0:s 49.43/14.03 0 :: 0:s 49.43/14.03 s :: 0:s -> 0:s 49.43/14.03 mod :: 0:s -> 0:s -> 0:s 49.43/14.03 if :: true:false -> 0:s -> 0:s -> 0:s 49.43/14.03 lt :: 0:s -> 0:s -> true:false 49.43/14.03 true :: true:false 49.43/14.03 false :: true:false 49.43/14.03 gcd :: 0:s -> 0:s -> 0:s 49.43/14.03 49.43/14.03 Rewrite Strategy: INNERMOST 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (5) CompletionProof (UPPER BOUND(ID)) 49.43/14.03 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 49.43/14.03 none 49.43/14.03 49.43/14.03 And the following fresh constants: none 49.43/14.03 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (6) 49.43/14.03 Obligation: 49.43/14.03 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 49.43/14.03 49.43/14.03 Runtime Complexity Weighted TRS with Types. 49.43/14.03 The TRS R consists of the following rules: 49.43/14.03 49.43/14.03 minus(0, x) -> 0 [1] 49.43/14.03 minus(s(x), 0) -> s(x) [1] 49.43/14.03 minus(s(x), s(y)) -> minus(x, y) [1] 49.43/14.03 mod(x, 0) -> 0 [1] 49.43/14.03 mod(x, s(y)) -> if(lt(x, s(y)), x, s(y)) [1] 49.43/14.03 if(true, x, y) -> x [1] 49.43/14.03 if(false, x, y) -> mod(minus(x, y), y) [1] 49.43/14.03 gcd(x, 0) -> x [1] 49.43/14.03 gcd(0, s(y)) -> s(y) [1] 49.43/14.03 gcd(s(x), s(y)) -> gcd(mod(s(x), s(y)), mod(s(y), s(x))) [1] 49.43/14.03 lt(x, 0) -> false [1] 49.43/14.03 lt(0, s(x)) -> true [1] 49.43/14.03 lt(s(x), s(y)) -> lt(x, y) [1] 49.43/14.03 49.43/14.03 The TRS has the following type information: 49.43/14.03 minus :: 0:s -> 0:s -> 0:s 49.43/14.03 0 :: 0:s 49.43/14.03 s :: 0:s -> 0:s 49.43/14.03 mod :: 0:s -> 0:s -> 0:s 49.43/14.03 if :: true:false -> 0:s -> 0:s -> 0:s 49.43/14.03 lt :: 0:s -> 0:s -> true:false 49.43/14.03 true :: true:false 49.43/14.03 false :: true:false 49.43/14.03 gcd :: 0:s -> 0:s -> 0:s 49.43/14.03 49.43/14.03 Rewrite Strategy: INNERMOST 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 49.43/14.03 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 49.43/14.03 The constant constructors are abstracted as follows: 49.43/14.03 49.43/14.03 0 => 0 49.43/14.03 true => 1 49.43/14.03 false => 0 49.43/14.03 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (8) 49.43/14.03 Obligation: 49.43/14.03 Complexity RNTS consisting of the following rules: 49.43/14.03 49.43/14.03 gcd(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 49.43/14.03 gcd(z, z') -{ 1 }-> gcd(mod(1 + x, 1 + y), mod(1 + y, 1 + x)) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 49.43/14.03 gcd(z, z') -{ 1 }-> 1 + y :|: z' = 1 + y, y >= 0, z = 0 49.43/14.03 if(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 49.43/14.03 if(z, z', z'') -{ 1 }-> mod(minus(x, y), y) :|: z' = x, z'' = y, x >= 0, y >= 0, z = 0 49.43/14.03 lt(z, z') -{ 1 }-> lt(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 49.43/14.03 lt(z, z') -{ 1 }-> 1 :|: z' = 1 + x, x >= 0, z = 0 49.43/14.03 lt(z, z') -{ 1 }-> 0 :|: x >= 0, z = x, z' = 0 49.43/14.03 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 49.43/14.03 minus(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = 0 49.43/14.03 minus(z, z') -{ 1 }-> 1 + x :|: x >= 0, z = 1 + x, z' = 0 49.43/14.03 mod(z, z') -{ 1 }-> if(lt(x, 1 + y), x, 1 + y) :|: z' = 1 + y, x >= 0, y >= 0, z = x 49.43/14.03 mod(z, z') -{ 1 }-> 0 :|: x >= 0, z = x, z' = 0 49.43/14.03 49.43/14.03 Only complete derivations are relevant for the runtime complexity. 49.43/14.03 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (9) CompleteCoflocoProof (FINISHED) 49.43/14.03 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 49.43/14.03 49.43/14.03 eq(start(V1, V, V10),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). 49.43/14.03 eq(start(V1, V, V10),0,[mod(V1, V, Out)],[V1 >= 0,V >= 0]). 49.43/14.03 eq(start(V1, V, V10),0,[if(V1, V, V10, Out)],[V1 >= 0,V >= 0,V10 >= 0]). 49.43/14.03 eq(start(V1, V, V10),0,[gcd(V1, V, Out)],[V1 >= 0,V >= 0]). 49.43/14.03 eq(start(V1, V, V10),0,[lt(V1, V, Out)],[V1 >= 0,V >= 0]). 49.43/14.03 eq(minus(V1, V, Out),1,[],[Out = 0,V = V2,V2 >= 0,V1 = 0]). 49.43/14.03 eq(minus(V1, V, Out),1,[],[Out = 1 + V3,V3 >= 0,V1 = 1 + V3,V = 0]). 49.43/14.03 eq(minus(V1, V, Out),1,[minus(V4, V5, Ret)],[Out = Ret,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]). 49.43/14.03 eq(mod(V1, V, Out),1,[],[Out = 0,V6 >= 0,V1 = V6,V = 0]). 49.43/14.03 eq(mod(V1, V, Out),1,[lt(V7, 1 + V8, Ret0),if(Ret0, V7, 1 + V8, Ret1)],[Out = Ret1,V = 1 + V8,V7 >= 0,V8 >= 0,V1 = V7]). 49.43/14.03 eq(if(V1, V, V10, Out),1,[],[Out = V11,V = V11,V10 = V9,V1 = 1,V11 >= 0,V9 >= 0]). 49.43/14.03 eq(if(V1, V, V10, Out),1,[minus(V13, V12, Ret01),mod(Ret01, V12, Ret2)],[Out = Ret2,V = V13,V10 = V12,V13 >= 0,V12 >= 0,V1 = 0]). 49.43/14.03 eq(gcd(V1, V, Out),1,[],[Out = V14,V14 >= 0,V1 = V14,V = 0]). 49.43/14.03 eq(gcd(V1, V, Out),1,[],[Out = 1 + V15,V = 1 + V15,V15 >= 0,V1 = 0]). 49.43/14.03 eq(gcd(V1, V, Out),1,[mod(1 + V17, 1 + V16, Ret02),mod(1 + V16, 1 + V17, Ret11),gcd(Ret02, Ret11, Ret3)],[Out = Ret3,V = 1 + V16,V17 >= 0,V16 >= 0,V1 = 1 + V17]). 49.43/14.03 eq(lt(V1, V, Out),1,[],[Out = 0,V18 >= 0,V1 = V18,V = 0]). 49.43/14.03 eq(lt(V1, V, Out),1,[],[Out = 1,V = 1 + V19,V19 >= 0,V1 = 0]). 49.43/14.03 eq(lt(V1, V, Out),1,[lt(V21, V20, Ret4)],[Out = Ret4,V = 1 + V20,V21 >= 0,V20 >= 0,V1 = 1 + V21]). 49.43/14.03 input_output_vars(minus(V1,V,Out),[V1,V],[Out]). 49.43/14.03 input_output_vars(mod(V1,V,Out),[V1,V],[Out]). 49.43/14.03 input_output_vars(if(V1,V,V10,Out),[V1,V,V10],[Out]). 49.43/14.03 input_output_vars(gcd(V1,V,Out),[V1,V],[Out]). 49.43/14.03 input_output_vars(lt(V1,V,Out),[V1,V],[Out]). 49.43/14.03 49.43/14.03 49.43/14.03 CoFloCo proof output: 49.43/14.03 Preprocessing Cost Relations 49.43/14.03 ===================================== 49.43/14.03 49.43/14.03 #### Computed strongly connected components 49.43/14.03 0. recursive : [minus/3] 49.43/14.03 1. recursive : [lt/3] 49.43/14.03 2. recursive : [if/4,(mod)/3] 49.43/14.03 3. recursive : [gcd/3] 49.43/14.03 4. non_recursive : [start/3] 49.43/14.03 49.43/14.03 #### Obtained direct recursion through partial evaluation 49.43/14.03 0. SCC is partially evaluated into minus/3 49.43/14.03 1. SCC is partially evaluated into lt/3 49.43/14.03 2. SCC is partially evaluated into (mod)/3 49.43/14.03 3. SCC is partially evaluated into gcd/3 49.43/14.03 4. SCC is partially evaluated into start/3 49.43/14.03 49.43/14.03 Control-Flow Refinement of Cost Relations 49.43/14.03 ===================================== 49.43/14.03 49.43/14.03 ### Specialization of cost equations minus/3 49.43/14.03 * CE 9 is refined into CE [19] 49.43/14.03 * CE 8 is refined into CE [20] 49.43/14.03 * CE 7 is refined into CE [21] 49.43/14.03 49.43/14.03 49.43/14.03 ### Cost equations --> "Loop" of minus/3 49.43/14.03 * CEs [20] --> Loop 15 49.43/14.03 * CEs [21] --> Loop 16 49.43/14.03 * CEs [19] --> Loop 17 49.43/14.03 49.43/14.03 ### Ranking functions of CR minus(V1,V,Out) 49.43/14.03 * RF of phase [17]: [V,V1] 49.43/14.03 49.43/14.03 #### Partial ranking functions of CR minus(V1,V,Out) 49.43/14.03 * Partial RF of phase [17]: 49.43/14.03 - RF of loop [17:1]: 49.43/14.03 V 49.43/14.03 V1 49.43/14.03 49.43/14.03 49.43/14.03 ### Specialization of cost equations lt/3 49.43/14.03 * CE 18 is refined into CE [22] 49.43/14.03 * CE 16 is refined into CE [23] 49.43/14.03 * CE 17 is refined into CE [24] 49.43/14.03 49.43/14.03 49.43/14.03 ### Cost equations --> "Loop" of lt/3 49.43/14.03 * CEs [23] --> Loop 18 49.43/14.03 * CEs [24] --> Loop 19 49.43/14.03 * CEs [22] --> Loop 20 49.43/14.03 49.43/14.03 ### Ranking functions of CR lt(V1,V,Out) 49.43/14.03 * RF of phase [20]: [V,V1] 49.43/14.03 49.43/14.03 #### Partial ranking functions of CR lt(V1,V,Out) 49.43/14.03 * Partial RF of phase [20]: 49.43/14.03 - RF of loop [20:1]: 49.43/14.03 V 49.43/14.03 V1 49.43/14.03 49.43/14.03 49.43/14.03 ### Specialization of cost equations (mod)/3 49.43/14.03 * CE 11 is refined into CE [25,26] 49.43/14.03 * CE 12 is refined into CE [27] 49.43/14.03 * CE 10 is refined into CE [28,29] 49.43/14.03 49.43/14.03 49.43/14.03 ### Cost equations --> "Loop" of (mod)/3 49.43/14.03 * CEs [29] --> Loop 21 49.43/14.03 * CEs [28] --> Loop 22 49.43/14.03 * CEs [26] --> Loop 23 49.43/14.03 * CEs [27] --> Loop 24 49.43/14.03 * CEs [25] --> Loop 25 49.43/14.03 49.43/14.03 ### Ranking functions of CR mod(V1,V,Out) 49.43/14.03 * RF of phase [21]: [V1-1,V1-V] 49.43/14.03 49.43/14.03 #### Partial ranking functions of CR mod(V1,V,Out) 49.43/14.03 * Partial RF of phase [21]: 49.43/14.03 - RF of loop [21:1]: 49.43/14.03 V1-1 49.43/14.03 V1-V 49.43/14.03 49.43/14.03 49.43/14.03 ### Specialization of cost equations gcd/3 49.43/14.03 * CE 15 is refined into CE [30,31,32,33,34] 49.43/14.03 * CE 13 is refined into CE [35] 49.43/14.03 * CE 14 is refined into CE [36] 49.43/14.03 49.43/14.03 49.43/14.03 ### Cost equations --> "Loop" of gcd/3 49.43/14.03 * CEs [35] --> Loop 26 49.43/14.03 * CEs [36] --> Loop 27 49.43/14.03 * CEs [34] --> Loop 28 49.43/14.03 * CEs [33] --> Loop 29 49.43/14.03 * CEs [32] --> Loop 30 49.43/14.03 * CEs [31] --> Loop 31 49.43/14.03 * CEs [30] --> Loop 32 49.43/14.03 49.43/14.03 ### Ranking functions of CR gcd(V1,V,Out) 49.43/14.03 * RF of phase [28,29]: [V1+V-4,V1+2*V-6,V1+V/2-3,2*V1+V-6,V1/2+V-3,V1/2+V/2-2,V1/2+3/4*V-11/4,2/3*V1+2/3*V-3,2/3*V1+4/3*V-13/3,3/2*V1+3/4*V-5,3/4*V1+V/2-11/4,3/4*V1+3/2*V-5,3/4*V1+3/4*V-7/2,4/3*V1+2/3*V-13/3] 49.43/14.03 49.43/14.03 #### Partial ranking functions of CR gcd(V1,V,Out) 49.43/14.03 * Partial RF of phase [28,29]: 49.43/14.03 - RF of loop [28:1]: 49.43/14.03 V1/2-1 49.43/14.03 V1/2-V/2 depends on loops [29:1] 49.43/14.03 - RF of loop [29:1]: 49.43/14.03 V/2-1 49.43/14.03 -V1/2+V/2 depends on loops [28:1] 49.43/14.03 49.43/14.03 49.43/14.03 ### Specialization of cost equations start/3 49.43/14.03 * CE 2 is refined into CE [37] 49.43/14.03 * CE 1 is refined into CE [38,39,40,41,42,43,44,45] 49.43/14.03 * CE 3 is refined into CE [46,47,48,49] 49.43/14.03 * CE 4 is refined into CE [50,51,52,53,54,55] 49.43/14.03 * CE 5 is refined into CE [56,57,58,59,60,61,62] 49.43/14.03 * CE 6 is refined into CE [63,64,65,66] 49.43/14.03 49.43/14.03 49.43/14.03 ### Cost equations --> "Loop" of start/3 49.43/14.03 * CEs [49,53,60,65] --> Loop 33 49.43/14.03 * CEs [55,61] --> Loop 34 49.43/14.03 * CEs [62] --> Loop 35 49.43/14.03 * CEs [59] --> Loop 36 49.43/14.03 * CEs [48,52,54,58,66] --> Loop 37 49.43/14.03 * CEs [37] --> Loop 38 49.43/14.03 * CEs [42] --> Loop 39 49.43/14.03 * CEs [40] --> Loop 40 49.43/14.03 * CEs [38,47,51,57,64] --> Loop 41 49.43/14.03 * CEs [39,41,43,44,45,46,50,56,63] --> Loop 42 49.43/14.03 49.43/14.03 ### Ranking functions of CR start(V1,V,V10) 49.43/14.03 49.43/14.03 #### Partial ranking functions of CR start(V1,V,V10) 49.43/14.03 49.43/14.03 49.43/14.03 Computing Bounds 49.43/14.03 ===================================== 49.43/14.03 49.43/14.03 #### Cost of chains of minus(V1,V,Out): 49.43/14.03 * Chain [[17],16]: 1*it(17)+1 49.43/14.03 Such that:it(17) =< V1 49.43/14.03 49.43/14.03 with precondition: [Out=0,V1>=1,V>=V1] 49.43/14.03 49.43/14.03 * Chain [[17],15]: 1*it(17)+1 49.43/14.03 Such that:it(17) =< V 49.43/14.03 49.43/14.03 with precondition: [V1=Out+V,V>=1,V1>=V+1] 49.43/14.03 49.43/14.03 * Chain [16]: 1 49.43/14.03 with precondition: [V1=0,Out=0,V>=0] 49.43/14.03 49.43/14.03 * Chain [15]: 1 49.43/14.03 with precondition: [V=0,V1=Out,V1>=1] 49.43/14.03 49.43/14.03 49.43/14.03 #### Cost of chains of lt(V1,V,Out): 49.43/14.03 * Chain [[20],19]: 1*it(20)+1 49.43/14.03 Such that:it(20) =< V1 49.43/14.03 49.43/14.03 with precondition: [Out=1,V1>=1,V>=V1+1] 49.43/14.03 49.43/14.03 * Chain [[20],18]: 1*it(20)+1 49.43/14.03 Such that:it(20) =< V 49.43/14.03 49.43/14.03 with precondition: [Out=0,V>=1,V1>=V] 49.43/14.03 49.43/14.03 * Chain [19]: 1 49.43/14.03 with precondition: [V1=0,Out=1,V>=1] 49.43/14.03 49.43/14.03 * Chain [18]: 1 49.43/14.03 with precondition: [V=0,Out=0,V1>=0] 49.43/14.03 49.43/14.03 49.43/14.03 #### Cost of chains of mod(V1,V,Out): 49.43/14.03 * Chain [[21],23]: 4*it(21)+1*s(1)+2*s(6)+3 49.43/14.03 Such that:aux(2) =< V1 49.43/14.03 it(21) =< V1-V 49.43/14.03 aux(3) =< V1-Out 49.43/14.03 s(1) =< Out 49.43/14.03 it(21) =< aux(2) 49.43/14.03 s(7) =< aux(2) 49.43/14.03 it(21) =< aux(3) 49.43/14.03 s(7) =< aux(3) 49.43/14.03 s(6) =< s(7) 49.43/14.03 49.43/14.03 with precondition: [Out>=1,V>=Out+1,V1>=Out+V] 49.43/14.03 49.43/14.03 * Chain [[21],22,25]: 4*it(21)+2*s(6)+2*s(8)+7 49.43/14.03 Such that:aux(2) =< V1 49.43/14.03 aux(4) =< V 49.43/14.03 aux(5) =< V1-V 49.43/14.03 it(21) =< aux(5) 49.43/14.03 s(8) =< aux(4) 49.43/14.03 it(21) =< aux(2) 49.43/14.03 s(7) =< aux(2) 49.43/14.03 s(7) =< aux(5) 49.43/14.03 s(6) =< s(7) 49.43/14.03 49.43/14.03 with precondition: [Out=0,V>=1,V1>=2*V] 49.43/14.03 49.43/14.03 * Chain [25]: 3 49.43/14.03 with precondition: [V1=0,Out=0,V>=1] 49.43/14.03 49.43/14.03 * Chain [24]: 1 49.43/14.03 with precondition: [V=0,Out=0,V1>=0] 49.43/14.03 49.43/14.03 * Chain [23]: 1*s(1)+3 49.43/14.03 Such that:s(1) =< V1 49.43/14.03 49.43/14.03 with precondition: [V1=Out,V1>=1,V>=V1+1] 49.43/14.03 49.43/14.03 * Chain [22,25]: 2*s(8)+7 49.43/14.03 Such that:aux(4) =< V1 49.43/14.03 s(8) =< aux(4) 49.43/14.03 49.43/14.03 with precondition: [Out=0,V1=V,V1>=1] 49.43/14.03 49.43/14.03 49.43/14.03 #### Cost of chains of gcd(V1,V,Out): 49.43/14.03 * Chain [[28,29],31,27]: 7*it(28)+7*it(29)+4*s(13)+3*s(14)+2*s(16)+4*s(46)+1*s(47)+2*s(48)+2*s(49)+4*s(54)+1*s(55)+2*s(56)+12 49.43/14.03 Such that:aux(22) =< -V1+V 49.43/14.03 aux(18) =< -V1+2*V 49.43/14.03 aux(13) =< V1-V 49.43/14.03 aux(28) =< V1+V 49.43/14.03 aux(30) =< V1+2*V 49.43/14.03 aux(32) =< V1+V/2 49.43/14.03 aux(33) =< V1+V/2-Out/2 49.43/14.03 aux(42) =< V1+3/2*V-3/2*Out 49.43/14.03 aux(10) =< 2*V1-V 49.43/14.03 aux(34) =< 2*V1+V 49.43/14.03 aux(35) =< 2*V1+V-Out 49.43/14.03 aux(45) =< 2*V1+2*V-2*Out 49.43/14.03 aux(47) =< 2*V1+4*V-4*Out 49.43/14.03 aux(51) =< 3*V1+2*V-2*Out 49.43/14.03 s(10) =< 3*V1+3*V-3*Out 49.43/14.03 aux(53) =< 3*V1+6*V-6*Out 49.43/14.03 aux(49) =< 3*V1+3/2*V-3/2*Out 49.43/14.03 aux(57) =< 4*V1+2*V-2*Out 49.43/14.03 aux(16) =< -V1/2+V/2 49.43/14.03 aux(36) =< V1/2 49.43/14.03 aux(37) =< V1/2+V 49.43/14.03 aux(8) =< V1/2-V/2 49.43/14.03 aux(39) =< V1/2+V/2 49.43/14.03 aux(41) =< V1/2+3/4*V 49.43/14.03 aux(44) =< 2/3*V1+2/3*V 49.43/14.03 aux(46) =< 2/3*V1+4/3*V 49.43/14.03 aux(48) =< 3/2*V1+3/4*V 49.43/14.03 aux(50) =< 3/4*V1+V/2 49.43/14.03 aux(52) =< 3/4*V1+3/2*V 49.43/14.03 aux(54) =< 3/4*V1+3/4*V 49.43/14.03 aux(56) =< 4/3*V1+2/3*V 49.43/14.03 aux(58) =< V 49.43/14.03 aux(59) =< V-Out 49.43/14.03 it(29) =< V/2-Out/2 49.43/14.03 aux(6) =< Out 49.43/14.03 aux(60) =< V1 49.43/14.03 aux(61) =< V1+V-Out 49.43/14.03 aux(62) =< V1+2*V-2*Out 49.43/14.03 aux(63) =< 3*V1+3*V-6*Out 49.43/14.03 s(47) =< aux(60) 49.43/14.03 s(14) =< aux(6) 49.43/14.03 s(13) =< aux(63) 49.43/14.03 s(13) =< s(10) 49.43/14.03 s(15) =< s(10) 49.43/14.03 s(15) =< aux(63) 49.43/14.03 s(16) =< s(15) 49.43/14.03 it(28) =< aux(28) 49.43/14.03 it(29) =< aux(28) 49.43/14.03 s(49) =< aux(28) 49.43/14.03 s(51) =< aux(28) 49.43/14.03 it(28) =< aux(61) 49.43/14.03 it(29) =< aux(61) 49.43/14.03 s(49) =< aux(61) 49.43/14.03 s(51) =< aux(61) 49.43/14.03 it(28) =< aux(30) 49.43/14.03 it(29) =< aux(30) 49.43/14.03 it(28) =< aux(62) 49.43/14.03 it(29) =< aux(62) 49.43/14.03 it(28) =< aux(32) 49.43/14.03 it(29) =< aux(32) 49.43/14.03 it(28) =< aux(33) 49.43/14.03 it(29) =< aux(33) 49.43/14.03 it(28) =< aux(34) 49.43/14.03 it(29) =< aux(34) 49.43/14.03 it(28) =< aux(35) 49.43/14.03 it(29) =< aux(35) 49.43/14.03 aux(15) =< aux(36) 49.43/14.03 it(28) =< aux(36) 49.43/14.03 it(28) =< aux(37) 49.43/14.03 it(29) =< aux(37) 49.43/14.03 it(28) =< aux(39) 49.43/14.03 it(29) =< aux(39) 49.43/14.03 it(28) =< aux(41) 49.43/14.03 it(29) =< aux(41) 49.43/14.03 it(28) =< aux(42) 49.43/14.03 it(29) =< aux(42) 49.43/14.03 aux(15) =< aux(60) 49.43/14.03 it(28) =< aux(60) 49.43/14.03 it(28) =< aux(44) 49.43/14.03 it(29) =< aux(44) 49.43/14.03 it(28) =< aux(45) 49.43/14.03 it(29) =< aux(45) 49.43/14.03 it(28) =< aux(46) 49.43/14.03 it(29) =< aux(46) 49.43/14.03 it(28) =< aux(47) 49.43/14.03 it(29) =< aux(47) 49.43/14.03 it(28) =< aux(48) 49.43/14.03 it(29) =< aux(48) 49.43/14.03 it(28) =< aux(49) 49.43/14.03 it(29) =< aux(49) 49.43/14.03 it(28) =< aux(50) 49.43/14.03 it(29) =< aux(50) 49.43/14.03 it(28) =< aux(51) 49.43/14.03 it(29) =< aux(51) 49.43/14.03 it(28) =< aux(52) 49.43/14.03 it(29) =< aux(52) 49.43/14.03 it(28) =< aux(53) 49.43/14.03 it(29) =< aux(53) 49.43/14.03 it(28) =< aux(54) 49.43/14.03 it(29) =< aux(54) 49.43/14.03 it(28) =< aux(63) 49.43/14.03 it(29) =< aux(63) 49.43/14.03 it(28) =< aux(56) 49.43/14.03 it(29) =< aux(56) 49.43/14.03 it(28) =< aux(57) 49.43/14.03 it(29) =< aux(57) 49.43/14.03 aux(12) =< aux(58) 49.43/14.03 s(55) =< aux(58) 49.43/14.03 aux(12) =< aux(59) 49.43/14.03 s(55) =< aux(59) 49.43/14.03 aux(7) =< aux(12)*(1/2) 49.43/14.03 aux(9) =< aux(12)*2 49.43/14.03 aux(21) =< aux(15)*2 49.43/14.03 aux(17) =< aux(15)*4 49.43/14.03 it(29) =< aux(15)+aux(16) 49.43/14.03 s(46) =< aux(12)+aux(13) 49.43/14.03 s(54) =< aux(21)+aux(22) 49.43/14.03 s(54) =< it(29)*aux(58) 49.43/14.03 s(59) =< aux(17)+aux(18) 49.43/14.03 s(59) =< it(29)*aux(58) 49.43/14.03 s(52) =< aux(9)+aux(10) 49.43/14.03 it(28) =< aux(7)+aux(8) 49.43/14.03 s(46) =< it(28)*aux(60) 49.43/14.03 s(52) =< it(28)*aux(60) 49.43/14.03 s(54) =< s(59) 49.43/14.03 s(57) =< s(59) 49.43/14.03 s(54) =< s(51) 49.43/14.03 s(57) =< s(51) 49.43/14.03 s(56) =< s(57) 49.43/14.03 s(46) =< s(52) 49.43/14.03 s(50) =< s(52) 49.43/14.03 s(46) =< s(51) 49.43/14.03 s(50) =< s(51) 49.43/14.03 s(48) =< s(50) 49.43/14.03 49.43/14.03 with precondition: [Out>=1,V>=3*Out,V1>=2*Out] 49.43/14.03 49.43/14.03 * Chain [[28,29],30,26]: 7*it(28)+7*it(29)+4*s(46)+1*s(47)+2*s(48)+2*s(49)+4*s(54)+1*s(55)+2*s(56)+3*s(60)+4*s(64)+2*s(67)+12 49.43/14.03 Such that:aux(22) =< -V1+V 49.43/14.03 aux(18) =< -V1+2*V 49.43/14.03 aux(27) =< V1 49.43/14.03 aux(13) =< V1-V 49.43/14.03 aux(28) =< V1+V 49.43/14.03 aux(30) =< V1+2*V 49.43/14.03 aux(31) =< V1+2*V-Out 49.43/14.03 aux(32) =< V1+V/2 49.43/14.03 s(47) =< V1-Out 49.43/14.03 aux(10) =< 2*V1-V 49.43/14.03 aux(34) =< 2*V1+V 49.43/14.03 aux(45) =< 2*V1+2*V-2*Out 49.43/14.03 aux(42) =< 2*V1+3*V-2*Out 49.43/14.03 aux(47) =< 2*V1+4*V-2*Out 49.43/14.03 aux(55) =< 3*V1+3*V-3*Out 49.43/14.03 aux(57) =< 4*V1+2*V-4*Out 49.43/14.03 aux(49) =< 6*V1+3*V-6*Out 49.43/14.03 aux(16) =< -V1/2+V/2 49.43/14.03 aux(36) =< V1/2 49.43/14.03 aux(37) =< V1/2+V 49.43/14.03 aux(38) =< V1/2+V-Out/2 49.43/14.03 aux(8) =< V1/2-V/2 49.43/14.03 aux(39) =< V1/2+V/2 49.43/14.03 aux(41) =< V1/2+3/4*V 49.43/14.03 aux(43) =< V1/2-Out/2 49.43/14.03 aux(44) =< 2/3*V1+2/3*V 49.43/14.03 aux(46) =< 2/3*V1+4/3*V 49.43/14.03 aux(51) =< 3/2*V1+V-3/2*Out 49.43/14.03 aux(53) =< 3/2*V1+3*V-3/2*Out 49.43/14.03 aux(48) =< 3/2*V1+3/4*V 49.43/14.03 aux(50) =< 3/4*V1+V/2 49.43/14.03 aux(52) =< 3/4*V1+3/2*V 49.43/14.03 aux(54) =< 3/4*V1+3/4*V 49.43/14.03 aux(56) =< 4/3*V1+2/3*V 49.43/14.03 aux(64) =< Out 49.43/14.03 aux(65) =< V1+V-2*Out 49.43/14.03 aux(66) =< V1+V-Out 49.43/14.03 aux(67) =< 2*V1+V-2*Out 49.43/14.03 aux(68) =< V 49.43/14.03 it(29) =< aux(68) 49.43/14.03 s(60) =< aux(64) 49.43/14.03 s(64) =< aux(65) 49.43/14.03 s(64) =< aux(66) 49.43/14.03 s(66) =< aux(66) 49.43/14.03 s(66) =< aux(65) 49.43/14.03 s(67) =< s(66) 49.43/14.03 s(47) =< aux(27) 49.43/14.03 it(28) =< aux(28) 49.43/14.03 it(29) =< aux(28) 49.43/14.03 s(49) =< aux(28) 49.43/14.03 s(51) =< aux(28) 49.43/14.03 it(28) =< aux(65) 49.43/14.03 it(29) =< aux(65) 49.43/14.03 s(49) =< aux(65) 49.43/14.03 s(51) =< aux(65) 49.43/14.03 it(28) =< aux(30) 49.43/14.03 it(29) =< aux(30) 49.43/14.03 it(28) =< aux(31) 49.43/14.03 it(29) =< aux(31) 49.43/14.03 it(28) =< aux(32) 49.43/14.03 it(29) =< aux(32) 49.43/14.03 it(28) =< aux(67) 49.43/14.03 it(29) =< aux(67) 49.43/14.03 it(28) =< aux(34) 49.43/14.03 it(29) =< aux(34) 49.43/14.03 aux(15) =< aux(36) 49.43/14.03 it(28) =< aux(36) 49.43/14.03 it(28) =< aux(37) 49.43/14.03 it(29) =< aux(37) 49.43/14.03 it(28) =< aux(38) 49.43/14.03 it(29) =< aux(38) 49.43/14.03 it(28) =< aux(39) 49.43/14.03 it(29) =< aux(39) 49.43/14.03 it(28) =< aux(66) 49.43/14.03 it(29) =< aux(66) 49.43/14.03 it(28) =< aux(41) 49.43/14.03 it(29) =< aux(41) 49.43/14.03 it(28) =< aux(42) 49.43/14.03 it(29) =< aux(42) 49.43/14.03 aux(15) =< aux(43) 49.43/14.03 it(28) =< aux(43) 49.43/14.03 it(28) =< aux(44) 49.43/14.03 it(29) =< aux(44) 49.43/14.03 it(28) =< aux(45) 49.43/14.03 it(29) =< aux(45) 49.43/14.03 it(28) =< aux(46) 49.43/14.03 it(29) =< aux(46) 49.43/14.03 it(28) =< aux(47) 49.43/14.03 it(29) =< aux(47) 49.43/14.03 it(28) =< aux(48) 49.43/14.03 it(29) =< aux(48) 49.43/14.03 it(28) =< aux(49) 49.43/14.03 it(29) =< aux(49) 49.43/14.03 it(28) =< aux(50) 49.43/14.03 it(29) =< aux(50) 49.43/14.03 it(28) =< aux(51) 49.43/14.03 it(29) =< aux(51) 49.43/14.03 it(28) =< aux(52) 49.43/14.03 it(29) =< aux(52) 49.43/14.03 it(28) =< aux(53) 49.43/14.03 it(29) =< aux(53) 49.43/14.03 it(28) =< aux(54) 49.43/14.03 it(29) =< aux(54) 49.43/14.03 it(28) =< aux(55) 49.43/14.03 it(29) =< aux(55) 49.43/14.03 it(28) =< aux(56) 49.43/14.03 it(29) =< aux(56) 49.43/14.03 it(28) =< aux(57) 49.43/14.03 it(29) =< aux(57) 49.43/14.03 s(55) =< aux(68) 49.43/14.03 aux(7) =< aux(68)*(1/2) 49.43/14.03 aux(9) =< aux(68)*2 49.43/14.03 aux(21) =< aux(15)*2 49.43/14.03 aux(17) =< aux(15)*4 49.43/14.03 it(29) =< aux(15)+aux(16) 49.43/14.03 s(46) =< aux(68)+aux(13) 49.43/14.03 s(54) =< aux(21)+aux(22) 49.43/14.03 s(54) =< it(29)*aux(68) 49.43/14.03 s(59) =< aux(17)+aux(18) 49.43/14.03 s(59) =< it(29)*aux(68) 49.43/14.03 s(52) =< aux(9)+aux(10) 49.43/14.03 it(28) =< aux(7)+aux(8) 49.43/14.03 s(46) =< it(28)*aux(27) 49.43/14.03 s(52) =< it(28)*aux(27) 49.43/14.03 s(54) =< s(59) 49.43/14.03 s(57) =< s(59) 49.43/14.03 s(54) =< s(51) 49.43/14.03 s(57) =< s(51) 49.43/14.03 s(56) =< s(57) 49.43/14.03 s(46) =< s(52) 49.43/14.03 s(50) =< s(52) 49.43/14.03 s(46) =< s(51) 49.43/14.03 s(50) =< s(51) 49.43/14.03 s(48) =< s(50) 49.43/14.03 49.43/14.03 with precondition: [Out>=1,V1>=3*Out,V>=2*Out] 49.43/14.03 49.43/14.03 * Chain [32,26]: 4*s(69)+16 49.43/14.03 Such that:aux(69) =< V1 49.43/14.03 s(69) =< aux(69) 49.43/14.03 49.43/14.03 with precondition: [Out=0,V1=V,V1>=1] 49.43/14.03 49.43/14.03 * Chain [31,27]: 4*s(13)+3*s(14)+2*s(16)+12 49.43/14.03 Such that:s(10) =< V1 49.43/14.03 s(12) =< V1-Out 49.43/14.03 aux(6) =< Out 49.43/14.03 s(14) =< aux(6) 49.43/14.03 s(13) =< s(12) 49.43/14.03 s(13) =< s(10) 49.43/14.03 s(15) =< s(10) 49.43/14.03 s(15) =< s(12) 49.43/14.03 s(16) =< s(15) 49.43/14.03 49.43/14.03 with precondition: [V=Out,V>=1,V1>=2*V] 49.43/14.03 49.43/14.03 * Chain [30,26]: 3*s(60)+4*s(64)+2*s(67)+12 49.43/14.03 Such that:s(61) =< V 49.43/14.03 s(63) =< V-Out 49.43/14.03 aux(64) =< Out 49.43/14.03 s(60) =< aux(64) 49.43/14.03 s(64) =< s(63) 49.43/14.03 s(64) =< s(61) 49.43/14.03 s(66) =< s(61) 49.43/14.03 s(66) =< s(63) 49.43/14.03 s(67) =< s(66) 49.43/14.03 49.43/14.03 with precondition: [V1=Out,V1>=1,V>=2*V1] 49.43/14.03 49.43/14.03 * Chain [27]: 1 49.43/14.03 with precondition: [V1=0,V=Out,V>=1] 49.43/14.03 49.43/14.03 * Chain [26]: 1 49.43/14.03 with precondition: [V=0,V1=Out,V1>=0] 49.43/14.03 49.43/14.03 49.43/14.03 #### Cost of chains of start(V1,V,V10): 49.43/14.03 * Chain [42]: 1*s(72)+5*s(73)+8*s(77)+2*s(80)+4*s(82)+9 49.43/14.03 Such that:s(72) =< V 49.43/14.03 aux(72) =< V-2*V10 49.43/14.03 aux(73) =< V-V10 49.43/14.03 aux(74) =< V10 49.43/14.03 s(77) =< aux(72) 49.43/14.03 s(82) =< aux(73) 49.43/14.03 s(73) =< aux(74) 49.43/14.03 s(77) =< aux(73) 49.43/14.03 s(79) =< aux(73) 49.43/14.03 s(79) =< aux(72) 49.43/14.03 s(80) =< s(79) 49.43/14.03 49.43/14.03 with precondition: [V1=0,V>=0] 49.43/14.03 49.43/14.03 * Chain [41]: 5 49.43/14.03 with precondition: [V=0,V1>=0] 49.43/14.03 49.43/14.03 * Chain [40]: 3 49.43/14.03 with precondition: [V1=0,V10=0,V>=1] 49.43/14.03 49.43/14.03 * Chain [39]: 3*s(90)+9 49.43/14.03 Such that:aux(75) =< V10 49.43/14.03 s(90) =< aux(75) 49.43/14.03 49.43/14.03 with precondition: [V1=0,V=2*V10,V>=2] 49.43/14.03 49.43/14.03 * Chain [38]: 1 49.43/14.03 with precondition: [V1=1,V>=0,V10>=0] 49.43/14.03 49.43/14.03 * Chain [37]: 3*s(93)+6*s(95)+16 49.43/14.03 Such that:aux(76) =< V1 49.43/14.03 aux(77) =< V 49.43/14.03 s(93) =< aux(76) 49.43/14.03 s(95) =< aux(77) 49.43/14.03 49.43/14.03 with precondition: [V1>=1,V>=V1] 49.43/14.03 49.43/14.03 * Chain [36]: 3*s(103)+4*s(104)+2*s(106)+12 49.43/14.03 Such that:s(101) =< -V1+V 49.43/14.03 s(102) =< V1 49.43/14.03 s(100) =< V 49.43/14.03 s(103) =< s(102) 49.43/14.03 s(104) =< s(101) 49.43/14.03 s(104) =< s(100) 49.43/14.03 s(105) =< s(100) 49.43/14.03 s(105) =< s(101) 49.43/14.03 s(106) =< s(105) 49.43/14.03 49.43/14.03 with precondition: [V1>=1,V>=2*V1] 49.43/14.03 49.43/14.03 * Chain [35]: 7*s(140)+1*s(146)+9*s(147)+7*s(151)+2*s(152)+1*s(156)+4*s(161)+4*s(162)+2*s(166)+2*s(168)+12 49.43/14.03 Such that:s(107) =< -V1+V 49.43/14.03 s(108) =< -V1+2*V 49.43/14.03 s(142) =< V1 49.43/14.03 s(109) =< V1-V 49.43/14.03 s(112) =< V1+V/2 49.43/14.03 s(115) =< 2*V1-V 49.43/14.03 s(118) =< 2*V1+2*V 49.43/14.03 s(114) =< 2*V1+3*V 49.43/14.03 s(119) =< 2*V1+4*V 49.43/14.03 s(120) =< 3*V1+2*V 49.43/14.03 s(122) =< 3*V1+6*V 49.43/14.03 s(124) =< 4*V1+2*V 49.43/14.03 s(123) =< 6*V1+3*V 49.43/14.03 s(125) =< -V1/2+V/2 49.43/14.03 s(126) =< V1/2 49.43/14.03 s(127) =< V1/2+V 49.43/14.03 s(128) =< V1/2-V/2 49.43/14.03 s(129) =< V1/2+V/2 49.43/14.03 s(130) =< V1/2+3/4*V 49.43/14.03 s(131) =< 2/3*V1+2/3*V 49.43/14.03 s(132) =< 2/3*V1+4/3*V 49.43/14.03 s(133) =< 3/2*V1+3/4*V 49.43/14.03 s(134) =< 3/4*V1+V/2 49.43/14.03 s(135) =< 3/4*V1+3/2*V 49.43/14.03 s(136) =< 3/4*V1+3/4*V 49.43/14.03 s(137) =< 4/3*V1+2/3*V 49.43/14.03 aux(78) =< V1+V 49.43/14.03 aux(79) =< V1+2*V 49.43/14.03 aux(80) =< 2*V1+V 49.43/14.03 aux(81) =< 3*V1+3*V 49.43/14.03 aux(82) =< V 49.43/14.03 s(140) =< aux(82) 49.43/14.03 s(146) =< s(142) 49.43/14.03 s(147) =< aux(81) 49.43/14.03 s(151) =< aux(78) 49.43/14.03 s(140) =< aux(78) 49.43/14.03 s(152) =< aux(78) 49.43/14.03 s(151) =< aux(79) 49.43/14.03 s(140) =< aux(79) 49.43/14.03 s(151) =< s(112) 49.43/14.03 s(140) =< s(112) 49.43/14.03 s(151) =< aux(80) 49.43/14.03 s(140) =< aux(80) 49.43/14.03 s(154) =< s(126) 49.43/14.03 s(151) =< s(126) 49.43/14.03 s(151) =< s(127) 49.43/14.03 s(140) =< s(127) 49.43/14.03 s(151) =< s(129) 49.43/14.03 s(140) =< s(129) 49.43/14.03 s(151) =< s(130) 49.43/14.03 s(140) =< s(130) 49.43/14.03 s(151) =< s(114) 49.43/14.03 s(140) =< s(114) 49.43/14.03 s(154) =< s(142) 49.43/14.03 s(151) =< s(142) 49.43/14.03 s(151) =< s(131) 49.43/14.03 s(140) =< s(131) 49.43/14.03 s(151) =< s(118) 49.43/14.03 s(140) =< s(118) 49.43/14.03 s(151) =< s(132) 49.43/14.03 s(140) =< s(132) 49.43/14.03 s(151) =< s(119) 49.43/14.03 s(140) =< s(119) 49.43/14.03 s(151) =< s(133) 49.43/14.03 s(140) =< s(133) 49.43/14.03 s(151) =< s(123) 49.43/14.03 s(140) =< s(123) 49.43/14.03 s(151) =< s(134) 49.43/14.03 s(140) =< s(134) 49.43/14.03 s(151) =< s(120) 49.43/14.03 s(140) =< s(120) 49.43/14.03 s(151) =< s(135) 49.43/14.03 s(140) =< s(135) 49.43/14.03 s(151) =< s(122) 49.43/14.03 s(140) =< s(122) 49.43/14.03 s(151) =< s(136) 49.43/14.03 s(140) =< s(136) 49.43/14.03 s(151) =< aux(81) 49.43/14.03 s(140) =< aux(81) 49.43/14.03 s(151) =< s(137) 49.43/14.03 s(140) =< s(137) 49.43/14.03 s(151) =< s(124) 49.43/14.03 s(140) =< s(124) 49.43/14.03 s(156) =< aux(82) 49.43/14.03 s(157) =< aux(82)*(1/2) 49.43/14.03 s(158) =< aux(82)*2 49.43/14.03 s(159) =< s(154)*2 49.43/14.03 s(160) =< s(154)*4 49.43/14.03 s(140) =< s(154)+s(125) 49.43/14.03 s(161) =< aux(82)+s(109) 49.43/14.03 s(162) =< s(159)+s(107) 49.43/14.03 s(162) =< s(140)*aux(82) 49.43/14.03 s(163) =< s(160)+s(108) 49.43/14.03 s(163) =< s(140)*aux(82) 49.43/14.03 s(164) =< s(158)+s(115) 49.43/14.03 s(151) =< s(157)+s(128) 49.43/14.03 s(161) =< s(151)*s(142) 49.43/14.03 s(164) =< s(151)*s(142) 49.43/14.03 s(162) =< s(163) 49.43/14.03 s(165) =< s(163) 49.43/14.03 s(162) =< aux(78) 49.43/14.03 s(165) =< aux(78) 49.43/14.03 s(166) =< s(165) 49.43/14.03 s(161) =< s(164) 49.43/14.03 s(167) =< s(164) 49.43/14.03 s(161) =< aux(78) 49.43/14.03 s(167) =< aux(78) 49.43/14.03 s(168) =< s(167) 49.43/14.03 49.43/14.03 with precondition: [V1>=2,V>=3] 49.43/14.03 49.43/14.03 * Chain [34]: 4*s(170)+7*s(172)+7*s(214)+8*s(216)+7*s(219)+1*s(223)+4*s(228)+4*s(229)+2*s(233)+2*s(235)+12 49.43/14.03 Such that:s(175) =< -V1+V 49.43/14.03 s(176) =< -V1+2*V 49.43/14.03 aux(85) =< V1+V 49.43/14.03 aux(86) =< V1+2*V 49.43/14.03 s(182) =< V1+V/2 49.43/14.03 s(184) =< 2*V1-V 49.43/14.03 aux(87) =< 2*V1+V 49.43/14.03 s(186) =< 2*V1+2*V 49.43/14.03 s(187) =< 2*V1+3*V 49.43/14.03 s(188) =< 2*V1+4*V 49.43/14.03 s(202) =< 3*V1+2*V 49.43/14.03 s(189) =< 3*V1+3*V 49.43/14.03 s(203) =< 3*V1+6*V 49.43/14.03 s(190) =< 4*V1+2*V 49.43/14.03 s(191) =< 6*V1+3*V 49.43/14.03 s(192) =< -V1/2+V/2 49.43/14.03 s(193) =< V1/2 49.43/14.03 s(194) =< V1/2+V 49.43/14.03 s(196) =< V1/2-V/2 49.43/14.03 s(197) =< V1/2+V/2 49.43/14.03 s(198) =< V1/2+3/4*V 49.43/14.03 s(200) =< 2/3*V1+2/3*V 49.43/14.03 s(201) =< 2/3*V1+4/3*V 49.43/14.03 s(204) =< 3/2*V1+3/4*V 49.43/14.03 s(205) =< 3/4*V1+V/2 49.43/14.03 s(206) =< 3/4*V1+3/2*V 49.43/14.03 s(207) =< 3/4*V1+3/4*V 49.43/14.03 s(208) =< 4/3*V1+2/3*V 49.43/14.03 s(213) =< V 49.43/14.03 aux(88) =< V1 49.43/14.03 aux(89) =< V1-V 49.43/14.03 s(170) =< aux(89) 49.43/14.03 s(172) =< aux(88) 49.43/14.03 s(214) =< s(213) 49.43/14.03 s(216) =< aux(85) 49.43/14.03 s(219) =< aux(85) 49.43/14.03 s(214) =< aux(85) 49.43/14.03 s(219) =< aux(86) 49.43/14.03 s(214) =< aux(86) 49.43/14.03 s(219) =< s(182) 49.43/14.03 s(214) =< s(182) 49.43/14.03 s(219) =< aux(87) 49.43/14.03 s(214) =< aux(87) 49.43/14.03 s(222) =< s(193) 49.43/14.03 s(219) =< s(193) 49.43/14.03 s(219) =< s(194) 49.43/14.03 s(214) =< s(194) 49.43/14.03 s(219) =< s(197) 49.43/14.03 s(214) =< s(197) 49.43/14.03 s(219) =< s(198) 49.43/14.03 s(214) =< s(198) 49.43/14.03 s(219) =< s(187) 49.43/14.03 s(214) =< s(187) 49.43/14.03 s(222) =< aux(88) 49.43/14.03 s(219) =< aux(88) 49.43/14.03 s(219) =< s(200) 49.43/14.03 s(214) =< s(200) 49.43/14.03 s(219) =< s(186) 49.43/14.03 s(214) =< s(186) 49.43/14.03 s(219) =< s(201) 49.43/14.03 s(214) =< s(201) 49.43/14.03 s(219) =< s(188) 49.43/14.03 s(214) =< s(188) 49.43/14.03 s(219) =< s(204) 49.43/14.03 s(214) =< s(204) 49.43/14.03 s(219) =< s(191) 49.43/14.03 s(214) =< s(191) 49.43/14.03 s(219) =< s(205) 49.43/14.03 s(214) =< s(205) 49.43/14.03 s(219) =< s(202) 49.43/14.03 s(214) =< s(202) 49.43/14.03 s(219) =< s(206) 49.43/14.03 s(214) =< s(206) 49.43/14.03 s(219) =< s(203) 49.43/14.03 s(214) =< s(203) 49.43/14.03 s(219) =< s(207) 49.43/14.03 s(214) =< s(207) 49.43/14.03 s(219) =< s(189) 49.43/14.03 s(214) =< s(189) 49.43/14.03 s(219) =< s(208) 49.43/14.03 s(214) =< s(208) 49.43/14.03 s(219) =< s(190) 49.43/14.03 s(214) =< s(190) 49.43/14.03 s(223) =< s(213) 49.43/14.03 s(224) =< s(213)*(1/2) 49.43/14.03 s(225) =< s(213)*2 49.43/14.03 s(226) =< s(222)*2 49.43/14.03 s(227) =< s(222)*4 49.43/14.03 s(214) =< s(222)+s(192) 49.43/14.03 s(228) =< s(213)+aux(89) 49.43/14.03 s(229) =< s(226)+s(175) 49.43/14.03 s(229) =< s(214)*s(213) 49.43/14.03 s(230) =< s(227)+s(176) 49.43/14.03 s(230) =< s(214)*s(213) 49.43/14.03 s(231) =< s(225)+s(184) 49.43/14.03 s(219) =< s(224)+s(196) 49.43/14.03 s(228) =< s(219)*aux(88) 49.43/14.03 s(231) =< s(219)*aux(88) 49.43/14.03 s(229) =< s(230) 49.43/14.03 s(232) =< s(230) 49.43/14.03 s(229) =< aux(85) 49.43/14.03 s(232) =< aux(85) 49.43/14.03 s(233) =< s(232) 49.43/14.03 s(228) =< s(231) 49.43/14.03 s(234) =< s(231) 49.43/14.03 s(228) =< aux(85) 49.43/14.03 s(234) =< aux(85) 49.43/14.03 s(235) =< s(234) 49.43/14.03 s(170) =< aux(88) 49.43/14.03 49.43/14.03 with precondition: [V1>=3,V>=2] 49.43/14.03 49.43/14.03 * Chain [33]: 7*s(236)+8*s(240)+4*s(243)+12 49.43/14.03 Such that:aux(90) =< V1 49.43/14.03 aux(91) =< V1-V 49.43/14.03 aux(92) =< V 49.43/14.03 s(236) =< aux(92) 49.43/14.03 s(240) =< aux(91) 49.43/14.03 s(240) =< aux(90) 49.43/14.03 s(242) =< aux(90) 49.43/14.03 s(242) =< aux(91) 49.43/14.03 s(243) =< s(242) 49.43/14.03 49.43/14.03 with precondition: [V>=1,V1>=V] 49.43/14.03 49.43/14.03 49.43/14.03 Closed-form bounds of start(V1,V,V10): 49.43/14.03 ------------------------------------- 49.43/14.03 * Chain [42] with precondition: [V1=0,V>=0] 49.43/14.03 - Upper bound: V+9+nat(V10)*5+nat(V-V10)*6+nat(V-2*V10)*8 49.43/14.03 - Complexity: n 49.43/14.03 * Chain [41] with precondition: [V=0,V1>=0] 49.43/14.03 - Upper bound: 5 49.43/14.03 - Complexity: constant 49.43/14.03 * Chain [40] with precondition: [V1=0,V10=0,V>=1] 49.43/14.03 - Upper bound: 3 49.43/14.03 - Complexity: constant 49.43/14.03 * Chain [39] with precondition: [V1=0,V=2*V10,V>=2] 49.43/14.03 - Upper bound: 3*V10+9 49.43/14.03 - Complexity: n 49.43/14.03 * Chain [38] with precondition: [V1=1,V>=0,V10>=0] 49.43/14.03 - Upper bound: 1 49.43/14.03 - Complexity: constant 49.43/14.03 * Chain [37] with precondition: [V1>=1,V>=V1] 49.43/14.03 - Upper bound: 3*V1+6*V+16 49.43/14.03 - Complexity: n 49.43/14.03 * Chain [36] with precondition: [V1>=1,V>=2*V1] 49.43/14.03 - Upper bound: -V1+6*V+12 49.43/14.03 - Complexity: n 49.43/14.03 * Chain [35] with precondition: [V1>=2,V>=3] 49.43/14.03 - Upper bound: 10*V1+25*V+12+nat(-V1+V)*4+nat(-V1+2*V)*2+(27*V1+27*V)+nat(V1-V)*4+nat(2*V1-V)*2+8*V1 49.43/14.03 - Complexity: n 49.43/14.03 * Chain [34] with precondition: [V1>=3,V>=2] 49.43/14.03 - Upper bound: 22*V1+31*V+12+nat(-V1+V)*4+nat(-V1+2*V)*2+nat(V1-V)*8+nat(2*V1-V)*2+8*V1 49.43/14.03 - Complexity: n 49.43/14.03 * Chain [33] with precondition: [V>=1,V1>=V] 49.43/14.03 - Upper bound: 12*V1-V+12 49.43/14.03 - Complexity: n 49.43/14.03 49.43/14.03 ### Maximum cost of start(V1,V,V10): max([max([4,nat(V10)*3+8]),V+8+max([nat(V-V10)*6+nat(V10)*5+nat(V-2*V10)*8,V1+V+3+max([2*V1+max([nat(-V1+V)*4,4*V+max([4,18*V1+24*V+nat(-V1+V)*4+nat(-V1+2*V)*2+nat(2*V1-V)*2+8*V1+(V1+V+nat(V1-V)*8)])]),9*V1+23*V+nat(-V1+V)*4+nat(-V1+2*V)*2+(27*V1+27*V)+nat(V1-V)*4+nat(2*V1-V)*2+8*V1])])])+1 49.43/14.03 Asymptotic class: n 49.43/14.03 * Total analysis performed in 1177 ms. 49.43/14.03 49.43/14.03 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (10) 49.43/14.03 BOUNDS(1, n^1) 49.43/14.03 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 49.43/14.03 Transformed a relative TRS into a decreasing-loop problem. 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (12) 49.43/14.03 Obligation: 49.43/14.03 Analyzing the following TRS for decreasing loops: 49.43/14.03 49.43/14.03 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 49.43/14.03 49.43/14.03 49.43/14.03 The TRS R consists of the following rules: 49.43/14.03 49.43/14.03 minus(0, x) -> 0 49.43/14.03 minus(s(x), 0) -> s(x) 49.43/14.03 minus(s(x), s(y)) -> minus(x, y) 49.43/14.03 mod(x, 0) -> 0 49.43/14.03 mod(x, s(y)) -> if(lt(x, s(y)), x, s(y)) 49.43/14.03 if(true, x, y) -> x 49.43/14.03 if(false, x, y) -> mod(minus(x, y), y) 49.43/14.03 gcd(x, 0) -> x 49.43/14.03 gcd(0, s(y)) -> s(y) 49.43/14.03 gcd(s(x), s(y)) -> gcd(mod(s(x), s(y)), mod(s(y), s(x))) 49.43/14.03 lt(x, 0) -> false 49.43/14.03 lt(0, s(x)) -> true 49.43/14.03 lt(s(x), s(y)) -> lt(x, y) 49.43/14.03 49.43/14.03 S is empty. 49.43/14.03 Rewrite Strategy: INNERMOST 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (13) DecreasingLoopProof (LOWER BOUND(ID)) 49.43/14.03 The following loop(s) give(s) rise to the lower bound Omega(n^1): 49.43/14.03 49.43/14.03 The rewrite sequence 49.43/14.03 49.43/14.03 lt(s(x), s(y)) ->^+ lt(x, y) 49.43/14.03 49.43/14.03 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 49.43/14.03 49.43/14.03 The pumping substitution is [x / s(x), y / s(y)]. 49.43/14.03 49.43/14.03 The result substitution is [ ]. 49.43/14.03 49.43/14.03 49.43/14.03 49.43/14.03 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (14) 49.43/14.03 Complex Obligation (BEST) 49.43/14.03 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (15) 49.43/14.03 Obligation: 49.43/14.03 Proved the lower bound n^1 for the following obligation: 49.43/14.03 49.43/14.03 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 49.43/14.03 49.43/14.03 49.43/14.03 The TRS R consists of the following rules: 49.43/14.03 49.43/14.03 minus(0, x) -> 0 49.43/14.03 minus(s(x), 0) -> s(x) 49.43/14.03 minus(s(x), s(y)) -> minus(x, y) 49.43/14.03 mod(x, 0) -> 0 49.43/14.03 mod(x, s(y)) -> if(lt(x, s(y)), x, s(y)) 49.43/14.03 if(true, x, y) -> x 49.43/14.03 if(false, x, y) -> mod(minus(x, y), y) 49.43/14.03 gcd(x, 0) -> x 49.43/14.03 gcd(0, s(y)) -> s(y) 49.43/14.03 gcd(s(x), s(y)) -> gcd(mod(s(x), s(y)), mod(s(y), s(x))) 49.43/14.03 lt(x, 0) -> false 49.43/14.03 lt(0, s(x)) -> true 49.43/14.03 lt(s(x), s(y)) -> lt(x, y) 49.43/14.03 49.43/14.03 S is empty. 49.43/14.03 Rewrite Strategy: INNERMOST 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (16) LowerBoundPropagationProof (FINISHED) 49.43/14.03 Propagated lower bound. 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (17) 49.43/14.03 BOUNDS(n^1, INF) 49.43/14.03 49.43/14.03 ---------------------------------------- 49.43/14.03 49.43/14.03 (18) 49.43/14.03 Obligation: 49.43/14.03 Analyzing the following TRS for decreasing loops: 49.43/14.03 49.43/14.03 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 49.43/14.03 49.43/14.03 49.43/14.03 The TRS R consists of the following rules: 49.43/14.03 49.43/14.03 minus(0, x) -> 0 49.43/14.03 minus(s(x), 0) -> s(x) 49.43/14.03 minus(s(x), s(y)) -> minus(x, y) 49.43/14.03 mod(x, 0) -> 0 49.43/14.03 mod(x, s(y)) -> if(lt(x, s(y)), x, s(y)) 49.43/14.03 if(true, x, y) -> x 49.43/14.03 if(false, x, y) -> mod(minus(x, y), y) 49.43/14.03 gcd(x, 0) -> x 49.43/14.03 gcd(0, s(y)) -> s(y) 49.43/14.03 gcd(s(x), s(y)) -> gcd(mod(s(x), s(y)), mod(s(y), s(x))) 49.43/14.03 lt(x, 0) -> false 49.43/14.03 lt(0, s(x)) -> true 49.43/14.03 lt(s(x), s(y)) -> lt(x, y) 49.43/14.03 49.43/14.03 S is empty. 49.43/14.03 Rewrite Strategy: INNERMOST 49.43/14.06 EOF