/export/starexec/sandbox2/solver/bin/starexec_run_Transition /export/starexec/sandbox2/benchmark/theBenchmark.smt2 /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE DP problem for innermost termination. P = init#(x1, x2) -> f1#(rnd1, rnd2) f5#(I0, I1) -> f5#(I0 - 1, I2) [0 <= I0 - 1] f1#(I3, I4) -> f5#(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] f4#(I7, I8) -> f3#(I9, 1) [I7 - 2 * I10 = 0 /\ 0 <= I8 - 1 /\ I9 <= I7 /\ I11 <= I8 - 1 /\ 0 <= I7 - 2 * I10 /\ I7 - 2 * I10 <= 1 /\ I7 - 2 * I9 <= 1 /\ 0 <= I7 - 2 * I9] f3#(I12, I13) -> f4#(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] f4#(I16, I17) -> f3#(I18, 1) [I16 - 2 * I19 = 1 /\ 0 <= I17 - 1 /\ I18 <= I16 /\ I20 <= I17 - 1 /\ 0 <= I16 - 2 * I19 /\ I16 - 2 * I19 <= 1 /\ I16 - 2 * I18 <= 1 /\ 0 <= I16 - 2 * I18] f3#(I21, I22) -> f4#(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] f4#(I26, I27) -> f3#(I28, 1) [I26 - 2 * I29 = 1 /\ 0 <= I27 - 1 /\ I30 <= I27 - 1 /\ I28 <= I26 /\ 0 <= I30 - 1 /\ 0 <= I26 - 2 * I29 /\ I26 - 2 * I29 <= 1 /\ I26 - 2 * I28 <= 1 /\ 0 <= I26 - 2 * I28] f3#(I31, I32) -> f4#(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] f4#(I36, I37) -> f3#(I38, 0) [I36 - 2 * I39 = 0 /\ 0 <= I37 - 1 /\ I40 <= I37 - 1 /\ I38 <= I36 /\ 0 <= I40 - 1 /\ 0 <= I36 - 2 * I39 /\ I36 - 2 * I39 <= 1 /\ I36 - 2 * I38 <= 1 /\ 0 <= I36 - 2 * I38] f3#(I41, I42) -> f4#(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] f2#(I46, I47) -> f3#(I46, 1) f2#(I48, I49) -> f3#(I48, 0) [0 <= I49 - 1] f1#(I50, I51) -> f2#(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] f1#(I55, I56) -> f2#(I57, I58) [-1 <= I59 - 1 /\ 1 <= I56 - 1 /\ -1 <= I57 - 1 /\ I58 <= I60 - 1 /\ -1 <= I60 - 1 /\ 0 <= I55 - 1] R = init(x1, x2) -> f1(rnd1, rnd2) f5(I0, I1) -> f5(I0 - 1, I2) [0 <= I0 - 1] f1(I3, I4) -> f5(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] f4(I7, I8) -> f3(I9, 1) [I7 - 2 * I10 = 0 /\ 0 <= I8 - 1 /\ I9 <= I7 /\ I11 <= I8 - 1 /\ 0 <= I7 - 2 * I10 /\ I7 - 2 * I10 <= 1 /\ I7 - 2 * I9 <= 1 /\ 0 <= I7 - 2 * I9] f3(I12, I13) -> f4(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] f4(I16, I17) -> f3(I18, 1) [I16 - 2 * I19 = 1 /\ 0 <= I17 - 1 /\ I18 <= I16 /\ I20 <= I17 - 1 /\ 0 <= I16 - 2 * I19 /\ I16 - 2 * I19 <= 1 /\ I16 - 2 * I18 <= 1 /\ 0 <= I16 - 2 * I18] f3(I21, I22) -> f4(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] f4(I26, I27) -> f3(I28, 1) [I26 - 2 * I29 = 1 /\ 0 <= I27 - 1 /\ I30 <= I27 - 1 /\ I28 <= I26 /\ 0 <= I30 - 1 /\ 0 <= I26 - 2 * I29 /\ I26 - 2 * I29 <= 1 /\ I26 - 2 * I28 <= 1 /\ 0 <= I26 - 2 * I28] f3(I31, I32) -> f4(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] f4(I36, I37) -> f3(I38, 0) [I36 - 2 * I39 = 0 /\ 0 <= I37 - 1 /\ I40 <= I37 - 1 /\ I38 <= I36 /\ 0 <= I40 - 1 /\ 0 <= I36 - 2 * I39 /\ I36 - 2 * I39 <= 1 /\ I36 - 2 * I38 <= 1 /\ 0 <= I36 - 2 * I38] f3(I41, I42) -> f4(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] f2(I46, I47) -> f3(I46, 1) f2(I48, I49) -> f3(I48, 0) [0 <= I49 - 1] f1(I50, I51) -> f2(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] f1(I55, I56) -> f2(I57, I58) [-1 <= I59 - 1 /\ 1 <= I56 - 1 /\ -1 <= I57 - 1 /\ I58 <= I60 - 1 /\ -1 <= I60 - 1 /\ 0 <= I55 - 1] The dependency graph for this problem is: 0 -> 2, 13, 14 1 -> 1 2 -> 1 3 -> 4, 6 4 -> 3, 9 5 -> 4, 6 6 -> 5, 7 7 -> 4, 6 8 -> 5, 7 9 -> 10 -> 3, 9 11 -> 4, 6 12 -> 13 -> 11 14 -> 11, 12 Where: 0) init#(x1, x2) -> f1#(rnd1, rnd2) 1) f5#(I0, I1) -> f5#(I0 - 1, I2) [0 <= I0 - 1] 2) f1#(I3, I4) -> f5#(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] 3) f4#(I7, I8) -> f3#(I9, 1) [I7 - 2 * I10 = 0 /\ 0 <= I8 - 1 /\ I9 <= I7 /\ I11 <= I8 - 1 /\ 0 <= I7 - 2 * I10 /\ I7 - 2 * I10 <= 1 /\ I7 - 2 * I9 <= 1 /\ 0 <= I7 - 2 * I9] 4) f3#(I12, I13) -> f4#(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] 5) f4#(I16, I17) -> f3#(I18, 1) [I16 - 2 * I19 = 1 /\ 0 <= I17 - 1 /\ I18 <= I16 /\ I20 <= I17 - 1 /\ 0 <= I16 - 2 * I19 /\ I16 - 2 * I19 <= 1 /\ I16 - 2 * I18 <= 1 /\ 0 <= I16 - 2 * I18] 6) f3#(I21, I22) -> f4#(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] 7) f4#(I26, I27) -> f3#(I28, 1) [I26 - 2 * I29 = 1 /\ 0 <= I27 - 1 /\ I30 <= I27 - 1 /\ I28 <= I26 /\ 0 <= I30 - 1 /\ 0 <= I26 - 2 * I29 /\ I26 - 2 * I29 <= 1 /\ I26 - 2 * I28 <= 1 /\ 0 <= I26 - 2 * I28] 8) f3#(I31, I32) -> f4#(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] 9) f4#(I36, I37) -> f3#(I38, 0) [I36 - 2 * I39 = 0 /\ 0 <= I37 - 1 /\ I40 <= I37 - 1 /\ I38 <= I36 /\ 0 <= I40 - 1 /\ 0 <= I36 - 2 * I39 /\ I36 - 2 * I39 <= 1 /\ I36 - 2 * I38 <= 1 /\ 0 <= I36 - 2 * I38] 10) f3#(I41, I42) -> f4#(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] 11) f2#(I46, I47) -> f3#(I46, 1) 12) f2#(I48, I49) -> f3#(I48, 0) [0 <= I49 - 1] 13) f1#(I50, I51) -> f2#(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] 14) f1#(I55, I56) -> f2#(I57, I58) [-1 <= I59 - 1 /\ 1 <= I56 - 1 /\ -1 <= I57 - 1 /\ I58 <= I60 - 1 /\ -1 <= I60 - 1 /\ 0 <= I55 - 1] We have the following SCCs. { 1 } { 3, 4, 5, 6, 7 } DP problem for innermost termination. P = f4#(I7, I8) -> f3#(I9, 1) [I7 - 2 * I10 = 0 /\ 0 <= I8 - 1 /\ I9 <= I7 /\ I11 <= I8 - 1 /\ 0 <= I7 - 2 * I10 /\ I7 - 2 * I10 <= 1 /\ I7 - 2 * I9 <= 1 /\ 0 <= I7 - 2 * I9] f3#(I12, I13) -> f4#(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] f4#(I16, I17) -> f3#(I18, 1) [I16 - 2 * I19 = 1 /\ 0 <= I17 - 1 /\ I18 <= I16 /\ I20 <= I17 - 1 /\ 0 <= I16 - 2 * I19 /\ I16 - 2 * I19 <= 1 /\ I16 - 2 * I18 <= 1 /\ 0 <= I16 - 2 * I18] f3#(I21, I22) -> f4#(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] f4#(I26, I27) -> f3#(I28, 1) [I26 - 2 * I29 = 1 /\ 0 <= I27 - 1 /\ I30 <= I27 - 1 /\ I28 <= I26 /\ 0 <= I30 - 1 /\ 0 <= I26 - 2 * I29 /\ I26 - 2 * I29 <= 1 /\ I26 - 2 * I28 <= 1 /\ 0 <= I26 - 2 * I28] R = init(x1, x2) -> f1(rnd1, rnd2) f5(I0, I1) -> f5(I0 - 1, I2) [0 <= I0 - 1] f1(I3, I4) -> f5(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] f4(I7, I8) -> f3(I9, 1) [I7 - 2 * I10 = 0 /\ 0 <= I8 - 1 /\ I9 <= I7 /\ I11 <= I8 - 1 /\ 0 <= I7 - 2 * I10 /\ I7 - 2 * I10 <= 1 /\ I7 - 2 * I9 <= 1 /\ 0 <= I7 - 2 * I9] f3(I12, I13) -> f4(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] f4(I16, I17) -> f3(I18, 1) [I16 - 2 * I19 = 1 /\ 0 <= I17 - 1 /\ I18 <= I16 /\ I20 <= I17 - 1 /\ 0 <= I16 - 2 * I19 /\ I16 - 2 * I19 <= 1 /\ I16 - 2 * I18 <= 1 /\ 0 <= I16 - 2 * I18] f3(I21, I22) -> f4(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] f4(I26, I27) -> f3(I28, 1) [I26 - 2 * I29 = 1 /\ 0 <= I27 - 1 /\ I30 <= I27 - 1 /\ I28 <= I26 /\ 0 <= I30 - 1 /\ 0 <= I26 - 2 * I29 /\ I26 - 2 * I29 <= 1 /\ I26 - 2 * I28 <= 1 /\ 0 <= I26 - 2 * I28] f3(I31, I32) -> f4(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] f4(I36, I37) -> f3(I38, 0) [I36 - 2 * I39 = 0 /\ 0 <= I37 - 1 /\ I40 <= I37 - 1 /\ I38 <= I36 /\ 0 <= I40 - 1 /\ 0 <= I36 - 2 * I39 /\ I36 - 2 * I39 <= 1 /\ I36 - 2 * I38 <= 1 /\ 0 <= I36 - 2 * I38] f3(I41, I42) -> f4(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] f2(I46, I47) -> f3(I46, 1) f2(I48, I49) -> f3(I48, 0) [0 <= I49 - 1] f1(I50, I51) -> f2(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] f1(I55, I56) -> f2(I57, I58) [-1 <= I59 - 1 /\ 1 <= I56 - 1 /\ -1 <= I57 - 1 /\ I58 <= I60 - 1 /\ -1 <= I60 - 1 /\ 0 <= I55 - 1] We use the basic value criterion with the projection function NU: NU[f3#(z1,z2)] = z2 NU[f4#(z1,z2)] = z2 This gives the following inequalities: I7 - 2 * I10 = 0 /\ 0 <= I8 - 1 /\ I9 <= I7 /\ I11 <= I8 - 1 /\ 0 <= I7 - 2 * I10 /\ I7 - 2 * I10 <= 1 /\ I7 - 2 * I9 <= 1 /\ 0 <= I7 - 2 * I9 ==> I8 (>! \union =) 1 I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12 ==> I13 (>! \union =) I13 I16 - 2 * I19 = 1 /\ 0 <= I17 - 1 /\ I18 <= I16 /\ I20 <= I17 - 1 /\ 0 <= I16 - 2 * I19 /\ I16 - 2 * I19 <= 1 /\ I16 - 2 * I18 <= 1 /\ 0 <= I16 - 2 * I18 ==> I17 (>! \union =) 1 I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21 ==> I22 (>! \union =) I22 I26 - 2 * I29 = 1 /\ 0 <= I27 - 1 /\ I30 <= I27 - 1 /\ I28 <= I26 /\ 0 <= I30 - 1 /\ 0 <= I26 - 2 * I29 /\ I26 - 2 * I29 <= 1 /\ I26 - 2 * I28 <= 1 /\ 0 <= I26 - 2 * I28 ==> I27 >! 1 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = f4#(I7, I8) -> f3#(I9, 1) [I7 - 2 * I10 = 0 /\ 0 <= I8 - 1 /\ I9 <= I7 /\ I11 <= I8 - 1 /\ 0 <= I7 - 2 * I10 /\ I7 - 2 * I10 <= 1 /\ I7 - 2 * I9 <= 1 /\ 0 <= I7 - 2 * I9] f3#(I12, I13) -> f4#(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] f4#(I16, I17) -> f3#(I18, 1) [I16 - 2 * I19 = 1 /\ 0 <= I17 - 1 /\ I18 <= I16 /\ I20 <= I17 - 1 /\ 0 <= I16 - 2 * I19 /\ I16 - 2 * I19 <= 1 /\ I16 - 2 * I18 <= 1 /\ 0 <= I16 - 2 * I18] f3#(I21, I22) -> f4#(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] R = init(x1, x2) -> f1(rnd1, rnd2) f5(I0, I1) -> f5(I0 - 1, I2) [0 <= I0 - 1] f1(I3, I4) -> f5(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] f4(I7, I8) -> f3(I9, 1) [I7 - 2 * I10 = 0 /\ 0 <= I8 - 1 /\ I9 <= I7 /\ I11 <= I8 - 1 /\ 0 <= I7 - 2 * I10 /\ I7 - 2 * I10 <= 1 /\ I7 - 2 * I9 <= 1 /\ 0 <= I7 - 2 * I9] f3(I12, I13) -> f4(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] f4(I16, I17) -> f3(I18, 1) [I16 - 2 * I19 = 1 /\ 0 <= I17 - 1 /\ I18 <= I16 /\ I20 <= I17 - 1 /\ 0 <= I16 - 2 * I19 /\ I16 - 2 * I19 <= 1 /\ I16 - 2 * I18 <= 1 /\ 0 <= I16 - 2 * I18] f3(I21, I22) -> f4(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] f4(I26, I27) -> f3(I28, 1) [I26 - 2 * I29 = 1 /\ 0 <= I27 - 1 /\ I30 <= I27 - 1 /\ I28 <= I26 /\ 0 <= I30 - 1 /\ 0 <= I26 - 2 * I29 /\ I26 - 2 * I29 <= 1 /\ I26 - 2 * I28 <= 1 /\ 0 <= I26 - 2 * I28] f3(I31, I32) -> f4(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] f4(I36, I37) -> f3(I38, 0) [I36 - 2 * I39 = 0 /\ 0 <= I37 - 1 /\ I40 <= I37 - 1 /\ I38 <= I36 /\ 0 <= I40 - 1 /\ 0 <= I36 - 2 * I39 /\ I36 - 2 * I39 <= 1 /\ I36 - 2 * I38 <= 1 /\ 0 <= I36 - 2 * I38] f3(I41, I42) -> f4(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] f2(I46, I47) -> f3(I46, 1) f2(I48, I49) -> f3(I48, 0) [0 <= I49 - 1] f1(I50, I51) -> f2(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] f1(I55, I56) -> f2(I57, I58) [-1 <= I59 - 1 /\ 1 <= I56 - 1 /\ -1 <= I57 - 1 /\ I58 <= I60 - 1 /\ -1 <= I60 - 1 /\ 0 <= I55 - 1]