1149.56/291.96 WORST_CASE(Omega(n^1), O(n^2)) 1149.70/291.98 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1149.70/291.98 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1149.70/291.98 1149.70/291.98 1149.70/291.98 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1149.70/291.98 1149.70/291.98 (0) CpxTRS 1149.70/291.98 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1149.70/291.98 (2) CpxWeightedTrs 1149.70/291.98 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1149.70/291.98 (4) CpxTypedWeightedTrs 1149.70/291.98 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1149.70/291.98 (6) CpxTypedWeightedCompleteTrs 1149.70/291.98 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1149.70/291.98 (8) CpxRNTS 1149.70/291.98 (9) CompleteCoflocoProof [FINISHED, 3400 ms] 1149.70/291.98 (10) BOUNDS(1, n^2) 1149.70/291.98 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1149.70/291.98 (12) CpxTRS 1149.70/291.98 (13) SlicingProof [LOWER BOUND(ID), 0 ms] 1149.70/291.98 (14) CpxTRS 1149.70/291.98 (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1149.70/291.98 (16) typed CpxTrs 1149.70/291.98 (17) OrderProof [LOWER BOUND(ID), 0 ms] 1149.70/291.98 (18) typed CpxTrs 1149.70/291.98 (19) RewriteLemmaProof [LOWER BOUND(ID), 299 ms] 1149.70/291.98 (20) BEST 1149.70/291.98 (21) proven lower bound 1149.70/291.98 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 1149.70/291.98 (23) BOUNDS(n^1, INF) 1149.70/291.98 (24) typed CpxTrs 1149.70/291.98 (25) RewriteLemmaProof [LOWER BOUND(ID), 38 ms] 1149.70/291.98 (26) typed CpxTrs 1149.70/291.98 (27) RewriteLemmaProof [LOWER BOUND(ID), 54 ms] 1149.70/291.98 (28) typed CpxTrs 1149.70/291.98 1149.70/291.98 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (0) 1149.70/291.98 Obligation: 1149.70/291.98 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1149.70/291.98 1149.70/291.98 1149.70/291.98 The TRS R consists of the following rules: 1149.70/291.98 1149.70/291.98 gcd(x, y) -> gcd2(x, y, 0) 1149.70/291.98 gcd2(x, y, i) -> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.98 if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i)) 1149.70/291.98 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.98 if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i)) 1149.70/291.98 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.98 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.98 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.98 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.98 if4(true, x, y, i) -> pair(result(x), neededIterations(i)) 1149.70/291.98 inc(0) -> 0 1149.70/291.98 inc(s(i)) -> s(inc(i)) 1149.70/291.98 le(s(x), 0) -> false 1149.70/291.98 le(0, y) -> true 1149.70/291.98 le(s(x), s(y)) -> le(x, y) 1149.70/291.98 minus(x, 0) -> x 1149.70/291.98 minus(0, y) -> 0 1149.70/291.98 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.98 a -> b 1149.70/291.98 a -> c 1149.70/291.98 1149.70/291.98 S is empty. 1149.70/291.98 Rewrite Strategy: INNERMOST 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1149.70/291.98 Transformed relative TRS to weighted TRS 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (2) 1149.70/291.98 Obligation: 1149.70/291.98 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1149.70/291.98 1149.70/291.98 1149.70/291.98 The TRS R consists of the following rules: 1149.70/291.98 1149.70/291.98 gcd(x, y) -> gcd2(x, y, 0) [1] 1149.70/291.98 gcd2(x, y, i) -> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) [1] 1149.70/291.98 if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i)) [1] 1149.70/291.98 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) [1] 1149.70/291.98 if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i)) [1] 1149.70/291.98 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) [1] 1149.70/291.98 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) [1] 1149.70/291.98 if3(true, b3, x, y, i) -> if4(b3, x, y, i) [1] 1149.70/291.98 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) [1] 1149.70/291.98 if4(true, x, y, i) -> pair(result(x), neededIterations(i)) [1] 1149.70/291.98 inc(0) -> 0 [1] 1149.70/291.98 inc(s(i)) -> s(inc(i)) [1] 1149.70/291.98 le(s(x), 0) -> false [1] 1149.70/291.98 le(0, y) -> true [1] 1149.70/291.98 le(s(x), s(y)) -> le(x, y) [1] 1149.70/291.98 minus(x, 0) -> x [1] 1149.70/291.98 minus(0, y) -> 0 [1] 1149.70/291.98 minus(s(x), s(y)) -> minus(x, y) [1] 1149.70/291.98 a -> b [1] 1149.70/291.98 a -> c [1] 1149.70/291.98 1149.70/291.98 Rewrite Strategy: INNERMOST 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1149.70/291.98 Infered types. 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (4) 1149.70/291.98 Obligation: 1149.70/291.98 Runtime Complexity Weighted TRS with Types. 1149.70/291.98 The TRS R consists of the following rules: 1149.70/291.98 1149.70/291.98 gcd(x, y) -> gcd2(x, y, 0) [1] 1149.70/291.98 gcd2(x, y, i) -> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) [1] 1149.70/291.98 if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i)) [1] 1149.70/291.98 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) [1] 1149.70/291.98 if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i)) [1] 1149.70/291.98 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) [1] 1149.70/291.98 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) [1] 1149.70/291.98 if3(true, b3, x, y, i) -> if4(b3, x, y, i) [1] 1149.70/291.98 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) [1] 1149.70/291.98 if4(true, x, y, i) -> pair(result(x), neededIterations(i)) [1] 1149.70/291.98 inc(0) -> 0 [1] 1149.70/291.98 inc(s(i)) -> s(inc(i)) [1] 1149.70/291.98 le(s(x), 0) -> false [1] 1149.70/291.98 le(0, y) -> true [1] 1149.70/291.98 le(s(x), s(y)) -> le(x, y) [1] 1149.70/291.98 minus(x, 0) -> x [1] 1149.70/291.98 minus(0, y) -> 0 [1] 1149.70/291.98 minus(s(x), s(y)) -> minus(x, y) [1] 1149.70/291.98 a -> b [1] 1149.70/291.98 a -> c [1] 1149.70/291.98 1149.70/291.98 The TRS has the following type information: 1149.70/291.98 gcd :: 0:s -> 0:s -> pair 1149.70/291.98 gcd2 :: 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 0 :: 0:s 1149.70/291.98 if1 :: true:false -> true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 le :: 0:s -> 0:s -> true:false 1149.70/291.98 inc :: 0:s -> 0:s 1149.70/291.98 true :: true:false 1149.70/291.98 pair :: result -> neededIterations -> pair 1149.70/291.98 result :: 0:s -> result 1149.70/291.98 neededIterations :: 0:s -> neededIterations 1149.70/291.98 false :: true:false 1149.70/291.98 if2 :: true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 if3 :: true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 minus :: 0:s -> 0:s -> 0:s 1149.70/291.98 if4 :: true:false -> 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 s :: 0:s -> 0:s 1149.70/291.98 a :: b:c 1149.70/291.98 b :: b:c 1149.70/291.98 c :: b:c 1149.70/291.98 1149.70/291.98 Rewrite Strategy: INNERMOST 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (5) CompletionProof (UPPER BOUND(ID)) 1149.70/291.98 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 1149.70/291.98 none 1149.70/291.98 1149.70/291.98 And the following fresh constants: const, const1, const2 1149.70/291.98 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (6) 1149.70/291.98 Obligation: 1149.70/291.98 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 1149.70/291.98 1149.70/291.98 Runtime Complexity Weighted TRS with Types. 1149.70/291.98 The TRS R consists of the following rules: 1149.70/291.98 1149.70/291.98 gcd(x, y) -> gcd2(x, y, 0) [1] 1149.70/291.98 gcd2(x, y, i) -> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) [1] 1149.70/291.98 if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i)) [1] 1149.70/291.98 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) [1] 1149.70/291.98 if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i)) [1] 1149.70/291.98 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) [1] 1149.70/291.98 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) [1] 1149.70/291.98 if3(true, b3, x, y, i) -> if4(b3, x, y, i) [1] 1149.70/291.98 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) [1] 1149.70/291.98 if4(true, x, y, i) -> pair(result(x), neededIterations(i)) [1] 1149.70/291.98 inc(0) -> 0 [1] 1149.70/291.98 inc(s(i)) -> s(inc(i)) [1] 1149.70/291.98 le(s(x), 0) -> false [1] 1149.70/291.98 le(0, y) -> true [1] 1149.70/291.98 le(s(x), s(y)) -> le(x, y) [1] 1149.70/291.98 minus(x, 0) -> x [1] 1149.70/291.98 minus(0, y) -> 0 [1] 1149.70/291.98 minus(s(x), s(y)) -> minus(x, y) [1] 1149.70/291.98 a -> b [1] 1149.70/291.98 a -> c [1] 1149.70/291.98 1149.70/291.98 The TRS has the following type information: 1149.70/291.98 gcd :: 0:s -> 0:s -> pair 1149.70/291.98 gcd2 :: 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 0 :: 0:s 1149.70/291.98 if1 :: true:false -> true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 le :: 0:s -> 0:s -> true:false 1149.70/291.98 inc :: 0:s -> 0:s 1149.70/291.98 true :: true:false 1149.70/291.98 pair :: result -> neededIterations -> pair 1149.70/291.98 result :: 0:s -> result 1149.70/291.98 neededIterations :: 0:s -> neededIterations 1149.70/291.98 false :: true:false 1149.70/291.98 if2 :: true:false -> true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 if3 :: true:false -> true:false -> 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 minus :: 0:s -> 0:s -> 0:s 1149.70/291.98 if4 :: true:false -> 0:s -> 0:s -> 0:s -> pair 1149.70/291.98 s :: 0:s -> 0:s 1149.70/291.98 a :: b:c 1149.70/291.98 b :: b:c 1149.70/291.98 c :: b:c 1149.70/291.98 const :: pair 1149.70/291.98 const1 :: result 1149.70/291.98 const2 :: neededIterations 1149.70/291.98 1149.70/291.98 Rewrite Strategy: INNERMOST 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1149.70/291.98 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1149.70/291.98 The constant constructors are abstracted as follows: 1149.70/291.98 1149.70/291.98 0 => 0 1149.70/291.98 true => 1 1149.70/291.98 false => 0 1149.70/291.98 b => 0 1149.70/291.98 c => 1 1149.70/291.98 const => 0 1149.70/291.98 const1 => 0 1149.70/291.98 const2 => 0 1149.70/291.98 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (8) 1149.70/291.98 Obligation: 1149.70/291.98 Complexity RNTS consisting of the following rules: 1149.70/291.98 1149.70/291.98 a -{ 1 }-> 1 :|: 1149.70/291.98 a -{ 1 }-> 0 :|: 1149.70/291.98 gcd(z, z') -{ 1 }-> gcd2(x, y, 0) :|: x >= 0, y >= 0, z = x, z' = y 1149.70/291.98 gcd2(z, z', z'') -{ 1 }-> if1(le(x, 0), le(y, 0), le(x, y), le(y, x), x, y, inc(i)) :|: z'' = i, x >= 0, y >= 0, i >= 0, z = x, z' = y 1149.70/291.98 if1(z, z', z'', z1, z2, z3, z4) -{ 1 }-> if2(b1, b2, b3, x, y, i) :|: z2 = x, b1 >= 0, z1 = b3, z3 = y, y >= 0, z4 = i, i >= 0, z' = b1, z = 0, z'' = b2, b3 >= 0, b2 >= 0, x >= 0 1149.70/291.98 if1(z, z', z'', z1, z2, z3, z4) -{ 1 }-> 1 + (1 + y) + (1 + i) :|: z2 = x, b1 >= 0, z = 1, z1 = b3, z3 = y, y >= 0, z4 = i, i >= 0, z' = b1, z'' = b2, b3 >= 0, b2 >= 0, x >= 0 1149.70/291.98 if2(z, z', z'', z1, z2, z3) -{ 1 }-> if3(b2, b3, x, y, i) :|: b2 >= 0, z2 = y, z3 = i, x >= 0, y >= 0, i >= 0, z' = b2, z = 0, z'' = b3, z1 = x, b3 >= 0 1149.70/291.98 if2(z, z', z'', z1, z2, z3) -{ 1 }-> 1 + (1 + x) + (1 + i) :|: b2 >= 0, z2 = y, z = 1, z3 = i, x >= 0, y >= 0, i >= 0, z' = b2, z'' = b3, z1 = x, b3 >= 0 1149.70/291.98 if3(z, z', z'', z1, z2) -{ 1 }-> if4(b3, x, y, i) :|: z1 = y, z2 = i, z' = b3, z = 1, x >= 0, y >= 0, i >= 0, z'' = x, b3 >= 0 1149.70/291.98 if3(z, z', z'', z1, z2) -{ 1 }-> gcd2(minus(x, y), y, i) :|: z1 = y, z2 = i, z' = b3, x >= 0, y >= 0, i >= 0, z'' = x, z = 0, b3 >= 0 1149.70/291.98 if4(z, z', z'', z1) -{ 1 }-> gcd2(x, minus(y, x), i) :|: z' = x, z'' = y, x >= 0, y >= 0, i >= 0, z = 0, z1 = i 1149.70/291.98 if4(z, z', z'', z1) -{ 1 }-> 1 + (1 + x) + (1 + i) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0, i >= 0, z1 = i 1149.70/291.98 inc(z) -{ 1 }-> 0 :|: z = 0 1149.70/291.98 inc(z) -{ 1 }-> 1 + inc(i) :|: z = 1 + i, i >= 0 1149.70/291.98 le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1149.70/291.98 le(z, z') -{ 1 }-> 1 :|: y >= 0, z = 0, z' = y 1149.70/291.98 le(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 1149.70/291.98 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 1149.70/291.98 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 1149.70/291.98 minus(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y 1149.70/291.98 1149.70/291.98 Only complete derivations are relevant for the runtime complexity. 1149.70/291.98 1149.70/291.98 ---------------------------------------- 1149.70/291.98 1149.70/291.98 (9) CompleteCoflocoProof (FINISHED) 1149.70/291.98 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 1149.70/291.98 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[gcd(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[gcd2(V1, V, V5, Out)],[V1 >= 0,V >= 0,V5 >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[if1(V1, V, V5, V17, V15, V16, V10, Out)],[V1 >= 0,V >= 0,V5 >= 0,V17 >= 0,V15 >= 0,V16 >= 0,V10 >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[if2(V1, V, V5, V17, V15, V16, Out)],[V1 >= 0,V >= 0,V5 >= 0,V17 >= 0,V15 >= 0,V16 >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[if3(V1, V, V5, V17, V15, Out)],[V1 >= 0,V >= 0,V5 >= 0,V17 >= 0,V15 >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[if4(V1, V, V5, V17, Out)],[V1 >= 0,V >= 0,V5 >= 0,V17 >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[inc(V1, Out)],[V1 >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[le(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). 1149.70/291.98 eq(start(V1, V, V5, V17, V15, V16, V10),0,[a(Out)],[]). 1149.70/291.98 eq(gcd(V1, V, Out),1,[gcd2(V3, V2, 0, Ret)],[Out = Ret,V3 >= 0,V2 >= 0,V1 = V3,V = V2]). 1149.70/291.98 eq(gcd2(V1, V, V5, Out),1,[le(V4, 0, Ret0),le(V7, 0, Ret1),le(V4, V7, Ret2),le(V7, V4, Ret3),inc(V6, Ret6),if1(Ret0, Ret1, Ret2, Ret3, V4, V7, Ret6, Ret4)],[Out = Ret4,V5 = V6,V4 >= 0,V7 >= 0,V6 >= 0,V1 = V4,V = V7]). 1149.70/291.98 eq(if1(V1, V, V5, V17, V15, V16, V10, Out),1,[],[Out = 3 + V11 + V9,V15 = V12,V8 >= 0,V1 = 1,V17 = V14,V16 = V11,V11 >= 0,V10 = V9,V9 >= 0,V = V8,V5 = V13,V14 >= 0,V13 >= 0,V12 >= 0]). 1149.70/291.98 eq(if1(V1, V, V5, V17, V15, V16, V10, Out),1,[if2(V19, V20, V23, V21, V22, V18, Ret5)],[Out = Ret5,V15 = V21,V19 >= 0,V17 = V23,V16 = V22,V22 >= 0,V10 = V18,V18 >= 0,V = V19,V1 = 0,V5 = V20,V23 >= 0,V20 >= 0,V21 >= 0]). 1149.70/291.98 eq(if2(V1, V, V5, V17, V15, V16, Out),1,[],[Out = 3 + V25 + V26,V27 >= 0,V15 = V24,V1 = 1,V16 = V26,V25 >= 0,V24 >= 0,V26 >= 0,V = V27,V5 = V28,V17 = V25,V28 >= 0]). 1149.70/291.98 eq(if2(V1, V, V5, V17, V15, V16, Out),1,[if3(V32, V33, V31, V30, V29, Ret7)],[Out = Ret7,V32 >= 0,V15 = V30,V16 = V29,V31 >= 0,V30 >= 0,V29 >= 0,V = V32,V1 = 0,V5 = V33,V17 = V31,V33 >= 0]). 1149.70/291.98 eq(if3(V1, V, V5, V17, V15, Out),1,[minus(V36, V35, Ret01),gcd2(Ret01, V35, V34, Ret8)],[Out = Ret8,V17 = V35,V15 = V34,V = V37,V36 >= 0,V35 >= 0,V34 >= 0,V5 = V36,V1 = 0,V37 >= 0]). 1149.70/291.98 eq(if3(V1, V, V5, V17, V15, Out),1,[if4(V41, V38, V40, V39, Ret9)],[Out = Ret9,V17 = V40,V15 = V39,V = V41,V1 = 1,V38 >= 0,V40 >= 0,V39 >= 0,V5 = V38,V41 >= 0]). 1149.70/291.98 eq(if4(V1, V, V5, V17, Out),1,[minus(V42, V43, Ret11),gcd2(V43, Ret11, V44, Ret10)],[Out = Ret10,V = V43,V5 = V42,V43 >= 0,V42 >= 0,V44 >= 0,V1 = 0,V17 = V44]). 1149.70/291.98 eq(if4(V1, V, V5, V17, Out),1,[],[Out = 3 + V45 + V46,V = V46,V5 = V47,V1 = 1,V46 >= 0,V47 >= 0,V45 >= 0,V17 = V45]). 1149.70/291.98 eq(inc(V1, Out),1,[],[Out = 0,V1 = 0]). 1149.70/291.98 eq(inc(V1, Out),1,[inc(V48, Ret12)],[Out = 1 + Ret12,V1 = 1 + V48,V48 >= 0]). 1149.70/291.98 eq(le(V1, V, Out),1,[],[Out = 0,V49 >= 0,V1 = 1 + V49,V = 0]). 1149.70/291.98 eq(le(V1, V, Out),1,[],[Out = 1,V50 >= 0,V1 = 0,V = V50]). 1149.70/291.98 eq(le(V1, V, Out),1,[le(V52, V51, Ret13)],[Out = Ret13,V = 1 + V51,V52 >= 0,V51 >= 0,V1 = 1 + V52]). 1149.70/291.98 eq(minus(V1, V, Out),1,[],[Out = V53,V53 >= 0,V1 = V53,V = 0]). 1149.70/291.98 eq(minus(V1, V, Out),1,[],[Out = 0,V54 >= 0,V1 = 0,V = V54]). 1149.70/291.98 eq(minus(V1, V, Out),1,[minus(V55, V56, Ret14)],[Out = Ret14,V = 1 + V56,V55 >= 0,V56 >= 0,V1 = 1 + V55]). 1149.70/291.98 eq(a(Out),1,[],[Out = 0]). 1149.70/291.98 eq(a(Out),1,[],[Out = 1]). 1149.70/291.98 input_output_vars(gcd(V1,V,Out),[V1,V],[Out]). 1149.70/291.98 input_output_vars(gcd2(V1,V,V5,Out),[V1,V,V5],[Out]). 1149.70/291.98 input_output_vars(if1(V1,V,V5,V17,V15,V16,V10,Out),[V1,V,V5,V17,V15,V16,V10],[Out]). 1149.70/291.98 input_output_vars(if2(V1,V,V5,V17,V15,V16,Out),[V1,V,V5,V17,V15,V16],[Out]). 1149.70/291.98 input_output_vars(if3(V1,V,V5,V17,V15,Out),[V1,V,V5,V17,V15],[Out]). 1149.70/291.98 input_output_vars(if4(V1,V,V5,V17,Out),[V1,V,V5,V17],[Out]). 1149.70/291.98 input_output_vars(inc(V1,Out),[V1],[Out]). 1149.70/291.98 input_output_vars(le(V1,V,Out),[V1,V],[Out]). 1149.70/291.98 input_output_vars(minus(V1,V,Out),[V1,V],[Out]). 1149.70/291.98 input_output_vars(a(Out),[],[Out]). 1149.70/291.98 1149.70/291.98 1149.70/291.98 CoFloCo proof output: 1149.70/291.98 Preprocessing Cost Relations 1149.70/291.98 ===================================== 1149.70/291.98 1149.70/291.98 #### Computed strongly connected components 1149.70/291.98 0. non_recursive : [a/1] 1149.70/291.98 1. recursive : [minus/3] 1149.70/291.98 2. recursive : [inc/2] 1149.70/291.98 3. recursive : [le/3] 1149.70/291.98 4. recursive : [gcd2/4,if1/8,if2/7,if3/6,if4/5] 1149.70/291.98 5. non_recursive : [gcd/3] 1149.70/291.98 6. non_recursive : [start/7] 1149.70/291.98 1149.70/291.98 #### Obtained direct recursion through partial evaluation 1149.70/291.98 0. SCC is partially evaluated into a/1 1149.70/291.98 1. SCC is partially evaluated into minus/3 1149.70/291.98 2. SCC is partially evaluated into inc/2 1149.70/291.98 3. SCC is partially evaluated into le/3 1149.70/291.98 4. SCC is partially evaluated into gcd2/4 1149.70/291.98 5. SCC is completely evaluated into other SCCs 1149.70/291.98 6. SCC is partially evaluated into start/7 1149.70/291.98 1149.70/291.98 Control-Flow Refinement of Cost Relations 1149.70/291.98 ===================================== 1149.70/291.98 1149.70/291.98 ### Specialization of cost equations a/1 1149.70/291.98 * CE 33 is refined into CE [34] 1149.70/291.98 * CE 32 is refined into CE [35] 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Cost equations --> "Loop" of a/1 1149.70/291.98 * CEs [34] --> Loop 16 1149.70/291.98 * CEs [35] --> Loop 17 1149.70/291.98 1149.70/291.98 ### Ranking functions of CR a(Out) 1149.70/291.98 1149.70/291.98 #### Partial ranking functions of CR a(Out) 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Specialization of cost equations minus/3 1149.70/291.98 * CE 21 is refined into CE [36] 1149.70/291.98 * CE 19 is refined into CE [37] 1149.70/291.98 * CE 20 is refined into CE [38] 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Cost equations --> "Loop" of minus/3 1149.70/291.98 * CEs [37] --> Loop 18 1149.70/291.98 * CEs [38] --> Loop 19 1149.70/291.98 * CEs [36] --> Loop 20 1149.70/291.98 1149.70/291.98 ### Ranking functions of CR minus(V1,V,Out) 1149.70/291.98 * RF of phase [20]: [V,V1] 1149.70/291.98 1149.70/291.98 #### Partial ranking functions of CR minus(V1,V,Out) 1149.70/291.98 * Partial RF of phase [20]: 1149.70/291.98 - RF of loop [20:1]: 1149.70/291.98 V 1149.70/291.98 V1 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Specialization of cost equations inc/2 1149.70/291.98 * CE 28 is refined into CE [39] 1149.70/291.98 * CE 27 is refined into CE [40] 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Cost equations --> "Loop" of inc/2 1149.70/291.98 * CEs [40] --> Loop 21 1149.70/291.98 * CEs [39] --> Loop 22 1149.70/291.98 1149.70/291.98 ### Ranking functions of CR inc(V1,Out) 1149.70/291.98 * RF of phase [22]: [V1] 1149.70/291.98 1149.70/291.98 #### Partial ranking functions of CR inc(V1,Out) 1149.70/291.98 * Partial RF of phase [22]: 1149.70/291.98 - RF of loop [22:1]: 1149.70/291.98 V1 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Specialization of cost equations le/3 1149.70/291.98 * CE 31 is refined into CE [41] 1149.70/291.98 * CE 29 is refined into CE [42] 1149.70/291.98 * CE 30 is refined into CE [43] 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Cost equations --> "Loop" of le/3 1149.70/291.98 * CEs [42] --> Loop 23 1149.70/291.98 * CEs [43] --> Loop 24 1149.70/291.98 * CEs [41] --> Loop 25 1149.70/291.98 1149.70/291.98 ### Ranking functions of CR le(V1,V,Out) 1149.70/291.98 * RF of phase [25]: [V,V1] 1149.70/291.98 1149.70/291.98 #### Partial ranking functions of CR le(V1,V,Out) 1149.70/291.98 * Partial RF of phase [25]: 1149.70/291.98 - RF of loop [25:1]: 1149.70/291.98 V 1149.70/291.98 V1 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Specialization of cost equations gcd2/4 1149.70/291.98 * CE 25 is refined into CE [44,45,46,47] 1149.70/291.98 * CE 24 is refined into CE [48,49] 1149.70/291.98 * CE 26 is refined into CE [50,51] 1149.70/291.98 * CE 22 is refined into CE [52,53] 1149.70/291.98 * CE 23 is refined into CE [54,55] 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Cost equations --> "Loop" of gcd2/4 1149.70/291.98 * CEs [53] --> Loop 26 1149.70/291.98 * CEs [55] --> Loop 27 1149.70/291.98 * CEs [52] --> Loop 28 1149.70/291.98 * CEs [54] --> Loop 29 1149.70/291.98 * CEs [49] --> Loop 30 1149.70/291.98 * CEs [48] --> Loop 31 1149.70/291.98 * CEs [51] --> Loop 32 1149.70/291.98 * CEs [50] --> Loop 33 1149.70/291.98 * CEs [47] --> Loop 34 1149.70/291.98 * CEs [46] --> Loop 35 1149.70/291.98 * CEs [45] --> Loop 36 1149.70/291.98 * CEs [44] --> Loop 37 1149.70/291.98 1149.70/291.98 ### Ranking functions of CR gcd2(V1,V,V5,Out) 1149.70/291.98 * RF of phase [26,27]: [V1+V-2] 1149.70/291.98 * RF of phase [28,29]: [V1+V-2] 1149.70/291.98 1149.70/291.98 #### Partial ranking functions of CR gcd2(V1,V,V5,Out) 1149.70/291.98 * Partial RF of phase [26,27]: 1149.70/291.98 - RF of loop [26:1]: 1149.70/291.98 V1-1 1149.70/291.98 V1-V depends on loops [27:1] 1149.70/291.98 - RF of loop [27:1]: 1149.70/291.98 V-1 1149.70/291.98 -V1+V depends on loops [26:1] 1149.70/291.98 * Partial RF of phase [28,29]: 1149.70/291.98 - RF of loop [28:1]: 1149.70/291.98 V1-1 1149.70/291.98 V1-V depends on loops [29:1] 1149.70/291.98 - RF of loop [29:1]: 1149.70/291.98 V-1 1149.70/291.98 -V1+V depends on loops [28:1] 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Specialization of cost equations start/7 1149.70/291.98 * CE 1 is refined into CE [56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71] 1149.70/291.98 * CE 2 is refined into CE [72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87] 1149.70/291.98 * CE 3 is refined into CE [88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103] 1149.70/291.98 * CE 4 is refined into CE [104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119] 1149.70/291.98 * CE 5 is refined into CE [120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135] 1149.70/291.98 * CE 6 is refined into CE [136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151] 1149.70/291.98 * CE 7 is refined into CE [152] 1149.70/291.98 * CE 8 is refined into CE [153] 1149.70/291.98 * CE 9 is refined into CE [154] 1149.70/291.98 * CE 10 is refined into CE [155] 1149.70/291.98 * CE 11 is refined into CE [156] 1149.70/291.98 * CE 12 is refined into CE [157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172] 1149.70/291.98 * CE 13 is refined into CE [173,174,175,176,177] 1149.70/291.98 * CE 14 is refined into CE [178,179,180,181,182,183,184,185,186,187] 1149.70/291.98 * CE 15 is refined into CE [188,189] 1149.70/291.98 * CE 16 is refined into CE [190,191,192,193] 1149.70/291.98 * CE 17 is refined into CE [194,195,196,197] 1149.70/291.98 * CE 18 is refined into CE [198,199] 1149.70/291.98 1149.70/291.98 1149.70/291.98 ### Cost equations --> "Loop" of start/7 1149.70/291.98 * CEs [56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199] --> Loop 38 1149.70/291.98 1149.70/291.98 ### Ranking functions of CR start(V1,V,V5,V17,V15,V16,V10) 1149.70/291.98 1149.70/291.98 #### Partial ranking functions of CR start(V1,V,V5,V17,V15,V16,V10) 1149.70/291.98 1149.70/291.98 1149.70/291.98 Computing Bounds 1149.70/291.98 ===================================== 1149.70/291.98 1149.70/291.98 #### Cost of chains of a(Out): 1149.70/291.98 * Chain [17]: 1 1149.70/291.98 with precondition: [Out=0] 1149.70/291.98 1149.70/291.98 * Chain [16]: 1 1149.70/291.98 with precondition: [Out=1] 1149.70/291.98 1149.70/291.98 1149.70/291.98 #### Cost of chains of minus(V1,V,Out): 1149.70/291.98 * Chain [[20],19]: 1*it(20)+1 1149.70/291.98 Such that:it(20) =< V1 1149.70/291.98 1149.70/291.98 with precondition: [Out=0,V1>=1,V>=V1] 1149.70/291.98 1149.70/291.98 * Chain [[20],18]: 1*it(20)+1 1149.70/291.98 Such that:it(20) =< V 1149.70/291.98 1149.70/291.98 with precondition: [V1=Out+V,V>=1,V1>=V] 1149.70/291.98 1149.70/291.98 * Chain [19]: 1 1149.70/291.98 with precondition: [V1=0,Out=0,V>=0] 1149.70/291.98 1149.70/291.98 * Chain [18]: 1 1149.70/291.98 with precondition: [V=0,V1=Out,V1>=0] 1149.70/291.98 1149.70/291.98 1149.70/291.98 #### Cost of chains of inc(V1,Out): 1149.70/291.98 * Chain [[22],21]: 1*it(22)+1 1149.70/291.98 Such that:it(22) =< Out 1149.70/291.98 1149.70/291.98 with precondition: [V1=Out,V1>=1] 1149.70/291.98 1149.70/291.98 * Chain [21]: 1 1149.70/291.98 with precondition: [V1=0,Out=0] 1149.70/291.98 1149.70/291.98 1149.70/291.98 #### Cost of chains of le(V1,V,Out): 1149.70/291.98 * Chain [[25],24]: 1*it(25)+1 1149.70/291.98 Such that:it(25) =< V1 1149.70/291.98 1149.70/291.98 with precondition: [Out=1,V1>=1,V>=V1] 1149.70/291.98 1149.70/291.98 * Chain [[25],23]: 1*it(25)+1 1149.70/291.98 Such that:it(25) =< V 1149.70/291.98 1149.70/291.98 with precondition: [Out=0,V>=1,V1>=V+1] 1149.70/291.98 1149.70/291.98 * Chain [24]: 1 1149.70/291.98 with precondition: [V1=0,Out=1,V>=0] 1149.70/291.98 1149.70/291.98 * Chain [23]: 1 1149.70/291.98 with precondition: [V=0,Out=0,V1>=1] 1149.70/291.98 1149.70/291.98 1149.70/291.98 #### Cost of chains of gcd2(V1,V,V5,Out): 1149.70/291.98 * Chain [[28,29],31]: 10*it(28)+11*it(29)+2*s(1)+3*s(13)+3*s(15)+10 1149.70/291.98 Such that:aux(7) =< -V1+V 1149.70/291.98 aux(8) =< V1 1149.70/291.98 aux(5) =< V1-V 1149.70/291.98 aux(9) =< V1+V 1149.70/291.98 aux(10) =< V1+V-2*Out+6 1149.70/291.98 aux(11) =< V1-Out+3 1149.70/291.98 aux(12) =< V 1149.70/291.98 aux(13) =< V-Out+3 1149.70/291.98 aux(1) =< Out 1149.70/291.98 s(1) =< aux(1) 1149.70/291.98 aux(6) =< aux(8) 1149.70/291.98 it(28) =< aux(8) 1149.70/291.98 it(28) =< aux(9) 1149.70/291.98 it(29) =< aux(9) 1149.70/291.98 it(28) =< aux(10) 1149.70/291.98 it(29) =< aux(10) 1149.70/291.98 aux(6) =< aux(11) 1149.70/291.98 it(28) =< aux(11) 1149.70/291.98 aux(4) =< aux(12) 1149.70/291.98 it(29) =< aux(12) 1149.70/291.98 aux(4) =< aux(13) 1149.70/291.98 it(29) =< aux(13) 1149.70/291.98 it(29) =< aux(6)+aux(7) 1149.70/291.98 it(28) =< aux(4)+aux(5) 1149.70/291.98 s(15) =< aux(4) 1149.70/291.98 s(13) =< aux(6) 1149.70/291.98 1149.70/291.98 with precondition: [V5=0,Out>=4,V1+3>=Out,V+3>=Out,V+V1+9>=3*Out] 1149.70/291.98 1149.70/291.98 * Chain [[26,27],30]: 10*it(26)+11*it(27)+2*s(17)+1*s(19)+3*s(34)+1*s(35)+3*s(37)+1*s(38)+10 1149.70/291.98 Such that:aux(21) =< -V1+V 1149.70/291.98 aux(23) =< V1 1149.70/291.98 aux(18) =< V1-V 1149.70/291.98 aux(24) =< V1+V 1149.70/291.98 aux(25) =< V1+V+2*V5-2*Out+6 1149.70/291.98 aux(26) =< V1+V5-Out+3 1149.70/291.98 aux(27) =< V 1149.70/291.98 aux(28) =< V+V5-Out+3 1149.70/291.98 aux(14) =< -V5+Out 1149.70/291.98 aux(29) =< V5 1149.70/291.98 s(19) =< aux(29) 1149.70/291.98 s(17) =< aux(14) 1149.70/291.98 aux(20) =< aux(23) 1149.70/291.98 it(26) =< aux(23) 1149.70/291.98 it(26) =< aux(24) 1149.70/291.98 it(27) =< aux(24) 1149.70/291.98 it(26) =< aux(25) 1149.70/291.98 it(27) =< aux(25) 1149.70/291.98 aux(20) =< aux(26) 1149.70/291.98 it(26) =< aux(26) 1149.70/291.98 aux(17) =< aux(27) 1149.70/291.98 it(27) =< aux(27) 1149.70/291.98 aux(17) =< aux(28) 1149.70/291.98 it(27) =< aux(28) 1149.70/291.98 aux(22) =< aux(29) 1149.70/291.98 it(27) =< aux(20)+aux(21) 1149.70/291.98 it(26) =< aux(17)+aux(18) 1149.70/291.98 s(38) =< it(27)*aux(22) 1149.70/291.98 s(35) =< it(26)*aux(29) 1149.70/291.98 s(37) =< aux(17) 1149.70/291.98 s(34) =< aux(20) 1149.70/291.98 1149.70/291.98 with precondition: [V5>=1,Out>=V5+4,V1+V5+3>=Out,V+V5+3>=Out,V+V1+3*V5+9>=3*Out] 1149.70/291.98 1149.70/291.98 * Chain [37]: 7 1149.70/291.98 with precondition: [V1=0,V=0,V5=0,Out=3] 1149.70/291.98 1149.70/291.98 * Chain [36]: 1*s(40)+7 1149.70/291.98 Such that:s(40) =< V5 1149.70/291.98 1149.70/291.98 with precondition: [V1=0,V=0,V5+3=Out,V5>=1] 1149.70/291.98 1149.70/291.98 * Chain [35]: 7 1149.70/291.98 with precondition: [V1=0,V5=0,V+3=Out,V>=1] 1149.70/291.98 1149.70/291.98 * Chain [34]: 1*s(41)+7 1149.70/291.98 Such that:s(41) =< V5 1149.70/291.98 1149.70/291.98 with precondition: [V1=0,V+V5+3=Out,V>=1,V5>=1] 1149.70/291.98 1149.70/291.98 * Chain [33]: 8 1149.70/291.98 with precondition: [V=0,V5=0,V1+3=Out,V1>=1] 1149.70/291.98 1149.70/291.98 * Chain [32]: 1*s(42)+8 1149.70/291.98 Such that:s(42) =< V5 1149.70/291.98 1149.70/291.98 with precondition: [V=0,V1+V5+3=Out,V1>=1,V5>=1] 1149.70/291.98 1149.70/291.98 * Chain [31]: 2*s(1)+10 1149.70/291.98 Such that:aux(1) =< V 1149.70/291.98 s(1) =< aux(1) 1149.70/291.98 1149.70/291.98 with precondition: [V5=0,V1=V,V1+3=Out,V1>=1] 1149.70/291.98 1149.70/291.98 * Chain [30]: 2*s(17)+1*s(19)+10 1149.70/291.98 Such that:s(19) =< V5 1149.70/291.98 aux(14) =< V1 1149.70/291.98 s(17) =< aux(14) 1149.70/291.98 1149.70/291.98 with precondition: [V1=V,V1+V5+3=Out,V1>=1,V5>=1] 1149.70/291.98 1149.70/291.98 1149.70/291.98 #### Cost of chains of start(V1,V,V5,V17,V15,V16,V10): 1149.70/291.98 * Chain [38]: 16*s(43)+34*s(47)+27*s(50)+4*s(66)+20*s(68)+22*s(69)+6*s(71)+6*s(72)+1*s(95)+1*s(96)+26*s(103)+4*s(122)+20*s(124)+22*s(125)+12*s(127)+6*s(128)+1*s(151)+1*s(152)+14*s(159)+4*s(178)+20*s(180)+22*s(181)+12*s(183)+6*s(184)+1*s(207)+1*s(208)+6*s(221)+4*s(234)+20*s(236)+22*s(237)+6*s(239)+1*s(263)+1*s(264)+6*s(277)+4*s(290)+20*s(292)+22*s(293)+6*s(295)+1*s(319)+1*s(320)+6*s(333)+4*s(346)+20*s(348)+22*s(349)+6*s(351)+6*s(352)+1*s(375)+1*s(376)+10*s(386)+6*s(389)+4*s(402)+20*s(404)+22*s(405)+6*s(407)+15*s(408)+1*s(431)+1*s(432)+6*s(446)+30*s(448)+33*s(449)+9*s(452)+5*s(457)+1*s(494)+1*s(495)+15 1149.70/291.98 Such that:aux(75) =< -V1+V 1149.70/291.98 aux(76) =< V1 1149.70/291.98 aux(77) =< V1+3 1149.70/291.98 aux(78) =< V1-V 1149.70/291.98 aux(79) =< V1+V 1149.70/291.98 aux(80) =< V1+V+6 1149.70/291.98 aux(81) =< -2*V+V5 1149.70/291.98 aux(82) =< -V+V5 1149.70/291.98 aux(83) =< -V+V5+3 1149.70/291.98 aux(84) =< V 1149.70/291.98 aux(85) =< V+3 1149.70/291.98 aux(86) =< 2*V-V5 1149.70/291.98 aux(87) =< -2*V5+V17 1149.70/291.98 aux(88) =< -V5+V17 1149.70/291.98 aux(89) =< -V5+V17+3 1149.70/291.98 aux(90) =< -V5+2*V17 1149.70/291.98 aux(91) =< V5 1149.70/291.98 aux(92) =< V5+3 1149.70/291.98 aux(93) =< V5+6 1149.70/291.98 aux(94) =< V5-2*V17 1149.70/291.98 aux(95) =< V5-V17 1149.70/291.98 aux(96) =< V5-V17+3 1149.70/291.98 aux(97) =< 2*V5-V17 1149.70/291.98 aux(98) =< V5/2 1149.70/291.98 aux(99) =< -2*V17+V15 1149.70/291.98 aux(100) =< -V17+V15 1149.70/291.98 aux(101) =< -V17+V15+3 1149.70/291.98 aux(102) =< -V17+2*V15 1149.70/291.98 aux(103) =< V17 1149.70/291.98 aux(104) =< V17+3 1149.70/291.98 aux(105) =< V17+6 1149.70/291.98 aux(106) =< V17-2*V15 1149.70/291.98 aux(107) =< V17-V15 1149.70/291.98 aux(108) =< V17-V15+3 1149.70/291.98 aux(109) =< 2*V17-V15 1149.70/291.98 aux(110) =< V17/2 1149.70/291.98 aux(111) =< -2*V15+V16 1149.70/291.98 aux(112) =< -V15+V16 1149.70/291.98 aux(113) =< -V15+V16+3 1149.70/291.98 aux(114) =< -V15+2*V16 1149.70/291.98 aux(115) =< V15 1149.70/291.98 aux(116) =< V15+3 1149.70/291.98 aux(117) =< V15+6 1149.70/291.98 aux(118) =< V15-2*V16 1149.70/291.98 aux(119) =< V15-V16 1149.70/291.98 aux(120) =< V15-V16+3 1149.70/291.98 aux(121) =< 2*V15-V16 1149.70/291.98 aux(122) =< V15/2 1149.70/291.98 aux(123) =< V16 1149.70/291.98 aux(124) =< V16+3 1149.70/291.98 aux(125) =< V16+6 1149.70/291.98 aux(126) =< V16/2 1149.70/291.98 aux(127) =< V10 1149.70/291.98 s(457) =< aux(76) 1149.70/291.98 s(386) =< aux(84) 1149.70/291.98 s(159) =< aux(91) 1149.70/291.98 s(103) =< aux(103) 1149.70/291.98 s(47) =< aux(115) 1149.70/291.98 s(50) =< aux(123) 1149.70/291.98 s(43) =< aux(127) 1149.70/291.98 s(446) =< aux(85) 1149.70/291.98 s(447) =< aux(76) 1149.70/291.98 s(448) =< aux(76) 1149.70/291.98 s(448) =< aux(79) 1149.70/291.98 s(449) =< aux(79) 1149.70/291.98 s(448) =< aux(80) 1149.70/291.98 s(449) =< aux(80) 1149.70/291.98 s(447) =< aux(77) 1149.70/291.98 s(448) =< aux(77) 1149.70/291.98 s(403) =< aux(84) 1149.70/291.98 s(449) =< aux(84) 1149.70/291.98 s(403) =< aux(85) 1149.70/291.98 s(449) =< aux(85) 1149.70/291.98 s(449) =< s(447)+aux(75) 1149.70/291.98 s(448) =< s(403)+aux(78) 1149.70/291.98 s(408) =< s(403) 1149.70/291.98 s(452) =< s(447) 1149.70/291.98 s(493) =< aux(91) 1149.70/291.98 s(494) =< s(449)*s(493) 1149.70/291.99 s(495) =< s(448)*aux(91) 1149.70/291.99 s(402) =< aux(83) 1149.70/291.99 s(404) =< aux(84) 1149.70/291.99 s(404) =< aux(91) 1149.70/291.99 s(405) =< aux(91) 1149.70/291.99 s(404) =< aux(93) 1149.70/291.99 s(405) =< aux(93) 1149.70/291.99 s(404) =< aux(85) 1149.70/291.99 s(406) =< aux(82) 1149.70/291.99 s(405) =< aux(82) 1149.70/291.99 s(406) =< aux(83) 1149.70/291.99 s(405) =< aux(83) 1149.70/291.99 s(405) =< s(403)+aux(81) 1149.70/291.99 s(404) =< s(406)+aux(86) 1149.70/291.99 s(407) =< s(406) 1149.70/291.99 s(430) =< aux(103) 1149.70/291.99 s(431) =< s(405)*s(430) 1149.70/291.99 s(432) =< s(404)*aux(103) 1149.70/291.99 s(346) =< aux(89) 1149.70/291.99 s(347) =< aux(91) 1149.70/291.99 s(348) =< aux(91) 1149.70/291.99 s(348) =< aux(103) 1149.70/291.99 s(349) =< aux(103) 1149.70/291.99 s(348) =< aux(105) 1149.70/291.99 s(349) =< aux(105) 1149.70/291.99 s(347) =< aux(92) 1149.70/291.99 s(348) =< aux(92) 1149.70/291.99 s(350) =< aux(88) 1149.70/291.99 s(349) =< aux(88) 1149.70/291.99 s(350) =< aux(89) 1149.70/291.99 s(349) =< aux(89) 1149.70/291.99 s(349) =< s(347)+aux(87) 1149.70/291.99 s(348) =< s(350)+aux(97) 1149.70/291.99 s(351) =< s(350) 1149.70/291.99 s(352) =< s(347) 1149.70/291.99 s(206) =< aux(115) 1149.70/291.99 s(375) =< s(349)*s(206) 1149.70/291.99 s(376) =< s(348)*aux(115) 1149.70/291.99 s(178) =< aux(104) 1149.70/291.99 s(179) =< aux(95) 1149.70/291.99 s(180) =< aux(95) 1149.70/291.99 s(180) =< aux(91) 1149.70/291.99 s(181) =< aux(91) 1149.70/291.99 s(180) =< aux(93) 1149.70/291.99 s(181) =< aux(93) 1149.70/291.99 s(179) =< aux(96) 1149.70/291.99 s(180) =< aux(96) 1149.70/291.99 s(182) =< aux(103) 1149.70/291.99 s(181) =< aux(103) 1149.70/291.99 s(182) =< aux(104) 1149.70/291.99 s(181) =< aux(104) 1149.70/291.99 s(181) =< s(179)+aux(90) 1149.70/291.99 s(180) =< s(182)+aux(94) 1149.70/291.99 s(183) =< s(182) 1149.70/291.99 s(184) =< s(179) 1149.70/291.99 s(207) =< s(181)*s(206) 1149.70/291.99 s(208) =< s(180)*aux(115) 1149.70/291.99 s(389) =< aux(98) 1149.70/291.99 s(290) =< aux(101) 1149.70/291.99 s(292) =< aux(103) 1149.70/291.99 s(292) =< aux(115) 1149.70/291.99 s(293) =< aux(115) 1149.70/291.99 s(292) =< aux(117) 1149.70/291.99 s(293) =< aux(117) 1149.70/291.99 s(292) =< aux(104) 1149.70/291.99 s(294) =< aux(100) 1149.70/291.99 s(293) =< aux(100) 1149.70/291.99 s(294) =< aux(101) 1149.70/291.99 s(293) =< aux(101) 1149.70/291.99 s(293) =< s(182)+aux(99) 1149.70/291.99 s(292) =< s(294)+aux(109) 1149.70/291.99 s(295) =< s(294) 1149.70/291.99 s(150) =< aux(123) 1149.70/291.99 s(319) =< s(293)*s(150) 1149.70/291.99 s(320) =< s(292)*aux(123) 1149.70/291.99 s(122) =< aux(116) 1149.70/291.99 s(123) =< aux(107) 1149.70/291.99 s(124) =< aux(107) 1149.70/291.99 s(124) =< aux(103) 1149.70/291.99 s(125) =< aux(103) 1149.70/291.99 s(124) =< aux(105) 1149.70/291.99 s(125) =< aux(105) 1149.70/291.99 s(123) =< aux(108) 1149.70/291.99 s(124) =< aux(108) 1149.70/291.99 s(126) =< aux(115) 1149.70/291.99 s(125) =< aux(115) 1149.70/291.99 s(126) =< aux(116) 1149.70/291.99 s(125) =< aux(116) 1149.70/291.99 s(125) =< s(123)+aux(102) 1149.70/291.99 s(124) =< s(126)+aux(106) 1149.70/291.99 s(127) =< s(126) 1149.70/291.99 s(128) =< s(123) 1149.70/291.99 s(151) =< s(125)*s(150) 1149.70/291.99 s(152) =< s(124)*aux(123) 1149.70/291.99 s(333) =< aux(110) 1149.70/291.99 s(234) =< aux(113) 1149.70/291.99 s(236) =< aux(115) 1149.70/291.99 s(236) =< aux(123) 1149.70/291.99 s(237) =< aux(123) 1149.70/291.99 s(236) =< aux(125) 1149.70/291.99 s(237) =< aux(125) 1149.70/291.99 s(236) =< aux(116) 1149.70/291.99 s(238) =< aux(112) 1149.70/291.99 s(237) =< aux(112) 1149.70/291.99 s(238) =< aux(113) 1149.70/291.99 s(237) =< aux(113) 1149.70/291.99 s(237) =< s(126)+aux(111) 1149.70/291.99 s(236) =< s(238)+aux(121) 1149.70/291.99 s(239) =< s(238) 1149.70/291.99 s(94) =< aux(127) 1149.70/291.99 s(263) =< s(237)*s(94) 1149.70/291.99 s(264) =< s(236)*aux(127) 1149.70/291.99 s(66) =< aux(124) 1149.70/291.99 s(67) =< aux(119) 1149.70/291.99 s(68) =< aux(119) 1149.70/291.99 s(68) =< aux(115) 1149.70/291.99 s(69) =< aux(115) 1149.70/291.99 s(68) =< aux(117) 1149.70/291.99 s(69) =< aux(117) 1149.70/291.99 s(67) =< aux(120) 1149.70/291.99 s(68) =< aux(120) 1149.70/291.99 s(70) =< aux(123) 1149.70/291.99 s(69) =< aux(123) 1149.70/291.99 s(70) =< aux(124) 1149.70/291.99 s(69) =< aux(124) 1149.70/291.99 s(69) =< s(67)+aux(114) 1149.70/291.99 s(68) =< s(70)+aux(118) 1149.70/291.99 s(71) =< s(70) 1149.70/291.99 s(72) =< s(67) 1149.70/291.99 s(95) =< s(69)*s(94) 1149.70/291.99 s(96) =< s(68)*aux(127) 1149.70/291.99 s(277) =< aux(122) 1149.70/291.99 s(221) =< aux(126) 1149.70/291.99 1149.70/291.99 with precondition: [] 1149.70/291.99 1149.70/291.99 1149.70/291.99 Closed-form bounds of start(V1,V,V5,V17,V15,V16,V10): 1149.70/291.99 ------------------------------------- 1149.70/291.99 * Chain [38] with precondition: [] 1149.70/291.99 - Upper bound: nat(V1)*44+15+nat(V5)*nat(V1)+nat(V)*45+nat(V17)*nat(V)+nat(V5)*84+nat(V17)*nat(V5)+nat(V5)*2*nat(V15)+nat(V1+V)*nat(V5)+nat(V17)*102+nat(V15)*nat(V17)+nat(V17)*2*nat(V16)+nat(V15)*110+nat(V16)*nat(V15)+nat(V15)*2*nat(V10)+nat(V5-V17)*nat(V15)+nat(V16)*55+nat(V10)*nat(V16)+nat(V17-V15)*nat(V16)+nat(V10)*16+nat(V15-V16)*nat(V10)+nat(V1+V)*33+nat(V+3)*6+nat(V17+3)*4+nat(V15+3)*4+nat(V16+3)*4+nat(-V+V5)*6+nat(-V5+V17)*6+nat(-V17+V15)*6+nat(-V15+V16)*6+nat(-V+V5+3)*4+nat(-V5+V17+3)*4+nat(-V17+V15+3)*4+nat(-V15+V16+3)*4+nat(V5-V17)*26+nat(V17-V15)*26+nat(V15-V16)*26+nat(V5/2)*6+nat(V17/2)*6+nat(V15/2)*6+nat(V16/2)*6 1149.70/291.99 - Complexity: n^2 1149.70/291.99 1149.70/291.99 ### Maximum cost of start(V1,V,V5,V17,V15,V16,V10): nat(V1)*44+15+nat(V5)*nat(V1)+nat(V)*45+nat(V17)*nat(V)+nat(V5)*84+nat(V17)*nat(V5)+nat(V5)*2*nat(V15)+nat(V1+V)*nat(V5)+nat(V17)*102+nat(V15)*nat(V17)+nat(V17)*2*nat(V16)+nat(V15)*110+nat(V16)*nat(V15)+nat(V15)*2*nat(V10)+nat(V5-V17)*nat(V15)+nat(V16)*55+nat(V10)*nat(V16)+nat(V17-V15)*nat(V16)+nat(V10)*16+nat(V15-V16)*nat(V10)+nat(V1+V)*33+nat(V+3)*6+nat(V17+3)*4+nat(V15+3)*4+nat(V16+3)*4+nat(-V+V5)*6+nat(-V5+V17)*6+nat(-V17+V15)*6+nat(-V15+V16)*6+nat(-V+V5+3)*4+nat(-V5+V17+3)*4+nat(-V17+V15+3)*4+nat(-V15+V16+3)*4+nat(V5-V17)*26+nat(V17-V15)*26+nat(V15-V16)*26+nat(V5/2)*6+nat(V17/2)*6+nat(V15/2)*6+nat(V16/2)*6 1149.70/291.99 Asymptotic class: n^2 1149.70/291.99 * Total analysis performed in 2894 ms. 1149.70/291.99 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (10) 1149.70/291.99 BOUNDS(1, n^2) 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 1149.70/291.99 Renamed function symbols to avoid clashes with predefined symbol. 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (12) 1149.70/291.99 Obligation: 1149.70/291.99 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1149.70/291.99 1149.70/291.99 1149.70/291.99 The TRS R consists of the following rules: 1149.70/291.99 1149.70/291.99 gcd(x, y) -> gcd2(x, y, 0') 1149.70/291.99 gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.99 if1(true, b1, b2, b3, x, y, i) -> pair(result(y), neededIterations(i)) 1149.70/291.99 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.99 if2(true, b2, b3, x, y, i) -> pair(result(x), neededIterations(i)) 1149.70/291.99 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.99 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.99 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.99 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.99 if4(true, x, y, i) -> pair(result(x), neededIterations(i)) 1149.70/291.99 inc(0') -> 0' 1149.70/291.99 inc(s(i)) -> s(inc(i)) 1149.70/291.99 le(s(x), 0') -> false 1149.70/291.99 le(0', y) -> true 1149.70/291.99 le(s(x), s(y)) -> le(x, y) 1149.70/291.99 minus(x, 0') -> x 1149.70/291.99 minus(0', y) -> 0' 1149.70/291.99 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.99 a -> b 1149.70/291.99 a -> c 1149.70/291.99 1149.70/291.99 S is empty. 1149.70/291.99 Rewrite Strategy: INNERMOST 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (13) SlicingProof (LOWER BOUND(ID)) 1149.70/291.99 Sliced the following arguments: 1149.70/291.99 pair/0 1149.70/291.99 pair/1 1149.70/291.99 result/0 1149.70/291.99 neededIterations/0 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (14) 1149.70/291.99 Obligation: 1149.70/291.99 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1149.70/291.99 1149.70/291.99 1149.70/291.99 The TRS R consists of the following rules: 1149.70/291.99 1149.70/291.99 gcd(x, y) -> gcd2(x, y, 0') 1149.70/291.99 gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.99 if1(true, b1, b2, b3, x, y, i) -> pair 1149.70/291.99 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.99 if2(true, b2, b3, x, y, i) -> pair 1149.70/291.99 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.99 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.99 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.99 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.99 if4(true, x, y, i) -> pair 1149.70/291.99 inc(0') -> 0' 1149.70/291.99 inc(s(i)) -> s(inc(i)) 1149.70/291.99 le(s(x), 0') -> false 1149.70/291.99 le(0', y) -> true 1149.70/291.99 le(s(x), s(y)) -> le(x, y) 1149.70/291.99 minus(x, 0') -> x 1149.70/291.99 minus(0', y) -> 0' 1149.70/291.99 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.99 a -> b 1149.70/291.99 a -> c 1149.70/291.99 1149.70/291.99 S is empty. 1149.70/291.99 Rewrite Strategy: INNERMOST 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (15) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1149.70/291.99 Infered types. 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (16) 1149.70/291.99 Obligation: 1149.70/291.99 Innermost TRS: 1149.70/291.99 Rules: 1149.70/291.99 gcd(x, y) -> gcd2(x, y, 0') 1149.70/291.99 gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.99 if1(true, b1, b2, b3, x, y, i) -> pair 1149.70/291.99 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.99 if2(true, b2, b3, x, y, i) -> pair 1149.70/291.99 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.99 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.99 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.99 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.99 if4(true, x, y, i) -> pair 1149.70/291.99 inc(0') -> 0' 1149.70/291.99 inc(s(i)) -> s(inc(i)) 1149.70/291.99 le(s(x), 0') -> false 1149.70/291.99 le(0', y) -> true 1149.70/291.99 le(s(x), s(y)) -> le(x, y) 1149.70/291.99 minus(x, 0') -> x 1149.70/291.99 minus(0', y) -> 0' 1149.70/291.99 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.99 a -> b 1149.70/291.99 a -> c 1149.70/291.99 1149.70/291.99 Types: 1149.70/291.99 gcd :: 0':s -> 0':s -> pair 1149.70/291.99 gcd2 :: 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 0' :: 0':s 1149.70/291.99 if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 le :: 0':s -> 0':s -> true:false 1149.70/291.99 inc :: 0':s -> 0':s 1149.70/291.99 true :: true:false 1149.70/291.99 pair :: pair 1149.70/291.99 false :: true:false 1149.70/291.99 if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 minus :: 0':s -> 0':s -> 0':s 1149.70/291.99 if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 s :: 0':s -> 0':s 1149.70/291.99 a :: b:c 1149.70/291.99 b :: b:c 1149.70/291.99 c :: b:c 1149.70/291.99 hole_pair1_0 :: pair 1149.70/291.99 hole_0':s2_0 :: 0':s 1149.70/291.99 hole_true:false3_0 :: true:false 1149.70/291.99 hole_b:c4_0 :: b:c 1149.70/291.99 gen_0':s5_0 :: Nat -> 0':s 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (17) OrderProof (LOWER BOUND(ID)) 1149.70/291.99 Heuristically decided to analyse the following defined symbols: 1149.70/291.99 gcd2, le, inc, minus 1149.70/291.99 1149.70/291.99 They will be analysed ascendingly in the following order: 1149.70/291.99 le < gcd2 1149.70/291.99 inc < gcd2 1149.70/291.99 minus < gcd2 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (18) 1149.70/291.99 Obligation: 1149.70/291.99 Innermost TRS: 1149.70/291.99 Rules: 1149.70/291.99 gcd(x, y) -> gcd2(x, y, 0') 1149.70/291.99 gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.99 if1(true, b1, b2, b3, x, y, i) -> pair 1149.70/291.99 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.99 if2(true, b2, b3, x, y, i) -> pair 1149.70/291.99 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.99 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.99 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.99 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.99 if4(true, x, y, i) -> pair 1149.70/291.99 inc(0') -> 0' 1149.70/291.99 inc(s(i)) -> s(inc(i)) 1149.70/291.99 le(s(x), 0') -> false 1149.70/291.99 le(0', y) -> true 1149.70/291.99 le(s(x), s(y)) -> le(x, y) 1149.70/291.99 minus(x, 0') -> x 1149.70/291.99 minus(0', y) -> 0' 1149.70/291.99 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.99 a -> b 1149.70/291.99 a -> c 1149.70/291.99 1149.70/291.99 Types: 1149.70/291.99 gcd :: 0':s -> 0':s -> pair 1149.70/291.99 gcd2 :: 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 0' :: 0':s 1149.70/291.99 if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 le :: 0':s -> 0':s -> true:false 1149.70/291.99 inc :: 0':s -> 0':s 1149.70/291.99 true :: true:false 1149.70/291.99 pair :: pair 1149.70/291.99 false :: true:false 1149.70/291.99 if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 minus :: 0':s -> 0':s -> 0':s 1149.70/291.99 if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 s :: 0':s -> 0':s 1149.70/291.99 a :: b:c 1149.70/291.99 b :: b:c 1149.70/291.99 c :: b:c 1149.70/291.99 hole_pair1_0 :: pair 1149.70/291.99 hole_0':s2_0 :: 0':s 1149.70/291.99 hole_true:false3_0 :: true:false 1149.70/291.99 hole_b:c4_0 :: b:c 1149.70/291.99 gen_0':s5_0 :: Nat -> 0':s 1149.70/291.99 1149.70/291.99 1149.70/291.99 Generator Equations: 1149.70/291.99 gen_0':s5_0(0) <=> 0' 1149.70/291.99 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 1149.70/291.99 1149.70/291.99 1149.70/291.99 The following defined symbols remain to be analysed: 1149.70/291.99 le, gcd2, inc, minus 1149.70/291.99 1149.70/291.99 They will be analysed ascendingly in the following order: 1149.70/291.99 le < gcd2 1149.70/291.99 inc < gcd2 1149.70/291.99 minus < gcd2 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1149.70/291.99 Proved the following rewrite lemma: 1149.70/291.99 le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) -> false, rt in Omega(1 + n7_0) 1149.70/291.99 1149.70/291.99 Induction Base: 1149.70/291.99 le(gen_0':s5_0(+(1, 0)), gen_0':s5_0(0)) ->_R^Omega(1) 1149.70/291.99 false 1149.70/291.99 1149.70/291.99 Induction Step: 1149.70/291.99 le(gen_0':s5_0(+(1, +(n7_0, 1))), gen_0':s5_0(+(n7_0, 1))) ->_R^Omega(1) 1149.70/291.99 le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) ->_IH 1149.70/291.99 false 1149.70/291.99 1149.70/291.99 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (20) 1149.70/291.99 Complex Obligation (BEST) 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (21) 1149.70/291.99 Obligation: 1149.70/291.99 Proved the lower bound n^1 for the following obligation: 1149.70/291.99 1149.70/291.99 Innermost TRS: 1149.70/291.99 Rules: 1149.70/291.99 gcd(x, y) -> gcd2(x, y, 0') 1149.70/291.99 gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.99 if1(true, b1, b2, b3, x, y, i) -> pair 1149.70/291.99 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.99 if2(true, b2, b3, x, y, i) -> pair 1149.70/291.99 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.99 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.99 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.99 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.99 if4(true, x, y, i) -> pair 1149.70/291.99 inc(0') -> 0' 1149.70/291.99 inc(s(i)) -> s(inc(i)) 1149.70/291.99 le(s(x), 0') -> false 1149.70/291.99 le(0', y) -> true 1149.70/291.99 le(s(x), s(y)) -> le(x, y) 1149.70/291.99 minus(x, 0') -> x 1149.70/291.99 minus(0', y) -> 0' 1149.70/291.99 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.99 a -> b 1149.70/291.99 a -> c 1149.70/291.99 1149.70/291.99 Types: 1149.70/291.99 gcd :: 0':s -> 0':s -> pair 1149.70/291.99 gcd2 :: 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 0' :: 0':s 1149.70/291.99 if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 le :: 0':s -> 0':s -> true:false 1149.70/291.99 inc :: 0':s -> 0':s 1149.70/291.99 true :: true:false 1149.70/291.99 pair :: pair 1149.70/291.99 false :: true:false 1149.70/291.99 if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 minus :: 0':s -> 0':s -> 0':s 1149.70/291.99 if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 s :: 0':s -> 0':s 1149.70/291.99 a :: b:c 1149.70/291.99 b :: b:c 1149.70/291.99 c :: b:c 1149.70/291.99 hole_pair1_0 :: pair 1149.70/291.99 hole_0':s2_0 :: 0':s 1149.70/291.99 hole_true:false3_0 :: true:false 1149.70/291.99 hole_b:c4_0 :: b:c 1149.70/291.99 gen_0':s5_0 :: Nat -> 0':s 1149.70/291.99 1149.70/291.99 1149.70/291.99 Generator Equations: 1149.70/291.99 gen_0':s5_0(0) <=> 0' 1149.70/291.99 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 1149.70/291.99 1149.70/291.99 1149.70/291.99 The following defined symbols remain to be analysed: 1149.70/291.99 le, gcd2, inc, minus 1149.70/291.99 1149.70/291.99 They will be analysed ascendingly in the following order: 1149.70/291.99 le < gcd2 1149.70/291.99 inc < gcd2 1149.70/291.99 minus < gcd2 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (22) LowerBoundPropagationProof (FINISHED) 1149.70/291.99 Propagated lower bound. 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (23) 1149.70/291.99 BOUNDS(n^1, INF) 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (24) 1149.70/291.99 Obligation: 1149.70/291.99 Innermost TRS: 1149.70/291.99 Rules: 1149.70/291.99 gcd(x, y) -> gcd2(x, y, 0') 1149.70/291.99 gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.99 if1(true, b1, b2, b3, x, y, i) -> pair 1149.70/291.99 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.99 if2(true, b2, b3, x, y, i) -> pair 1149.70/291.99 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.99 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.99 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.99 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.99 if4(true, x, y, i) -> pair 1149.70/291.99 inc(0') -> 0' 1149.70/291.99 inc(s(i)) -> s(inc(i)) 1149.70/291.99 le(s(x), 0') -> false 1149.70/291.99 le(0', y) -> true 1149.70/291.99 le(s(x), s(y)) -> le(x, y) 1149.70/291.99 minus(x, 0') -> x 1149.70/291.99 minus(0', y) -> 0' 1149.70/291.99 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.99 a -> b 1149.70/291.99 a -> c 1149.70/291.99 1149.70/291.99 Types: 1149.70/291.99 gcd :: 0':s -> 0':s -> pair 1149.70/291.99 gcd2 :: 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 0' :: 0':s 1149.70/291.99 if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 le :: 0':s -> 0':s -> true:false 1149.70/291.99 inc :: 0':s -> 0':s 1149.70/291.99 true :: true:false 1149.70/291.99 pair :: pair 1149.70/291.99 false :: true:false 1149.70/291.99 if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 minus :: 0':s -> 0':s -> 0':s 1149.70/291.99 if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 s :: 0':s -> 0':s 1149.70/291.99 a :: b:c 1149.70/291.99 b :: b:c 1149.70/291.99 c :: b:c 1149.70/291.99 hole_pair1_0 :: pair 1149.70/291.99 hole_0':s2_0 :: 0':s 1149.70/291.99 hole_true:false3_0 :: true:false 1149.70/291.99 hole_b:c4_0 :: b:c 1149.70/291.99 gen_0':s5_0 :: Nat -> 0':s 1149.70/291.99 1149.70/291.99 1149.70/291.99 Lemmas: 1149.70/291.99 le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) -> false, rt in Omega(1 + n7_0) 1149.70/291.99 1149.70/291.99 1149.70/291.99 Generator Equations: 1149.70/291.99 gen_0':s5_0(0) <=> 0' 1149.70/291.99 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 1149.70/291.99 1149.70/291.99 1149.70/291.99 The following defined symbols remain to be analysed: 1149.70/291.99 inc, gcd2, minus 1149.70/291.99 1149.70/291.99 They will be analysed ascendingly in the following order: 1149.70/291.99 inc < gcd2 1149.70/291.99 minus < gcd2 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (25) RewriteLemmaProof (LOWER BOUND(ID)) 1149.70/291.99 Proved the following rewrite lemma: 1149.70/291.99 inc(gen_0':s5_0(n344_0)) -> gen_0':s5_0(n344_0), rt in Omega(1 + n344_0) 1149.70/291.99 1149.70/291.99 Induction Base: 1149.70/291.99 inc(gen_0':s5_0(0)) ->_R^Omega(1) 1149.70/291.99 0' 1149.70/291.99 1149.70/291.99 Induction Step: 1149.70/291.99 inc(gen_0':s5_0(+(n344_0, 1))) ->_R^Omega(1) 1149.70/291.99 s(inc(gen_0':s5_0(n344_0))) ->_IH 1149.70/291.99 s(gen_0':s5_0(c345_0)) 1149.70/291.99 1149.70/291.99 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (26) 1149.70/291.99 Obligation: 1149.70/291.99 Innermost TRS: 1149.70/291.99 Rules: 1149.70/291.99 gcd(x, y) -> gcd2(x, y, 0') 1149.70/291.99 gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.99 if1(true, b1, b2, b3, x, y, i) -> pair 1149.70/291.99 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.99 if2(true, b2, b3, x, y, i) -> pair 1149.70/291.99 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.99 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.99 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.99 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.99 if4(true, x, y, i) -> pair 1149.70/291.99 inc(0') -> 0' 1149.70/291.99 inc(s(i)) -> s(inc(i)) 1149.70/291.99 le(s(x), 0') -> false 1149.70/291.99 le(0', y) -> true 1149.70/291.99 le(s(x), s(y)) -> le(x, y) 1149.70/291.99 minus(x, 0') -> x 1149.70/291.99 minus(0', y) -> 0' 1149.70/291.99 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.99 a -> b 1149.70/291.99 a -> c 1149.70/291.99 1149.70/291.99 Types: 1149.70/291.99 gcd :: 0':s -> 0':s -> pair 1149.70/291.99 gcd2 :: 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 0' :: 0':s 1149.70/291.99 if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 le :: 0':s -> 0':s -> true:false 1149.70/291.99 inc :: 0':s -> 0':s 1149.70/291.99 true :: true:false 1149.70/291.99 pair :: pair 1149.70/291.99 false :: true:false 1149.70/291.99 if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 minus :: 0':s -> 0':s -> 0':s 1149.70/291.99 if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 s :: 0':s -> 0':s 1149.70/291.99 a :: b:c 1149.70/291.99 b :: b:c 1149.70/291.99 c :: b:c 1149.70/291.99 hole_pair1_0 :: pair 1149.70/291.99 hole_0':s2_0 :: 0':s 1149.70/291.99 hole_true:false3_0 :: true:false 1149.70/291.99 hole_b:c4_0 :: b:c 1149.70/291.99 gen_0':s5_0 :: Nat -> 0':s 1149.70/291.99 1149.70/291.99 1149.70/291.99 Lemmas: 1149.70/291.99 le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) -> false, rt in Omega(1 + n7_0) 1149.70/291.99 inc(gen_0':s5_0(n344_0)) -> gen_0':s5_0(n344_0), rt in Omega(1 + n344_0) 1149.70/291.99 1149.70/291.99 1149.70/291.99 Generator Equations: 1149.70/291.99 gen_0':s5_0(0) <=> 0' 1149.70/291.99 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 1149.70/291.99 1149.70/291.99 1149.70/291.99 The following defined symbols remain to be analysed: 1149.70/291.99 minus, gcd2 1149.70/291.99 1149.70/291.99 They will be analysed ascendingly in the following order: 1149.70/291.99 minus < gcd2 1149.70/291.99 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (27) RewriteLemmaProof (LOWER BOUND(ID)) 1149.70/291.99 Proved the following rewrite lemma: 1149.70/291.99 minus(gen_0':s5_0(n594_0), gen_0':s5_0(n594_0)) -> gen_0':s5_0(0), rt in Omega(1 + n594_0) 1149.70/291.99 1149.70/291.99 Induction Base: 1149.70/291.99 minus(gen_0':s5_0(0), gen_0':s5_0(0)) ->_R^Omega(1) 1149.70/291.99 gen_0':s5_0(0) 1149.70/291.99 1149.70/291.99 Induction Step: 1149.70/291.99 minus(gen_0':s5_0(+(n594_0, 1)), gen_0':s5_0(+(n594_0, 1))) ->_R^Omega(1) 1149.70/291.99 minus(gen_0':s5_0(n594_0), gen_0':s5_0(n594_0)) ->_IH 1149.70/291.99 gen_0':s5_0(0) 1149.70/291.99 1149.70/291.99 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1149.70/291.99 ---------------------------------------- 1149.70/291.99 1149.70/291.99 (28) 1149.70/291.99 Obligation: 1149.70/291.99 Innermost TRS: 1149.70/291.99 Rules: 1149.70/291.99 gcd(x, y) -> gcd2(x, y, 0') 1149.70/291.99 gcd2(x, y, i) -> if1(le(x, 0'), le(y, 0'), le(x, y), le(y, x), x, y, inc(i)) 1149.70/291.99 if1(true, b1, b2, b3, x, y, i) -> pair 1149.70/291.99 if1(false, b1, b2, b3, x, y, i) -> if2(b1, b2, b3, x, y, i) 1149.70/291.99 if2(true, b2, b3, x, y, i) -> pair 1149.70/291.99 if2(false, b2, b3, x, y, i) -> if3(b2, b3, x, y, i) 1149.70/291.99 if3(false, b3, x, y, i) -> gcd2(minus(x, y), y, i) 1149.70/291.99 if3(true, b3, x, y, i) -> if4(b3, x, y, i) 1149.70/291.99 if4(false, x, y, i) -> gcd2(x, minus(y, x), i) 1149.70/291.99 if4(true, x, y, i) -> pair 1149.70/291.99 inc(0') -> 0' 1149.70/291.99 inc(s(i)) -> s(inc(i)) 1149.70/291.99 le(s(x), 0') -> false 1149.70/291.99 le(0', y) -> true 1149.70/291.99 le(s(x), s(y)) -> le(x, y) 1149.70/291.99 minus(x, 0') -> x 1149.70/291.99 minus(0', y) -> 0' 1149.70/291.99 minus(s(x), s(y)) -> minus(x, y) 1149.70/291.99 a -> b 1149.70/291.99 a -> c 1149.70/291.99 1149.70/291.99 Types: 1149.70/291.99 gcd :: 0':s -> 0':s -> pair 1149.70/291.99 gcd2 :: 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 0' :: 0':s 1149.70/291.99 if1 :: true:false -> true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 le :: 0':s -> 0':s -> true:false 1149.70/291.99 inc :: 0':s -> 0':s 1149.70/291.99 true :: true:false 1149.70/291.99 pair :: pair 1149.70/291.99 false :: true:false 1149.70/291.99 if2 :: true:false -> true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 if3 :: true:false -> true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 minus :: 0':s -> 0':s -> 0':s 1149.70/291.99 if4 :: true:false -> 0':s -> 0':s -> 0':s -> pair 1149.70/291.99 s :: 0':s -> 0':s 1149.70/291.99 a :: b:c 1149.70/291.99 b :: b:c 1149.70/291.99 c :: b:c 1149.70/291.99 hole_pair1_0 :: pair 1149.70/291.99 hole_0':s2_0 :: 0':s 1149.70/291.99 hole_true:false3_0 :: true:false 1149.70/291.99 hole_b:c4_0 :: b:c 1149.70/291.99 gen_0':s5_0 :: Nat -> 0':s 1149.70/291.99 1149.70/291.99 1149.70/291.99 Lemmas: 1149.70/291.99 le(gen_0':s5_0(+(1, n7_0)), gen_0':s5_0(n7_0)) -> false, rt in Omega(1 + n7_0) 1149.70/291.99 inc(gen_0':s5_0(n344_0)) -> gen_0':s5_0(n344_0), rt in Omega(1 + n344_0) 1149.70/291.99 minus(gen_0':s5_0(n594_0), gen_0':s5_0(n594_0)) -> gen_0':s5_0(0), rt in Omega(1 + n594_0) 1149.70/291.99 1149.70/291.99 1149.70/291.99 Generator Equations: 1149.70/291.99 gen_0':s5_0(0) <=> 0' 1149.70/291.99 gen_0':s5_0(+(x, 1)) <=> s(gen_0':s5_0(x)) 1149.70/291.99 1149.70/291.99 1149.70/291.99 The following defined symbols remain to be analysed: 1149.70/291.99 gcd2 1149.83/292.05 EOF