39.38/13.01 WORST_CASE(Omega(n^1), O(n^1)) 39.38/13.02 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 39.38/13.02 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 39.38/13.02 39.38/13.02 39.38/13.02 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 39.38/13.02 39.38/13.02 (0) CpxTRS 39.38/13.02 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 39.38/13.02 (2) CpxWeightedTrs 39.38/13.02 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 39.38/13.02 (4) CpxTypedWeightedTrs 39.38/13.02 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 39.38/13.02 (6) CpxTypedWeightedCompleteTrs 39.38/13.02 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 39.38/13.02 (8) CpxRNTS 39.38/13.02 (9) CompleteCoflocoProof [FINISHED, 1455 ms] 39.38/13.02 (10) BOUNDS(1, n^1) 39.38/13.02 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 39.38/13.02 (12) CpxTRS 39.38/13.02 (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 39.38/13.02 (14) typed CpxTrs 39.38/13.02 (15) OrderProof [LOWER BOUND(ID), 0 ms] 39.38/13.02 (16) typed CpxTrs 39.38/13.02 (17) RewriteLemmaProof [LOWER BOUND(ID), 305 ms] 39.38/13.02 (18) BEST 39.38/13.02 (19) proven lower bound 39.38/13.02 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 39.38/13.02 (21) BOUNDS(n^1, INF) 39.38/13.02 (22) typed CpxTrs 39.38/13.02 (23) RewriteLemmaProof [LOWER BOUND(ID), 850 ms] 39.38/13.02 (24) typed CpxTrs 39.38/13.02 39.38/13.02 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (0) 39.38/13.02 Obligation: 39.38/13.02 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 39.38/13.02 39.38/13.02 39.38/13.02 The TRS R consists of the following rules: 39.38/13.02 39.38/13.02 le(0, y) -> true 39.38/13.02 le(s(x), 0) -> false 39.38/13.02 le(s(x), s(y)) -> le(x, y) 39.38/13.02 pred(s(x)) -> x 39.38/13.02 minus(x, 0) -> x 39.38/13.02 minus(x, s(y)) -> pred(minus(x, y)) 39.38/13.02 gcd(0, y) -> y 39.38/13.02 gcd(s(x), 0) -> s(x) 39.38/13.02 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) 39.38/13.02 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) 39.38/13.02 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) 39.38/13.02 39.38/13.02 S is empty. 39.38/13.02 Rewrite Strategy: INNERMOST 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 39.38/13.02 Transformed relative TRS to weighted TRS 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (2) 39.38/13.02 Obligation: 39.38/13.02 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 39.38/13.02 39.38/13.02 39.38/13.02 The TRS R consists of the following rules: 39.38/13.02 39.38/13.02 le(0, y) -> true [1] 39.38/13.02 le(s(x), 0) -> false [1] 39.38/13.02 le(s(x), s(y)) -> le(x, y) [1] 39.38/13.02 pred(s(x)) -> x [1] 39.38/13.02 minus(x, 0) -> x [1] 39.38/13.02 minus(x, s(y)) -> pred(minus(x, y)) [1] 39.38/13.02 gcd(0, y) -> y [1] 39.38/13.02 gcd(s(x), 0) -> s(x) [1] 39.38/13.02 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) [1] 39.38/13.02 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) [1] 39.38/13.02 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) [1] 39.38/13.02 39.38/13.02 Rewrite Strategy: INNERMOST 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 39.38/13.02 Infered types. 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (4) 39.38/13.02 Obligation: 39.38/13.02 Runtime Complexity Weighted TRS with Types. 39.38/13.02 The TRS R consists of the following rules: 39.38/13.02 39.38/13.02 le(0, y) -> true [1] 39.38/13.02 le(s(x), 0) -> false [1] 39.38/13.02 le(s(x), s(y)) -> le(x, y) [1] 39.38/13.02 pred(s(x)) -> x [1] 39.38/13.02 minus(x, 0) -> x [1] 39.38/13.02 minus(x, s(y)) -> pred(minus(x, y)) [1] 39.38/13.02 gcd(0, y) -> y [1] 39.38/13.02 gcd(s(x), 0) -> s(x) [1] 39.38/13.02 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) [1] 39.38/13.02 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) [1] 39.38/13.02 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) [1] 39.38/13.02 39.38/13.02 The TRS has the following type information: 39.38/13.02 le :: 0:s -> 0:s -> true:false 39.38/13.02 0 :: 0:s 39.38/13.02 true :: true:false 39.38/13.02 s :: 0:s -> 0:s 39.38/13.02 false :: true:false 39.38/13.02 pred :: 0:s -> 0:s 39.38/13.02 minus :: 0:s -> 0:s -> 0:s 39.38/13.02 gcd :: 0:s -> 0:s -> 0:s 39.38/13.02 if_gcd :: true:false -> 0:s -> 0:s -> 0:s 39.38/13.02 39.38/13.02 Rewrite Strategy: INNERMOST 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (5) CompletionProof (UPPER BOUND(ID)) 39.38/13.02 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 39.38/13.02 39.38/13.02 pred(v0) -> null_pred [0] 39.38/13.02 if_gcd(v0, v1, v2) -> null_if_gcd [0] 39.38/13.02 le(v0, v1) -> null_le [0] 39.38/13.02 minus(v0, v1) -> null_minus [0] 39.38/13.02 gcd(v0, v1) -> null_gcd [0] 39.38/13.02 39.38/13.02 And the following fresh constants: null_pred, null_if_gcd, null_le, null_minus, null_gcd 39.38/13.02 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (6) 39.38/13.02 Obligation: 39.38/13.02 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 39.38/13.02 39.38/13.02 Runtime Complexity Weighted TRS with Types. 39.38/13.02 The TRS R consists of the following rules: 39.38/13.02 39.38/13.02 le(0, y) -> true [1] 39.38/13.02 le(s(x), 0) -> false [1] 39.38/13.02 le(s(x), s(y)) -> le(x, y) [1] 39.38/13.02 pred(s(x)) -> x [1] 39.38/13.02 minus(x, 0) -> x [1] 39.38/13.02 minus(x, s(y)) -> pred(minus(x, y)) [1] 39.38/13.02 gcd(0, y) -> y [1] 39.38/13.02 gcd(s(x), 0) -> s(x) [1] 39.38/13.02 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) [1] 39.38/13.02 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) [1] 39.38/13.02 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) [1] 39.38/13.02 pred(v0) -> null_pred [0] 39.38/13.02 if_gcd(v0, v1, v2) -> null_if_gcd [0] 39.38/13.02 le(v0, v1) -> null_le [0] 39.38/13.02 minus(v0, v1) -> null_minus [0] 39.38/13.02 gcd(v0, v1) -> null_gcd [0] 39.38/13.02 39.38/13.02 The TRS has the following type information: 39.38/13.02 le :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> true:false:null_le 39.38/13.02 0 :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 true :: true:false:null_le 39.38/13.02 s :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 false :: true:false:null_le 39.38/13.02 pred :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 minus :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 gcd :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 if_gcd :: true:false:null_le -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd -> 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 null_pred :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 null_if_gcd :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 null_le :: true:false:null_le 39.38/13.02 null_minus :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 null_gcd :: 0:s:null_pred:null_if_gcd:null_minus:null_gcd 39.38/13.02 39.38/13.02 Rewrite Strategy: INNERMOST 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 39.38/13.02 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 39.38/13.02 The constant constructors are abstracted as follows: 39.38/13.02 39.38/13.02 0 => 0 39.38/13.02 true => 2 39.38/13.02 false => 1 39.38/13.02 null_pred => 0 39.38/13.02 null_if_gcd => 0 39.38/13.02 null_le => 0 39.38/13.02 null_minus => 0 39.38/13.02 null_gcd => 0 39.38/13.02 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (8) 39.38/13.02 Obligation: 39.38/13.02 Complexity RNTS consisting of the following rules: 39.38/13.02 39.38/13.02 gcd(z, z') -{ 1 }-> y :|: y >= 0, z = 0, z' = y 39.38/13.02 gcd(z, z') -{ 1 }-> if_gcd(le(y, x), 1 + x, 1 + y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 39.38/13.02 gcd(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 39.38/13.02 gcd(z, z') -{ 1 }-> 1 + x :|: x >= 0, z = 1 + x, z' = 0 39.38/13.02 if_gcd(z, z', z'') -{ 1 }-> gcd(minus(x, y), 1 + y) :|: z = 2, z' = 1 + x, x >= 0, y >= 0, z'' = 1 + y 39.38/13.02 if_gcd(z, z', z'') -{ 1 }-> gcd(minus(y, x), 1 + x) :|: z' = 1 + x, z = 1, x >= 0, y >= 0, z'' = 1 + y 39.38/13.02 if_gcd(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 39.38/13.02 le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 39.38/13.02 le(z, z') -{ 1 }-> 2 :|: y >= 0, z = 0, z' = y 39.38/13.02 le(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0 39.38/13.02 le(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 39.38/13.02 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 39.38/13.02 minus(z, z') -{ 1 }-> pred(minus(x, y)) :|: z' = 1 + y, x >= 0, y >= 0, z = x 39.38/13.02 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 39.38/13.02 pred(z) -{ 1 }-> x :|: x >= 0, z = 1 + x 39.38/13.02 pred(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 39.38/13.02 39.38/13.02 Only complete derivations are relevant for the runtime complexity. 39.38/13.02 39.38/13.02 ---------------------------------------- 39.38/13.02 39.38/13.02 (9) CompleteCoflocoProof (FINISHED) 39.38/13.02 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 39.38/13.02 39.38/13.02 eq(start(V1, V, V15),0,[le(V1, V, Out)],[V1 >= 0,V >= 0]). 39.38/13.02 eq(start(V1, V, V15),0,[pred(V1, Out)],[V1 >= 0]). 39.38/13.02 eq(start(V1, V, V15),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). 39.38/13.02 eq(start(V1, V, V15),0,[gcd(V1, V, Out)],[V1 >= 0,V >= 0]). 39.38/13.02 eq(start(V1, V, V15),0,[fun(V1, V, V15, Out)],[V1 >= 0,V >= 0,V15 >= 0]). 39.38/13.02 eq(le(V1, V, Out),1,[],[Out = 2,V2 >= 0,V1 = 0,V = V2]). 39.38/13.02 eq(le(V1, V, Out),1,[],[Out = 1,V3 >= 0,V1 = 1 + V3,V = 0]). 39.38/13.02 eq(le(V1, V, Out),1,[le(V4, V5, Ret)],[Out = Ret,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]). 39.38/13.02 eq(pred(V1, Out),1,[],[Out = V6,V6 >= 0,V1 = 1 + V6]). 39.38/13.02 eq(minus(V1, V, Out),1,[],[Out = V7,V7 >= 0,V1 = V7,V = 0]). 39.38/13.02 eq(minus(V1, V, Out),1,[minus(V8, V9, Ret0),pred(Ret0, Ret1)],[Out = Ret1,V = 1 + V9,V8 >= 0,V9 >= 0,V1 = V8]). 39.38/13.02 eq(gcd(V1, V, Out),1,[],[Out = V10,V10 >= 0,V1 = 0,V = V10]). 39.38/13.02 eq(gcd(V1, V, Out),1,[],[Out = 1 + V11,V11 >= 0,V1 = 1 + V11,V = 0]). 39.38/13.02 eq(gcd(V1, V, Out),1,[le(V12, V13, Ret01),fun(Ret01, 1 + V13, 1 + V12, Ret2)],[Out = Ret2,V = 1 + V12,V13 >= 0,V12 >= 0,V1 = 1 + V13]). 39.38/13.02 eq(fun(V1, V, V15, Out),1,[minus(V16, V14, Ret02),gcd(Ret02, 1 + V14, Ret3)],[Out = Ret3,V1 = 2,V = 1 + V16,V16 >= 0,V14 >= 0,V15 = 1 + V14]). 39.38/13.02 eq(fun(V1, V, V15, Out),1,[minus(V18, V17, Ret03),gcd(Ret03, 1 + V17, Ret4)],[Out = Ret4,V = 1 + V17,V1 = 1,V17 >= 0,V18 >= 0,V15 = 1 + V18]). 39.38/13.02 eq(pred(V1, Out),0,[],[Out = 0,V19 >= 0,V1 = V19]). 39.38/13.02 eq(fun(V1, V, V15, Out),0,[],[Out = 0,V21 >= 0,V15 = V22,V20 >= 0,V1 = V21,V = V20,V22 >= 0]). 39.38/13.02 eq(le(V1, V, Out),0,[],[Out = 0,V24 >= 0,V23 >= 0,V1 = V24,V = V23]). 39.38/13.02 eq(minus(V1, V, Out),0,[],[Out = 0,V25 >= 0,V26 >= 0,V1 = V25,V = V26]). 39.38/13.02 eq(gcd(V1, V, Out),0,[],[Out = 0,V27 >= 0,V28 >= 0,V1 = V27,V = V28]). 39.38/13.02 input_output_vars(le(V1,V,Out),[V1,V],[Out]). 39.38/13.02 input_output_vars(pred(V1,Out),[V1],[Out]). 39.38/13.02 input_output_vars(minus(V1,V,Out),[V1,V],[Out]). 39.38/13.02 input_output_vars(gcd(V1,V,Out),[V1,V],[Out]). 39.38/13.02 input_output_vars(fun(V1,V,V15,Out),[V1,V,V15],[Out]). 39.38/13.02 39.38/13.02 39.38/13.02 CoFloCo proof output: 39.38/13.02 Preprocessing Cost Relations 39.38/13.02 ===================================== 39.38/13.02 39.38/13.02 #### Computed strongly connected components 39.38/13.02 0. recursive : [le/3] 39.38/13.02 1. non_recursive : [pred/2] 39.38/13.02 2. recursive [non_tail] : [minus/3] 39.38/13.02 3. recursive : [fun/4,gcd/3] 39.38/13.02 4. non_recursive : [start/3] 39.38/13.02 39.38/13.02 #### Obtained direct recursion through partial evaluation 39.38/13.02 0. SCC is partially evaluated into le/3 39.38/13.02 1. SCC is partially evaluated into pred/2 39.38/13.02 2. SCC is partially evaluated into minus/3 39.38/13.02 3. SCC is partially evaluated into gcd/3 39.38/13.02 4. SCC is partially evaluated into start/3 39.38/13.02 39.38/13.02 Control-Flow Refinement of Cost Relations 39.38/13.02 ===================================== 39.38/13.02 39.38/13.02 ### Specialization of cost equations le/3 39.38/13.02 * CE 20 is refined into CE [23] 39.38/13.02 * CE 18 is refined into CE [24] 39.38/13.02 * CE 17 is refined into CE [25] 39.38/13.02 * CE 19 is refined into CE [26] 39.38/13.02 39.38/13.02 39.38/13.02 ### Cost equations --> "Loop" of le/3 39.38/13.02 * CEs [26] --> Loop 17 39.38/13.02 * CEs [23] --> Loop 18 39.38/13.02 * CEs [24] --> Loop 19 39.38/13.02 * CEs [25] --> Loop 20 39.38/13.02 39.38/13.02 ### Ranking functions of CR le(V1,V,Out) 39.38/13.02 * RF of phase [17]: [V,V1] 39.38/13.02 39.38/13.02 #### Partial ranking functions of CR le(V1,V,Out) 39.38/13.02 * Partial RF of phase [17]: 39.38/13.02 - RF of loop [17:1]: 39.38/13.02 V 39.38/13.02 V1 39.38/13.02 39.38/13.02 39.38/13.02 ### Specialization of cost equations pred/2 39.38/13.02 * CE 21 is refined into CE [27] 39.38/13.02 * CE 22 is refined into CE [28] 39.38/13.02 39.38/13.02 39.38/13.02 ### Cost equations --> "Loop" of pred/2 39.38/13.02 * CEs [27] --> Loop 21 39.38/13.02 * CEs [28] --> Loop 22 39.38/13.02 39.38/13.02 ### Ranking functions of CR pred(V1,Out) 39.38/13.02 39.38/13.02 #### Partial ranking functions of CR pred(V1,Out) 39.38/13.02 39.38/13.02 39.38/13.02 ### Specialization of cost equations minus/3 39.38/13.02 * CE 10 is refined into CE [29] 39.38/13.02 * CE 8 is refined into CE [30] 39.38/13.02 * CE 9 is refined into CE [31,32] 39.38/13.02 39.38/13.02 39.38/13.02 ### Cost equations --> "Loop" of minus/3 39.38/13.02 * CEs [32] --> Loop 23 39.38/13.02 * CEs [31] --> Loop 24 39.38/13.02 * CEs [29] --> Loop 25 39.38/13.02 * CEs [30] --> Loop 26 39.38/13.02 39.38/13.02 ### Ranking functions of CR minus(V1,V,Out) 39.38/13.02 * RF of phase [23]: [V] 39.38/13.02 * RF of phase [24]: [V] 39.38/13.02 39.38/13.02 #### Partial ranking functions of CR minus(V1,V,Out) 39.38/13.02 * Partial RF of phase [23]: 39.38/13.02 - RF of loop [23:1]: 39.38/13.02 V 39.38/13.02 * Partial RF of phase [24]: 39.38/13.02 - RF of loop [24:1]: 39.38/13.02 V 39.38/13.02 39.38/13.02 39.38/13.02 ### Specialization of cost equations gcd/3 39.38/13.02 * CE 11 is refined into CE [33,34,35,36,37] 39.38/13.02 * CE 16 is refined into CE [38] 39.38/13.02 * CE 15 is refined into CE [39] 39.38/13.02 * CE 14 is refined into CE [40] 39.38/13.02 * CE 13 is refined into CE [41,42,43,44] 39.38/13.02 * CE 12 is refined into CE [45,46,47,48] 39.38/13.02 39.38/13.02 39.38/13.02 ### Cost equations --> "Loop" of gcd/3 39.38/13.02 * CEs [48] --> Loop 27 39.38/13.02 * CEs [44] --> Loop 28 39.38/13.02 * CEs [47] --> Loop 29 39.38/13.02 * CEs [43] --> Loop 30 39.38/13.02 * CEs [41] --> Loop 31 39.38/13.02 * CEs [42] --> Loop 32 39.38/13.02 * CEs [45] --> Loop 33 39.38/13.02 * CEs [46] --> Loop 34 39.38/13.02 * CEs [33] --> Loop 35 39.38/13.02 * CEs [39] --> Loop 36 39.38/13.02 * CEs [34,35,36,37,38] --> Loop 37 39.38/13.02 * CEs [40] --> Loop 38 39.38/13.02 39.38/13.02 ### Ranking functions of CR gcd(V1,V,Out) 39.38/13.02 * RF of phase [27,28]: [V1+V-3] 39.38/13.02 * RF of phase [31]: [V1] 39.38/13.02 39.38/13.02 #### Partial ranking functions of CR gcd(V1,V,Out) 39.38/13.02 * Partial RF of phase [27,28]: 39.38/13.02 - RF of loop [27:1]: 39.38/13.02 V-2 39.38/13.02 V1/2+V/2-2 39.38/13.02 - RF of loop [28:1]: 39.38/13.02 V1-1 depends on loops [27:1] 39.38/13.02 V1-V+1 depends on loops [27:1] 39.38/13.02 * Partial RF of phase [31]: 39.38/13.02 - RF of loop [31:1]: 39.38/13.02 V1 39.38/13.02 39.38/13.02 39.38/13.02 ### Specialization of cost equations start/3 39.38/13.02 * CE 3 is refined into CE [49,50,51,52,53,54,55,56,57,58,59,60] 39.38/13.02 * CE 1 is refined into CE [61] 39.38/13.02 * CE 2 is refined into CE [62,63,64,65,66,67,68,69,70,71,72,73] 39.38/13.02 * CE 4 is refined into CE [74,75,76,77,78] 39.38/13.02 * CE 5 is refined into CE [79,80] 39.38/13.02 * CE 6 is refined into CE [81,82,83] 39.38/13.02 * CE 7 is refined into CE [84,85,86,87,88,89,90,91,92] 39.38/13.02 39.38/13.02 39.38/13.02 ### Cost equations --> "Loop" of start/3 39.38/13.02 * CEs [88,89] --> Loop 39 39.38/13.02 * CEs [75,81,87] --> Loop 40 39.38/13.02 * CEs [57] --> Loop 41 39.38/13.02 * CEs [55] --> Loop 42 39.38/13.02 * CEs [49,50,51,52,53,54,56,58,59,60] --> Loop 43 39.38/13.02 * CEs [68] --> Loop 44 39.38/13.02 * CEs [70,86] --> Loop 45 39.38/13.02 * CEs [62,63,64,65,66,67,69,71,72,73] --> Loop 46 39.38/13.02 * CEs [61,74,76,77,78,79,80,82,83,84,85,90,91,92] --> Loop 47 39.38/13.02 39.38/13.02 ### Ranking functions of CR start(V1,V,V15) 39.38/13.02 39.38/13.02 #### Partial ranking functions of CR start(V1,V,V15) 39.38/13.02 39.38/13.02 39.38/13.02 Computing Bounds 39.38/13.02 ===================================== 39.38/13.02 39.38/13.02 #### Cost of chains of le(V1,V,Out): 39.38/13.02 * Chain [[17],20]: 1*it(17)+1 39.38/13.02 Such that:it(17) =< V1 39.38/13.02 39.38/13.02 with precondition: [Out=2,V1>=1,V>=V1] 39.38/13.02 39.38/13.02 * Chain [[17],19]: 1*it(17)+1 39.38/13.02 Such that:it(17) =< V 39.38/13.02 39.38/13.02 with precondition: [Out=1,V>=1,V1>=V+1] 39.38/13.02 39.38/13.02 * Chain [[17],18]: 1*it(17)+0 39.38/13.02 Such that:it(17) =< V 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=1,V>=1] 39.38/13.02 39.38/13.02 * Chain [20]: 1 39.38/13.02 with precondition: [V1=0,Out=2,V>=0] 39.38/13.02 39.38/13.02 * Chain [19]: 1 39.38/13.02 with precondition: [V=0,Out=1,V1>=1] 39.38/13.02 39.38/13.02 * Chain [18]: 0 39.38/13.02 with precondition: [Out=0,V1>=0,V>=0] 39.38/13.02 39.38/13.02 39.38/13.02 #### Cost of chains of pred(V1,Out): 39.38/13.02 * Chain [22]: 0 39.38/13.02 with precondition: [Out=0,V1>=0] 39.38/13.02 39.38/13.02 * Chain [21]: 1 39.38/13.02 with precondition: [V1=Out+1,V1>=1] 39.38/13.02 39.38/13.02 39.38/13.02 #### Cost of chains of minus(V1,V,Out): 39.38/13.02 * Chain [[24],[23],26]: 3*it(23)+1 39.38/13.02 Such that:aux(1) =< V 39.38/13.02 it(23) =< aux(1) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=1,V>=2] 39.38/13.02 39.38/13.02 * Chain [[24],26]: 1*it(24)+1 39.38/13.02 Such that:it(24) =< V 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=0,V>=1] 39.38/13.02 39.38/13.02 * Chain [[24],25]: 1*it(24)+0 39.38/13.02 Such that:it(24) =< V 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=0,V>=1] 39.38/13.02 39.38/13.02 * Chain [[23],26]: 2*it(23)+1 39.38/13.02 Such that:it(23) =< V 39.38/13.02 39.38/13.02 with precondition: [V1=Out+V,V>=1,V1>=V] 39.38/13.02 39.38/13.02 * Chain [26]: 1 39.38/13.02 with precondition: [V=0,V1=Out,V1>=0] 39.38/13.02 39.38/13.02 * Chain [25]: 0 39.38/13.02 with precondition: [Out=0,V1>=0,V>=0] 39.38/13.02 39.38/13.02 39.38/13.02 #### Cost of chains of gcd(V1,V,Out): 39.38/13.02 * Chain [[31],38]: 4*it(31)+1 39.38/13.02 Such that:it(31) =< V1 39.38/13.02 39.38/13.02 with precondition: [V=1,Out=1,V1>=1] 39.38/13.02 39.38/13.02 * Chain [[31],37]: 6*it(31)+1*s(8)+2 39.38/13.02 Such that:s(8) =< 1 39.38/13.02 aux(4) =< V1 39.38/13.02 it(31) =< aux(4) 39.38/13.02 39.38/13.02 with precondition: [V=1,Out=0,V1>=1] 39.38/13.02 39.38/13.02 * Chain [[31],35]: 4*it(31)+2 39.38/13.02 Such that:it(31) =< V1 39.38/13.02 39.38/13.02 with precondition: [V=1,Out=0,V1>=2] 39.38/13.02 39.38/13.02 * Chain [[31],32,38]: 4*it(31)+5 39.38/13.02 Such that:it(31) =< V1 39.38/13.02 39.38/13.02 with precondition: [V=1,Out=1,V1>=2] 39.38/13.02 39.38/13.02 * Chain [[31],32,37]: 4*it(31)+1*s(8)+6 39.38/13.02 Such that:s(8) =< 1 39.38/13.02 it(31) =< V1 39.38/13.02 39.38/13.02 with precondition: [V=1,Out=0,V1>=2] 39.38/13.02 39.38/13.02 * Chain [[27,28],38]: 4*it(27)+4*it(28)+3*s(19)+3*s(21)+1 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 aux(22) =< V1+V 39.38/13.02 aux(23) =< V1+V-Out 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(25) =< V1/2+V/2-Out/2 39.38/13.02 aux(26) =< V 39.38/13.02 aux(27) =< V-Out 39.38/13.02 aux(9) =< 2*V-2*Out 39.38/13.02 aux(28) =< V1 39.38/13.02 it(27) =< aux(22) 39.38/13.02 it(28) =< aux(22) 39.38/13.02 s(20) =< aux(22) 39.38/13.02 it(27) =< aux(23) 39.38/13.02 it(28) =< aux(23) 39.38/13.02 s(20) =< aux(23) 39.38/13.02 it(27) =< aux(25) 39.38/13.02 it(28) =< aux(25) 39.38/13.02 aux(7) =< aux(26) 39.38/13.02 it(27) =< aux(26) 39.38/13.02 aux(7) =< aux(27) 39.38/13.02 it(27) =< aux(27) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(7)+aux(28) 39.38/13.02 s(22) =< aux(7)+aux(28) 39.38/13.02 s(22) =< it(28)*aux(26) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< s(20) 39.38/13.02 39.38/13.02 with precondition: [Out>=2,V1>=Out,V>=Out] 39.38/13.02 39.38/13.02 * Chain [[27,28],37]: 4*it(27)+4*it(28)+6*s(6)+3*s(21)+2 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(29) =< V1 39.38/13.02 aux(30) =< V1+V 39.38/13.02 aux(31) =< V 39.38/13.02 s(6) =< aux(30) 39.38/13.02 it(27) =< aux(30) 39.38/13.02 it(28) =< aux(30) 39.38/13.02 it(27) =< aux(31) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(31)+aux(29) 39.38/13.02 s(22) =< aux(31)+aux(29) 39.38/13.02 s(22) =< it(28)*aux(31) 39.38/13.02 s(21) =< s(22) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=2,V>=2] 39.38/13.02 39.38/13.02 * Chain [[27,28],34,38]: 4*it(27)+4*it(28)+3*s(19)+3*s(21)+5 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(32) =< V1 39.38/13.02 aux(33) =< V1+V 39.38/13.02 aux(34) =< V1/2+V/2 39.38/13.02 aux(35) =< V 39.38/13.02 it(27) =< aux(34) 39.38/13.02 it(27) =< aux(33) 39.38/13.02 it(28) =< aux(33) 39.38/13.02 it(28) =< aux(34) 39.38/13.02 it(27) =< aux(35) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(35)+aux(32) 39.38/13.02 s(22) =< aux(35)+aux(32) 39.38/13.02 s(22) =< it(28)*aux(35) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(33) 39.38/13.02 39.38/13.02 with precondition: [Out=1,V1>=2,V>=2,V+V1>=5] 39.38/13.02 39.38/13.02 * Chain [[27,28],34,37]: 4*it(27)+4*it(28)+1*s(8)+3*s(19)+3*s(21)+6 39.38/13.02 Such that:s(8) =< 1 39.38/13.02 aux(10) =< V1-V+1 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(36) =< V1 39.38/13.02 aux(37) =< V1+V 39.38/13.02 aux(38) =< V1/2+V/2 39.38/13.02 aux(39) =< V 39.38/13.02 it(27) =< aux(38) 39.38/13.02 it(27) =< aux(37) 39.38/13.02 it(28) =< aux(37) 39.38/13.02 it(28) =< aux(38) 39.38/13.02 it(27) =< aux(39) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(39)+aux(36) 39.38/13.02 s(22) =< aux(39)+aux(36) 39.38/13.02 s(22) =< it(28)*aux(39) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(37) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=2,V>=2,V+V1>=5] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,[31],38]: 4*it(27)+4*it(28)+4*it(31)+3*s(19)+3*s(21)+5 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(40) =< V1 39.38/13.02 aux(41) =< V1+V 39.38/13.02 aux(42) =< V 39.38/13.02 it(31) =< aux(42) 39.38/13.02 it(27) =< aux(41) 39.38/13.02 it(28) =< aux(41) 39.38/13.02 it(27) =< aux(42) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(42)+aux(40) 39.38/13.02 s(22) =< aux(42)+aux(40) 39.38/13.02 s(22) =< it(28)*aux(42) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(41) 39.38/13.02 39.38/13.02 with precondition: [Out=1,V1>=2,V>=2,V+V1>=5] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,[31],37]: 4*it(27)+4*it(28)+6*it(31)+1*s(8)+3*s(19)+3*s(21)+6 39.38/13.02 Such that:s(8) =< 1 39.38/13.02 aux(10) =< V1-V+1 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(43) =< V1 39.38/13.02 aux(44) =< V1+V 39.38/13.02 aux(45) =< V 39.38/13.02 aux(46) =< 2*V 39.38/13.02 it(31) =< aux(46) 39.38/13.02 it(27) =< aux(44) 39.38/13.02 it(28) =< aux(44) 39.38/13.02 it(27) =< aux(45) 39.38/13.02 it(28) =< aux(46)+aux(10) 39.38/13.02 it(28) =< aux(45)+aux(43) 39.38/13.02 s(22) =< aux(45)+aux(43) 39.38/13.02 s(22) =< it(28)*aux(45) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(44) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=2,V>=2,V+V1>=5] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,[31],35]: 4*it(27)+4*it(28)+4*it(31)+3*s(19)+3*s(21)+6 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(47) =< V1 39.38/13.02 aux(48) =< V1+V 39.38/13.02 aux(49) =< V 39.38/13.02 it(31) =< aux(49) 39.38/13.02 it(27) =< aux(48) 39.38/13.02 it(28) =< aux(48) 39.38/13.02 it(27) =< aux(49) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(49)+aux(47) 39.38/13.02 s(22) =< aux(49)+aux(47) 39.38/13.02 s(22) =< it(28)*aux(49) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(48) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=3,V>=3,V+V1>=7] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,[31],32,38]: 4*it(27)+4*it(28)+4*it(31)+3*s(19)+3*s(21)+9 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(50) =< V1 39.38/13.02 aux(51) =< V1+V 39.38/13.02 aux(52) =< V 39.38/13.02 it(31) =< aux(52) 39.38/13.02 it(27) =< aux(51) 39.38/13.02 it(28) =< aux(51) 39.38/13.02 it(27) =< aux(52) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(52)+aux(50) 39.38/13.02 s(22) =< aux(52)+aux(50) 39.38/13.02 s(22) =< it(28)*aux(52) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(51) 39.38/13.02 39.38/13.02 with precondition: [Out=1,V1>=3,V>=3,V+V1>=7] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,[31],32,37]: 4*it(27)+4*it(28)+4*it(31)+1*s(8)+3*s(19)+3*s(21)+10 39.38/13.02 Such that:s(8) =< 1 39.38/13.02 aux(10) =< V1-V+1 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(53) =< V1 39.38/13.02 aux(54) =< V1+V 39.38/13.02 aux(55) =< V 39.38/13.02 it(31) =< aux(55) 39.38/13.02 it(27) =< aux(54) 39.38/13.02 it(28) =< aux(54) 39.38/13.02 it(27) =< aux(55) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(55)+aux(53) 39.38/13.02 s(22) =< aux(55)+aux(53) 39.38/13.02 s(22) =< it(28)*aux(55) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(54) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=3,V>=3,V+V1>=7] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,37]: 4*it(27)+4*it(28)+2*s(6)+1*s(8)+3*s(19)+3*s(21)+6 39.38/13.02 Such that:s(8) =< 1 39.38/13.02 aux(10) =< V1-V+1 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(56) =< V1 39.38/13.02 aux(57) =< V1+V 39.38/13.02 aux(58) =< V 39.38/13.02 aux(59) =< 2*V 39.38/13.02 s(6) =< aux(59) 39.38/13.02 it(27) =< aux(57) 39.38/13.02 it(28) =< aux(57) 39.38/13.02 it(27) =< aux(58) 39.38/13.02 it(28) =< aux(59)+aux(10) 39.38/13.02 it(28) =< aux(58)+aux(56) 39.38/13.02 s(22) =< aux(58)+aux(56) 39.38/13.02 s(22) =< it(28)*aux(58) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(57) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=2,V>=2,V+V1>=5] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,35]: 4*it(27)+4*it(28)+3*s(19)+3*s(21)+6 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(60) =< V1 39.38/13.02 aux(61) =< V1+V 39.38/13.02 aux(62) =< V1/2+V/2 39.38/13.02 aux(63) =< V 39.38/13.02 it(27) =< aux(62) 39.38/13.02 it(27) =< aux(61) 39.38/13.02 it(28) =< aux(61) 39.38/13.02 it(28) =< aux(62) 39.38/13.02 it(27) =< aux(63) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(63)+aux(60) 39.38/13.02 s(22) =< aux(63)+aux(60) 39.38/13.02 s(22) =< it(28)*aux(63) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(61) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=2,V>=2,V+V1>=5] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,32,38]: 4*it(27)+4*it(28)+3*s(19)+3*s(21)+9 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(64) =< V1 39.38/13.02 aux(65) =< V1+V 39.38/13.02 aux(66) =< V1/2+V/2 39.38/13.02 aux(67) =< V 39.38/13.02 it(27) =< aux(66) 39.38/13.02 it(27) =< aux(65) 39.38/13.02 it(28) =< aux(65) 39.38/13.02 it(28) =< aux(66) 39.38/13.02 it(27) =< aux(67) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(67)+aux(64) 39.38/13.02 s(22) =< aux(67)+aux(64) 39.38/13.02 s(22) =< it(28)*aux(67) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(65) 39.38/13.02 39.38/13.02 with precondition: [Out=1,V1>=2,V>=2,V+V1>=5] 39.38/13.02 39.38/13.02 * Chain [[27,28],33,32,37]: 4*it(27)+4*it(28)+1*s(8)+3*s(19)+3*s(21)+10 39.38/13.02 Such that:s(8) =< 1 39.38/13.02 aux(10) =< V1-V+1 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(68) =< V1 39.38/13.02 aux(69) =< V1+V 39.38/13.02 aux(70) =< V1/2+V/2 39.38/13.02 aux(71) =< V 39.38/13.02 it(27) =< aux(70) 39.38/13.02 it(27) =< aux(69) 39.38/13.02 it(28) =< aux(69) 39.38/13.02 it(28) =< aux(70) 39.38/13.02 it(27) =< aux(71) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(71)+aux(68) 39.38/13.02 s(22) =< aux(71)+aux(68) 39.38/13.02 s(22) =< it(28)*aux(71) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(69) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=2,V>=2,V+V1>=5] 39.38/13.02 39.38/13.02 * Chain [[27,28],30,38]: 4*it(27)+4*it(28)+3*s(19)+3*s(21)+6*s(25)+5 39.38/13.02 Such that:aux(21) =< V1 39.38/13.02 aux(10) =< V1-V+1 39.38/13.02 aux(22) =< V1+V 39.38/13.02 aux(23) =< V1+V-2*Out 39.38/13.02 aux(24) =< V1-Out 39.38/13.02 it(27) =< V1/2+V/2 39.38/13.02 aux(25) =< V1/2+V/2-Out 39.38/13.02 aux(26) =< V 39.38/13.02 aux(27) =< V-Out 39.38/13.02 aux(9) =< 2*V-2*Out 39.38/13.02 aux(72) =< Out 39.38/13.02 s(25) =< aux(72) 39.38/13.02 it(27) =< aux(22) 39.38/13.02 it(28) =< aux(22) 39.38/13.02 s(20) =< aux(22) 39.38/13.02 it(27) =< aux(23) 39.38/13.02 it(28) =< aux(23) 39.38/13.02 s(20) =< aux(23) 39.38/13.02 it(27) =< aux(25) 39.38/13.02 it(28) =< aux(25) 39.38/13.02 aux(7) =< aux(26) 39.38/13.02 it(27) =< aux(26) 39.38/13.02 aux(7) =< aux(27) 39.38/13.02 it(27) =< aux(27) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(7)+aux(21) 39.38/13.02 s(22) =< aux(7)+aux(24) 39.38/13.02 s(22) =< aux(7)+aux(21) 39.38/13.02 it(28) =< aux(7)+aux(24) 39.38/13.02 s(22) =< it(28)*aux(26) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< s(20) 39.38/13.02 39.38/13.02 with precondition: [Out>=2,V1>=Out,V>=Out,V+V1>=3*Out] 39.38/13.02 39.38/13.02 * Chain [[27,28],30,37]: 4*it(27)+4*it(28)+7*s(8)+3*s(19)+3*s(21)+6 39.38/13.02 Such that:aux(10) =< V1-V+1 39.38/13.02 aux(9) =< 2*V 39.38/13.02 aux(74) =< V1 39.38/13.02 aux(75) =< V1+V 39.38/13.02 aux(76) =< V1/2+V/2 39.38/13.02 aux(77) =< V 39.38/13.02 it(27) =< aux(76) 39.38/13.02 s(8) =< aux(77) 39.38/13.02 it(27) =< aux(75) 39.38/13.02 it(28) =< aux(75) 39.38/13.02 it(28) =< aux(76) 39.38/13.02 it(27) =< aux(77) 39.38/13.02 it(28) =< aux(9)+aux(10) 39.38/13.02 it(28) =< aux(77)+aux(74) 39.38/13.02 s(22) =< aux(77)+aux(74) 39.38/13.02 s(22) =< it(28)*aux(77) 39.38/13.02 s(21) =< s(22) 39.38/13.02 s(19) =< aux(75) 39.38/13.02 39.38/13.02 with precondition: [Out=0,V1>=2,V>=2,V+V1>=6] 39.38/13.03 39.38/13.03 * Chain [[27,28],29,38]: 4*it(27)+4*it(28)+3*s(19)+3*s(21)+6*s(28)+5 39.38/13.03 Such that:aux(21) =< V1 39.38/13.03 aux(10) =< V1-V+1 39.38/13.03 aux(22) =< V1+V 39.38/13.03 aux(23) =< V1+V-2*Out 39.38/13.03 aux(24) =< V1-Out 39.38/13.03 it(27) =< V1/2+V/2 39.38/13.03 aux(25) =< V1/2+V/2-Out 39.38/13.03 aux(26) =< V 39.38/13.03 aux(27) =< V-Out 39.38/13.03 aux(9) =< 2*V-2*Out 39.38/13.03 aux(78) =< Out 39.38/13.03 s(28) =< aux(78) 39.38/13.03 it(27) =< aux(22) 39.38/13.03 it(28) =< aux(22) 39.38/13.03 s(20) =< aux(22) 39.38/13.03 it(27) =< aux(23) 39.38/13.03 it(28) =< aux(23) 39.38/13.03 s(20) =< aux(23) 39.38/13.03 it(27) =< aux(25) 39.38/13.03 it(28) =< aux(25) 39.38/13.03 aux(7) =< aux(26) 39.38/13.03 it(27) =< aux(26) 39.38/13.03 aux(7) =< aux(27) 39.38/13.03 it(27) =< aux(27) 39.38/13.03 it(28) =< aux(9)+aux(10) 39.38/13.03 it(28) =< aux(7)+aux(21) 39.38/13.03 s(22) =< aux(7)+aux(24) 39.38/13.03 s(22) =< aux(7)+aux(21) 39.38/13.03 it(28) =< aux(7)+aux(24) 39.38/13.03 s(22) =< it(28)*aux(26) 39.38/13.03 s(21) =< s(22) 39.38/13.03 s(19) =< s(20) 39.38/13.03 39.38/13.03 with precondition: [Out>=2,V1>=Out+1,V>=Out+1,V+V1>=3*Out+2] 39.38/13.03 39.38/13.03 * Chain [[27,28],29,37]: 4*it(27)+4*it(28)+7*s(8)+3*s(19)+3*s(21)+6 39.38/13.03 Such that:aux(10) =< V1-V+1 39.38/13.03 aux(9) =< 2*V 39.38/13.03 aux(80) =< V1 39.38/13.03 aux(81) =< V1+V 39.38/13.03 aux(82) =< V1/2+V/2 39.38/13.03 aux(83) =< V 39.38/13.03 it(27) =< aux(82) 39.38/13.03 s(8) =< aux(80) 39.38/13.03 it(27) =< aux(81) 39.38/13.03 it(28) =< aux(81) 39.38/13.03 it(28) =< aux(82) 39.38/13.03 it(27) =< aux(83) 39.38/13.03 it(28) =< aux(9)+aux(10) 39.38/13.03 it(28) =< aux(83)+aux(80) 39.38/13.03 s(22) =< aux(83)+aux(80) 39.38/13.03 s(22) =< it(28)*aux(83) 39.38/13.03 s(21) =< s(22) 39.38/13.03 s(19) =< aux(81) 39.38/13.03 39.38/13.03 with precondition: [Out=0,V1>=3,V>=3,V+V1>=8] 39.38/13.03 39.38/13.03 * Chain [38]: 1 39.38/13.03 with precondition: [V1=0,V=Out,V>=0] 39.38/13.03 39.38/13.03 * Chain [37]: 2*s(6)+1*s(8)+2 39.38/13.03 Such that:s(8) =< V 39.38/13.03 aux(3) =< V1 39.38/13.03 s(6) =< aux(3) 39.38/13.03 39.38/13.03 with precondition: [Out=0,V1>=0,V>=0] 39.38/13.03 39.38/13.03 * Chain [36]: 1 39.38/13.03 with precondition: [V=0,V1=Out,V1>=1] 39.38/13.03 39.38/13.03 * Chain [35]: 2 39.38/13.03 with precondition: [V=1,Out=0,V1>=1] 39.38/13.03 39.38/13.03 * Chain [34,38]: 5 39.38/13.03 with precondition: [V1=1,Out=1,V>=2] 39.38/13.03 39.38/13.03 * Chain [34,37]: 1*s(8)+6 39.38/13.03 Such that:s(8) =< 1 39.38/13.03 39.38/13.03 with precondition: [V1=1,Out=0,V>=2] 39.38/13.03 39.38/13.03 * Chain [33,[31],38]: 4*it(31)+5 39.38/13.03 Such that:it(31) =< V 39.38/13.03 39.38/13.03 with precondition: [V1=1,Out=1,V>=2] 39.38/13.03 39.38/13.03 * Chain [33,[31],37]: 6*it(31)+1*s(8)+6 39.38/13.03 Such that:s(8) =< 1 39.38/13.03 aux(4) =< V 39.38/13.03 it(31) =< aux(4) 39.38/13.03 39.38/13.03 with precondition: [V1=1,Out=0,V>=2] 39.38/13.03 39.38/13.03 * Chain [33,[31],35]: 4*it(31)+6 39.38/13.03 Such that:it(31) =< V 39.38/13.03 39.38/13.03 with precondition: [V1=1,Out=0,V>=3] 39.38/13.03 39.38/13.03 * Chain [33,[31],32,38]: 4*it(31)+9 39.38/13.03 Such that:it(31) =< V 39.38/13.03 39.38/13.03 with precondition: [V1=1,Out=1,V>=3] 39.38/13.03 39.38/13.03 * Chain [33,[31],32,37]: 4*it(31)+1*s(8)+10 39.38/13.03 Such that:s(8) =< 1 39.38/13.03 it(31) =< V 39.38/13.03 39.38/13.03 with precondition: [V1=1,Out=0,V>=3] 39.38/13.03 39.38/13.03 * Chain [33,37]: 2*s(6)+1*s(8)+6 39.38/13.03 Such that:s(8) =< 1 39.38/13.03 aux(3) =< V 39.38/13.03 s(6) =< aux(3) 39.38/13.03 39.38/13.03 with precondition: [V1=1,Out=0,V>=2] 39.38/13.03 39.38/13.03 * Chain [33,35]: 6 39.38/13.03 with precondition: [V1=1,Out=0,V>=2] 39.38/13.03 39.38/13.03 * Chain [33,32,38]: 9 39.38/13.03 with precondition: [V1=1,Out=1,V>=2] 39.38/13.03 39.38/13.03 * Chain [33,32,37]: 1*s(8)+10 39.38/13.03 Such that:s(8) =< 1 39.38/13.03 39.38/13.03 with precondition: [V1=1,Out=0,V>=2] 39.38/13.03 39.38/13.03 * Chain [32,38]: 5 39.38/13.03 with precondition: [V=1,Out=1,V1>=1] 39.38/13.03 39.38/13.03 * Chain [32,37]: 1*s(8)+6 39.38/13.03 Such that:s(8) =< 1 39.38/13.03 39.38/13.03 with precondition: [V=1,Out=0,V1>=1] 39.38/13.03 39.38/13.03 * Chain [30,38]: 6*s(25)+5 39.38/13.03 Such that:aux(72) =< Out 39.38/13.03 s(25) =< aux(72) 39.38/13.03 39.38/13.03 with precondition: [V=Out,V>=2,V1>=V] 39.38/13.03 39.38/13.03 * Chain [30,37]: 7*s(8)+6 39.38/13.03 Such that:aux(73) =< V 39.38/13.03 s(8) =< aux(73) 39.38/13.03 39.38/13.03 with precondition: [Out=0,V>=2,V1>=V] 39.38/13.03 39.38/13.03 * Chain [29,38]: 6*s(28)+5 39.38/13.03 Such that:aux(78) =< Out 39.38/13.03 s(28) =< aux(78) 39.38/13.03 39.38/13.03 with precondition: [V1=Out,V1>=2,V>=V1+1] 39.38/13.03 39.38/13.03 * Chain [29,37]: 7*s(8)+6 39.38/13.03 Such that:aux(79) =< V1 39.38/13.03 s(8) =< aux(79) 39.38/13.03 39.38/13.03 with precondition: [Out=0,V1>=2,V>=V1+1] 39.38/13.03 39.38/13.03 39.38/13.03 #### Cost of chains of start(V1,V,V15): 39.38/13.03 * Chain [47]: 62*s(273)+17*s(275)+10*s(286)+68*s(287)+36*s(289)+27*s(291)+72*s(292)+8*s(293)+32*s(294)+24*s(296)+10 39.38/13.03 Such that:s(279) =< 1 39.38/13.03 aux(116) =< V1 39.38/13.03 aux(117) =< V1-V+1 39.38/13.03 aux(118) =< V1+V 39.38/13.03 aux(119) =< V1/2+V/2 39.38/13.03 aux(120) =< V 39.38/13.03 aux(121) =< 2*V 39.38/13.03 s(275) =< aux(116) 39.38/13.03 s(273) =< aux(120) 39.38/13.03 s(286) =< s(279) 39.38/13.03 s(287) =< aux(119) 39.38/13.03 s(287) =< aux(118) 39.38/13.03 s(289) =< aux(118) 39.38/13.03 s(289) =< aux(119) 39.38/13.03 s(287) =< aux(120) 39.38/13.03 s(289) =< aux(121)+aux(117) 39.38/13.03 s(289) =< aux(120)+aux(116) 39.38/13.03 s(290) =< aux(120)+aux(116) 39.38/13.03 s(290) =< s(289)*aux(120) 39.38/13.03 s(291) =< s(290) 39.38/13.03 s(292) =< aux(118) 39.38/13.03 s(293) =< aux(121) 39.38/13.03 s(294) =< aux(118) 39.38/13.03 s(294) =< aux(121)+aux(117) 39.38/13.03 s(294) =< aux(120)+aux(116) 39.38/13.03 s(295) =< aux(120)+aux(116) 39.38/13.03 s(295) =< s(294)*aux(120) 39.38/13.03 s(296) =< s(295) 39.38/13.03 39.38/13.03 with precondition: [V1>=0] 39.38/13.03 39.38/13.03 * Chain [46]: 72*s(349)+40*s(350)+20*s(352)+15*s(354)+143*s(355)+8*s(356)+20*s(357)+15*s(359)+143*s(368)+40*s(379)+20*s(381)+15*s(383)+16*s(385)+20*s(386)+15*s(388)+68*s(399)+36*s(401)+27*s(403)+32*s(406)+24*s(408)+16*s(409)+12 39.38/13.03 Such that:s(348) =< 2 39.38/13.03 s(373) =< -V+1 39.38/13.03 s(375) =< V/2 39.38/13.03 aux(132) =< 1 39.38/13.03 aux(133) =< -2*V+V15+1 39.38/13.03 aux(134) =< -V+V15 39.38/13.03 aux(135) =< V 39.38/13.03 aux(136) =< 2*V 39.38/13.03 aux(137) =< V15 39.38/13.03 aux(138) =< V15/2 39.38/13.03 s(349) =< aux(132) 39.38/13.03 s(355) =< aux(137) 39.38/13.03 s(379) =< s(375) 39.38/13.03 s(368) =< aux(135) 39.38/13.03 s(379) =< aux(135) 39.38/13.03 s(381) =< aux(135) 39.38/13.03 s(381) =< s(375) 39.38/13.03 s(381) =< aux(136)+s(373) 39.38/13.03 s(382) =< aux(135) 39.38/13.03 s(382) =< s(381)*aux(135) 39.38/13.03 s(383) =< s(382) 39.38/13.03 s(385) =< aux(136) 39.38/13.03 s(386) =< aux(135) 39.38/13.03 s(386) =< aux(136)+s(373) 39.38/13.03 s(387) =< aux(135) 39.38/13.03 s(387) =< s(386)*aux(135) 39.38/13.03 s(388) =< s(387) 39.38/13.03 s(399) =< aux(138) 39.38/13.03 s(399) =< aux(137) 39.38/13.03 s(401) =< aux(137) 39.38/13.03 s(401) =< aux(138) 39.38/13.03 s(399) =< aux(135) 39.38/13.03 s(401) =< aux(136)+aux(133) 39.38/13.03 s(401) =< aux(135)+aux(134) 39.38/13.03 s(402) =< aux(135)+aux(134) 39.38/13.03 s(402) =< s(401)*aux(135) 39.38/13.03 s(403) =< s(402) 39.38/13.03 s(406) =< aux(137) 39.38/13.03 s(406) =< aux(136)+aux(133) 39.38/13.03 s(406) =< aux(135)+aux(134) 39.38/13.03 s(407) =< aux(135)+aux(134) 39.38/13.03 s(407) =< s(406)*aux(135) 39.38/13.03 s(408) =< s(407) 39.38/13.03 s(409) =< aux(134) 39.38/13.03 s(350) =< aux(138) 39.38/13.03 s(350) =< aux(137) 39.38/13.03 s(352) =< aux(137) 39.38/13.03 s(352) =< aux(138) 39.38/13.03 s(350) =< aux(132) 39.38/13.03 s(352) =< s(348)+aux(137) 39.38/13.03 s(352) =< aux(132)+aux(137) 39.38/13.03 s(353) =< aux(132)+aux(137) 39.38/13.03 s(353) =< s(352)*aux(132) 39.38/13.03 s(354) =< s(353) 39.38/13.03 s(356) =< s(348) 39.38/13.03 s(357) =< aux(137) 39.38/13.03 s(357) =< s(348)+aux(137) 39.38/13.03 s(357) =< aux(132)+aux(137) 39.38/13.03 s(358) =< aux(132)+aux(137) 39.38/13.03 s(358) =< s(357)*aux(132) 39.38/13.03 s(359) =< s(358) 39.38/13.03 39.38/13.03 with precondition: [V1=1,V>=1,V15>=1] 39.38/13.03 39.38/13.03 * Chain [45]: 10*s(457)+8*s(461)+11 39.38/13.03 Such that:s(460) =< V 39.38/13.03 aux(139) =< V15 39.38/13.03 s(461) =< s(460) 39.38/13.03 s(457) =< aux(139) 39.38/13.03 39.38/13.03 with precondition: [V1=1,V>=2] 39.38/13.03 39.38/13.03 * Chain [44]: 2*s(462)+3 39.38/13.03 Such that:s(462) =< V15 39.38/13.03 39.38/13.03 with precondition: [V1=1,V=V15,V>=2] 39.38/13.03 39.38/13.03 * Chain [43]: 72*s(470)+40*s(471)+20*s(473)+15*s(475)+143*s(476)+8*s(477)+20*s(478)+15*s(480)+143*s(489)+40*s(500)+20*s(502)+15*s(504)+16*s(506)+20*s(507)+15*s(509)+68*s(520)+36*s(522)+27*s(524)+32*s(527)+24*s(529)+16*s(530)+12 39.38/13.03 Such that:s(469) =< 2 39.38/13.03 s(494) =< -V15+1 39.38/13.03 s(496) =< V15/2 39.38/13.03 aux(150) =< 1 39.38/13.03 aux(151) =< V 39.38/13.03 aux(152) =< V-2*V15+1 39.38/13.03 aux(153) =< V-V15 39.38/13.03 aux(154) =< V/2 39.38/13.03 aux(155) =< V15 39.38/13.03 aux(156) =< 2*V15 39.38/13.03 s(470) =< aux(150) 39.38/13.03 s(476) =< aux(151) 39.38/13.03 s(500) =< s(496) 39.38/13.03 s(489) =< aux(155) 39.38/13.03 s(500) =< aux(155) 39.38/13.03 s(502) =< aux(155) 39.38/13.03 s(502) =< s(496) 39.38/13.03 s(502) =< aux(156)+s(494) 39.38/13.03 s(503) =< aux(155) 39.38/13.03 s(503) =< s(502)*aux(155) 39.38/13.03 s(504) =< s(503) 39.38/13.03 s(506) =< aux(156) 39.38/13.03 s(507) =< aux(155) 39.38/13.03 s(507) =< aux(156)+s(494) 39.38/13.03 s(508) =< aux(155) 39.38/13.03 s(508) =< s(507)*aux(155) 39.38/13.03 s(509) =< s(508) 39.38/13.03 s(520) =< aux(154) 39.38/13.03 s(520) =< aux(151) 39.38/13.03 s(522) =< aux(151) 39.38/13.03 s(522) =< aux(154) 39.38/13.03 s(520) =< aux(155) 39.38/13.03 s(522) =< aux(156)+aux(152) 39.38/13.03 s(522) =< aux(155)+aux(153) 39.38/13.03 s(523) =< aux(155)+aux(153) 39.38/13.03 s(523) =< s(522)*aux(155) 39.38/13.03 s(524) =< s(523) 39.38/13.03 s(527) =< aux(151) 39.38/13.03 s(527) =< aux(156)+aux(152) 39.38/13.03 s(527) =< aux(155)+aux(153) 39.38/13.03 s(528) =< aux(155)+aux(153) 39.38/13.03 s(528) =< s(527)*aux(155) 39.38/13.03 s(529) =< s(528) 39.38/13.03 s(530) =< aux(153) 39.38/13.03 s(471) =< aux(154) 39.38/13.03 s(471) =< aux(151) 39.38/13.03 s(473) =< aux(151) 39.38/13.03 s(473) =< aux(154) 39.38/13.03 s(471) =< aux(150) 39.38/13.03 s(473) =< s(469)+aux(151) 39.38/13.03 s(473) =< aux(150)+aux(151) 39.38/13.03 s(474) =< aux(150)+aux(151) 39.38/13.03 s(474) =< s(473)*aux(150) 39.38/13.03 s(475) =< s(474) 39.38/13.03 s(477) =< s(469) 39.38/13.03 s(478) =< aux(151) 39.38/13.03 s(478) =< s(469)+aux(151) 39.38/13.03 s(478) =< aux(150)+aux(151) 39.38/13.03 s(479) =< aux(150)+aux(151) 39.38/13.03 s(479) =< s(478)*aux(150) 39.38/13.03 s(480) =< s(479) 39.38/13.03 39.38/13.03 with precondition: [V1=2,V>=1,V15>=1] 39.38/13.03 39.38/13.03 * Chain [42]: 2*s(578)+3 39.38/13.03 Such that:s(578) =< V15 39.38/13.03 39.38/13.03 with precondition: [V1=2,V=V15,V>=2] 39.38/13.03 39.38/13.03 * Chain [41]: 10*s(579)+11 39.38/13.03 Such that:aux(157) =< V15 39.38/13.03 s(579) =< aux(157) 39.38/13.03 39.38/13.03 with precondition: [V1=2,V=V15+1,V>=3] 39.38/13.03 39.38/13.03 * Chain [40]: 1 39.38/13.03 with precondition: [V=0,V1>=0] 39.38/13.03 39.38/13.03 * Chain [39]: 3*s(584)+22*s(585)+6 39.38/13.03 Such that:s(582) =< 1 39.38/13.03 aux(158) =< V1 39.38/13.03 s(584) =< s(582) 39.38/13.03 s(585) =< aux(158) 39.38/13.03 39.38/13.03 with precondition: [V=1,V1>=1] 39.38/13.03 39.38/13.03 39.38/13.03 Closed-form bounds of start(V1,V,V15): 39.38/13.03 ------------------------------------- 39.38/13.03 * Chain [47] with precondition: [V1>=0] 39.38/13.03 - Upper bound: 68*V1+20+nat(V)*113+nat(2*V)*8+nat(V1+V)*140+nat(V1/2+V/2)*68 39.38/13.03 - Complexity: n 39.38/13.03 * Chain [46] with precondition: [V1=1,V>=1,V15>=1] 39.38/13.03 - Upper bound: 296*V+281*V15+170+nat(-V+V15)*67+20*V+34*V15 39.38/13.03 - Complexity: n 39.38/13.03 * Chain [45] with precondition: [V1=1,V>=2] 39.38/13.03 - Upper bound: 8*V+11+nat(V15)*10 39.38/13.03 - Complexity: n 39.38/13.03 * Chain [44] with precondition: [V1=1,V=V15,V>=2] 39.38/13.03 - Upper bound: 2*V15+3 39.38/13.03 - Complexity: n 39.38/13.03 * Chain [43] with precondition: [V1=2,V>=1,V15>=1] 39.38/13.03 - Upper bound: 281*V+296*V15+170+nat(V-V15)*67+34*V+20*V15 39.38/13.03 - Complexity: n 39.38/13.03 * Chain [42] with precondition: [V1=2,V=V15,V>=2] 39.38/13.03 - Upper bound: 2*V15+3 39.38/13.03 - Complexity: n 39.38/13.03 * Chain [41] with precondition: [V1=2,V=V15+1,V>=3] 39.38/13.03 - Upper bound: 10*V15+11 39.38/13.03 - Complexity: n 39.38/13.03 * Chain [40] with precondition: [V=0,V1>=0] 39.38/13.03 - Upper bound: 1 39.38/13.03 - Complexity: constant 39.38/13.03 * Chain [39] with precondition: [V=1,V1>=1] 39.38/13.03 - Upper bound: 22*V1+9 39.38/13.03 - Complexity: n 39.38/13.03 39.38/13.03 ### Maximum cost of start(V1,V,V15): max([46*V1+11+nat(V)*113+nat(2*V)*8+nat(V1+V)*140+nat(V1/2+V/2)*68+(22*V1+8),nat(V)*256+159+nat(V15)*254+nat(V/2)*40+nat(V15/2)*40+max([nat(2*V)*16+nat(V15)*17+nat(-V+V15)*67+nat(V15/2)*28,nat(2*V15)*16+nat(V)*17+nat(V-V15)*67+nat(V/2)*28])+nat(V)*8+(nat(V15)*8+8)+(nat(V15)*2+2)])+1 39.38/13.03 Asymptotic class: n 39.38/13.03 * Total analysis performed in 1298 ms. 39.38/13.03 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (10) 39.38/13.03 BOUNDS(1, n^1) 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 39.38/13.03 Renamed function symbols to avoid clashes with predefined symbol. 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (12) 39.38/13.03 Obligation: 39.38/13.03 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 39.38/13.03 39.38/13.03 39.38/13.03 The TRS R consists of the following rules: 39.38/13.03 39.38/13.03 le(0', y) -> true 39.38/13.03 le(s(x), 0') -> false 39.38/13.03 le(s(x), s(y)) -> le(x, y) 39.38/13.03 pred(s(x)) -> x 39.38/13.03 minus(x, 0') -> x 39.38/13.03 minus(x, s(y)) -> pred(minus(x, y)) 39.38/13.03 gcd(0', y) -> y 39.38/13.03 gcd(s(x), 0') -> s(x) 39.38/13.03 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) 39.38/13.03 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) 39.38/13.03 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) 39.38/13.03 39.38/13.03 S is empty. 39.38/13.03 Rewrite Strategy: INNERMOST 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (13) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 39.38/13.03 Infered types. 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (14) 39.38/13.03 Obligation: 39.38/13.03 Innermost TRS: 39.38/13.03 Rules: 39.38/13.03 le(0', y) -> true 39.38/13.03 le(s(x), 0') -> false 39.38/13.03 le(s(x), s(y)) -> le(x, y) 39.38/13.03 pred(s(x)) -> x 39.38/13.03 minus(x, 0') -> x 39.38/13.03 minus(x, s(y)) -> pred(minus(x, y)) 39.38/13.03 gcd(0', y) -> y 39.38/13.03 gcd(s(x), 0') -> s(x) 39.38/13.03 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) 39.38/13.03 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) 39.38/13.03 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) 39.38/13.03 39.38/13.03 Types: 39.38/13.03 le :: 0':s -> 0':s -> true:false 39.38/13.03 0' :: 0':s 39.38/13.03 true :: true:false 39.38/13.03 s :: 0':s -> 0':s 39.38/13.03 false :: true:false 39.38/13.03 pred :: 0':s -> 0':s 39.38/13.03 minus :: 0':s -> 0':s -> 0':s 39.38/13.03 gcd :: 0':s -> 0':s -> 0':s 39.38/13.03 if_gcd :: true:false -> 0':s -> 0':s -> 0':s 39.38/13.03 hole_true:false1_0 :: true:false 39.38/13.03 hole_0':s2_0 :: 0':s 39.38/13.03 gen_0':s3_0 :: Nat -> 0':s 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (15) OrderProof (LOWER BOUND(ID)) 39.38/13.03 Heuristically decided to analyse the following defined symbols: 39.38/13.03 le, minus, gcd 39.38/13.03 39.38/13.03 They will be analysed ascendingly in the following order: 39.38/13.03 le < gcd 39.38/13.03 minus < gcd 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (16) 39.38/13.03 Obligation: 39.38/13.03 Innermost TRS: 39.38/13.03 Rules: 39.38/13.03 le(0', y) -> true 39.38/13.03 le(s(x), 0') -> false 39.38/13.03 le(s(x), s(y)) -> le(x, y) 39.38/13.03 pred(s(x)) -> x 39.38/13.03 minus(x, 0') -> x 39.38/13.03 minus(x, s(y)) -> pred(minus(x, y)) 39.38/13.03 gcd(0', y) -> y 39.38/13.03 gcd(s(x), 0') -> s(x) 39.38/13.03 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) 39.38/13.03 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) 39.38/13.03 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) 39.38/13.03 39.38/13.03 Types: 39.38/13.03 le :: 0':s -> 0':s -> true:false 39.38/13.03 0' :: 0':s 39.38/13.03 true :: true:false 39.38/13.03 s :: 0':s -> 0':s 39.38/13.03 false :: true:false 39.38/13.03 pred :: 0':s -> 0':s 39.38/13.03 minus :: 0':s -> 0':s -> 0':s 39.38/13.03 gcd :: 0':s -> 0':s -> 0':s 39.38/13.03 if_gcd :: true:false -> 0':s -> 0':s -> 0':s 39.38/13.03 hole_true:false1_0 :: true:false 39.38/13.03 hole_0':s2_0 :: 0':s 39.38/13.03 gen_0':s3_0 :: Nat -> 0':s 39.38/13.03 39.38/13.03 39.38/13.03 Generator Equations: 39.38/13.03 gen_0':s3_0(0) <=> 0' 39.38/13.03 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 39.38/13.03 39.38/13.03 39.38/13.03 The following defined symbols remain to be analysed: 39.38/13.03 le, minus, gcd 39.38/13.03 39.38/13.03 They will be analysed ascendingly in the following order: 39.38/13.03 le < gcd 39.38/13.03 minus < gcd 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (17) RewriteLemmaProof (LOWER BOUND(ID)) 39.38/13.03 Proved the following rewrite lemma: 39.38/13.03 le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 39.38/13.03 39.38/13.03 Induction Base: 39.38/13.03 le(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 39.38/13.03 true 39.38/13.03 39.38/13.03 Induction Step: 39.38/13.03 le(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1) 39.38/13.03 le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) ->_IH 39.38/13.03 true 39.38/13.03 39.38/13.03 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (18) 39.38/13.03 Complex Obligation (BEST) 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (19) 39.38/13.03 Obligation: 39.38/13.03 Proved the lower bound n^1 for the following obligation: 39.38/13.03 39.38/13.03 Innermost TRS: 39.38/13.03 Rules: 39.38/13.03 le(0', y) -> true 39.38/13.03 le(s(x), 0') -> false 39.38/13.03 le(s(x), s(y)) -> le(x, y) 39.38/13.03 pred(s(x)) -> x 39.38/13.03 minus(x, 0') -> x 39.38/13.03 minus(x, s(y)) -> pred(minus(x, y)) 39.38/13.03 gcd(0', y) -> y 39.38/13.03 gcd(s(x), 0') -> s(x) 39.38/13.03 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) 39.38/13.03 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) 39.38/13.03 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) 39.38/13.03 39.38/13.03 Types: 39.38/13.03 le :: 0':s -> 0':s -> true:false 39.38/13.03 0' :: 0':s 39.38/13.03 true :: true:false 39.38/13.03 s :: 0':s -> 0':s 39.38/13.03 false :: true:false 39.38/13.03 pred :: 0':s -> 0':s 39.38/13.03 minus :: 0':s -> 0':s -> 0':s 39.38/13.03 gcd :: 0':s -> 0':s -> 0':s 39.38/13.03 if_gcd :: true:false -> 0':s -> 0':s -> 0':s 39.38/13.03 hole_true:false1_0 :: true:false 39.38/13.03 hole_0':s2_0 :: 0':s 39.38/13.03 gen_0':s3_0 :: Nat -> 0':s 39.38/13.03 39.38/13.03 39.38/13.03 Generator Equations: 39.38/13.03 gen_0':s3_0(0) <=> 0' 39.38/13.03 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 39.38/13.03 39.38/13.03 39.38/13.03 The following defined symbols remain to be analysed: 39.38/13.03 le, minus, gcd 39.38/13.03 39.38/13.03 They will be analysed ascendingly in the following order: 39.38/13.03 le < gcd 39.38/13.03 minus < gcd 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (20) LowerBoundPropagationProof (FINISHED) 39.38/13.03 Propagated lower bound. 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (21) 39.38/13.03 BOUNDS(n^1, INF) 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (22) 39.38/13.03 Obligation: 39.38/13.03 Innermost TRS: 39.38/13.03 Rules: 39.38/13.03 le(0', y) -> true 39.38/13.03 le(s(x), 0') -> false 39.38/13.03 le(s(x), s(y)) -> le(x, y) 39.38/13.03 pred(s(x)) -> x 39.38/13.03 minus(x, 0') -> x 39.38/13.03 minus(x, s(y)) -> pred(minus(x, y)) 39.38/13.03 gcd(0', y) -> y 39.38/13.03 gcd(s(x), 0') -> s(x) 39.38/13.03 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) 39.38/13.03 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) 39.38/13.03 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) 39.38/13.03 39.38/13.03 Types: 39.38/13.03 le :: 0':s -> 0':s -> true:false 39.38/13.03 0' :: 0':s 39.38/13.03 true :: true:false 39.38/13.03 s :: 0':s -> 0':s 39.38/13.03 false :: true:false 39.38/13.03 pred :: 0':s -> 0':s 39.38/13.03 minus :: 0':s -> 0':s -> 0':s 39.38/13.03 gcd :: 0':s -> 0':s -> 0':s 39.38/13.03 if_gcd :: true:false -> 0':s -> 0':s -> 0':s 39.38/13.03 hole_true:false1_0 :: true:false 39.38/13.03 hole_0':s2_0 :: 0':s 39.38/13.03 gen_0':s3_0 :: Nat -> 0':s 39.38/13.03 39.38/13.03 39.38/13.03 Lemmas: 39.38/13.03 le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 39.38/13.03 39.38/13.03 39.38/13.03 Generator Equations: 39.38/13.03 gen_0':s3_0(0) <=> 0' 39.38/13.03 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 39.38/13.03 39.38/13.03 39.38/13.03 The following defined symbols remain to be analysed: 39.38/13.03 minus, gcd 39.38/13.03 39.38/13.03 They will be analysed ascendingly in the following order: 39.38/13.03 minus < gcd 39.38/13.03 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (23) RewriteLemmaProof (LOWER BOUND(ID)) 39.38/13.03 Proved the following rewrite lemma: 39.38/13.03 minus(gen_0':s3_0(a), gen_0':s3_0(+(1, n306_0))) -> *4_0, rt in Omega(n306_0) 39.38/13.03 39.38/13.03 Induction Base: 39.38/13.03 minus(gen_0':s3_0(a), gen_0':s3_0(+(1, 0))) 39.38/13.03 39.38/13.03 Induction Step: 39.38/13.03 minus(gen_0':s3_0(a), gen_0':s3_0(+(1, +(n306_0, 1)))) ->_R^Omega(1) 39.38/13.03 pred(minus(gen_0':s3_0(a), gen_0':s3_0(+(1, n306_0)))) ->_IH 39.38/13.03 pred(*4_0) 39.38/13.03 39.38/13.03 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 39.38/13.03 ---------------------------------------- 39.38/13.03 39.38/13.03 (24) 39.38/13.03 Obligation: 39.38/13.03 Innermost TRS: 39.38/13.03 Rules: 39.38/13.03 le(0', y) -> true 39.38/13.03 le(s(x), 0') -> false 39.38/13.03 le(s(x), s(y)) -> le(x, y) 39.38/13.03 pred(s(x)) -> x 39.38/13.03 minus(x, 0') -> x 39.38/13.03 minus(x, s(y)) -> pred(minus(x, y)) 39.38/13.03 gcd(0', y) -> y 39.38/13.03 gcd(s(x), 0') -> s(x) 39.38/13.03 gcd(s(x), s(y)) -> if_gcd(le(y, x), s(x), s(y)) 39.38/13.03 if_gcd(true, s(x), s(y)) -> gcd(minus(x, y), s(y)) 39.38/13.03 if_gcd(false, s(x), s(y)) -> gcd(minus(y, x), s(x)) 39.38/13.03 39.38/13.03 Types: 39.38/13.03 le :: 0':s -> 0':s -> true:false 39.38/13.03 0' :: 0':s 39.38/13.03 true :: true:false 39.38/13.03 s :: 0':s -> 0':s 39.38/13.03 false :: true:false 39.38/13.03 pred :: 0':s -> 0':s 39.38/13.03 minus :: 0':s -> 0':s -> 0':s 39.38/13.03 gcd :: 0':s -> 0':s -> 0':s 39.38/13.03 if_gcd :: true:false -> 0':s -> 0':s -> 0':s 39.38/13.03 hole_true:false1_0 :: true:false 39.38/13.03 hole_0':s2_0 :: 0':s 39.38/13.03 gen_0':s3_0 :: Nat -> 0':s 39.38/13.03 39.38/13.03 39.38/13.03 Lemmas: 39.38/13.03 le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 39.38/13.03 minus(gen_0':s3_0(a), gen_0':s3_0(+(1, n306_0))) -> *4_0, rt in Omega(n306_0) 39.38/13.03 39.38/13.03 39.38/13.03 Generator Equations: 39.38/13.03 gen_0':s3_0(0) <=> 0' 39.38/13.03 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 39.38/13.03 39.38/13.03 39.38/13.03 The following defined symbols remain to be analysed: 39.38/13.03 gcd 39.45/13.08 EOF