14.43/14.33 YES 14.43/14.33 14.43/14.33 DP problem for innermost termination. 14.43/14.33 P = 14.43/14.33 init#(x1, x2, x3, x4) -> f1#(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 f7#(I0, I1, I2, I3) -> f7#(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7#(I5, I6, I7, I8) -> f6#(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6#(I11, I12, I13, I14) -> f7#(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 f5#(I16, I17, I18, I19) -> f6#(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 f3#(I22, I23, I24, I25) -> f5#(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 f4#(I29, I30, I31, I32) -> f4#(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4#(I35, I36, I37, I38) -> f3#(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3#(I41, I42, I43, I44) -> f4#(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 f2#(I46, I47, I48, I49) -> f3#(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 f1#(I55, I56, I57, I58) -> f2#(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 R = 14.43/14.33 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 f7(I0, I1, I2, I3) -> f7(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7(I5, I6, I7, I8) -> f6(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6(I11, I12, I13, I14) -> f7(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 f5(I16, I17, I18, I19) -> f6(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 f3(I22, I23, I24, I25) -> f5(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 f4(I29, I30, I31, I32) -> f4(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4(I35, I36, I37, I38) -> f3(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3(I41, I42, I43, I44) -> f4(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 f2(I46, I47, I48, I49) -> f3(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 f1(I55, I56, I57, I58) -> f2(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 14.43/14.33 The dependency graph for this problem is: 14.43/14.33 0 -> 10 14.43/14.33 1 -> 1, 2 14.43/14.33 2 -> 3 14.43/14.33 3 -> 1, 2 14.43/14.33 4 -> 3 14.43/14.33 5 -> 4 14.43/14.33 6 -> 6, 7 14.43/14.33 7 -> 5, 8 14.43/14.33 8 -> 6 14.43/14.33 9 -> 8 14.43/14.33 10 -> 9 14.43/14.33 Where: 14.43/14.33 0) init#(x1, x2, x3, x4) -> f1#(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 1) f7#(I0, I1, I2, I3) -> f7#(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 2) f7#(I5, I6, I7, I8) -> f6#(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 3) f6#(I11, I12, I13, I14) -> f7#(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 4) f5#(I16, I17, I18, I19) -> f6#(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 5) f3#(I22, I23, I24, I25) -> f5#(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 6) f4#(I29, I30, I31, I32) -> f4#(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 7) f4#(I35, I36, I37, I38) -> f3#(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 8) f3#(I41, I42, I43, I44) -> f4#(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 9) f2#(I46, I47, I48, I49) -> f3#(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 10) f1#(I55, I56, I57, I58) -> f2#(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 14.43/14.33 We have the following SCCs. 14.43/14.33 { 6, 7, 8 } 14.43/14.33 { 1, 2, 3 } 14.43/14.33 14.43/14.33 DP problem for innermost termination. 14.43/14.33 P = 14.43/14.33 f7#(I0, I1, I2, I3) -> f7#(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7#(I5, I6, I7, I8) -> f6#(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6#(I11, I12, I13, I14) -> f7#(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 R = 14.43/14.33 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 f7(I0, I1, I2, I3) -> f7(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7(I5, I6, I7, I8) -> f6(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6(I11, I12, I13, I14) -> f7(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 f5(I16, I17, I18, I19) -> f6(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 f3(I22, I23, I24, I25) -> f5(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 f4(I29, I30, I31, I32) -> f4(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4(I35, I36, I37, I38) -> f3(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3(I41, I42, I43, I44) -> f4(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 f2(I46, I47, I48, I49) -> f3(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 f1(I55, I56, I57, I58) -> f2(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 14.43/14.33 We use the reverse value criterion with the projection function NU: 14.43/14.33 NU[f6#(z1,z2,z3,z4)] = z3 - 1 + -1 * z2 14.43/14.33 NU[f7#(z1,z2,z3,z4)] = z4 - 1 + -1 * (z2 + 1) 14.43/14.33 14.43/14.33 This gives the following inequalities: 14.43/14.33 I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0 ==> I3 - 1 + -1 * (I1 + 1) >= I3 - 1 + -1 * (I1 + 1) 14.43/14.33 I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5 ==> I8 - 1 + -1 * (I6 + 1) >= I8 - 1 + -1 * (I6 + 1) 14.43/14.33 I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11 ==> I13 - 1 + -1 * I12 > I13 - 1 + -1 * (I12 + 1) with I13 - 1 + -1 * I12 >= 0 14.43/14.33 14.43/14.33 We remove all the strictly oriented dependency pairs. 14.43/14.33 14.43/14.33 DP problem for innermost termination. 14.43/14.33 P = 14.43/14.33 f7#(I0, I1, I2, I3) -> f7#(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7#(I5, I6, I7, I8) -> f6#(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 R = 14.43/14.33 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 f7(I0, I1, I2, I3) -> f7(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7(I5, I6, I7, I8) -> f6(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6(I11, I12, I13, I14) -> f7(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 f5(I16, I17, I18, I19) -> f6(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 f3(I22, I23, I24, I25) -> f5(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 f4(I29, I30, I31, I32) -> f4(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4(I35, I36, I37, I38) -> f3(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3(I41, I42, I43, I44) -> f4(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 f2(I46, I47, I48, I49) -> f3(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 f1(I55, I56, I57, I58) -> f2(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 14.43/14.33 The dependency graph for this problem is: 14.43/14.33 1 -> 1, 2 14.43/14.33 2 -> 14.43/14.33 Where: 14.43/14.33 1) f7#(I0, I1, I2, I3) -> f7#(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 2) f7#(I5, I6, I7, I8) -> f6#(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 14.43/14.33 We have the following SCCs. 14.43/14.33 { 1 } 14.43/14.33 14.43/14.33 DP problem for innermost termination. 14.43/14.33 P = 14.43/14.33 f7#(I0, I1, I2, I3) -> f7#(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 R = 14.43/14.33 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 f7(I0, I1, I2, I3) -> f7(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7(I5, I6, I7, I8) -> f6(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6(I11, I12, I13, I14) -> f7(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 f5(I16, I17, I18, I19) -> f6(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 f3(I22, I23, I24, I25) -> f5(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 f4(I29, I30, I31, I32) -> f4(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4(I35, I36, I37, I38) -> f3(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3(I41, I42, I43, I44) -> f4(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 f2(I46, I47, I48, I49) -> f3(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 f1(I55, I56, I57, I58) -> f2(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 14.43/14.33 We use the reverse value criterion with the projection function NU: 14.43/14.33 NU[f7#(z1,z2,z3,z4)] = z4 - 1 + -1 * z3 14.43/14.33 14.43/14.33 This gives the following inequalities: 14.43/14.33 I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0 ==> I3 - 1 + -1 * I2 > I3 - 1 + -1 * (I2 + 1) with I3 - 1 + -1 * I2 >= 0 14.43/14.33 14.43/14.33 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. 14.43/14.33 14.43/14.33 DP problem for innermost termination. 14.43/14.33 P = 14.43/14.33 f4#(I29, I30, I31, I32) -> f4#(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4#(I35, I36, I37, I38) -> f3#(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3#(I41, I42, I43, I44) -> f4#(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 R = 14.43/14.33 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 f7(I0, I1, I2, I3) -> f7(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7(I5, I6, I7, I8) -> f6(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6(I11, I12, I13, I14) -> f7(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 f5(I16, I17, I18, I19) -> f6(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 f3(I22, I23, I24, I25) -> f5(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 f4(I29, I30, I31, I32) -> f4(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4(I35, I36, I37, I38) -> f3(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3(I41, I42, I43, I44) -> f4(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 f2(I46, I47, I48, I49) -> f3(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 f1(I55, I56, I57, I58) -> f2(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 14.43/14.33 We use the reverse value criterion with the projection function NU: 14.43/14.33 NU[f3#(z1,z2,z3,z4)] = 2 + -1 * z2 14.43/14.33 NU[f4#(z1,z2,z3,z4)] = 2 + -1 * (z2 + 1) 14.43/14.33 14.43/14.33 This gives the following inequalities: 14.43/14.33 I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29 ==> 2 + -1 * (I30 + 1) >= 2 + -1 * (I30 + 1) 14.43/14.33 I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35 ==> 2 + -1 * (I36 + 1) >= 2 + -1 * (I36 + 1) 14.43/14.33 I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41 ==> 2 + -1 * I42 > 2 + -1 * (I42 + 1) with 2 + -1 * I42 >= 0 14.43/14.33 14.43/14.33 We remove all the strictly oriented dependency pairs. 14.43/14.33 14.43/14.33 DP problem for innermost termination. 14.43/14.33 P = 14.43/14.33 f4#(I29, I30, I31, I32) -> f4#(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4#(I35, I36, I37, I38) -> f3#(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 R = 14.43/14.33 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 f7(I0, I1, I2, I3) -> f7(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7(I5, I6, I7, I8) -> f6(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6(I11, I12, I13, I14) -> f7(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 f5(I16, I17, I18, I19) -> f6(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 f3(I22, I23, I24, I25) -> f5(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 f4(I29, I30, I31, I32) -> f4(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4(I35, I36, I37, I38) -> f3(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3(I41, I42, I43, I44) -> f4(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 f2(I46, I47, I48, I49) -> f3(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 f1(I55, I56, I57, I58) -> f2(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 14.43/14.33 The dependency graph for this problem is: 14.43/14.33 6 -> 6, 7 14.43/14.33 7 -> 14.43/14.33 Where: 14.43/14.33 6) f4#(I29, I30, I31, I32) -> f4#(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 7) f4#(I35, I36, I37, I38) -> f3#(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 14.43/14.33 We have the following SCCs. 14.43/14.33 { 6 } 14.43/14.33 14.43/14.33 DP problem for innermost termination. 14.43/14.33 P = 14.43/14.33 f4#(I29, I30, I31, I32) -> f4#(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 R = 14.43/14.33 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 14.43/14.33 f7(I0, I1, I2, I3) -> f7(I4, I1, I2 + 1, I3) [I3 + 4 <= I0 /\ 2 <= I4 - 1 /\ 2 <= I0 - 1 /\ I2 <= I3 - 1 /\ I4 <= I0] 14.43/14.33 f7(I5, I6, I7, I8) -> f6(I9, I6 + 1, I8, I10) [I8 + 4 <= I5 /\ 2 <= I9 - 1 /\ 2 <= I5 - 1 /\ I8 <= I7 /\ I9 <= I5] 14.43/14.33 f6(I11, I12, I13, I14) -> f7(I15, I12, 0, I13) [I13 + 4 <= I11 /\ 2 <= I15 - 1 /\ 2 <= I11 - 1 /\ I12 <= I13 - 1 /\ I15 <= I11] 14.43/14.33 f5(I16, I17, I18, I19) -> f6(I20, 0, I18, I21) [1 <= I18 - 1 /\ 2 <= I17 - 1 /\ y1 <= I18 - 1 /\ y2 <= I18 - 1 /\ I20 <= I16 /\ 2 <= I16 - 1 /\ 2 <= I20 - 1 /\ I18 + 4 <= I16 /\ 0 <= I18 - 2 * y1 /\ I18 - 2 * y1 <= 1 /\ I18 - 2 * y2 <= 1 /\ 0 <= I18 - 2 * y2] 14.43/14.33 f3(I22, I23, I24, I25) -> f5(I22, I23, I24, I26) [1 <= I24 - 1 /\ 2 <= I23 - 1 /\ I27 <= I24 - 1 /\ I28 <= I24 - 1 /\ y3 <= I22 /\ 2 <= I22 - 1 /\ 2 <= y3 - 1 /\ I24 + 4 <= I22] 14.43/14.33 f4(I29, I30, I31, I32) -> f4(I33, I30, I31 + 1, I32) [I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29] 14.43/14.33 f4(I35, I36, I37, I38) -> f3(I39, I36 + 1, I38, I40) [I38 + 4 <= I35 /\ 2 <= I39 - 1 /\ 2 <= I35 - 1 /\ 2 <= I37 - 1 /\ I39 <= I35] 14.43/14.33 f3(I41, I42, I43, I44) -> f4(I45, I42, 0, I43) [I43 + 4 <= I41 /\ 2 <= I45 - 1 /\ 2 <= I41 - 1 /\ I42 <= 2 /\ I45 <= I41] 14.43/14.33 f2(I46, I47, I48, I49) -> f3(I50, 0, I51, I52) [0 <= 2 * I53 - 1 /\ 0 <= I47 - 1 /\ 2 * I53 + 1 - 2 * I54 = 1 /\ -1 <= I53 - 1 /\ 0 <= I46 - 1 /\ 2 <= I50 - 1 /\ 2 * I53 + 1 - 2 * I54 <= 1 /\ 0 <= 2 * I53 + 1 - 2 * I54 /\ 2 * I53 + 1 = I51] 14.43/14.33 f1(I55, I56, I57, I58) -> f2(I55, I56, I59, I60) [0 <= 2 * I61 - 1 /\ 0 <= I56 - 1 /\ 2 * I61 + 1 - 2 * I62 = 1 /\ -1 <= I61 - 1 /\ 0 <= I55 - 1 /\ 2 <= I63 - 1] 14.43/14.33 14.43/14.33 We use the reverse value criterion with the projection function NU: 14.43/14.33 NU[f4#(z1,z2,z3,z4)] = 2 + -1 * z3 14.43/14.33 14.43/14.33 This gives the following inequalities: 14.43/14.33 I30 <= I32 - 1 /\ I31 <= 2 /\ I31 <= I34 - 1 /\ -1 <= I34 - 1 /\ I33 <= I29 /\ 2 <= I29 - 1 /\ 2 <= I33 - 1 /\ I32 + 4 <= I29 ==> 2 + -1 * I31 > 2 + -1 * (I31 + 1) with 2 + -1 * I31 >= 0 14.43/14.33 14.43/14.33 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. 14.43/17.31 EOF