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