/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, x6, x7, x8) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8) f2#(I0, I1, I2, I3, I4, I5, I6, I7) -> f2#(I8, I9, I10, I11, I12, I5, I6 + 2, I5) [I3 + 2 * I9 - I10 = I12 /\ I3 + 2 * I9 - I10 = I11 /\ I5 = I7 /\ I3 = I4 /\ 0 <= I8 - 1 /\ 0 <= I0 - 1 /\ I8 <= I0 /\ 0 <= I3 + 2 * I9 /\ 2 * I9 - I10 <= 2 * I1 - I2 - 1 /\ 0 <= 2 * I9 /\ 0 <= 2 * I1 /\ -1 <= I2 - 1 /\ -1 <= I10 - 1 /\ -1 <= I9 - 1 /\ -1 <= I6 - 1 /\ -1 <= I3 - 1 /\ I6 + 1 <= I5 - 1 /\ -1 <= I5 - 1] f2#(I13, I14, I15, I16, I17, I18, I19, I20) -> f2#(I21, I22, 0, I23, I24, I18, I19 + 1, I18) [I16 + 2 * I22 = I24 /\ I16 + 2 * I22 = I23 /\ I18 = I20 /\ I16 = I17 /\ 0 <= I21 - 1 /\ 0 <= I13 - 1 /\ I21 <= I13 /\ 0 <= I16 + 2 * I22 /\ 2 * I22 <= 2 * I14 - I15 - 1 /\ 0 <= 2 * I22 /\ 0 <= 2 * I14 /\ -1 <= I15 - 1 /\ I18 <= I19 + 1 /\ -1 <= I22 - 1 /\ I19 <= I18 - 1 /\ -1 <= I19 - 1 /\ -1 <= I18 - 1 /\ -1 <= I16 - 1] f2#(I25, I26, I27, I28, I29, I30, I31, I32) -> f2#(I33, 0, 0, I28, I28, I30, I31, I30) [I30 = I32 /\ I28 = I29 /\ 0 <= I33 - 1 /\ 0 <= I25 - 1 /\ I33 <= I25 /\ 0 <= 2 * I26 - I27 - 1 /\ 0 <= 2 * I26 /\ -1 <= I27 - 1 /\ I30 <= I31 /\ -1 <= I30 - 1 /\ -1 <= I28 - 1] f1#(I34, I35, I36, I37, I38, I39, I40, I41) -> f2#(I42, I43, I44, I45, I46, I35, 3, I35) [I45 = I46 /\ 0 <= I42 - 1 /\ 0 <= I34 - 1 /\ I42 <= I34 /\ -1 <= I44 - 1 /\ -1 <= I45 - 1 /\ 2 <= I35 - 1 /\ -1 <= I43 - 1] f1#(I47, I48, I49, I50, I51, I52, I53, I54) -> f2#(I55, I56, I57, 0, 0, 2, 2, 2) [2 = I48 /\ 0 <= I55 - 1 /\ 0 <= I47 - 1 /\ I55 <= I47 /\ -1 <= I57 - 1 /\ -1 <= I56 - 1] f1#(I58, I59, I60, I61, I62, I63, I64, I65) -> f2#(I66, I67, 0, 0, 0, 1, 1, 1) [1 = I59 /\ 0 <= I66 - 1 /\ 0 <= I58 - 1 /\ -1 <= I67 - 1 /\ I66 <= I58] f1#(I68, I69, I70, I71, I72, I73, I74, I75) -> f2#(I76, 0, 0, 0, 0, 0, 0, 0) [0 = I69 /\ 0 <= I76 - 1 /\ 0 <= I68 - 1 /\ I76 <= I68] R = init(x1, x2, x3, x4, x5, x6, x7, x8) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8) f2(I0, I1, I2, I3, I4, I5, I6, I7) -> f2(I8, I9, I10, I11, I12, I5, I6 + 2, I5) [I3 + 2 * I9 - I10 = I12 /\ I3 + 2 * I9 - I10 = I11 /\ I5 = I7 /\ I3 = I4 /\ 0 <= I8 - 1 /\ 0 <= I0 - 1 /\ I8 <= I0 /\ 0 <= I3 + 2 * I9 /\ 2 * I9 - I10 <= 2 * I1 - I2 - 1 /\ 0 <= 2 * I9 /\ 0 <= 2 * I1 /\ -1 <= I2 - 1 /\ -1 <= I10 - 1 /\ -1 <= I9 - 1 /\ -1 <= I6 - 1 /\ -1 <= I3 - 1 /\ I6 + 1 <= I5 - 1 /\ -1 <= I5 - 1] f2(I13, I14, I15, I16, I17, I18, I19, I20) -> f2(I21, I22, 0, I23, I24, I18, I19 + 1, I18) [I16 + 2 * I22 = I24 /\ I16 + 2 * I22 = I23 /\ I18 = I20 /\ I16 = I17 /\ 0 <= I21 - 1 /\ 0 <= I13 - 1 /\ I21 <= I13 /\ 0 <= I16 + 2 * I22 /\ 2 * I22 <= 2 * I14 - I15 - 1 /\ 0 <= 2 * I22 /\ 0 <= 2 * I14 /\ -1 <= I15 - 1 /\ I18 <= I19 + 1 /\ -1 <= I22 - 1 /\ I19 <= I18 - 1 /\ -1 <= I19 - 1 /\ -1 <= I18 - 1 /\ -1 <= I16 - 1] f2(I25, I26, I27, I28, I29, I30, I31, I32) -> f2(I33, 0, 0, I28, I28, I30, I31, I30) [I30 = I32 /\ I28 = I29 /\ 0 <= I33 - 1 /\ 0 <= I25 - 1 /\ I33 <= I25 /\ 0 <= 2 * I26 - I27 - 1 /\ 0 <= 2 * I26 /\ -1 <= I27 - 1 /\ I30 <= I31 /\ -1 <= I30 - 1 /\ -1 <= I28 - 1] f1(I34, I35, I36, I37, I38, I39, I40, I41) -> f2(I42, I43, I44, I45, I46, I35, 3, I35) [I45 = I46 /\ 0 <= I42 - 1 /\ 0 <= I34 - 1 /\ I42 <= I34 /\ -1 <= I44 - 1 /\ -1 <= I45 - 1 /\ 2 <= I35 - 1 /\ -1 <= I43 - 1] f1(I47, I48, I49, I50, I51, I52, I53, I54) -> f2(I55, I56, I57, 0, 0, 2, 2, 2) [2 = I48 /\ 0 <= I55 - 1 /\ 0 <= I47 - 1 /\ I55 <= I47 /\ -1 <= I57 - 1 /\ -1 <= I56 - 1] f1(I58, I59, I60, I61, I62, I63, I64, I65) -> f2(I66, I67, 0, 0, 0, 1, 1, 1) [1 = I59 /\ 0 <= I66 - 1 /\ 0 <= I58 - 1 /\ -1 <= I67 - 1 /\ I66 <= I58] f1(I68, I69, I70, I71, I72, I73, I74, I75) -> f2(I76, 0, 0, 0, 0, 0, 0, 0) [0 = I69 /\ 0 <= I76 - 1 /\ 0 <= I68 - 1 /\ I76 <= I68] The dependency graph for this problem is: 0 -> 4, 5, 6, 7 1 -> 1, 2, 3 2 -> 3 3 -> 4 -> 1, 2, 3 5 -> 3 6 -> 3 7 -> Where: 0) init#(x1, x2, x3, x4, x5, x6, x7, x8) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8) 1) f2#(I0, I1, I2, I3, I4, I5, I6, I7) -> f2#(I8, I9, I10, I11, I12, I5, I6 + 2, I5) [I3 + 2 * I9 - I10 = I12 /\ I3 + 2 * I9 - I10 = I11 /\ I5 = I7 /\ I3 = I4 /\ 0 <= I8 - 1 /\ 0 <= I0 - 1 /\ I8 <= I0 /\ 0 <= I3 + 2 * I9 /\ 2 * I9 - I10 <= 2 * I1 - I2 - 1 /\ 0 <= 2 * I9 /\ 0 <= 2 * I1 /\ -1 <= I2 - 1 /\ -1 <= I10 - 1 /\ -1 <= I9 - 1 /\ -1 <= I6 - 1 /\ -1 <= I3 - 1 /\ I6 + 1 <= I5 - 1 /\ -1 <= I5 - 1] 2) f2#(I13, I14, I15, I16, I17, I18, I19, I20) -> f2#(I21, I22, 0, I23, I24, I18, I19 + 1, I18) [I16 + 2 * I22 = I24 /\ I16 + 2 * I22 = I23 /\ I18 = I20 /\ I16 = I17 /\ 0 <= I21 - 1 /\ 0 <= I13 - 1 /\ I21 <= I13 /\ 0 <= I16 + 2 * I22 /\ 2 * I22 <= 2 * I14 - I15 - 1 /\ 0 <= 2 * I22 /\ 0 <= 2 * I14 /\ -1 <= I15 - 1 /\ I18 <= I19 + 1 /\ -1 <= I22 - 1 /\ I19 <= I18 - 1 /\ -1 <= I19 - 1 /\ -1 <= I18 - 1 /\ -1 <= I16 - 1] 3) f2#(I25, I26, I27, I28, I29, I30, I31, I32) -> f2#(I33, 0, 0, I28, I28, I30, I31, I30) [I30 = I32 /\ I28 = I29 /\ 0 <= I33 - 1 /\ 0 <= I25 - 1 /\ I33 <= I25 /\ 0 <= 2 * I26 - I27 - 1 /\ 0 <= 2 * I26 /\ -1 <= I27 - 1 /\ I30 <= I31 /\ -1 <= I30 - 1 /\ -1 <= I28 - 1] 4) f1#(I34, I35, I36, I37, I38, I39, I40, I41) -> f2#(I42, I43, I44, I45, I46, I35, 3, I35) [I45 = I46 /\ 0 <= I42 - 1 /\ 0 <= I34 - 1 /\ I42 <= I34 /\ -1 <= I44 - 1 /\ -1 <= I45 - 1 /\ 2 <= I35 - 1 /\ -1 <= I43 - 1] 5) f1#(I47, I48, I49, I50, I51, I52, I53, I54) -> f2#(I55, I56, I57, 0, 0, 2, 2, 2) [2 = I48 /\ 0 <= I55 - 1 /\ 0 <= I47 - 1 /\ I55 <= I47 /\ -1 <= I57 - 1 /\ -1 <= I56 - 1] 6) f1#(I58, I59, I60, I61, I62, I63, I64, I65) -> f2#(I66, I67, 0, 0, 0, 1, 1, 1) [1 = I59 /\ 0 <= I66 - 1 /\ 0 <= I58 - 1 /\ -1 <= I67 - 1 /\ I66 <= I58] 7) f1#(I68, I69, I70, I71, I72, I73, I74, I75) -> f2#(I76, 0, 0, 0, 0, 0, 0, 0) [0 = I69 /\ 0 <= I76 - 1 /\ 0 <= I68 - 1 /\ I76 <= I68] We have the following SCCs. { 1 } DP problem for innermost termination. P = f2#(I0, I1, I2, I3, I4, I5, I6, I7) -> f2#(I8, I9, I10, I11, I12, I5, I6 + 2, I5) [I3 + 2 * I9 - I10 = I12 /\ I3 + 2 * I9 - I10 = I11 /\ I5 = I7 /\ I3 = I4 /\ 0 <= I8 - 1 /\ 0 <= I0 - 1 /\ I8 <= I0 /\ 0 <= I3 + 2 * I9 /\ 2 * I9 - I10 <= 2 * I1 - I2 - 1 /\ 0 <= 2 * I9 /\ 0 <= 2 * I1 /\ -1 <= I2 - 1 /\ -1 <= I10 - 1 /\ -1 <= I9 - 1 /\ -1 <= I6 - 1 /\ -1 <= I3 - 1 /\ I6 + 1 <= I5 - 1 /\ -1 <= I5 - 1] R = init(x1, x2, x3, x4, x5, x6, x7, x8) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8) f2(I0, I1, I2, I3, I4, I5, I6, I7) -> f2(I8, I9, I10, I11, I12, I5, I6 + 2, I5) [I3 + 2 * I9 - I10 = I12 /\ I3 + 2 * I9 - I10 = I11 /\ I5 = I7 /\ I3 = I4 /\ 0 <= I8 - 1 /\ 0 <= I0 - 1 /\ I8 <= I0 /\ 0 <= I3 + 2 * I9 /\ 2 * I9 - I10 <= 2 * I1 - I2 - 1 /\ 0 <= 2 * I9 /\ 0 <= 2 * I1 /\ -1 <= I2 - 1 /\ -1 <= I10 - 1 /\ -1 <= I9 - 1 /\ -1 <= I6 - 1 /\ -1 <= I3 - 1 /\ I6 + 1 <= I5 - 1 /\ -1 <= I5 - 1] f2(I13, I14, I15, I16, I17, I18, I19, I20) -> f2(I21, I22, 0, I23, I24, I18, I19 + 1, I18) [I16 + 2 * I22 = I24 /\ I16 + 2 * I22 = I23 /\ I18 = I20 /\ I16 = I17 /\ 0 <= I21 - 1 /\ 0 <= I13 - 1 /\ I21 <= I13 /\ 0 <= I16 + 2 * I22 /\ 2 * I22 <= 2 * I14 - I15 - 1 /\ 0 <= 2 * I22 /\ 0 <= 2 * I14 /\ -1 <= I15 - 1 /\ I18 <= I19 + 1 /\ -1 <= I22 - 1 /\ I19 <= I18 - 1 /\ -1 <= I19 - 1 /\ -1 <= I18 - 1 /\ -1 <= I16 - 1] f2(I25, I26, I27, I28, I29, I30, I31, I32) -> f2(I33, 0, 0, I28, I28, I30, I31, I30) [I30 = I32 /\ I28 = I29 /\ 0 <= I33 - 1 /\ 0 <= I25 - 1 /\ I33 <= I25 /\ 0 <= 2 * I26 - I27 - 1 /\ 0 <= 2 * I26 /\ -1 <= I27 - 1 /\ I30 <= I31 /\ -1 <= I30 - 1 /\ -1 <= I28 - 1] f1(I34, I35, I36, I37, I38, I39, I40, I41) -> f2(I42, I43, I44, I45, I46, I35, 3, I35) [I45 = I46 /\ 0 <= I42 - 1 /\ 0 <= I34 - 1 /\ I42 <= I34 /\ -1 <= I44 - 1 /\ -1 <= I45 - 1 /\ 2 <= I35 - 1 /\ -1 <= I43 - 1] f1(I47, I48, I49, I50, I51, I52, I53, I54) -> f2(I55, I56, I57, 0, 0, 2, 2, 2) [2 = I48 /\ 0 <= I55 - 1 /\ 0 <= I47 - 1 /\ I55 <= I47 /\ -1 <= I57 - 1 /\ -1 <= I56 - 1] f1(I58, I59, I60, I61, I62, I63, I64, I65) -> f2(I66, I67, 0, 0, 0, 1, 1, 1) [1 = I59 /\ 0 <= I66 - 1 /\ 0 <= I58 - 1 /\ -1 <= I67 - 1 /\ I66 <= I58] f1(I68, I69, I70, I71, I72, I73, I74, I75) -> f2(I76, 0, 0, 0, 0, 0, 0, 0) [0 = I69 /\ 0 <= I76 - 1 /\ 0 <= I68 - 1 /\ I76 <= I68] We use the reverse value criterion with the projection function NU: NU[f2#(z1,z2,z3,z4,z5,z6,z7,z8)] = z6 - 1 + -1 * (z7 + 1) This gives the following inequalities: I3 + 2 * I9 - I10 = I12 /\ I3 + 2 * I9 - I10 = I11 /\ I5 = I7 /\ I3 = I4 /\ 0 <= I8 - 1 /\ 0 <= I0 - 1 /\ I8 <= I0 /\ 0 <= I3 + 2 * I9 /\ 2 * I9 - I10 <= 2 * I1 - I2 - 1 /\ 0 <= 2 * I9 /\ 0 <= 2 * I1 /\ -1 <= I2 - 1 /\ -1 <= I10 - 1 /\ -1 <= I9 - 1 /\ -1 <= I6 - 1 /\ -1 <= I3 - 1 /\ I6 + 1 <= I5 - 1 /\ -1 <= I5 - 1 ==> I5 - 1 + -1 * (I6 + 1) > I5 - 1 + -1 * (I6 + 2 + 1) with I5 - 1 + -1 * (I6 + 1) >= 0 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed.