4.15/4.14 MAYBE 4.15/4.14 4.15/4.14 DP problem for innermost termination. 4.15/4.14 P = 4.15/4.14 init#(x1, x2) -> f1#(rnd1, rnd2) 4.15/4.14 f5#(I0, I1) -> f5#(I0 - 1, I2) [0 <= I0 - 1] 4.15/4.14 f1#(I3, I4) -> f5#(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] 4.15/4.14 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.15/4.14 f3#(I12, I13) -> f4#(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] 4.15/4.14 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] 4.15/4.14 f3#(I21, I22) -> f4#(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] 4.15/4.14 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] 4.15/4.14 f3#(I31, I32) -> f4#(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] 4.15/4.14 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] 4.15/4.14 f3#(I41, I42) -> f4#(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] 4.15/4.14 f2#(I46, I47) -> f3#(I46, 1) 4.15/4.14 f2#(I48, I49) -> f3#(I48, 0) [0 <= I49 - 1] 4.15/4.14 f1#(I50, I51) -> f2#(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] 4.15/4.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] 4.15/4.14 R = 4.15/4.14 init(x1, x2) -> f1(rnd1, rnd2) 4.15/4.14 f5(I0, I1) -> f5(I0 - 1, I2) [0 <= I0 - 1] 4.15/4.14 f1(I3, I4) -> f5(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] 4.15/4.14 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.15/4.14 f3(I12, I13) -> f4(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] 4.15/4.14 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] 4.15/4.14 f3(I21, I22) -> f4(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] 4.15/4.14 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] 4.15/4.14 f3(I31, I32) -> f4(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] 4.15/4.14 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] 4.15/4.14 f3(I41, I42) -> f4(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] 4.15/4.14 f2(I46, I47) -> f3(I46, 1) 4.15/4.14 f2(I48, I49) -> f3(I48, 0) [0 <= I49 - 1] 4.15/4.14 f1(I50, I51) -> f2(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] 4.15/4.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] 4.15/4.14 4.15/4.14 The dependency graph for this problem is: 4.15/4.14 0 -> 2, 13, 14 4.15/4.14 1 -> 1 4.15/4.14 2 -> 1 4.15/4.14 3 -> 4, 6 4.15/4.14 4 -> 3, 9 4.15/4.14 5 -> 4, 6 4.15/4.14 6 -> 5, 7 4.15/4.14 7 -> 4, 6 4.15/4.14 8 -> 5, 7 4.15/4.14 9 -> 4.15/4.14 10 -> 3, 9 4.15/4.14 11 -> 4, 6 4.15/4.14 12 -> 4.15/4.14 13 -> 11 4.15/4.14 14 -> 11, 12 4.15/4.14 Where: 4.15/4.14 0) init#(x1, x2) -> f1#(rnd1, rnd2) 4.15/4.14 1) f5#(I0, I1) -> f5#(I0 - 1, I2) [0 <= I0 - 1] 4.15/4.14 2) f1#(I3, I4) -> f5#(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] 4.15/4.14 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.15/4.14 4) f3#(I12, I13) -> f4#(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] 4.15/4.14 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] 4.15/4.14 6) f3#(I21, I22) -> f4#(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] 4.15/4.14 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] 4.15/4.14 8) f3#(I31, I32) -> f4#(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] 4.15/4.14 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] 4.15/4.14 10) f3#(I41, I42) -> f4#(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] 4.15/4.14 11) f2#(I46, I47) -> f3#(I46, 1) 4.15/4.14 12) f2#(I48, I49) -> f3#(I48, 0) [0 <= I49 - 1] 4.15/4.14 13) f1#(I50, I51) -> f2#(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] 4.15/4.14 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] 4.15/4.14 4.15/4.14 We have the following SCCs. 4.15/4.14 { 1 } 4.15/4.14 { 3, 4, 5, 6, 7 } 4.15/4.14 4.15/4.14 DP problem for innermost termination. 4.15/4.14 P = 4.15/4.14 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.15/4.14 f3#(I12, I13) -> f4#(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] 4.15/4.14 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] 4.15/4.14 f3#(I21, I22) -> f4#(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] 4.15/4.14 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] 4.15/4.14 R = 4.15/4.14 init(x1, x2) -> f1(rnd1, rnd2) 4.15/4.14 f5(I0, I1) -> f5(I0 - 1, I2) [0 <= I0 - 1] 4.15/4.14 f1(I3, I4) -> f5(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] 4.15/4.14 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.15/4.14 f3(I12, I13) -> f4(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] 4.15/4.14 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] 4.15/4.14 f3(I21, I22) -> f4(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] 4.15/4.14 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] 4.15/4.14 f3(I31, I32) -> f4(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] 4.15/4.14 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] 4.15/4.14 f3(I41, I42) -> f4(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] 4.15/4.14 f2(I46, I47) -> f3(I46, 1) 4.15/4.14 f2(I48, I49) -> f3(I48, 0) [0 <= I49 - 1] 4.15/4.14 f1(I50, I51) -> f2(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] 4.15/4.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] 4.15/4.14 4.15/4.14 We use the basic value criterion with the projection function NU: 4.15/4.14 NU[f3#(z1,z2)] = z2 4.15/4.14 NU[f4#(z1,z2)] = z2 4.15/4.14 4.15/4.14 This gives the following inequalities: 4.15/4.14 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 4.15/4.14 I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12 ==> I13 (>! \union =) I13 4.15/4.14 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 4.15/4.14 I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21 ==> I22 (>! \union =) I22 4.15/4.14 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 4.15/4.14 4.15/4.14 We remove all the strictly oriented dependency pairs. 4.15/4.14 4.15/4.14 DP problem for innermost termination. 4.15/4.14 P = 4.15/4.14 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.15/4.14 f3#(I12, I13) -> f4#(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] 4.15/4.14 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] 4.15/4.14 f3#(I21, I22) -> f4#(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] 4.15/4.14 R = 4.15/4.14 init(x1, x2) -> f1(rnd1, rnd2) 4.15/4.14 f5(I0, I1) -> f5(I0 - 1, I2) [0 <= I0 - 1] 4.15/4.14 f1(I3, I4) -> f5(I5, I6) [-1 <= y2 - 1 /\ 1 <= I4 - 1 /\ -1 <= y1 - 1 /\ 0 <= I3 - 1 /\ y1 - 1 = I5] 4.15/4.14 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.15/4.14 f3(I12, I13) -> f4(I12, I13) [I12 - 2 * I14 = 0 /\ 0 <= I13 - 1 /\ I15 <= I13 - 1 /\ y3 <= I12] 4.15/4.14 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] 4.15/4.14 f3(I21, I22) -> f4(I21, I22) [I21 - 2 * I23 = 1 /\ 0 <= I22 - 1 /\ I24 <= I22 - 1 /\ I25 <= I21] 4.15/4.14 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] 4.15/4.14 f3(I31, I32) -> f4(I31, I32) [I31 - 2 * I33 = 1 /\ 0 <= I32 - 1 /\ I34 <= I32 - 1 /\ 0 <= I34 - 1 /\ I35 <= I31] 4.15/4.14 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] 4.15/4.14 f3(I41, I42) -> f4(I41, I42) [I41 - 2 * I43 = 0 /\ 0 <= I42 - 1 /\ I44 <= I42 - 1 /\ 0 <= I44 - 1 /\ I45 <= I41] 4.15/4.14 f2(I46, I47) -> f3(I46, 1) 4.15/4.14 f2(I48, I49) -> f3(I48, 0) [0 <= I49 - 1] 4.15/4.14 f1(I50, I51) -> f2(I52, I53) [-1 <= I54 - 1 /\ 1 <= I51 - 1 /\ I53 <= 0 /\ -1 <= I52 - 1 /\ 0 <= I50 - 1] 4.15/4.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] 4.15/4.14 4.15/7.12 EOF