1.17/1.20 MAYBE 1.17/1.20 1.17/1.20 DP problem for innermost termination. 1.17/1.20 P = 1.17/1.20 init#(x1, x2, x3) -> f3#(rnd1, rnd2, rnd3) 1.17/1.20 f8#(I0, I1, I2) -> f8#(I3, I4, I5) [I3 <= I0 /\ y2 <= y1 - 1 /\ I3 <= I1 /\ I4 <= I0 /\ I4 <= I1 /\ 2 <= I0 - 1 /\ 2 <= I1 - 1 /\ 0 <= I3 - 1 /\ 0 <= I4 - 1] 1.17/1.20 f8#(I6, I7, I8) -> f8#(I9, I10, I11) [I9 + 2 <= I6 /\ I12 <= I13 /\ I9 + 2 <= I7 /\ I10 + 2 <= I6 /\ I10 + 2 <= I7 /\ 2 <= I6 - 1 /\ 2 <= I7 - 1 /\ 0 <= I9 - 1 /\ 0 <= I10 - 1] 1.17/1.20 f5#(I14, I15, I16) -> f8#(I17, I18, I19) [-1 <= I17 - 1 /\ -1 <= I18 - 1 /\ I14 <= 2 /\ I15 <= I16 - 1 /\ 0 <= I16 - 1] 1.17/1.20 f7#(I20, I21, I22) -> f7#(I23, I24, I25) [-1 <= I24 - 1 /\ -1 <= I23 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1 /\ I24 + 1 <= I21 /\ I24 + 1 <= I20 /\ I23 + 1 <= I21 /\ I23 + 1 <= I20] 1.17/1.20 f4#(I26, I27, I28) -> f7#(I29, I30, I31) [I26 <= 2 /\ -1 <= I30 - 1 /\ -1 <= I29 - 1] 1.17/1.20 f6#(I32, I33, I34) -> f6#(I32 - 1, I32, I35) [0 <= I33 - 1] 1.17/1.20 f2#(I36, I37, I38) -> f6#(I37 - 1, I37, I39) [-1 <= I37 - 1 /\ 0 <= I36 - 1] 1.17/1.20 f2#(I40, I41, I42) -> f6#(I41 - 1, I41, I43) [0 <= I40 - 1] 1.17/1.20 f3#(I44, I45, I46) -> f6#(I45 - 1, I45, I47) [-1 <= I45 - 1 /\ 0 <= I44 - 1] 1.17/1.20 f5#(I48, I49, I50) -> f5#(I48, I49 + 1, I50) [I49 <= I50 - 1 /\ I48 <= 2 /\ 0 <= I50 - 1] 1.17/1.20 f5#(I51, I52, I53) -> f4#(I51 + 1, I54, I55) [I53 <= I52] 1.17/1.20 f4#(I56, I57, I58) -> f5#(I56, 0, I59) [I56 <= 2] 1.17/1.20 f2#(I60, I61, I62) -> f4#(0, I63, I64) [-1 <= I61 - 1 /\ 0 <= I60 - 1] 1.17/1.20 f3#(I65, I66, I67) -> f2#(I68, I66, I69) [0 <= I68 - 1 /\ 0 <= I65 - 1 /\ -1 <= I66 - 1 /\ I68 <= I65] 1.17/1.20 f1#(I70, I71, I72) -> f2#(I73, I71, I74) [0 <= I73 - 1 /\ 0 <= I70 - 1 /\ -1 <= I71 - 1 /\ I73 <= I70] 1.17/1.20 R = 1.17/1.20 init(x1, x2, x3) -> f3(rnd1, rnd2, rnd3) 1.17/1.20 f8(I0, I1, I2) -> f8(I3, I4, I5) [I3 <= I0 /\ y2 <= y1 - 1 /\ I3 <= I1 /\ I4 <= I0 /\ I4 <= I1 /\ 2 <= I0 - 1 /\ 2 <= I1 - 1 /\ 0 <= I3 - 1 /\ 0 <= I4 - 1] 1.17/1.20 f8(I6, I7, I8) -> f8(I9, I10, I11) [I9 + 2 <= I6 /\ I12 <= I13 /\ I9 + 2 <= I7 /\ I10 + 2 <= I6 /\ I10 + 2 <= I7 /\ 2 <= I6 - 1 /\ 2 <= I7 - 1 /\ 0 <= I9 - 1 /\ 0 <= I10 - 1] 1.17/1.20 f5(I14, I15, I16) -> f8(I17, I18, I19) [-1 <= I17 - 1 /\ -1 <= I18 - 1 /\ I14 <= 2 /\ I15 <= I16 - 1 /\ 0 <= I16 - 1] 1.17/1.20 f7(I20, I21, I22) -> f7(I23, I24, I25) [-1 <= I24 - 1 /\ -1 <= I23 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1 /\ I24 + 1 <= I21 /\ I24 + 1 <= I20 /\ I23 + 1 <= I21 /\ I23 + 1 <= I20] 1.17/1.20 f4(I26, I27, I28) -> f7(I29, I30, I31) [I26 <= 2 /\ -1 <= I30 - 1 /\ -1 <= I29 - 1] 1.17/1.20 f6(I32, I33, I34) -> f6(I32 - 1, I32, I35) [0 <= I33 - 1] 1.17/1.20 f2(I36, I37, I38) -> f6(I37 - 1, I37, I39) [-1 <= I37 - 1 /\ 0 <= I36 - 1] 1.17/1.20 f2(I40, I41, I42) -> f6(I41 - 1, I41, I43) [0 <= I40 - 1] 1.17/1.20 f3(I44, I45, I46) -> f6(I45 - 1, I45, I47) [-1 <= I45 - 1 /\ 0 <= I44 - 1] 1.17/1.20 f5(I48, I49, I50) -> f5(I48, I49 + 1, I50) [I49 <= I50 - 1 /\ I48 <= 2 /\ 0 <= I50 - 1] 1.17/1.20 f5(I51, I52, I53) -> f4(I51 + 1, I54, I55) [I53 <= I52] 1.17/1.20 f4(I56, I57, I58) -> f5(I56, 0, I59) [I56 <= 2] 1.17/1.20 f2(I60, I61, I62) -> f4(0, I63, I64) [-1 <= I61 - 1 /\ 0 <= I60 - 1] 1.17/1.20 f3(I65, I66, I67) -> f2(I68, I66, I69) [0 <= I68 - 1 /\ 0 <= I65 - 1 /\ -1 <= I66 - 1 /\ I68 <= I65] 1.17/1.20 f1(I70, I71, I72) -> f2(I73, I71, I74) [0 <= I73 - 1 /\ 0 <= I70 - 1 /\ -1 <= I71 - 1 /\ I73 <= I70] 1.17/1.20 1.17/1.20 The dependency graph for this problem is: 1.17/1.20 0 -> 9, 14 1.17/1.20 1 -> 1, 2 1.17/1.20 2 -> 1, 2 1.17/1.20 3 -> 1, 2 1.17/1.20 4 -> 4 1.17/1.20 5 -> 4 1.17/1.20 6 -> 6 1.17/1.20 7 -> 6 1.17/1.20 8 -> 6 1.17/1.20 9 -> 6 1.17/1.20 10 -> 3, 10, 11 1.17/1.20 11 -> 5, 12 1.17/1.20 12 -> 3, 10, 11 1.17/1.20 13 -> 5, 12 1.17/1.20 14 -> 7, 8, 13 1.17/1.20 15 -> 7, 8, 13 1.17/1.20 Where: 1.17/1.20 0) init#(x1, x2, x3) -> f3#(rnd1, rnd2, rnd3) 1.17/1.20 1) f8#(I0, I1, I2) -> f8#(I3, I4, I5) [I3 <= I0 /\ y2 <= y1 - 1 /\ I3 <= I1 /\ I4 <= I0 /\ I4 <= I1 /\ 2 <= I0 - 1 /\ 2 <= I1 - 1 /\ 0 <= I3 - 1 /\ 0 <= I4 - 1] 1.17/1.20 2) f8#(I6, I7, I8) -> f8#(I9, I10, I11) [I9 + 2 <= I6 /\ I12 <= I13 /\ I9 + 2 <= I7 /\ I10 + 2 <= I6 /\ I10 + 2 <= I7 /\ 2 <= I6 - 1 /\ 2 <= I7 - 1 /\ 0 <= I9 - 1 /\ 0 <= I10 - 1] 1.17/1.20 3) f5#(I14, I15, I16) -> f8#(I17, I18, I19) [-1 <= I17 - 1 /\ -1 <= I18 - 1 /\ I14 <= 2 /\ I15 <= I16 - 1 /\ 0 <= I16 - 1] 1.17/1.20 4) f7#(I20, I21, I22) -> f7#(I23, I24, I25) [-1 <= I24 - 1 /\ -1 <= I23 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1 /\ I24 + 1 <= I21 /\ I24 + 1 <= I20 /\ I23 + 1 <= I21 /\ I23 + 1 <= I20] 1.17/1.20 5) f4#(I26, I27, I28) -> f7#(I29, I30, I31) [I26 <= 2 /\ -1 <= I30 - 1 /\ -1 <= I29 - 1] 1.17/1.21 6) f6#(I32, I33, I34) -> f6#(I32 - 1, I32, I35) [0 <= I33 - 1] 1.17/1.21 7) f2#(I36, I37, I38) -> f6#(I37 - 1, I37, I39) [-1 <= I37 - 1 /\ 0 <= I36 - 1] 1.17/1.21 8) f2#(I40, I41, I42) -> f6#(I41 - 1, I41, I43) [0 <= I40 - 1] 1.17/1.21 9) f3#(I44, I45, I46) -> f6#(I45 - 1, I45, I47) [-1 <= I45 - 1 /\ 0 <= I44 - 1] 1.17/1.21 10) f5#(I48, I49, I50) -> f5#(I48, I49 + 1, I50) [I49 <= I50 - 1 /\ I48 <= 2 /\ 0 <= I50 - 1] 1.17/1.21 11) f5#(I51, I52, I53) -> f4#(I51 + 1, I54, I55) [I53 <= I52] 1.17/1.21 12) f4#(I56, I57, I58) -> f5#(I56, 0, I59) [I56 <= 2] 1.17/1.21 13) f2#(I60, I61, I62) -> f4#(0, I63, I64) [-1 <= I61 - 1 /\ 0 <= I60 - 1] 1.17/1.21 14) f3#(I65, I66, I67) -> f2#(I68, I66, I69) [0 <= I68 - 1 /\ 0 <= I65 - 1 /\ -1 <= I66 - 1 /\ I68 <= I65] 1.17/1.21 15) f1#(I70, I71, I72) -> f2#(I73, I71, I74) [0 <= I73 - 1 /\ 0 <= I70 - 1 /\ -1 <= I71 - 1 /\ I73 <= I70] 1.17/1.21 1.17/1.21 We have the following SCCs. 1.17/1.21 { 10, 11, 12 } 1.17/1.21 { 1, 2 } 1.17/1.21 { 4 } 1.17/1.21 { 6 } 1.17/1.21 1.17/1.21 DP problem for innermost termination. 1.17/1.21 P = 1.17/1.21 f6#(I32, I33, I34) -> f6#(I32 - 1, I32, I35) [0 <= I33 - 1] 1.17/1.21 R = 1.17/1.21 init(x1, x2, x3) -> f3(rnd1, rnd2, rnd3) 1.17/1.21 f8(I0, I1, I2) -> f8(I3, I4, I5) [I3 <= I0 /\ y2 <= y1 - 1 /\ I3 <= I1 /\ I4 <= I0 /\ I4 <= I1 /\ 2 <= I0 - 1 /\ 2 <= I1 - 1 /\ 0 <= I3 - 1 /\ 0 <= I4 - 1] 1.17/1.21 f8(I6, I7, I8) -> f8(I9, I10, I11) [I9 + 2 <= I6 /\ I12 <= I13 /\ I9 + 2 <= I7 /\ I10 + 2 <= I6 /\ I10 + 2 <= I7 /\ 2 <= I6 - 1 /\ 2 <= I7 - 1 /\ 0 <= I9 - 1 /\ 0 <= I10 - 1] 1.17/1.21 f5(I14, I15, I16) -> f8(I17, I18, I19) [-1 <= I17 - 1 /\ -1 <= I18 - 1 /\ I14 <= 2 /\ I15 <= I16 - 1 /\ 0 <= I16 - 1] 1.17/1.21 f7(I20, I21, I22) -> f7(I23, I24, I25) [-1 <= I24 - 1 /\ -1 <= I23 - 1 /\ 0 <= I21 - 1 /\ 0 <= I20 - 1 /\ I24 + 1 <= I21 /\ I24 + 1 <= I20 /\ I23 + 1 <= I21 /\ I23 + 1 <= I20] 1.17/1.21 f4(I26, I27, I28) -> f7(I29, I30, I31) [I26 <= 2 /\ -1 <= I30 - 1 /\ -1 <= I29 - 1] 1.17/1.21 f6(I32, I33, I34) -> f6(I32 - 1, I32, I35) [0 <= I33 - 1] 1.17/1.21 f2(I36, I37, I38) -> f6(I37 - 1, I37, I39) [-1 <= I37 - 1 /\ 0 <= I36 - 1] 1.17/1.21 f2(I40, I41, I42) -> f6(I41 - 1, I41, I43) [0 <= I40 - 1] 1.17/1.21 f3(I44, I45, I46) -> f6(I45 - 1, I45, I47) [-1 <= I45 - 1 /\ 0 <= I44 - 1] 1.17/1.21 f5(I48, I49, I50) -> f5(I48, I49 + 1, I50) [I49 <= I50 - 1 /\ I48 <= 2 /\ 0 <= I50 - 1] 1.17/1.21 f5(I51, I52, I53) -> f4(I51 + 1, I54, I55) [I53 <= I52] 1.17/1.21 f4(I56, I57, I58) -> f5(I56, 0, I59) [I56 <= 2] 1.17/1.21 f2(I60, I61, I62) -> f4(0, I63, I64) [-1 <= I61 - 1 /\ 0 <= I60 - 1] 1.17/1.21 f3(I65, I66, I67) -> f2(I68, I66, I69) [0 <= I68 - 1 /\ 0 <= I65 - 1 /\ -1 <= I66 - 1 /\ I68 <= I65] 1.17/1.21 f1(I70, I71, I72) -> f2(I73, I71, I74) [0 <= I73 - 1 /\ 0 <= I70 - 1 /\ -1 <= I71 - 1 /\ I73 <= I70] 1.17/1.21 1.17/4.45 EOF