3.92/3.89 YES 3.92/3.89 3.92/3.89 DP problem for innermost termination. 3.92/3.89 P = 3.92/3.89 init#(x1, x2, x3, x4) -> f1#(rnd1, rnd2, rnd3, rnd4) 3.92/3.89 f4#(I0, I1, I2, I3) -> f3#(I4, I5, I6, I7) [-1 <= y1 - 1 /\ y2 <= y1 - 1 /\ I4 - 2 <= I0 /\ I4 <= I1 /\ I5 <= I0 /\ 0 <= I0 - 1 /\ 2 <= I1 - 1 /\ 2 <= I4 - 1 /\ 0 <= I5 - 1] 3.92/3.89 f4#(I8, I9, I10, I11) -> f5#(I12, I13, I14, I15) [0 <= I16 - 1 /\ -1 <= I17 - 1 /\ I16 <= I17 - 1 /\ I14 - 2 <= I8 /\ 0 <= I8 - 1 /\ 2 <= I9 - 1 /\ -1 <= I12 - 1 /\ 0 <= I13 - 1 /\ 2 <= I14 - 1 /\ -1 <= I15 - 1] 3.92/3.89 f4#(I18, I19, I20, I21) -> f4#(I22, I23, I20, I24) [0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1] 3.92/3.89 f5#(I25, I26, I27, I28) -> f3#(I29, I30, I31, I32) [-1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25] 3.92/3.89 f5#(I33, I34, I35, I36) -> f3#(I37, I38, I39, I40) [-1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33] 3.92/3.89 f3#(I41, I42, I43, I44) -> f5#(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.89 f2#(I49, I50, I51, I52) -> f4#(I53, I54, I55, I56) [0 <= I54 - 1 /\ 1 <= I53 - 1 /\ 0 <= I50 - 1 /\ 1 <= I49 - 1 /\ I53 - 1 <= I50 /\ I51 <= 0 /\ I53 <= I49] 3.92/3.89 f2#(I57, I58, I59, I60) -> f3#(I61, I62, I63, I64) [0 <= I62 - 1 /\ 1 <= I61 - 1 /\ 0 <= I58 - 1 /\ 1 <= I57 - 1 /\ I61 - 1 <= I58 /\ I59 <= 0 /\ I61 <= I57] 3.92/3.89 f2#(I65, I66, I67, I68) -> f3#(I69, I70, I71, I72) [-1 <= I70 - 1 /\ 1 <= I69 - 1 /\ 0 <= I66 - 1 /\ 1 <= I65 - 1 /\ I69 - 1 <= I66 /\ I67 <= 0 /\ I69 <= I65] 3.92/3.89 f2#(I73, I74, I75, I76) -> f3#(I77, I78, I79, I80) [1 <= I78 - 1 /\ 1 <= I77 - 1 /\ 1 <= I74 - 1 /\ 1 <= I73 - 1 /\ I78 <= I74 /\ I78 <= I73 /\ I77 <= I74 /\ I75 <= 0 /\ I77 <= I73] 3.92/3.89 f2#(I81, I82, I83, I84) -> f2#(I85, I86, I83 - 1, I87) [2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81] 3.92/3.89 f1#(I88, I89, I90, I91) -> f2#(I92, I93, I94, I95) [-1 <= I96 - 1 /\ 0 <= I89 - 1 /\ I92 - 1 <= I88 /\ I93 - 1 <= I88 /\ 0 <= I88 - 1 /\ 1 <= I92 - 1 /\ 1 <= I93 - 1 /\ I96 - 2 = I94] 3.92/3.89 R = 3.92/3.89 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 3.92/3.89 f4(I0, I1, I2, I3) -> f3(I4, I5, I6, I7) [-1 <= y1 - 1 /\ y2 <= y1 - 1 /\ I4 - 2 <= I0 /\ I4 <= I1 /\ I5 <= I0 /\ 0 <= I0 - 1 /\ 2 <= I1 - 1 /\ 2 <= I4 - 1 /\ 0 <= I5 - 1] 3.92/3.89 f4(I8, I9, I10, I11) -> f5(I12, I13, I14, I15) [0 <= I16 - 1 /\ -1 <= I17 - 1 /\ I16 <= I17 - 1 /\ I14 - 2 <= I8 /\ 0 <= I8 - 1 /\ 2 <= I9 - 1 /\ -1 <= I12 - 1 /\ 0 <= I13 - 1 /\ 2 <= I14 - 1 /\ -1 <= I15 - 1] 3.92/3.89 f4(I18, I19, I20, I21) -> f4(I22, I23, I20, I24) [0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1] 3.92/3.89 f5(I25, I26, I27, I28) -> f3(I29, I30, I31, I32) [-1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25] 3.92/3.89 f5(I33, I34, I35, I36) -> f3(I37, I38, I39, I40) [-1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33] 3.92/3.89 f3(I41, I42, I43, I44) -> f5(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.89 f2(I49, I50, I51, I52) -> f4(I53, I54, I55, I56) [0 <= I54 - 1 /\ 1 <= I53 - 1 /\ 0 <= I50 - 1 /\ 1 <= I49 - 1 /\ I53 - 1 <= I50 /\ I51 <= 0 /\ I53 <= I49] 3.92/3.89 f2(I57, I58, I59, I60) -> f3(I61, I62, I63, I64) [0 <= I62 - 1 /\ 1 <= I61 - 1 /\ 0 <= I58 - 1 /\ 1 <= I57 - 1 /\ I61 - 1 <= I58 /\ I59 <= 0 /\ I61 <= I57] 3.92/3.89 f2(I65, I66, I67, I68) -> f3(I69, I70, I71, I72) [-1 <= I70 - 1 /\ 1 <= I69 - 1 /\ 0 <= I66 - 1 /\ 1 <= I65 - 1 /\ I69 - 1 <= I66 /\ I67 <= 0 /\ I69 <= I65] 3.92/3.89 f2(I73, I74, I75, I76) -> f3(I77, I78, I79, I80) [1 <= I78 - 1 /\ 1 <= I77 - 1 /\ 1 <= I74 - 1 /\ 1 <= I73 - 1 /\ I78 <= I74 /\ I78 <= I73 /\ I77 <= I74 /\ I75 <= 0 /\ I77 <= I73] 3.92/3.89 f2(I81, I82, I83, I84) -> f2(I85, I86, I83 - 1, I87) [2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81] 3.92/3.89 f1(I88, I89, I90, I91) -> f2(I92, I93, I94, I95) [-1 <= I96 - 1 /\ 0 <= I89 - 1 /\ I92 - 1 <= I88 /\ I93 - 1 <= I88 /\ 0 <= I88 - 1 /\ 1 <= I92 - 1 /\ 1 <= I93 - 1 /\ I96 - 2 = I94] 3.92/3.89 3.92/3.89 The dependency graph for this problem is: 3.92/3.89 0 -> 12 3.92/3.89 1 -> 6 3.92/3.89 2 -> 4, 5 3.92/3.89 3 -> 1, 2, 3 3.92/3.89 4 -> 6 3.92/3.89 5 -> 6 3.92/3.89 6 -> 4, 5 3.92/3.89 7 -> 1, 2, 3 3.92/3.89 8 -> 6 3.92/3.89 9 -> 6 3.92/3.89 10 -> 6 3.92/3.89 11 -> 7, 8, 9, 10, 11 3.92/3.89 12 -> 7, 8, 9, 10, 11 3.92/3.89 Where: 3.92/3.89 0) init#(x1, x2, x3, x4) -> f1#(rnd1, rnd2, rnd3, rnd4) 3.92/3.89 1) f4#(I0, I1, I2, I3) -> f3#(I4, I5, I6, I7) [-1 <= y1 - 1 /\ y2 <= y1 - 1 /\ I4 - 2 <= I0 /\ I4 <= I1 /\ I5 <= I0 /\ 0 <= I0 - 1 /\ 2 <= I1 - 1 /\ 2 <= I4 - 1 /\ 0 <= I5 - 1] 3.92/3.89 2) f4#(I8, I9, I10, I11) -> f5#(I12, I13, I14, I15) [0 <= I16 - 1 /\ -1 <= I17 - 1 /\ I16 <= I17 - 1 /\ I14 - 2 <= I8 /\ 0 <= I8 - 1 /\ 2 <= I9 - 1 /\ -1 <= I12 - 1 /\ 0 <= I13 - 1 /\ 2 <= I14 - 1 /\ -1 <= I15 - 1] 3.92/3.89 3) f4#(I18, I19, I20, I21) -> f4#(I22, I23, I20, I24) [0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1] 3.92/3.89 4) f5#(I25, I26, I27, I28) -> f3#(I29, I30, I31, I32) [-1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25] 3.92/3.89 5) f5#(I33, I34, I35, I36) -> f3#(I37, I38, I39, I40) [-1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33] 3.92/3.89 6) f3#(I41, I42, I43, I44) -> f5#(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.90 7) f2#(I49, I50, I51, I52) -> f4#(I53, I54, I55, I56) [0 <= I54 - 1 /\ 1 <= I53 - 1 /\ 0 <= I50 - 1 /\ 1 <= I49 - 1 /\ I53 - 1 <= I50 /\ I51 <= 0 /\ I53 <= I49] 3.92/3.90 8) f2#(I57, I58, I59, I60) -> f3#(I61, I62, I63, I64) [0 <= I62 - 1 /\ 1 <= I61 - 1 /\ 0 <= I58 - 1 /\ 1 <= I57 - 1 /\ I61 - 1 <= I58 /\ I59 <= 0 /\ I61 <= I57] 3.92/3.90 9) f2#(I65, I66, I67, I68) -> f3#(I69, I70, I71, I72) [-1 <= I70 - 1 /\ 1 <= I69 - 1 /\ 0 <= I66 - 1 /\ 1 <= I65 - 1 /\ I69 - 1 <= I66 /\ I67 <= 0 /\ I69 <= I65] 3.92/3.90 10) f2#(I73, I74, I75, I76) -> f3#(I77, I78, I79, I80) [1 <= I78 - 1 /\ 1 <= I77 - 1 /\ 1 <= I74 - 1 /\ 1 <= I73 - 1 /\ I78 <= I74 /\ I78 <= I73 /\ I77 <= I74 /\ I75 <= 0 /\ I77 <= I73] 3.92/3.90 11) f2#(I81, I82, I83, I84) -> f2#(I85, I86, I83 - 1, I87) [2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81] 3.92/3.90 12) f1#(I88, I89, I90, I91) -> f2#(I92, I93, I94, I95) [-1 <= I96 - 1 /\ 0 <= I89 - 1 /\ I92 - 1 <= I88 /\ I93 - 1 <= I88 /\ 0 <= I88 - 1 /\ 1 <= I92 - 1 /\ 1 <= I93 - 1 /\ I96 - 2 = I94] 3.92/3.90 3.92/3.90 We have the following SCCs. 3.92/3.90 { 11 } 3.92/3.90 { 3 } 3.92/3.90 { 4, 5, 6 } 3.92/3.90 3.92/3.90 DP problem for innermost termination. 3.92/3.90 P = 3.92/3.90 f5#(I25, I26, I27, I28) -> f3#(I29, I30, I31, I32) [-1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25] 3.92/3.90 f5#(I33, I34, I35, I36) -> f3#(I37, I38, I39, I40) [-1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33] 3.92/3.90 f3#(I41, I42, I43, I44) -> f5#(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.90 R = 3.92/3.90 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 3.92/3.90 f4(I0, I1, I2, I3) -> f3(I4, I5, I6, I7) [-1 <= y1 - 1 /\ y2 <= y1 - 1 /\ I4 - 2 <= I0 /\ I4 <= I1 /\ I5 <= I0 /\ 0 <= I0 - 1 /\ 2 <= I1 - 1 /\ 2 <= I4 - 1 /\ 0 <= I5 - 1] 3.92/3.90 f4(I8, I9, I10, I11) -> f5(I12, I13, I14, I15) [0 <= I16 - 1 /\ -1 <= I17 - 1 /\ I16 <= I17 - 1 /\ I14 - 2 <= I8 /\ 0 <= I8 - 1 /\ 2 <= I9 - 1 /\ -1 <= I12 - 1 /\ 0 <= I13 - 1 /\ 2 <= I14 - 1 /\ -1 <= I15 - 1] 3.92/3.90 f4(I18, I19, I20, I21) -> f4(I22, I23, I20, I24) [0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1] 3.92/3.90 f5(I25, I26, I27, I28) -> f3(I29, I30, I31, I32) [-1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25] 3.92/3.90 f5(I33, I34, I35, I36) -> f3(I37, I38, I39, I40) [-1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33] 3.92/3.90 f3(I41, I42, I43, I44) -> f5(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.90 f2(I49, I50, I51, I52) -> f4(I53, I54, I55, I56) [0 <= I54 - 1 /\ 1 <= I53 - 1 /\ 0 <= I50 - 1 /\ 1 <= I49 - 1 /\ I53 - 1 <= I50 /\ I51 <= 0 /\ I53 <= I49] 3.92/3.90 f2(I57, I58, I59, I60) -> f3(I61, I62, I63, I64) [0 <= I62 - 1 /\ 1 <= I61 - 1 /\ 0 <= I58 - 1 /\ 1 <= I57 - 1 /\ I61 - 1 <= I58 /\ I59 <= 0 /\ I61 <= I57] 3.92/3.90 f2(I65, I66, I67, I68) -> f3(I69, I70, I71, I72) [-1 <= I70 - 1 /\ 1 <= I69 - 1 /\ 0 <= I66 - 1 /\ 1 <= I65 - 1 /\ I69 - 1 <= I66 /\ I67 <= 0 /\ I69 <= I65] 3.92/3.90 f2(I73, I74, I75, I76) -> f3(I77, I78, I79, I80) [1 <= I78 - 1 /\ 1 <= I77 - 1 /\ 1 <= I74 - 1 /\ 1 <= I73 - 1 /\ I78 <= I74 /\ I78 <= I73 /\ I77 <= I74 /\ I75 <= 0 /\ I77 <= I73] 3.92/3.90 f2(I81, I82, I83, I84) -> f2(I85, I86, I83 - 1, I87) [2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81] 3.92/3.90 f1(I88, I89, I90, I91) -> f2(I92, I93, I94, I95) [-1 <= I96 - 1 /\ 0 <= I89 - 1 /\ I92 - 1 <= I88 /\ I93 - 1 <= I88 /\ 0 <= I88 - 1 /\ 1 <= I92 - 1 /\ 1 <= I93 - 1 /\ I96 - 2 = I94] 3.92/3.90 3.92/3.90 We use the basic value criterion with the projection function NU: 3.92/3.90 NU[f3#(z1,z2,z3,z4)] = z2 3.92/3.90 NU[f5#(z1,z2,z3,z4)] = z2 3.92/3.90 3.92/3.90 This gives the following inequalities: 3.92/3.90 -1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25 ==> I26 >! I30 3.92/3.90 -1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33 ==> I34 >! I38 3.92/3.90 -1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42 ==> I42 (>! \union =) I46 3.92/3.90 3.92/3.90 We remove all the strictly oriented dependency pairs. 3.92/3.90 3.92/3.90 DP problem for innermost termination. 3.92/3.90 P = 3.92/3.90 f3#(I41, I42, I43, I44) -> f5#(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.90 R = 3.92/3.90 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 3.92/3.90 f4(I0, I1, I2, I3) -> f3(I4, I5, I6, I7) [-1 <= y1 - 1 /\ y2 <= y1 - 1 /\ I4 - 2 <= I0 /\ I4 <= I1 /\ I5 <= I0 /\ 0 <= I0 - 1 /\ 2 <= I1 - 1 /\ 2 <= I4 - 1 /\ 0 <= I5 - 1] 3.92/3.90 f4(I8, I9, I10, I11) -> f5(I12, I13, I14, I15) [0 <= I16 - 1 /\ -1 <= I17 - 1 /\ I16 <= I17 - 1 /\ I14 - 2 <= I8 /\ 0 <= I8 - 1 /\ 2 <= I9 - 1 /\ -1 <= I12 - 1 /\ 0 <= I13 - 1 /\ 2 <= I14 - 1 /\ -1 <= I15 - 1] 3.92/3.90 f4(I18, I19, I20, I21) -> f4(I22, I23, I20, I24) [0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1] 3.92/3.90 f5(I25, I26, I27, I28) -> f3(I29, I30, I31, I32) [-1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25] 3.92/3.90 f5(I33, I34, I35, I36) -> f3(I37, I38, I39, I40) [-1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33] 3.92/3.90 f3(I41, I42, I43, I44) -> f5(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.90 f2(I49, I50, I51, I52) -> f4(I53, I54, I55, I56) [0 <= I54 - 1 /\ 1 <= I53 - 1 /\ 0 <= I50 - 1 /\ 1 <= I49 - 1 /\ I53 - 1 <= I50 /\ I51 <= 0 /\ I53 <= I49] 3.92/3.90 f2(I57, I58, I59, I60) -> f3(I61, I62, I63, I64) [0 <= I62 - 1 /\ 1 <= I61 - 1 /\ 0 <= I58 - 1 /\ 1 <= I57 - 1 /\ I61 - 1 <= I58 /\ I59 <= 0 /\ I61 <= I57] 3.92/3.90 f2(I65, I66, I67, I68) -> f3(I69, I70, I71, I72) [-1 <= I70 - 1 /\ 1 <= I69 - 1 /\ 0 <= I66 - 1 /\ 1 <= I65 - 1 /\ I69 - 1 <= I66 /\ I67 <= 0 /\ I69 <= I65] 3.92/3.90 f2(I73, I74, I75, I76) -> f3(I77, I78, I79, I80) [1 <= I78 - 1 /\ 1 <= I77 - 1 /\ 1 <= I74 - 1 /\ 1 <= I73 - 1 /\ I78 <= I74 /\ I78 <= I73 /\ I77 <= I74 /\ I75 <= 0 /\ I77 <= I73] 3.92/3.90 f2(I81, I82, I83, I84) -> f2(I85, I86, I83 - 1, I87) [2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81] 3.92/3.90 f1(I88, I89, I90, I91) -> f2(I92, I93, I94, I95) [-1 <= I96 - 1 /\ 0 <= I89 - 1 /\ I92 - 1 <= I88 /\ I93 - 1 <= I88 /\ 0 <= I88 - 1 /\ 1 <= I92 - 1 /\ 1 <= I93 - 1 /\ I96 - 2 = I94] 3.92/3.90 3.92/3.90 The dependency graph for this problem is: 3.92/3.90 6 -> 3.92/3.90 Where: 3.92/3.90 6) f3#(I41, I42, I43, I44) -> f5#(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.90 3.92/3.90 We have the following SCCs. 3.92/3.90 3.92/3.90 3.92/3.90 DP problem for innermost termination. 3.92/3.90 P = 3.92/3.90 f4#(I18, I19, I20, I21) -> f4#(I22, I23, I20, I24) [0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1] 3.92/3.90 R = 3.92/3.90 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 3.92/3.90 f4(I0, I1, I2, I3) -> f3(I4, I5, I6, I7) [-1 <= y1 - 1 /\ y2 <= y1 - 1 /\ I4 - 2 <= I0 /\ I4 <= I1 /\ I5 <= I0 /\ 0 <= I0 - 1 /\ 2 <= I1 - 1 /\ 2 <= I4 - 1 /\ 0 <= I5 - 1] 3.92/3.90 f4(I8, I9, I10, I11) -> f5(I12, I13, I14, I15) [0 <= I16 - 1 /\ -1 <= I17 - 1 /\ I16 <= I17 - 1 /\ I14 - 2 <= I8 /\ 0 <= I8 - 1 /\ 2 <= I9 - 1 /\ -1 <= I12 - 1 /\ 0 <= I13 - 1 /\ 2 <= I14 - 1 /\ -1 <= I15 - 1] 3.92/3.90 f4(I18, I19, I20, I21) -> f4(I22, I23, I20, I24) [0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1] 3.92/3.90 f5(I25, I26, I27, I28) -> f3(I29, I30, I31, I32) [-1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25] 3.92/3.90 f5(I33, I34, I35, I36) -> f3(I37, I38, I39, I40) [-1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33] 3.92/3.90 f3(I41, I42, I43, I44) -> f5(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.90 f2(I49, I50, I51, I52) -> f4(I53, I54, I55, I56) [0 <= I54 - 1 /\ 1 <= I53 - 1 /\ 0 <= I50 - 1 /\ 1 <= I49 - 1 /\ I53 - 1 <= I50 /\ I51 <= 0 /\ I53 <= I49] 3.92/3.90 f2(I57, I58, I59, I60) -> f3(I61, I62, I63, I64) [0 <= I62 - 1 /\ 1 <= I61 - 1 /\ 0 <= I58 - 1 /\ 1 <= I57 - 1 /\ I61 - 1 <= I58 /\ I59 <= 0 /\ I61 <= I57] 3.92/3.90 f2(I65, I66, I67, I68) -> f3(I69, I70, I71, I72) [-1 <= I70 - 1 /\ 1 <= I69 - 1 /\ 0 <= I66 - 1 /\ 1 <= I65 - 1 /\ I69 - 1 <= I66 /\ I67 <= 0 /\ I69 <= I65] 3.92/3.90 f2(I73, I74, I75, I76) -> f3(I77, I78, I79, I80) [1 <= I78 - 1 /\ 1 <= I77 - 1 /\ 1 <= I74 - 1 /\ 1 <= I73 - 1 /\ I78 <= I74 /\ I78 <= I73 /\ I77 <= I74 /\ I75 <= 0 /\ I77 <= I73] 3.92/3.90 f2(I81, I82, I83, I84) -> f2(I85, I86, I83 - 1, I87) [2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81] 3.92/3.90 f1(I88, I89, I90, I91) -> f2(I92, I93, I94, I95) [-1 <= I96 - 1 /\ 0 <= I89 - 1 /\ I92 - 1 <= I88 /\ I93 - 1 <= I88 /\ 0 <= I88 - 1 /\ 1 <= I92 - 1 /\ 1 <= I93 - 1 /\ I96 - 2 = I94] 3.92/3.90 3.92/3.90 We use the basic value criterion with the projection function NU: 3.92/3.90 NU[f4#(z1,z2,z3,z4)] = z4 3.92/3.90 3.92/3.90 This gives the following inequalities: 3.92/3.90 0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1 ==> I21 >! I24 3.92/3.90 3.92/3.90 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. 3.92/3.90 3.92/3.90 DP problem for innermost termination. 3.92/3.90 P = 3.92/3.90 f2#(I81, I82, I83, I84) -> f2#(I85, I86, I83 - 1, I87) [2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81] 3.92/3.90 R = 3.92/3.90 init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) 3.92/3.90 f4(I0, I1, I2, I3) -> f3(I4, I5, I6, I7) [-1 <= y1 - 1 /\ y2 <= y1 - 1 /\ I4 - 2 <= I0 /\ I4 <= I1 /\ I5 <= I0 /\ 0 <= I0 - 1 /\ 2 <= I1 - 1 /\ 2 <= I4 - 1 /\ 0 <= I5 - 1] 3.92/3.90 f4(I8, I9, I10, I11) -> f5(I12, I13, I14, I15) [0 <= I16 - 1 /\ -1 <= I17 - 1 /\ I16 <= I17 - 1 /\ I14 - 2 <= I8 /\ 0 <= I8 - 1 /\ 2 <= I9 - 1 /\ -1 <= I12 - 1 /\ 0 <= I13 - 1 /\ 2 <= I14 - 1 /\ -1 <= I15 - 1] 3.92/3.90 f4(I18, I19, I20, I21) -> f4(I22, I23, I20, I24) [0 <= I23 - 1 /\ 2 <= I22 - 1 /\ 2 <= I19 - 1 /\ 0 <= I18 - 1 /\ I22 - 2 <= I18 /\ I24 <= I21 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1] 3.92/3.90 f5(I25, I26, I27, I28) -> f3(I29, I30, I31, I32) [-1 <= I30 - 1 /\ 2 <= I29 - 1 /\ -1 <= I28 - 1 /\ 0 <= I27 - 1 /\ 0 <= I26 - 1 /\ -1 <= I25 - 1 /\ I30 <= I28 /\ I30 + 1 <= I27 /\ I30 + 1 <= I26 /\ I30 <= I25 /\ I29 - 3 <= I28 /\ I29 - 2 <= I27 /\ I29 - 2 <= I26 /\ I29 - 3 <= I25] 3.92/3.90 f5(I33, I34, I35, I36) -> f3(I37, I38, I39, I40) [-1 <= I38 - 1 /\ 2 <= I37 - 1 /\ -1 <= I36 - 1 /\ 0 <= I35 - 1 /\ 0 <= I34 - 1 /\ -1 <= I33 - 1 /\ I38 <= I36 /\ I38 + 1 <= I34 /\ I38 <= I33] 3.92/3.90 f3(I41, I42, I43, I44) -> f5(I45, I46, I47, I48) [-1 <= I48 - 1 /\ 0 <= I47 - 1 /\ 0 <= I46 - 1 /\ -1 <= I45 - 1 /\ 0 <= I42 - 1 /\ 0 <= I41 - 1 /\ I48 + 1 <= I42 /\ I47 <= I41 /\ I46 <= I42 /\ I45 + 1 <= I42] 3.92/3.90 f2(I49, I50, I51, I52) -> f4(I53, I54, I55, I56) [0 <= I54 - 1 /\ 1 <= I53 - 1 /\ 0 <= I50 - 1 /\ 1 <= I49 - 1 /\ I53 - 1 <= I50 /\ I51 <= 0 /\ I53 <= I49] 3.92/3.90 f2(I57, I58, I59, I60) -> f3(I61, I62, I63, I64) [0 <= I62 - 1 /\ 1 <= I61 - 1 /\ 0 <= I58 - 1 /\ 1 <= I57 - 1 /\ I61 - 1 <= I58 /\ I59 <= 0 /\ I61 <= I57] 3.92/3.90 f2(I65, I66, I67, I68) -> f3(I69, I70, I71, I72) [-1 <= I70 - 1 /\ 1 <= I69 - 1 /\ 0 <= I66 - 1 /\ 1 <= I65 - 1 /\ I69 - 1 <= I66 /\ I67 <= 0 /\ I69 <= I65] 3.92/3.90 f2(I73, I74, I75, I76) -> f3(I77, I78, I79, I80) [1 <= I78 - 1 /\ 1 <= I77 - 1 /\ 1 <= I74 - 1 /\ 1 <= I73 - 1 /\ I78 <= I74 /\ I78 <= I73 /\ I77 <= I74 /\ I75 <= 0 /\ I77 <= I73] 3.92/3.90 f2(I81, I82, I83, I84) -> f2(I85, I86, I83 - 1, I87) [2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81] 3.92/3.90 f1(I88, I89, I90, I91) -> f2(I92, I93, I94, I95) [-1 <= I96 - 1 /\ 0 <= I89 - 1 /\ I92 - 1 <= I88 /\ I93 - 1 <= I88 /\ 0 <= I88 - 1 /\ 1 <= I92 - 1 /\ 1 <= I93 - 1 /\ I96 - 2 = I94] 3.92/3.90 3.92/3.90 We use the basic value criterion with the projection function NU: 3.92/3.90 NU[f2#(z1,z2,z3,z4)] = z3 3.92/3.90 3.92/3.90 This gives the following inequalities: 3.92/3.90 2 <= I86 - 1 /\ 0 <= I85 - 1 /\ 0 <= I82 - 1 /\ 0 <= I81 - 1 /\ I86 - 2 <= I82 /\ 0 <= I83 - 1 /\ I85 <= I81 ==> I83 >! I83 - 1 3.92/3.90 3.92/3.90 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. 3.92/6.88 EOF