/export/starexec/sandbox2/solver/bin/starexec_run_Transition /export/starexec/sandbox2/benchmark/theBenchmark.smt2 /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES DP problem for innermost termination. P = init#(x1, x2, x3, x4, x5) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5) f3#(I0, I1, I2, I3, I4) -> f3#(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] f3#(I5, I6, I7, I8, I9) -> f2#(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] f3#(I12, I13, I14, I15, I16) -> f3#(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] f3#(I17, I18, I19, I20, I21) -> f3#(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] f3#(I24, I25, I26, I27, I28) -> f2#(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] f3#(I31, I32, I33, I34, I35) -> f2#(I31, I32 + 1, I32 + 1, I36, I37) [I34 = I35 /\ 1 = I33 /\ 19 <= I34 - 1] f2#(I38, I39, I40, I41, I42) -> f3#(I38, I39, 0, 0, 0) [I39 = I40 /\ I39 <= 19] f1#(I43, I44, I45, I46, I47) -> f2#(0, 0, 0, I48, I49) R = init(x1, x2, x3, x4, x5) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5) f3(I0, I1, I2, I3, I4) -> f3(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] f3(I5, I6, I7, I8, I9) -> f2(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] f3(I12, I13, I14, I15, I16) -> f3(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] f3(I17, I18, I19, I20, I21) -> f3(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] f3(I24, I25, I26, I27, I28) -> f2(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] f3(I31, I32, I33, I34, I35) -> f2(I31, I32 + 1, I32 + 1, I36, I37) [I34 = I35 /\ 1 = I33 /\ 19 <= I34 - 1] f2(I38, I39, I40, I41, I42) -> f3(I38, I39, 0, 0, 0) [I39 = I40 /\ I39 <= 19] f1(I43, I44, I45, I46, I47) -> f2(0, 0, 0, I48, I49) The dependency graph for this problem is: 0 -> 8 1 -> 5 2 -> 7 3 -> 1, 2, 3, 4 4 -> 1, 2, 3, 4 5 -> 7 6 -> 7 7 -> 1, 3, 4 8 -> 7 Where: 0) init#(x1, x2, x3, x4, x5) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5) 1) f3#(I0, I1, I2, I3, I4) -> f3#(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] 2) f3#(I5, I6, I7, I8, I9) -> f2#(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] 3) f3#(I12, I13, I14, I15, I16) -> f3#(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] 4) f3#(I17, I18, I19, I20, I21) -> f3#(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] 5) f3#(I24, I25, I26, I27, I28) -> f2#(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] 6) f3#(I31, I32, I33, I34, I35) -> f2#(I31, I32 + 1, I32 + 1, I36, I37) [I34 = I35 /\ 1 = I33 /\ 19 <= I34 - 1] 7) f2#(I38, I39, I40, I41, I42) -> f3#(I38, I39, 0, 0, 0) [I39 = I40 /\ I39 <= 19] 8) f1#(I43, I44, I45, I46, I47) -> f2#(0, 0, 0, I48, I49) We have the following SCCs. { 1, 2, 3, 4, 5, 7 } DP problem for innermost termination. P = f3#(I0, I1, I2, I3, I4) -> f3#(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] f3#(I5, I6, I7, I8, I9) -> f2#(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] f3#(I12, I13, I14, I15, I16) -> f3#(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] f3#(I17, I18, I19, I20, I21) -> f3#(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] f3#(I24, I25, I26, I27, I28) -> f2#(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] f2#(I38, I39, I40, I41, I42) -> f3#(I38, I39, 0, 0, 0) [I39 = I40 /\ I39 <= 19] R = init(x1, x2, x3, x4, x5) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5) f3(I0, I1, I2, I3, I4) -> f3(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] f3(I5, I6, I7, I8, I9) -> f2(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] f3(I12, I13, I14, I15, I16) -> f3(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] f3(I17, I18, I19, I20, I21) -> f3(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] f3(I24, I25, I26, I27, I28) -> f2(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] f3(I31, I32, I33, I34, I35) -> f2(I31, I32 + 1, I32 + 1, I36, I37) [I34 = I35 /\ 1 = I33 /\ 19 <= I34 - 1] f2(I38, I39, I40, I41, I42) -> f3(I38, I39, 0, 0, 0) [I39 = I40 /\ I39 <= 19] f1(I43, I44, I45, I46, I47) -> f2(0, 0, 0, I48, I49) We use the reverse value criterion with the projection function NU: NU[f2#(z1,z2,z3,z4,z5)] = 19 + -1 * z2 NU[f3#(z1,z2,z3,z4,z5)] = 19 + -1 * (z2 + 1) This gives the following inequalities: I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19 ==> 19 + -1 * (I1 + 1) >= 19 + -1 * (I1 + 1) I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19 ==> 19 + -1 * (I6 + 1) >= 19 + -1 * (I6 + 1) I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16 ==> 19 + -1 * (I13 + 1) >= 19 + -1 * (I13 + 1) I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21 ==> 19 + -1 * (I18 + 1) >= 19 + -1 * (I18 + 1) I27 = I28 /\ 1 = I26 /\ I27 <= 19 ==> 19 + -1 * (I25 + 1) >= 19 + -1 * (I25 + 1) I39 = I40 /\ I39 <= 19 ==> 19 + -1 * I39 > 19 + -1 * (I39 + 1) with 19 + -1 * I39 >= 0 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = f3#(I0, I1, I2, I3, I4) -> f3#(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] f3#(I5, I6, I7, I8, I9) -> f2#(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] f3#(I12, I13, I14, I15, I16) -> f3#(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] f3#(I17, I18, I19, I20, I21) -> f3#(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] f3#(I24, I25, I26, I27, I28) -> f2#(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] R = init(x1, x2, x3, x4, x5) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5) f3(I0, I1, I2, I3, I4) -> f3(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] f3(I5, I6, I7, I8, I9) -> f2(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] f3(I12, I13, I14, I15, I16) -> f3(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] f3(I17, I18, I19, I20, I21) -> f3(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] f3(I24, I25, I26, I27, I28) -> f2(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] f3(I31, I32, I33, I34, I35) -> f2(I31, I32 + 1, I32 + 1, I36, I37) [I34 = I35 /\ 1 = I33 /\ 19 <= I34 - 1] f2(I38, I39, I40, I41, I42) -> f3(I38, I39, 0, 0, 0) [I39 = I40 /\ I39 <= 19] f1(I43, I44, I45, I46, I47) -> f2(0, 0, 0, I48, I49) The dependency graph for this problem is: 1 -> 5 2 -> 3 -> 1, 2, 3, 4 4 -> 1, 2, 3, 4 5 -> Where: 1) f3#(I0, I1, I2, I3, I4) -> f3#(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] 2) f3#(I5, I6, I7, I8, I9) -> f2#(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] 3) f3#(I12, I13, I14, I15, I16) -> f3#(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] 4) f3#(I17, I18, I19, I20, I21) -> f3#(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] 5) f3#(I24, I25, I26, I27, I28) -> f2#(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] We have the following SCCs. { 3, 4 } DP problem for innermost termination. P = f3#(I12, I13, I14, I15, I16) -> f3#(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] f3#(I17, I18, I19, I20, I21) -> f3#(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] R = init(x1, x2, x3, x4, x5) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5) f3(I0, I1, I2, I3, I4) -> f3(I0, I1, 1, I3, I3) [I3 = I4 /\ 0 = I2 /\ I1 <= 19 /\ I3 <= 19] f3(I5, I6, I7, I8, I9) -> f2(I5 + 1, I6 + 1, I6 + 1, I10, I11) [I8 = I9 /\ 0 = I7 /\ 19 <= I8 - 1 /\ I6 <= 19 /\ I5 <= 19] f3(I12, I13, I14, I15, I16) -> f3(I12, I13, 0, I15 + 1, I15 + 1) [I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16] f3(I17, I18, I19, I20, I21) -> f3(I17, I18, 0, I20 + 1, I20 + 1) [I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21] f3(I24, I25, I26, I27, I28) -> f2(I24, I25 + 1, I25 + 1, I29, I30) [I27 = I28 /\ 1 = I26 /\ I27 <= 19] f3(I31, I32, I33, I34, I35) -> f2(I31, I32 + 1, I32 + 1, I36, I37) [I34 = I35 /\ 1 = I33 /\ 19 <= I34 - 1] f2(I38, I39, I40, I41, I42) -> f3(I38, I39, 0, 0, 0) [I39 = I40 /\ I39 <= 19] f1(I43, I44, I45, I46, I47) -> f2(0, 0, 0, I48, I49) We use the reverse value criterion with the projection function NU: NU[f3#(z1,z2,z3,z4,z5)] = 19 + -1 * z4 This gives the following inequalities: I13 <= 19 /\ y1 <= y2 - 1 /\ I15 <= 19 /\ 0 = I14 /\ I15 = I16 ==> 19 + -1 * I15 > 19 + -1 * (I15 + 1) with 19 + -1 * I15 >= 0 I18 <= 19 /\ I22 <= I23 - 1 /\ I20 <= 19 /\ 0 = I19 /\ I20 = I21 ==> 19 + -1 * I20 > 19 + -1 * (I20 + 1) with 19 + -1 * I20 >= 0 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed.