1143.61/291.60 WORST_CASE(Omega(n^1), O(n^3)) 1143.61/291.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1143.61/291.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1143.61/291.61 1143.61/291.61 1143.61/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 1143.61/291.61 1143.61/291.61 (0) CpxTRS 1143.61/291.61 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1143.61/291.61 (2) CpxWeightedTrs 1143.61/291.61 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1143.61/291.61 (4) CpxTypedWeightedTrs 1143.61/291.61 (5) CompletionProof [UPPER BOUND(ID), 3 ms] 1143.61/291.61 (6) CpxTypedWeightedCompleteTrs 1143.61/291.61 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1143.61/291.61 (8) CpxRNTS 1143.61/291.61 (9) CompleteCoflocoProof [FINISHED, 1517 ms] 1143.61/291.61 (10) BOUNDS(1, n^3) 1143.61/291.61 (11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1143.61/291.61 (12) TRS for Loop Detection 1143.61/291.61 (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1143.61/291.61 (14) BEST 1143.61/291.61 (15) proven lower bound 1143.61/291.61 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1143.61/291.61 (17) BOUNDS(n^1, INF) 1143.61/291.61 (18) TRS for Loop Detection 1143.61/291.61 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (0) 1143.61/291.61 Obligation: 1143.61/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 1143.61/291.61 1143.61/291.61 1143.61/291.61 The TRS R consists of the following rules: 1143.61/291.61 1143.61/291.61 minus(s(x), y) -> if(gt(s(x), y), x, y) 1143.61/291.61 if(true, x, y) -> s(minus(x, y)) 1143.61/291.61 if(false, x, y) -> 0 1143.61/291.61 gcd(x, y) -> if1(ge(x, y), x, y) 1143.61/291.61 if1(true, x, y) -> if2(gt(y, 0), x, y) 1143.61/291.61 if1(false, x, y) -> if3(gt(x, 0), x, y) 1143.61/291.61 if2(true, x, y) -> gcd(minus(x, y), y) 1143.61/291.61 if2(false, x, y) -> x 1143.61/291.61 if3(true, x, y) -> gcd(x, minus(y, x)) 1143.61/291.61 if3(false, x, y) -> y 1143.61/291.61 gt(0, y) -> false 1143.61/291.61 gt(s(x), 0) -> true 1143.61/291.61 gt(s(x), s(y)) -> gt(x, y) 1143.61/291.61 ge(x, 0) -> true 1143.61/291.61 ge(0, s(x)) -> false 1143.61/291.61 ge(s(x), s(y)) -> ge(x, y) 1143.61/291.61 1143.61/291.61 S is empty. 1143.61/291.61 Rewrite Strategy: INNERMOST 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1143.61/291.61 Transformed relative TRS to weighted TRS 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (2) 1143.61/291.61 Obligation: 1143.61/291.61 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3). 1143.61/291.61 1143.61/291.61 1143.61/291.61 The TRS R consists of the following rules: 1143.61/291.61 1143.61/291.61 minus(s(x), y) -> if(gt(s(x), y), x, y) [1] 1143.61/291.61 if(true, x, y) -> s(minus(x, y)) [1] 1143.61/291.61 if(false, x, y) -> 0 [1] 1143.61/291.61 gcd(x, y) -> if1(ge(x, y), x, y) [1] 1143.61/291.61 if1(true, x, y) -> if2(gt(y, 0), x, y) [1] 1143.61/291.61 if1(false, x, y) -> if3(gt(x, 0), x, y) [1] 1143.61/291.61 if2(true, x, y) -> gcd(minus(x, y), y) [1] 1143.61/291.61 if2(false, x, y) -> x [1] 1143.61/291.61 if3(true, x, y) -> gcd(x, minus(y, x)) [1] 1143.61/291.61 if3(false, x, y) -> y [1] 1143.61/291.61 gt(0, y) -> false [1] 1143.61/291.61 gt(s(x), 0) -> true [1] 1143.61/291.61 gt(s(x), s(y)) -> gt(x, y) [1] 1143.61/291.61 ge(x, 0) -> true [1] 1143.61/291.61 ge(0, s(x)) -> false [1] 1143.61/291.61 ge(s(x), s(y)) -> ge(x, y) [1] 1143.61/291.61 1143.61/291.61 Rewrite Strategy: INNERMOST 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1143.61/291.61 Infered types. 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (4) 1143.61/291.61 Obligation: 1143.61/291.61 Runtime Complexity Weighted TRS with Types. 1143.61/291.61 The TRS R consists of the following rules: 1143.61/291.61 1143.61/291.61 minus(s(x), y) -> if(gt(s(x), y), x, y) [1] 1143.61/291.61 if(true, x, y) -> s(minus(x, y)) [1] 1143.61/291.61 if(false, x, y) -> 0 [1] 1143.61/291.61 gcd(x, y) -> if1(ge(x, y), x, y) [1] 1143.61/291.61 if1(true, x, y) -> if2(gt(y, 0), x, y) [1] 1143.61/291.61 if1(false, x, y) -> if3(gt(x, 0), x, y) [1] 1143.61/291.61 if2(true, x, y) -> gcd(minus(x, y), y) [1] 1143.61/291.61 if2(false, x, y) -> x [1] 1143.61/291.61 if3(true, x, y) -> gcd(x, minus(y, x)) [1] 1143.61/291.61 if3(false, x, y) -> y [1] 1143.61/291.61 gt(0, y) -> false [1] 1143.61/291.61 gt(s(x), 0) -> true [1] 1143.61/291.61 gt(s(x), s(y)) -> gt(x, y) [1] 1143.61/291.61 ge(x, 0) -> true [1] 1143.61/291.61 ge(0, s(x)) -> false [1] 1143.61/291.61 ge(s(x), s(y)) -> ge(x, y) [1] 1143.61/291.61 1143.61/291.61 The TRS has the following type information: 1143.61/291.61 minus :: s:0 -> s:0 -> s:0 1143.61/291.61 s :: s:0 -> s:0 1143.61/291.61 if :: true:false -> s:0 -> s:0 -> s:0 1143.61/291.61 gt :: s:0 -> s:0 -> true:false 1143.61/291.61 true :: true:false 1143.61/291.61 false :: true:false 1143.61/291.61 0 :: s:0 1143.61/291.61 gcd :: s:0 -> s:0 -> s:0 1143.61/291.61 if1 :: true:false -> s:0 -> s:0 -> s:0 1143.61/291.61 ge :: s:0 -> s:0 -> true:false 1143.61/291.61 if2 :: true:false -> s:0 -> s:0 -> s:0 1143.61/291.61 if3 :: true:false -> s:0 -> s:0 -> s:0 1143.61/291.61 1143.61/291.61 Rewrite Strategy: INNERMOST 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (5) CompletionProof (UPPER BOUND(ID)) 1143.61/291.61 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 1143.61/291.61 1143.61/291.61 minus(v0, v1) -> null_minus [0] 1143.61/291.61 gt(v0, v1) -> null_gt [0] 1143.61/291.61 ge(v0, v1) -> null_ge [0] 1143.61/291.61 if(v0, v1, v2) -> null_if [0] 1143.61/291.61 if1(v0, v1, v2) -> null_if1 [0] 1143.61/291.61 if2(v0, v1, v2) -> null_if2 [0] 1143.61/291.61 if3(v0, v1, v2) -> null_if3 [0] 1143.61/291.61 1143.61/291.61 And the following fresh constants: null_minus, null_gt, null_ge, null_if, null_if1, null_if2, null_if3 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (6) 1143.61/291.61 Obligation: 1143.61/291.61 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 1143.61/291.61 1143.61/291.61 Runtime Complexity Weighted TRS with Types. 1143.61/291.61 The TRS R consists of the following rules: 1143.61/291.61 1143.61/291.61 minus(s(x), y) -> if(gt(s(x), y), x, y) [1] 1143.61/291.61 if(true, x, y) -> s(minus(x, y)) [1] 1143.61/291.61 if(false, x, y) -> 0 [1] 1143.61/291.61 gcd(x, y) -> if1(ge(x, y), x, y) [1] 1143.61/291.61 if1(true, x, y) -> if2(gt(y, 0), x, y) [1] 1143.61/291.61 if1(false, x, y) -> if3(gt(x, 0), x, y) [1] 1143.61/291.61 if2(true, x, y) -> gcd(minus(x, y), y) [1] 1143.61/291.61 if2(false, x, y) -> x [1] 1143.61/291.61 if3(true, x, y) -> gcd(x, minus(y, x)) [1] 1143.61/291.61 if3(false, x, y) -> y [1] 1143.61/291.61 gt(0, y) -> false [1] 1143.61/291.61 gt(s(x), 0) -> true [1] 1143.61/291.61 gt(s(x), s(y)) -> gt(x, y) [1] 1143.61/291.61 ge(x, 0) -> true [1] 1143.61/291.61 ge(0, s(x)) -> false [1] 1143.61/291.61 ge(s(x), s(y)) -> ge(x, y) [1] 1143.61/291.61 minus(v0, v1) -> null_minus [0] 1143.61/291.61 gt(v0, v1) -> null_gt [0] 1143.61/291.61 ge(v0, v1) -> null_ge [0] 1143.61/291.61 if(v0, v1, v2) -> null_if [0] 1143.61/291.61 if1(v0, v1, v2) -> null_if1 [0] 1143.61/291.61 if2(v0, v1, v2) -> null_if2 [0] 1143.61/291.61 if3(v0, v1, v2) -> null_if3 [0] 1143.61/291.61 1143.61/291.61 The TRS has the following type information: 1143.61/291.61 minus :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 s :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 if :: true:false:null_gt:null_ge -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 gt :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> true:false:null_gt:null_ge 1143.61/291.61 true :: true:false:null_gt:null_ge 1143.61/291.61 false :: true:false:null_gt:null_ge 1143.61/291.61 0 :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 gcd :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 if1 :: true:false:null_gt:null_ge -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 ge :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> true:false:null_gt:null_ge 1143.61/291.61 if2 :: true:false:null_gt:null_ge -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 if3 :: true:false:null_gt:null_ge -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 -> s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 null_minus :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 null_gt :: true:false:null_gt:null_ge 1143.61/291.61 null_ge :: true:false:null_gt:null_ge 1143.61/291.61 null_if :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 null_if1 :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 null_if2 :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 null_if3 :: s:0:null_minus:null_if:null_if1:null_if2:null_if3 1143.61/291.61 1143.61/291.61 Rewrite Strategy: INNERMOST 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1143.61/291.61 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1143.61/291.61 The constant constructors are abstracted as follows: 1143.61/291.61 1143.61/291.61 true => 2 1143.61/291.61 false => 1 1143.61/291.61 0 => 0 1143.61/291.61 null_minus => 0 1143.61/291.61 null_gt => 0 1143.61/291.61 null_ge => 0 1143.61/291.61 null_if => 0 1143.61/291.61 null_if1 => 0 1143.61/291.61 null_if2 => 0 1143.61/291.61 null_if3 => 0 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (8) 1143.61/291.61 Obligation: 1143.61/291.61 Complexity RNTS consisting of the following rules: 1143.61/291.61 1143.61/291.61 gcd(z, z') -{ 1 }-> if1(ge(x, y), x, y) :|: x >= 0, y >= 0, z = x, z' = y 1143.61/291.61 ge(z, z') -{ 1 }-> ge(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1143.61/291.61 ge(z, z') -{ 1 }-> 2 :|: x >= 0, z = x, z' = 0 1143.61/291.61 ge(z, z') -{ 1 }-> 1 :|: z' = 1 + x, x >= 0, z = 0 1143.61/291.61 ge(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1143.61/291.61 gt(z, z') -{ 1 }-> gt(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1143.61/291.61 gt(z, z') -{ 1 }-> 2 :|: x >= 0, z = 1 + x, z' = 0 1143.61/291.61 gt(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y 1143.61/291.61 gt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1143.61/291.61 if(z, z', z'') -{ 1 }-> 0 :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 1143.61/291.61 if(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1143.61/291.61 if(z, z', z'') -{ 1 }-> 1 + minus(x, y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 1143.61/291.61 if1(z, z', z'') -{ 1 }-> if3(gt(x, 0), x, y) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 1143.61/291.61 if1(z, z', z'') -{ 1 }-> if2(gt(y, 0), x, y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 1143.61/291.61 if1(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1143.61/291.61 if2(z, z', z'') -{ 1 }-> x :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 1143.61/291.61 if2(z, z', z'') -{ 1 }-> gcd(minus(x, y), y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 1143.61/291.61 if2(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1143.61/291.61 if3(z, z', z'') -{ 1 }-> y :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 1143.61/291.61 if3(z, z', z'') -{ 1 }-> gcd(x, minus(y, x)) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 1143.61/291.61 if3(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 1143.61/291.61 minus(z, z') -{ 1 }-> if(gt(1 + x, y), x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 1143.61/291.61 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 1143.61/291.61 1143.61/291.61 Only complete derivations are relevant for the runtime complexity. 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (9) CompleteCoflocoProof (FINISHED) 1143.61/291.61 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 1143.61/291.61 1143.61/291.61 eq(start(V1, V, V5),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). 1143.61/291.61 eq(start(V1, V, V5),0,[if(V1, V, V5, Out)],[V1 >= 0,V >= 0,V5 >= 0]). 1143.61/291.61 eq(start(V1, V, V5),0,[gcd(V1, V, Out)],[V1 >= 0,V >= 0]). 1143.61/291.61 eq(start(V1, V, V5),0,[if1(V1, V, V5, Out)],[V1 >= 0,V >= 0,V5 >= 0]). 1143.61/291.61 eq(start(V1, V, V5),0,[if2(V1, V, V5, Out)],[V1 >= 0,V >= 0,V5 >= 0]). 1143.61/291.61 eq(start(V1, V, V5),0,[if3(V1, V, V5, Out)],[V1 >= 0,V >= 0,V5 >= 0]). 1143.61/291.61 eq(start(V1, V, V5),0,[gt(V1, V, Out)],[V1 >= 0,V >= 0]). 1143.61/291.61 eq(start(V1, V, V5),0,[ge(V1, V, Out)],[V1 >= 0,V >= 0]). 1143.61/291.61 eq(minus(V1, V, Out),1,[gt(1 + V3, V2, Ret0),if(Ret0, V3, V2, Ret)],[Out = Ret,V3 >= 0,V2 >= 0,V1 = 1 + V3,V = V2]). 1143.61/291.61 eq(if(V1, V, V5, Out),1,[minus(V4, V6, Ret1)],[Out = 1 + Ret1,V1 = 2,V = V4,V5 = V6,V4 >= 0,V6 >= 0]). 1143.61/291.61 eq(if(V1, V, V5, Out),1,[],[Out = 0,V = V8,V5 = V7,V1 = 1,V8 >= 0,V7 >= 0]). 1143.61/291.61 eq(gcd(V1, V, Out),1,[ge(V9, V10, Ret01),if1(Ret01, V9, V10, Ret2)],[Out = Ret2,V9 >= 0,V10 >= 0,V1 = V9,V = V10]). 1143.61/291.61 eq(if1(V1, V, V5, Out),1,[gt(V11, 0, Ret02),if2(Ret02, V12, V11, Ret3)],[Out = Ret3,V1 = 2,V = V12,V5 = V11,V12 >= 0,V11 >= 0]). 1143.61/291.61 eq(if1(V1, V, V5, Out),1,[gt(V14, 0, Ret03),if3(Ret03, V14, V13, Ret4)],[Out = Ret4,V = V14,V5 = V13,V1 = 1,V14 >= 0,V13 >= 0]). 1143.61/291.61 eq(if2(V1, V, V5, Out),1,[minus(V16, V15, Ret04),gcd(Ret04, V15, Ret5)],[Out = Ret5,V1 = 2,V = V16,V5 = V15,V16 >= 0,V15 >= 0]). 1143.61/291.61 eq(if2(V1, V, V5, Out),1,[],[Out = V17,V = V17,V5 = V18,V1 = 1,V17 >= 0,V18 >= 0]). 1143.61/291.61 eq(if3(V1, V, V5, Out),1,[minus(V19, V20, Ret11),gcd(V20, Ret11, Ret6)],[Out = Ret6,V1 = 2,V = V20,V5 = V19,V20 >= 0,V19 >= 0]). 1143.61/291.61 eq(if3(V1, V, V5, Out),1,[],[Out = V22,V = V21,V5 = V22,V1 = 1,V21 >= 0,V22 >= 0]). 1143.61/291.61 eq(gt(V1, V, Out),1,[],[Out = 1,V23 >= 0,V1 = 0,V = V23]). 1143.61/291.61 eq(gt(V1, V, Out),1,[],[Out = 2,V24 >= 0,V1 = 1 + V24,V = 0]). 1143.61/291.61 eq(gt(V1, V, Out),1,[gt(V26, V25, Ret7)],[Out = Ret7,V = 1 + V25,V26 >= 0,V25 >= 0,V1 = 1 + V26]). 1143.61/291.61 eq(ge(V1, V, Out),1,[],[Out = 2,V27 >= 0,V1 = V27,V = 0]). 1143.61/291.61 eq(ge(V1, V, Out),1,[],[Out = 1,V = 1 + V28,V28 >= 0,V1 = 0]). 1143.61/291.61 eq(ge(V1, V, Out),1,[ge(V30, V29, Ret8)],[Out = Ret8,V = 1 + V29,V30 >= 0,V29 >= 0,V1 = 1 + V30]). 1143.61/291.61 eq(minus(V1, V, Out),0,[],[Out = 0,V32 >= 0,V31 >= 0,V1 = V32,V = V31]). 1143.61/291.61 eq(gt(V1, V, Out),0,[],[Out = 0,V34 >= 0,V33 >= 0,V1 = V34,V = V33]). 1143.61/291.61 eq(ge(V1, V, Out),0,[],[Out = 0,V36 >= 0,V35 >= 0,V1 = V36,V = V35]). 1143.61/291.61 eq(if(V1, V, V5, Out),0,[],[Out = 0,V37 >= 0,V5 = V39,V38 >= 0,V1 = V37,V = V38,V39 >= 0]). 1143.61/291.61 eq(if1(V1, V, V5, Out),0,[],[Out = 0,V41 >= 0,V5 = V42,V40 >= 0,V1 = V41,V = V40,V42 >= 0]). 1143.61/291.61 eq(if2(V1, V, V5, Out),0,[],[Out = 0,V44 >= 0,V5 = V45,V43 >= 0,V1 = V44,V = V43,V45 >= 0]). 1143.61/291.61 eq(if3(V1, V, V5, Out),0,[],[Out = 0,V47 >= 0,V5 = V48,V46 >= 0,V1 = V47,V = V46,V48 >= 0]). 1143.61/291.61 input_output_vars(minus(V1,V,Out),[V1,V],[Out]). 1143.61/291.61 input_output_vars(if(V1,V,V5,Out),[V1,V,V5],[Out]). 1143.61/291.61 input_output_vars(gcd(V1,V,Out),[V1,V],[Out]). 1143.61/291.61 input_output_vars(if1(V1,V,V5,Out),[V1,V,V5],[Out]). 1143.61/291.61 input_output_vars(if2(V1,V,V5,Out),[V1,V,V5],[Out]). 1143.61/291.61 input_output_vars(if3(V1,V,V5,Out),[V1,V,V5],[Out]). 1143.61/291.61 input_output_vars(gt(V1,V,Out),[V1,V],[Out]). 1143.61/291.61 input_output_vars(ge(V1,V,Out),[V1,V],[Out]). 1143.61/291.61 1143.61/291.61 1143.61/291.61 CoFloCo proof output: 1143.61/291.61 Preprocessing Cost Relations 1143.61/291.61 ===================================== 1143.61/291.61 1143.61/291.61 #### Computed strongly connected components 1143.61/291.61 0. recursive : [ge/3] 1143.61/291.61 1. recursive : [gt/3] 1143.61/291.61 2. recursive : [if/4,minus/3] 1143.61/291.61 3. recursive : [gcd/3,if1/4,if2/4,if3/4] 1143.61/291.61 4. non_recursive : [start/3] 1143.61/291.61 1143.61/291.61 #### Obtained direct recursion through partial evaluation 1143.61/291.61 0. SCC is partially evaluated into ge/3 1143.61/291.61 1. SCC is partially evaluated into gt/3 1143.61/291.61 2. SCC is partially evaluated into minus/3 1143.61/291.61 3. SCC is partially evaluated into gcd/3 1143.61/291.61 4. SCC is partially evaluated into start/3 1143.61/291.61 1143.61/291.61 Control-Flow Refinement of Cost Relations 1143.61/291.61 ===================================== 1143.61/291.61 1143.61/291.61 ### Specialization of cost equations ge/3 1143.61/291.61 * CE 34 is refined into CE [35] 1143.61/291.61 * CE 31 is refined into CE [36] 1143.61/291.61 * CE 32 is refined into CE [37] 1143.61/291.61 * CE 33 is refined into CE [38] 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Cost equations --> "Loop" of ge/3 1143.61/291.61 * CEs [38] --> Loop 18 1143.61/291.61 * CEs [35] --> Loop 19 1143.61/291.61 * CEs [36] --> Loop 20 1143.61/291.61 * CEs [37] --> Loop 21 1143.61/291.61 1143.61/291.61 ### Ranking functions of CR ge(V1,V,Out) 1143.61/291.61 * RF of phase [18]: [V,V1] 1143.61/291.61 1143.61/291.61 #### Partial ranking functions of CR ge(V1,V,Out) 1143.61/291.61 * Partial RF of phase [18]: 1143.61/291.61 - RF of loop [18:1]: 1143.61/291.61 V 1143.61/291.61 V1 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Specialization of cost equations gt/3 1143.61/291.61 * CE 19 is refined into CE [39] 1143.61/291.61 * CE 17 is refined into CE [40] 1143.61/291.61 * CE 16 is refined into CE [41] 1143.61/291.61 * CE 18 is refined into CE [42] 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Cost equations --> "Loop" of gt/3 1143.61/291.61 * CEs [42] --> Loop 22 1143.61/291.61 * CEs [39] --> Loop 23 1143.61/291.61 * CEs [40] --> Loop 24 1143.61/291.61 * CEs [41] --> Loop 25 1143.61/291.61 1143.61/291.61 ### Ranking functions of CR gt(V1,V,Out) 1143.61/291.61 * RF of phase [22]: [V,V1] 1143.61/291.61 1143.61/291.61 #### Partial ranking functions of CR gt(V1,V,Out) 1143.61/291.61 * Partial RF of phase [22]: 1143.61/291.61 - RF of loop [22:1]: 1143.61/291.61 V 1143.61/291.61 V1 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Specialization of cost equations minus/3 1143.61/291.61 * CE 20 is refined into CE [43,44,45,46] 1143.61/291.61 * CE 21 is refined into CE [47] 1143.61/291.61 * CE 23 is refined into CE [48] 1143.61/291.61 * CE 22 is refined into CE [49,50] 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Cost equations --> "Loop" of minus/3 1143.61/291.61 * CEs [50] --> Loop 26 1143.61/291.61 * CEs [49] --> Loop 27 1143.61/291.61 * CEs [43,44,45,46,47,48] --> Loop 28 1143.61/291.61 1143.61/291.61 ### Ranking functions of CR minus(V1,V,Out) 1143.61/291.61 * RF of phase [26]: [V1-1,V1-V] 1143.61/291.61 * RF of phase [27]: [V1] 1143.61/291.61 1143.61/291.61 #### Partial ranking functions of CR minus(V1,V,Out) 1143.61/291.61 * Partial RF of phase [26]: 1143.61/291.61 - RF of loop [26:1]: 1143.61/291.61 V1-1 1143.61/291.61 V1-V 1143.61/291.61 * Partial RF of phase [27]: 1143.61/291.61 - RF of loop [27:1]: 1143.61/291.61 V1 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Specialization of cost equations gcd/3 1143.61/291.61 * CE 25 is refined into CE [51] 1143.61/291.61 * CE 28 is refined into CE [52] 1143.61/291.61 * CE 24 is refined into CE [53,54,55,56] 1143.61/291.61 * CE 27 is refined into CE [57,58,59,60] 1143.61/291.61 * CE 30 is refined into CE [61,62,63,64,65] 1143.61/291.61 * CE 29 is refined into CE [66,67] 1143.61/291.61 * CE 26 is refined into CE [68,69] 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Cost equations --> "Loop" of gcd/3 1143.61/291.61 * CEs [67] --> Loop 29 1143.61/291.61 * CEs [69] --> Loop 30 1143.61/291.61 * CEs [68] --> Loop 31 1143.61/291.61 * CEs [66] --> Loop 32 1143.61/291.61 * CEs [52] --> Loop 33 1143.61/291.61 * CEs [57,58,62] --> Loop 34 1143.61/291.61 * CEs [51] --> Loop 35 1143.61/291.61 * CEs [53,54,55,56,59,60,61,63,64,65] --> Loop 36 1143.61/291.61 1143.61/291.61 ### Ranking functions of CR gcd(V1,V,Out) 1143.61/291.61 * RF of phase [29,30]: [V1+V-2] 1143.61/291.61 1143.61/291.61 #### Partial ranking functions of CR gcd(V1,V,Out) 1143.61/291.61 * Partial RF of phase [29,30]: 1143.61/291.61 - RF of loop [29:1]: 1143.61/291.61 V1-1 1143.61/291.61 V1-V depends on loops [30:1] 1143.61/291.61 - RF of loop [30:1]: 1143.61/291.61 V-1 1143.61/291.61 -V1+V depends on loops [29:1] 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Specialization of cost equations start/3 1143.61/291.61 * CE 6 is refined into CE [70,71,72,73,74,75,76,77] 1143.61/291.61 * CE 7 is refined into CE [78,79,80] 1143.61/291.61 * CE 8 is refined into CE [81] 1143.61/291.61 * CE 9 is refined into CE [82,83,84,85,86,87] 1143.61/291.61 * CE 10 is refined into CE [88,89,90,91,92,93,94,95,96] 1143.61/291.61 * CE 11 is refined into CE [97,98,99] 1143.61/291.61 * CE 1 is refined into CE [100,101,102] 1143.61/291.61 * CE 2 is refined into CE [103] 1143.61/291.61 * CE 3 is refined into CE [104] 1143.61/291.61 * CE 4 is refined into CE [105] 1143.61/291.61 * CE 5 is refined into CE [106,107,108,109,110,111] 1143.61/291.61 * CE 12 is refined into CE [112,113,114] 1143.61/291.61 * CE 13 is refined into CE [115,116,117,118,119,120] 1143.61/291.61 * CE 14 is refined into CE [121,122,123,124,125] 1143.61/291.61 * CE 15 is refined into CE [126,127,128,129,130] 1143.61/291.61 1143.61/291.61 1143.61/291.61 ### Cost equations --> "Loop" of start/3 1143.61/291.61 * CEs [112,117,122,127] --> Loop 37 1143.61/291.61 * CEs [78,81,88,89,92,97] --> Loop 38 1143.61/291.61 * CEs [70,71,72,73,74,75,76,77,79,80,82,83,84,85,86,87,90,91,93,94,95,96,98,99] --> Loop 39 1143.61/291.61 * CEs [100,101,102,104,105,106,107,108,109,110,111] --> Loop 40 1143.61/291.61 * CEs [103,113,114,115,116,118,119,120,121,123,124,125,126,128,129,130] --> Loop 41 1143.61/291.61 1143.61/291.61 ### Ranking functions of CR start(V1,V,V5) 1143.61/291.61 1143.61/291.61 #### Partial ranking functions of CR start(V1,V,V5) 1143.61/291.61 1143.61/291.61 1143.61/291.61 Computing Bounds 1143.61/291.61 ===================================== 1143.61/291.61 1143.61/291.61 #### Cost of chains of ge(V1,V,Out): 1143.61/291.61 * Chain [[18],21]: 1*it(18)+1 1143.61/291.61 Such that:it(18) =< V1 1143.61/291.61 1143.61/291.61 with precondition: [Out=1,V1>=1,V>=V1+1] 1143.61/291.61 1143.61/291.61 * Chain [[18],20]: 1*it(18)+1 1143.61/291.61 Such that:it(18) =< V 1143.61/291.61 1143.61/291.61 with precondition: [Out=2,V>=1,V1>=V] 1143.61/291.61 1143.61/291.61 * Chain [[18],19]: 1*it(18)+0 1143.61/291.61 Such that:it(18) =< V 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=1,V>=1] 1143.61/291.61 1143.61/291.61 * Chain [21]: 1 1143.61/291.61 with precondition: [V1=0,Out=1,V>=1] 1143.61/291.61 1143.61/291.61 * Chain [20]: 1 1143.61/291.61 with precondition: [V=0,Out=2,V1>=0] 1143.61/291.61 1143.61/291.61 * Chain [19]: 0 1143.61/291.61 with precondition: [Out=0,V1>=0,V>=0] 1143.61/291.61 1143.61/291.61 1143.61/291.61 #### Cost of chains of gt(V1,V,Out): 1143.61/291.61 * Chain [[22],25]: 1*it(22)+1 1143.61/291.61 Such that:it(22) =< V1 1143.61/291.61 1143.61/291.61 with precondition: [Out=1,V1>=1,V>=V1] 1143.61/291.61 1143.61/291.61 * Chain [[22],24]: 1*it(22)+1 1143.61/291.61 Such that:it(22) =< V 1143.61/291.61 1143.61/291.61 with precondition: [Out=2,V>=1,V1>=V+1] 1143.61/291.61 1143.61/291.61 * Chain [[22],23]: 1*it(22)+0 1143.61/291.61 Such that:it(22) =< V 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=1,V>=1] 1143.61/291.61 1143.61/291.61 * Chain [25]: 1 1143.61/291.61 with precondition: [V1=0,Out=1,V>=0] 1143.61/291.61 1143.61/291.61 * Chain [24]: 1 1143.61/291.61 with precondition: [V=0,Out=2,V1>=1] 1143.61/291.61 1143.61/291.61 * Chain [23]: 0 1143.61/291.61 with precondition: [Out=0,V1>=0,V>=0] 1143.61/291.61 1143.61/291.61 1143.61/291.61 #### Cost of chains of minus(V1,V,Out): 1143.61/291.61 * Chain [[27],28]: 3*it(27)+2*s(4)+3 1143.61/291.61 Such that:aux(1) =< V1-Out 1143.61/291.61 it(27) =< Out 1143.61/291.61 s(4) =< aux(1) 1143.61/291.61 1143.61/291.61 with precondition: [V=0,Out>=1,V1>=Out] 1143.61/291.61 1143.61/291.61 * Chain [[26],28]: 3*it(26)+2*s(3)+2*s(4)+1*s(9)+3 1143.61/291.61 Such that:aux(1) =< V1-Out 1143.61/291.61 it(26) =< Out 1143.61/291.61 aux(4) =< V 1143.61/291.61 s(4) =< aux(1) 1143.61/291.61 s(3) =< aux(4) 1143.61/291.61 s(9) =< it(26)*aux(4) 1143.61/291.61 1143.61/291.61 with precondition: [V>=1,Out>=1,V1>=Out+V] 1143.61/291.61 1143.61/291.61 * Chain [28]: 2*s(3)+2*s(4)+3 1143.61/291.61 Such that:aux(1) =< V1 1143.61/291.61 aux(2) =< V 1143.61/291.61 s(4) =< aux(1) 1143.61/291.61 s(3) =< aux(2) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=0,V>=0] 1143.61/291.61 1143.61/291.61 1143.61/291.61 #### Cost of chains of gcd(V1,V,Out): 1143.61/291.61 * Chain [[29,30],36]: 8*it(29)+8*it(30)+7*s(11)+5*s(46)+3*s(47)+1*s(49)+3*s(52)+3*s(53)+2*s(54)+1*s(55)+4 1143.61/291.61 Such that:aux(13) =< -V1+V 1143.61/291.61 aux(10) =< V1-V 1143.61/291.61 aux(21) =< V1 1143.61/291.61 aux(22) =< V1+V 1143.61/291.61 aux(23) =< V 1143.61/291.61 s(11) =< aux(22) 1143.61/291.61 it(29) =< aux(21) 1143.61/291.61 it(29) =< aux(22) 1143.61/291.61 it(30) =< aux(22) 1143.61/291.61 s(57) =< aux(22) 1143.61/291.61 it(30) =< aux(23) 1143.61/291.61 s(57) =< aux(23) 1143.61/291.61 it(30) =< aux(22)+aux(13) 1143.61/291.61 it(29) =< aux(22)+aux(10) 1143.61/291.61 s(53) =< it(30)*aux(23) 1143.61/291.61 s(47) =< it(29)*aux(21) 1143.61/291.61 s(52) =< s(57) 1143.61/291.61 s(54) =< aux(23) 1143.61/291.61 s(55) =< s(53)*aux(21) 1143.61/291.61 s(46) =< aux(21) 1143.61/291.61 s(49) =< s(47)*aux(23) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=1,V>=1,V+V1>=3] 1143.61/291.61 1143.61/291.61 * Chain [[29,30],32,36]: 8*it(29)+8*it(30)+9*s(14)+5*s(46)+3*s(47)+1*s(49)+3*s(52)+3*s(53)+2*s(54)+1*s(55)+12 1143.61/291.61 Such that:aux(13) =< -V1+V 1143.61/291.61 aux(10) =< V1-V 1143.61/291.61 aux(26) =< V1 1143.61/291.61 aux(27) =< V1+V 1143.61/291.61 aux(28) =< V 1143.61/291.61 s(14) =< aux(27) 1143.61/291.61 it(29) =< aux(26) 1143.61/291.61 it(29) =< aux(27) 1143.61/291.61 it(30) =< aux(27) 1143.61/291.61 s(57) =< aux(27) 1143.61/291.61 it(30) =< aux(28) 1143.61/291.61 s(57) =< aux(28) 1143.61/291.61 it(30) =< aux(27)+aux(13) 1143.61/291.61 it(29) =< aux(27)+aux(10) 1143.61/291.61 s(53) =< it(30)*aux(28) 1143.61/291.61 s(47) =< it(29)*aux(26) 1143.61/291.61 s(52) =< s(57) 1143.61/291.61 s(54) =< aux(28) 1143.61/291.61 s(55) =< s(53)*aux(26) 1143.61/291.61 s(46) =< aux(26) 1143.61/291.61 s(49) =< s(47)*aux(28) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=1,V>=1,V+V1>=3] 1143.61/291.61 1143.61/291.61 * Chain [[29,30],32,35]: 8*it(29)+8*it(30)+7*s(46)+3*s(47)+1*s(49)+3*s(52)+3*s(53)+2*s(54)+1*s(55)+3*s(58)+13 1143.61/291.61 Such that:aux(13) =< -V1+V 1143.61/291.61 aux(10) =< V1-V 1143.61/291.61 aux(16) =< V1+V 1143.61/291.61 aux(17) =< V1+V-Out 1143.61/291.61 aux(19) =< V 1143.61/291.61 aux(20) =< V-Out 1143.61/291.61 aux(24) =< Out 1143.61/291.61 aux(29) =< V1 1143.61/291.61 s(58) =< aux(24) 1143.61/291.61 s(46) =< aux(29) 1143.61/291.61 it(29) =< aux(29) 1143.61/291.61 aux(9) =< aux(16) 1143.61/291.61 it(29) =< aux(16) 1143.61/291.61 it(30) =< aux(16) 1143.61/291.61 s(57) =< aux(16) 1143.61/291.61 aux(9) =< aux(17) 1143.61/291.61 it(29) =< aux(17) 1143.61/291.61 it(30) =< aux(17) 1143.61/291.61 s(57) =< aux(17) 1143.61/291.61 it(30) =< aux(19) 1143.61/291.61 s(56) =< aux(19) 1143.61/291.61 s(57) =< aux(19) 1143.61/291.61 it(30) =< aux(20) 1143.61/291.61 s(56) =< aux(20) 1143.61/291.61 s(57) =< aux(20) 1143.61/291.61 it(30) =< aux(9)+aux(13) 1143.61/291.61 it(29) =< aux(9)+aux(10) 1143.61/291.61 s(53) =< it(30)*aux(19) 1143.61/291.61 s(47) =< it(29)*aux(29) 1143.61/291.61 s(52) =< s(57) 1143.61/291.61 s(54) =< s(56) 1143.61/291.61 s(55) =< s(53)*aux(29) 1143.61/291.61 s(49) =< s(47)*aux(19) 1143.61/291.61 1143.61/291.61 with precondition: [Out>=1,V1>=Out,V>=Out,V+V1>=3*Out] 1143.61/291.61 1143.61/291.61 * Chain [[29,30],31,36]: 8*it(29)+8*it(30)+8*s(11)+5*s(46)+3*s(47)+1*s(49)+3*s(52)+3*s(53)+2*s(54)+1*s(55)+12 1143.61/291.61 Such that:aux(13) =< -V1+V 1143.61/291.61 aux(10) =< V1-V 1143.61/291.61 aux(32) =< V1 1143.61/291.61 aux(33) =< V1+V 1143.61/291.61 aux(34) =< V 1143.61/291.61 s(11) =< aux(33) 1143.61/291.61 it(29) =< aux(32) 1143.61/291.61 it(29) =< aux(33) 1143.61/291.61 it(30) =< aux(33) 1143.61/291.61 s(57) =< aux(33) 1143.61/291.61 it(30) =< aux(34) 1143.61/291.61 s(57) =< aux(34) 1143.61/291.61 it(30) =< aux(33)+aux(13) 1143.61/291.61 it(29) =< aux(33)+aux(10) 1143.61/291.61 s(53) =< it(30)*aux(34) 1143.61/291.61 s(47) =< it(29)*aux(32) 1143.61/291.61 s(52) =< s(57) 1143.61/291.61 s(54) =< aux(34) 1143.61/291.61 s(55) =< s(53)*aux(32) 1143.61/291.61 s(46) =< aux(32) 1143.61/291.61 s(49) =< s(47)*aux(34) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=1,V>=2,V1+2*V>=7] 1143.61/291.61 1143.61/291.61 * Chain [[29,30],31,34]: 8*it(29)+8*it(30)+5*s(46)+3*s(47)+1*s(49)+3*s(52)+3*s(53)+2*s(54)+1*s(55)+5*s(63)+12 1143.61/291.61 Such that:aux(13) =< -V1+V 1143.61/291.61 aux(10) =< V1-V 1143.61/291.61 aux(35) =< V1 1143.61/291.61 aux(36) =< V1+V 1143.61/291.61 aux(37) =< V 1143.61/291.61 s(63) =< aux(36) 1143.61/291.61 it(29) =< aux(35) 1143.61/291.61 it(29) =< aux(36) 1143.61/291.61 it(30) =< aux(36) 1143.61/291.61 s(57) =< aux(36) 1143.61/291.61 it(30) =< aux(37) 1143.61/291.61 s(57) =< aux(37) 1143.61/291.61 it(30) =< aux(36)+aux(13) 1143.61/291.61 it(29) =< aux(36)+aux(10) 1143.61/291.61 s(53) =< it(30)*aux(37) 1143.61/291.61 s(47) =< it(29)*aux(35) 1143.61/291.61 s(52) =< s(57) 1143.61/291.61 s(54) =< aux(37) 1143.61/291.61 s(55) =< s(53)*aux(35) 1143.61/291.61 s(46) =< aux(35) 1143.61/291.61 s(49) =< s(47)*aux(37) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=1,V>=2,V1+2*V>=7] 1143.61/291.61 1143.61/291.61 * Chain [[29,30],31,33]: 8*it(29)+8*it(30)+5*s(46)+3*s(47)+1*s(49)+3*s(52)+3*s(53)+4*s(54)+1*s(55)+3*s(63)+13 1143.61/291.61 Such that:aux(13) =< -V1+V 1143.61/291.61 aux(15) =< V1 1143.61/291.61 aux(10) =< V1-V 1143.61/291.61 aux(16) =< V1+V 1143.61/291.61 aux(17) =< V1+V-Out 1143.61/291.61 aux(18) =< V1-Out 1143.61/291.61 aux(30) =< Out 1143.61/291.61 aux(38) =< V 1143.61/291.61 s(63) =< aux(30) 1143.61/291.61 s(54) =< aux(38) 1143.61/291.61 it(29) =< aux(15) 1143.61/291.61 s(50) =< aux(15) 1143.61/291.61 aux(9) =< aux(16) 1143.61/291.61 it(29) =< aux(16) 1143.61/291.61 it(30) =< aux(16) 1143.61/291.61 s(57) =< aux(16) 1143.61/291.61 aux(9) =< aux(17) 1143.61/291.61 it(29) =< aux(17) 1143.61/291.61 it(30) =< aux(17) 1143.61/291.61 s(57) =< aux(17) 1143.61/291.61 it(29) =< aux(18) 1143.61/291.61 s(50) =< aux(18) 1143.61/291.61 it(30) =< aux(38) 1143.61/291.61 s(57) =< aux(38) 1143.61/291.61 it(30) =< aux(9)+aux(13) 1143.61/291.61 it(29) =< aux(9)+aux(10) 1143.61/291.61 s(53) =< it(30)*aux(38) 1143.61/291.61 s(47) =< it(29)*aux(15) 1143.61/291.61 s(52) =< s(57) 1143.61/291.61 s(55) =< s(53)*aux(15) 1143.61/291.61 s(46) =< s(50) 1143.61/291.61 s(49) =< s(47)*aux(38) 1143.61/291.61 1143.61/291.61 with precondition: [Out>=1,V1>=Out,V>=Out+1,V1+2*V>=4*Out+3,V+V1>=3*Out+1] 1143.61/291.61 1143.61/291.61 * Chain [36]: 3*s(11)+4*s(14)+4 1143.61/291.61 Such that:aux(5) =< V1 1143.61/291.61 aux(6) =< V 1143.61/291.61 s(11) =< aux(5) 1143.61/291.61 s(14) =< aux(6) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=0,V>=0] 1143.61/291.61 1143.61/291.61 * Chain [35]: 5 1143.61/291.61 with precondition: [V1=0,V=Out,V>=1] 1143.61/291.61 1143.61/291.61 * Chain [34]: 4 1143.61/291.61 with precondition: [V=0,Out=0,V1>=0] 1143.61/291.61 1143.61/291.61 * Chain [33]: 5 1143.61/291.61 with precondition: [V=0,V1=Out,V1>=0] 1143.61/291.61 1143.61/291.61 * Chain [32,36]: 7*s(14)+2*s(61)+12 1143.61/291.61 Such that:s(59) =< V1 1143.61/291.61 aux(25) =< V 1143.61/291.61 s(14) =< aux(25) 1143.61/291.61 s(61) =< s(59) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V>=1,V1>=V] 1143.61/291.61 1143.61/291.61 * Chain [32,35]: 3*s(58)+2*s(61)+13 1143.61/291.61 Such that:s(59) =< V1 1143.61/291.61 aux(24) =< Out 1143.61/291.61 s(58) =< aux(24) 1143.61/291.61 s(61) =< s(59) 1143.61/291.61 1143.61/291.61 with precondition: [V=Out,V>=1,V1>=V] 1143.61/291.61 1143.61/291.61 * Chain [31,36]: 6*s(11)+2*s(66)+12 1143.61/291.61 Such that:s(64) =< V 1143.61/291.61 aux(31) =< V1 1143.61/291.61 s(11) =< aux(31) 1143.61/291.61 s(66) =< s(64) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=1,V>=V1+1] 1143.61/291.61 1143.61/291.61 * Chain [31,34]: 3*s(63)+2*s(66)+12 1143.61/291.61 Such that:aux(30) =< V1 1143.61/291.61 s(64) =< V 1143.61/291.61 s(63) =< aux(30) 1143.61/291.61 s(66) =< s(64) 1143.61/291.61 1143.61/291.61 with precondition: [Out=0,V1>=1,V>=V1+1] 1143.61/291.61 1143.61/291.61 * Chain [31,33]: 3*s(63)+2*s(66)+13 1143.61/291.61 Such that:s(64) =< V 1143.61/291.61 aux(30) =< Out 1143.61/291.61 s(63) =< aux(30) 1143.61/291.61 s(66) =< s(64) 1143.61/291.61 1143.61/291.61 with precondition: [V1=Out,V1>=1,V>=V1+1] 1143.61/291.61 1143.61/291.61 1143.61/291.61 #### Cost of chains of start(V1,V,V5): 1143.61/291.61 * Chain [41]: 66*s(193)+42*s(194)+1*s(200)+29*s(206)+48*s(207)+48*s(208)+18*s(210)+18*s(211)+18*s(212)+6*s(214)+6*s(216)+13 1143.61/291.61 Such that:aux(55) =< -V1+V 1143.61/291.61 aux(56) =< V1 1143.61/291.61 aux(57) =< V1-V 1143.61/291.61 aux(58) =< V1+V 1143.61/291.61 aux(59) =< V 1143.61/291.61 s(193) =< aux(56) 1143.61/291.61 s(194) =< aux(59) 1143.61/291.61 s(206) =< aux(58) 1143.61/291.61 s(207) =< aux(56) 1143.61/291.61 s(207) =< aux(58) 1143.61/291.61 s(208) =< aux(58) 1143.61/291.61 s(209) =< aux(58) 1143.61/291.61 s(208) =< aux(59) 1143.61/291.61 s(209) =< aux(59) 1143.61/291.61 s(208) =< aux(58)+aux(55) 1143.61/291.61 s(207) =< aux(58)+aux(57) 1143.61/291.61 s(210) =< s(208)*aux(59) 1143.61/291.61 s(211) =< s(207)*aux(56) 1143.61/291.61 s(212) =< s(209) 1143.61/291.61 s(214) =< s(210)*aux(56) 1143.61/291.61 s(216) =< s(211)*aux(59) 1143.61/291.61 s(200) =< s(193)*aux(59) 1143.61/291.61 1143.61/291.61 with precondition: [V1>=0,V>=0] 1143.61/291.61 1143.61/291.61 * Chain [40]: 56*s(267)+126*s(268)+32*s(275)+12*s(279)+4*s(294)+37*s(300)+48*s(301)+48*s(302)+18*s(304)+18*s(305)+18*s(306)+6*s(308)+6*s(310)+19 1143.61/291.61 Such that:aux(70) =< -2*V+V5 1143.61/291.61 aux(71) =< V 1143.61/291.61 aux(72) =< V+V5 1143.61/291.61 aux(73) =< V5 1143.61/291.61 s(267) =< aux(73) 1143.61/291.61 s(300) =< aux(72) 1143.61/291.61 s(301) =< aux(71) 1143.61/291.61 s(301) =< aux(72) 1143.61/291.61 s(302) =< aux(72) 1143.61/291.61 s(303) =< aux(72) 1143.61/291.61 s(302) =< aux(73) 1143.61/291.61 s(303) =< aux(73) 1143.61/291.61 s(302) =< aux(72)+aux(70) 1143.61/291.61 s(301) =< aux(72)+aux(71) 1143.61/291.61 s(304) =< s(302)*aux(73) 1143.61/291.61 s(305) =< s(301)*aux(71) 1143.61/291.61 s(306) =< s(303) 1143.61/291.61 s(308) =< s(304)*aux(71) 1143.61/291.61 s(268) =< aux(71) 1143.61/291.61 s(310) =< s(305)*aux(73) 1143.61/291.61 s(294) =< s(267)*aux(71) 1143.61/291.61 s(275) =< aux(71) 1143.61/291.61 s(275) =< aux(71)+aux(71) 1143.61/291.61 s(279) =< s(275)*aux(71) 1143.61/291.61 1143.61/291.61 with precondition: [V1=1,V>=0,V5>=0] 1143.61/291.61 1143.61/291.61 * Chain [39]: 354*s(371)+96*s(383)+36*s(385)+295*s(395)+32*s(402)+12*s(406)+4*s(421)+95*s(427)+48*s(428)+48*s(429)+18*s(431)+18*s(432)+54*s(433)+6*s(435)+6*s(437)+9*s(527)+96*s(534)+96*s(535)+36*s(537)+36*s(538)+12*s(541)+12*s(543)+19 1143.61/291.61 Such that:aux(108) =< -2*V+V5 1143.61/291.61 aux(109) =< V 1143.61/291.61 aux(110) =< V-2*V5 1143.61/291.61 aux(111) =< V+V5 1143.61/291.61 aux(112) =< V5 1143.61/291.61 s(371) =< aux(112) 1143.61/291.61 s(427) =< aux(111) 1143.61/291.61 s(428) =< aux(109) 1143.61/291.61 s(428) =< aux(111) 1143.61/291.61 s(429) =< aux(111) 1143.61/291.61 s(430) =< aux(111) 1143.61/291.61 s(429) =< aux(112) 1143.61/291.61 s(430) =< aux(112) 1143.61/291.61 s(429) =< aux(111)+aux(108) 1143.61/291.61 s(428) =< aux(111)+aux(109) 1143.61/291.61 s(431) =< s(429)*aux(112) 1143.61/291.61 s(432) =< s(428)*aux(109) 1143.61/291.61 s(433) =< s(430) 1143.61/291.61 s(435) =< s(431)*aux(109) 1143.61/291.61 s(395) =< aux(109) 1143.61/291.61 s(437) =< s(432)*aux(112) 1143.61/291.61 s(421) =< s(371)*aux(109) 1143.61/291.61 s(527) =< s(395)*aux(112) 1143.61/291.61 s(383) =< aux(112) 1143.61/291.61 s(383) =< aux(112)+aux(112) 1143.61/291.61 s(385) =< s(383)*aux(112) 1143.61/291.61 s(534) =< aux(109) 1143.61/291.61 s(534) =< aux(111) 1143.61/291.61 s(535) =< aux(111) 1143.61/291.61 s(535) =< aux(112) 1143.61/291.61 s(535) =< aux(111)+aux(112) 1143.61/291.61 s(534) =< aux(111)+aux(110) 1143.61/291.61 s(537) =< s(535)*aux(112) 1143.61/291.61 s(538) =< s(534)*aux(109) 1143.61/291.61 s(541) =< s(537)*aux(109) 1143.61/291.61 s(543) =< s(538)*aux(112) 1143.61/291.61 s(402) =< aux(109) 1143.61/291.61 s(402) =< aux(109)+aux(109) 1143.61/291.61 s(406) =< s(402)*aux(109) 1143.61/291.61 1143.61/291.61 with precondition: [V1=2,V>=0,V5>=0] 1143.61/291.61 1143.61/291.61 * Chain [38]: 80*s(719)+32*s(727)+12*s(731)+16 1143.61/291.61 Such that:aux(117) =< V 1143.61/291.61 s(719) =< aux(117) 1143.61/291.61 s(727) =< aux(117) 1143.61/291.61 s(727) =< aux(117)+aux(117) 1143.61/291.61 s(731) =< s(727)*aux(117) 1143.61/291.61 1143.61/291.61 with precondition: [V1=2,V5=0,V>=0] 1143.61/291.61 1143.61/291.61 * Chain [37]: 5*s(748)+5 1143.61/291.61 Such that:aux(118) =< V1 1143.61/291.61 s(748) =< aux(118) 1143.61/291.61 1143.61/291.61 with precondition: [V=0,V1>=0] 1143.61/291.61 1143.61/291.61 1143.61/291.61 Closed-form bounds of start(V1,V,V5): 1143.61/291.61 ------------------------------------- 1143.61/291.61 * Chain [41] with precondition: [V1>=0,V>=0] 1143.61/291.61 - Upper bound: 114*V1+13+18*V1*V1+6*V1*V1*V+V*V1+(V1+V)*(6*V1*V)+42*V+(V1+V)*(18*V)+(95*V1+95*V) 1143.61/291.61 - Complexity: n^3 1143.61/291.61 * Chain [40] with precondition: [V1=1,V>=0,V5>=0] 1143.61/291.61 - Upper bound: 206*V+19+30*V*V+6*V*V*V5+4*V*V5+(V+V5)*(6*V*V5)+56*V5+(V+V5)*(18*V5)+(103*V+103*V5) 1143.61/291.61 - Complexity: n^3 1143.61/291.61 * Chain [39] with precondition: [V1=2,V>=0,V5>=0] 1143.61/291.61 - Upper bound: 471*V+19+66*V*V+18*V*V*V5+13*V*V5+(V+V5)*(18*V*V5)+450*V5+36*V5*V5+(V+V5)*(54*V5)+(293*V+293*V5) 1143.61/291.61 - Complexity: n^3 1143.61/291.61 * Chain [38] with precondition: [V1=2,V5=0,V>=0] 1143.61/291.61 - Upper bound: 112*V+16+12*V*V 1143.61/291.61 - Complexity: n^2 1143.61/291.61 * Chain [37] with precondition: [V=0,V1>=0] 1143.61/291.61 - Upper bound: 5*V1+5 1143.61/291.61 - Complexity: n 1143.61/291.61 1143.61/291.61 ### Maximum cost of start(V1,V,V5): max([5*V1,42*V+8+max([18*V1*V1+114*V1+6*V1*V1*V+V*V1+(V1+V)*(6*V1*V)+(V1+V)*(18*V)+(95*V1+95*V),36*V*V+265*V+12*V*V*nat(V5)+9*V*nat(V5)+12*V*nat(V5)*nat(V+V5)+nat(V5)*394+nat(V5)*36*nat(V5)+nat(V5)*36*nat(V+V5)+nat(V+V5)*190+(94*V+3+18*V*V+6*V*V*nat(V5)+4*V*nat(V5)+6*V*nat(V5)*nat(V+V5)+nat(V5)*56+nat(V5)*18*nat(V+V5)+nat(V+V5)*103)+(70*V+3+12*V*V)])])+5 1143.61/291.61 Asymptotic class: n^3 1143.61/291.61 * Total analysis performed in 1294 ms. 1143.61/291.61 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (10) 1143.61/291.61 BOUNDS(1, n^3) 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1143.61/291.61 Transformed a relative TRS into a decreasing-loop problem. 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (12) 1143.61/291.61 Obligation: 1143.61/291.61 Analyzing the following TRS for decreasing loops: 1143.61/291.61 1143.61/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 1143.61/291.61 1143.61/291.61 1143.61/291.61 The TRS R consists of the following rules: 1143.61/291.61 1143.61/291.61 minus(s(x), y) -> if(gt(s(x), y), x, y) 1143.61/291.61 if(true, x, y) -> s(minus(x, y)) 1143.61/291.61 if(false, x, y) -> 0 1143.61/291.61 gcd(x, y) -> if1(ge(x, y), x, y) 1143.61/291.61 if1(true, x, y) -> if2(gt(y, 0), x, y) 1143.61/291.61 if1(false, x, y) -> if3(gt(x, 0), x, y) 1143.61/291.61 if2(true, x, y) -> gcd(minus(x, y), y) 1143.61/291.61 if2(false, x, y) -> x 1143.61/291.61 if3(true, x, y) -> gcd(x, minus(y, x)) 1143.61/291.61 if3(false, x, y) -> y 1143.61/291.61 gt(0, y) -> false 1143.61/291.61 gt(s(x), 0) -> true 1143.61/291.61 gt(s(x), s(y)) -> gt(x, y) 1143.61/291.61 ge(x, 0) -> true 1143.61/291.61 ge(0, s(x)) -> false 1143.61/291.61 ge(s(x), s(y)) -> ge(x, y) 1143.61/291.61 1143.61/291.61 S is empty. 1143.61/291.61 Rewrite Strategy: INNERMOST 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (13) DecreasingLoopProof (LOWER BOUND(ID)) 1143.61/291.61 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1143.61/291.61 1143.61/291.61 The rewrite sequence 1143.61/291.61 1143.61/291.61 gt(s(x), s(y)) ->^+ gt(x, y) 1143.61/291.61 1143.61/291.61 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 1143.61/291.61 1143.61/291.61 The pumping substitution is [x / s(x), y / s(y)]. 1143.61/291.61 1143.61/291.61 The result substitution is [ ]. 1143.61/291.61 1143.61/291.61 1143.61/291.61 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (14) 1143.61/291.61 Complex Obligation (BEST) 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (15) 1143.61/291.61 Obligation: 1143.61/291.61 Proved the lower bound n^1 for the following obligation: 1143.61/291.61 1143.61/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 1143.61/291.61 1143.61/291.61 1143.61/291.61 The TRS R consists of the following rules: 1143.61/291.61 1143.61/291.61 minus(s(x), y) -> if(gt(s(x), y), x, y) 1143.61/291.61 if(true, x, y) -> s(minus(x, y)) 1143.61/291.61 if(false, x, y) -> 0 1143.61/291.61 gcd(x, y) -> if1(ge(x, y), x, y) 1143.61/291.61 if1(true, x, y) -> if2(gt(y, 0), x, y) 1143.61/291.61 if1(false, x, y) -> if3(gt(x, 0), x, y) 1143.61/291.61 if2(true, x, y) -> gcd(minus(x, y), y) 1143.61/291.61 if2(false, x, y) -> x 1143.61/291.61 if3(true, x, y) -> gcd(x, minus(y, x)) 1143.61/291.61 if3(false, x, y) -> y 1143.61/291.61 gt(0, y) -> false 1143.61/291.61 gt(s(x), 0) -> true 1143.61/291.61 gt(s(x), s(y)) -> gt(x, y) 1143.61/291.61 ge(x, 0) -> true 1143.61/291.61 ge(0, s(x)) -> false 1143.61/291.61 ge(s(x), s(y)) -> ge(x, y) 1143.61/291.61 1143.61/291.61 S is empty. 1143.61/291.61 Rewrite Strategy: INNERMOST 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (16) LowerBoundPropagationProof (FINISHED) 1143.61/291.61 Propagated lower bound. 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (17) 1143.61/291.61 BOUNDS(n^1, INF) 1143.61/291.61 1143.61/291.61 ---------------------------------------- 1143.61/291.61 1143.61/291.61 (18) 1143.61/291.61 Obligation: 1143.61/291.61 Analyzing the following TRS for decreasing loops: 1143.61/291.61 1143.61/291.61 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). 1143.61/291.61 1143.61/291.61 1143.61/291.61 The TRS R consists of the following rules: 1143.61/291.61 1143.61/291.61 minus(s(x), y) -> if(gt(s(x), y), x, y) 1143.61/291.61 if(true, x, y) -> s(minus(x, y)) 1143.61/291.61 if(false, x, y) -> 0 1143.61/291.61 gcd(x, y) -> if1(ge(x, y), x, y) 1143.61/291.61 if1(true, x, y) -> if2(gt(y, 0), x, y) 1143.61/291.61 if1(false, x, y) -> if3(gt(x, 0), x, y) 1143.61/291.61 if2(true, x, y) -> gcd(minus(x, y), y) 1143.61/291.61 if2(false, x, y) -> x 1143.61/291.61 if3(true, x, y) -> gcd(x, minus(y, x)) 1143.61/291.61 if3(false, x, y) -> y 1143.61/291.61 gt(0, y) -> false 1143.61/291.61 gt(s(x), 0) -> true 1143.61/291.61 gt(s(x), s(y)) -> gt(x, y) 1143.61/291.61 ge(x, 0) -> true 1143.61/291.61 ge(0, s(x)) -> false 1143.61/291.61 ge(s(x), s(y)) -> ge(x, y) 1143.61/291.61 1143.61/291.61 S is empty. 1143.61/291.61 Rewrite Strategy: INNERMOST 1143.83/291.68 EOF