/export/starexec/sandbox2/solver/bin/starexec_run_Transition /export/starexec/sandbox2/benchmark/theBenchmark.smt2 /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES DP problem for innermost termination. P = init#(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4#(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3#(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3#(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4#(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3#(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2#(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2#(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3#(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1#(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2#(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] The dependency graph for this problem is: 0 -> 10 1 -> 1, 2 2 -> 3, 4 3 -> 1 4 -> 5, 6 5 -> 3, 4 6 -> 7, 8 7 -> 5 8 -> 9 9 -> 7, 8 10 -> 9 Where: 0) init#(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) 1) f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] 2) f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] 3) f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] 4) f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] 5) f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] 6) f4#(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3#(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] 7) f3#(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4#(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] 8) f3#(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2#(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] 9) f2#(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3#(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] 10) f1#(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2#(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] We have the following SCCs. { 1, 2, 3, 4, 5, 6, 7, 8, 9 } DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4#(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3#(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3#(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4#(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3#(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2#(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2#(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3#(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] We use the extended value criterion with the projection function NU: NU[f2#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = -x1 + x2 - 1 NU[f3#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = -x1 + x4 - 2 NU[f4#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = -x1 + x5 - 2 NU[f5#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = -x1 + x7 - 2 NU[f6#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = -x1 + x8 - 2 This gives the following inequalities: 0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0 ==> -I1 + I8 - 2 >= -I1 + I8 - 2 0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10 ==> -I11 + I18 - 2 >= -I11 + I18 - 2 0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24 ==> -I22 + I28 - 2 >= -I22 + I28 - 2 0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31 ==> -I32 + I38 - 2 >= -I32 + I38 - 2 0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47 ==> -I45 + I49 - 2 >= -I45 + I49 - 2 0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55 ==> -I56 + I60 - 2 >= -I56 + I60 - 2 0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1 ==> -I70 + I73 - 2 >= -I70 + I73 - 2 0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84 ==> -I83 + I86 - 2 >= -(I83 + 1) + I86 - 1 0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98 ==> -I99 + I100 - 1 > -I99 + I100 - 2 with -I99 + I100 - 1 >= 0 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4#(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3#(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3#(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4#(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3#(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2#(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] The dependency graph for this problem is: 1 -> 1, 2 2 -> 3, 4 3 -> 1 4 -> 5, 6 5 -> 3, 4 6 -> 7, 8 7 -> 5 8 -> Where: 1) f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] 2) f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] 3) f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] 4) f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] 5) f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] 6) f4#(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3#(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] 7) f3#(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4#(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] 8) f3#(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2#(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] We have the following SCCs. { 1, 2, 3, 4, 5, 6, 7 } DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4#(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3#(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3#(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4#(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] We use the extended value criterion with the projection function NU: NU[f3#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = -x2 + x3 - 1 NU[f4#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = x2 - x3 - 2 NU[f5#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = x2 - x3 - 2 NU[f6#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = x2 - x3 - 2 This gives the following inequalities: 0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0 ==> I2 - I3 - 2 >= I2 - I3 - 2 0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10 ==> I12 - I13 - 2 >= I12 - I13 - 2 0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24 ==> I23 - I24 - 2 >= I23 - I24 - 2 0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31 ==> I33 - I34 - 2 >= I33 - I34 - 2 0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47 ==> I46 - I47 - 2 >= I46 - I47 - 2 0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55 ==> I57 - I58 - 2 >= -(I58 + 1) + I57 - 1 0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1 ==> -I71 + I72 - 1 > I72 - I71 - 2 with -I71 + I72 - 1 >= 0 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4#(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3#(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] The dependency graph for this problem is: 1 -> 1, 2 2 -> 3, 4 3 -> 1 4 -> 5, 6 5 -> 3, 4 6 -> Where: 1) f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] 2) f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] 3) f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] 4) f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] 5) f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] 6) f4#(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3#(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] We have the following SCCs. { 1, 2, 3, 4, 5 } DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4#(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5#(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] We use the extended value criterion with the projection function NU: NU[f4#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = x4 NU[f5#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = x4 - 1 NU[f6#(x0,x1,x2,x3,x4,x5,x6,x7,x8)] = x4 - 1 This gives the following inequalities: 0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0 ==> I4 - 1 >= I4 - 1 0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10 ==> I14 - 1 >= I14 - 1 0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24 ==> I25 - 1 >= I25 - 1 0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31 ==> I35 - 1 >= (I35 - 1) 0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47 ==> I48 > I48 - 1 with I48 >= 0 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] The dependency graph for this problem is: 1 -> 1, 2 2 -> 3, 4 3 -> 1 4 -> Where: 1) f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] 2) f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] 3) f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] 4) f5#(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4#(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] We have the following SCCs. { 1, 2, 3 } DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5#(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6#(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] We use the reverse value criterion with the projection function NU: NU[f5#(z1,z2,z3,z4,z5,z6,z7,z8,z9)] = z7 - 1 + -1 * z6 NU[f6#(z1,z2,z3,z4,z5,z6,z7,z8,z9)] = z6 - 1 + -1 * (z7 + 1) This gives the following inequalities: 0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0 ==> I5 - 1 + -1 * (I6 + 1) >= I5 - 1 + -1 * (I6 + 1) 0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10 ==> I15 - 1 + -1 * (I16 + 1) >= I15 - 1 + -1 * (I16 + 1) 0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24 ==> I27 - 1 + -1 * I26 > I27 - 1 + -1 * (I26 + 1) with I27 - 1 + -1 * I26 >= 0 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] The dependency graph for this problem is: 1 -> 1, 2 2 -> Where: 1) f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] 2) f6#(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5#(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] We have the following SCCs. { 1 } DP problem for innermost termination. P = f6#(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6#(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] R = init(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5, rnd6, rnd7, rnd8, rnd9) f6(I0, I1, I2, I3, I4, I5, I6, I7, I8) -> f6(I9, I1, I2, I3, I4, I5, I6, I7 - 1, I8) [0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0] f6(I10, I11, I12, I13, I14, I15, I16, I17, I18) -> f5(I19, I11, I12, I13, I14, I16 + 1, I15, I18, I20) [0 <= I19 - 1 /\ 0 <= I10 - 1 /\ I17 <= -1 /\ I19 <= I10] f5(I21, I22, I23, I24, I25, I26, I27, I28, I29) -> f6(I30, I22, I23, I24, I25, I27, I26, 1000 * I22 + 100 * I24 + 10 * I25 + I26, I28) [0 <= I30 - 1 /\ 0 <= I21 - 1 /\ I30 <= I21 /\ -1 <= I26 - 1 /\ 0 <= 1000 * I22 + 100 * I24 + 10 * I25 /\ 0 <= 1000 * I22 + 100 * I24 /\ 0 <= 10 * I25 /\ 0 <= 1000 * I22 /\ I26 <= I27 - 1 /\ 0 <= 100 * I24] f5(I31, I32, I33, I34, I35, I36, I37, I38, I39) -> f4(I40, I32, I33, I34, I35 - 1, I38, I41, I42, I43) [0 <= I40 - 1 /\ 0 <= I31 - 1 /\ I37 <= I36 /\ I40 <= I31] f4(I44, I45, I46, I47, I48, I49, I50, I51, I52) -> f5(I53, I45, I46, I47, I48, 0, 2 * I45 + 3 * I47 + 4 * I48, I49, I54) [0 <= I53 - 1 /\ 0 <= I44 - 1 /\ I53 <= I44 /\ 0 <= 4 * I48 /\ 0 <= 2 * I45 + 3 * I47 /\ 0 <= 2 * I45 /\ -1 <= I48 - 1 /\ 0 <= 3 * I47] f4(I55, I56, I57, I58, I59, I60, I61, I62, I63) -> f3(I64, I56, I58 + 1, I57, I60, I65, I66, I67, I68) [0 <= I64 - 1 /\ 0 <= I55 - 1 /\ I59 <= -1 /\ I64 <= I55] f3(I69, I70, I71, I72, I73, I74, I75, I76, I77) -> f4(I78, I70, I72, I71, I70 + I71, I73, I79, I80, I81) [0 <= I78 - 1 /\ 0 <= I69 - 1 /\ I78 <= I69 /\ -1 <= I70 - 1 /\ -1 <= I71 - 1 /\ I71 <= I72 - 1] f3(I82, I83, I84, I85, I86, I87, I88, I89, I90) -> f2(I91, I83 + 1, I86, I92, I93, I94, I95, I96, I97) [0 <= I91 - 1 /\ 0 <= I82 - 1 /\ I91 <= I82 /\ -1 <= I86 - 1 /\ I85 <= I84] f2(I98, I99, I100, I101, I102, I103, I104, I105, I106) -> f3(I107, I99, 0, 2 * I99, I100, I108, I109, I110, I111) [0 <= I107 - 1 /\ 0 <= I98 - 1 /\ I99 <= I100 - 1 /\ I107 <= I98] f1(I112, I113, I114, I115, I116, I117, I118, I119, I120) -> f2(I121, 0, I113, I122, I123, I124, I125, I126, I127) [0 <= I121 - 1 /\ 0 <= I112 - 1 /\ -1 <= I113 - 1 /\ I121 <= I112] We use the basic value criterion with the projection function NU: NU[f6#(z1,z2,z3,z4,z5,z6,z7,z8,z9)] = z8 This gives the following inequalities: 0 <= I9 - 1 /\ 0 <= I0 - 1 /\ -1 <= I7 - 1 /\ I9 <= I0 ==> I7 >! I7 - 1 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed.