1.60/1.64 YES 1.60/1.64 1.60/1.64 DP problem for innermost termination. 1.60/1.64 P = 1.60/1.64 init#(x1, x2, x3, x4, x5, x6, x7, x8) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8) 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 R = 1.60/1.64 init(x1, x2, x3, x4, x5, x6, x7, x8) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8) 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 1.60/1.64 The dependency graph for this problem is: 1.60/1.64 0 -> 4, 5, 6, 7 1.60/1.64 1 -> 1, 2, 3 1.60/1.64 2 -> 3 1.60/1.64 3 -> 1.60/1.64 4 -> 1, 2, 3 1.60/1.64 5 -> 3 1.60/1.64 6 -> 3 1.60/1.64 7 -> 1.60/1.64 Where: 1.60/1.64 0) init#(x1, x2, x3, x4, x5, x6, x7, x8) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8) 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 1.60/1.64 We have the following SCCs. 1.60/1.64 { 1 } 1.60/1.64 1.60/1.64 DP problem for innermost termination. 1.60/1.64 P = 1.60/1.64 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] 1.60/1.64 R = 1.60/1.64 init(x1, x2, x3, x4, x5, x6, x7, x8) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8) 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 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] 1.60/1.64 1.60/1.64 We use the reverse value criterion with the projection function NU: 1.60/1.64 NU[f2#(z1,z2,z3,z4,z5,z6,z7,z8)] = z6 - 1 + -1 * (z7 + 1) 1.60/1.64 1.60/1.64 This gives the following inequalities: 1.60/1.64 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 1.60/1.64 1.60/1.64 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. 1.60/4.62 EOF