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