/export/starexec/sandbox/solver/bin/starexec_run_Transition /export/starexec/sandbox/benchmark/theBenchmark.smt2 /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE DP problem for innermost termination. P = init#(x1, x2, x3, x4) -> f1#(rnd1, rnd2, rnd3, rnd4) f2#(I0, I1, I2, I3) -> f2#(2, 1, 1, I4) [0 = I2 /\ 3 = I0] f5#(I5, I6, I7, I8) -> f2#(I5 - 1, 0, I6, I9) [I6 = I7] f4#(I10, I11, I12, I13) -> f2#(I10 - 1, 0, I11, I14) [I11 = I12] f2#(I15, I16, I17, I18) -> f2#(0, 0, -1, I19) [0 = I17 /\ 0 = I15] f3#(I20, I21, I22, I23) -> f2#(I20 - 1, I21, I22, I24) [I22 = I23] f2#(I25, I26, I27, I28) -> f2#(I25, 1, 1, I29) [0 = I27 /\ 3 <= I25 - 1] f2#(I30, I31, I32, I33) -> f2#(I30, 1, 1, I34) [0 = I32 /\ I30 <= 2 /\ 0 <= I30 - 1] f5#(I35, I36, I37, I38) -> f2#(I35, 0, I36, I39) [I37 <= I36 - 1] f5#(I40, I41, I42, I43) -> f2#(I40, 0, I41, I44) [I41 <= I42 - 1] f4#(I45, I46, I47, I48) -> f2#(I45, 0, I46, I49) [I47 <= I46 - 1] f4#(I50, I51, I52, I53) -> f2#(I50, 0, I51, I54) [I51 <= I52 - 1] f3#(I55, I56, I57, I58) -> f2#(I55, I56, I57, I59) [I58 <= I57 - 1] f3#(I60, I61, I62, I63) -> f2#(I60, I61, I62, I64) [I62 <= I63 - 1] f2#(I65, I66, I67, I68) -> f5#(I65, I65 - 1, I65 - 2, I69) [I65 = I67 /\ 0 <= I65 - 1] f2#(I70, I71, I72, I73) -> f4#(I70, I72 - 1, I70 - 2, I74) [0 = I71 /\ I72 <= I70 - 1 /\ 0 <= I72 - 1 /\ -1 <= I70 - 1] f2#(I75, I76, I77, I78) -> f3#(I75, I76, I77 + 1, I75 - 2) [0 <= I76 - 1 /\ -1 <= I75 - 1 /\ I77 <= I75 - 1 /\ 0 <= I77 - 1] f2#(I79, I80, I81, I82) -> f3#(I79, I80, I81 + 1, I79 - 2) [I80 <= -1 /\ -1 <= I79 - 1 /\ I81 <= I79 - 1 /\ 0 <= I81 - 1] f1#(I83, I84, I85, I86) -> f2#(20, 0, I84, I87) [-1 <= I84 - 1 /\ 0 <= I83 - 1] R = init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) f2(I0, I1, I2, I3) -> f2(2, 1, 1, I4) [0 = I2 /\ 3 = I0] f5(I5, I6, I7, I8) -> f2(I5 - 1, 0, I6, I9) [I6 = I7] f4(I10, I11, I12, I13) -> f2(I10 - 1, 0, I11, I14) [I11 = I12] f2(I15, I16, I17, I18) -> f2(0, 0, -1, I19) [0 = I17 /\ 0 = I15] f3(I20, I21, I22, I23) -> f2(I20 - 1, I21, I22, I24) [I22 = I23] f2(I25, I26, I27, I28) -> f2(I25, 1, 1, I29) [0 = I27 /\ 3 <= I25 - 1] f2(I30, I31, I32, I33) -> f2(I30, 1, 1, I34) [0 = I32 /\ I30 <= 2 /\ 0 <= I30 - 1] f5(I35, I36, I37, I38) -> f2(I35, 0, I36, I39) [I37 <= I36 - 1] f5(I40, I41, I42, I43) -> f2(I40, 0, I41, I44) [I41 <= I42 - 1] f4(I45, I46, I47, I48) -> f2(I45, 0, I46, I49) [I47 <= I46 - 1] f4(I50, I51, I52, I53) -> f2(I50, 0, I51, I54) [I51 <= I52 - 1] f3(I55, I56, I57, I58) -> f2(I55, I56, I57, I59) [I58 <= I57 - 1] f3(I60, I61, I62, I63) -> f2(I60, I61, I62, I64) [I62 <= I63 - 1] f2(I65, I66, I67, I68) -> f5(I65, I65 - 1, I65 - 2, I69) [I65 = I67 /\ 0 <= I65 - 1] f2(I70, I71, I72, I73) -> f4(I70, I72 - 1, I70 - 2, I74) [0 = I71 /\ I72 <= I70 - 1 /\ 0 <= I72 - 1 /\ -1 <= I70 - 1] f2(I75, I76, I77, I78) -> f3(I75, I76, I77 + 1, I75 - 2) [0 <= I76 - 1 /\ -1 <= I75 - 1 /\ I77 <= I75 - 1 /\ 0 <= I77 - 1] f2(I79, I80, I81, I82) -> f3(I79, I80, I81 + 1, I79 - 2) [I80 <= -1 /\ -1 <= I79 - 1 /\ I81 <= I79 - 1 /\ 0 <= I81 - 1] f1(I83, I84, I85, I86) -> f2(20, 0, I84, I87) [-1 <= I84 - 1 /\ 0 <= I83 - 1] The dependency graph for this problem is: 0 -> 18 1 -> 16 2 -> 1, 4, 6, 7, 14, 15 3 -> 1, 4, 6, 7, 14, 15 4 -> 5 -> 1, 4, 6, 7, 14, 15, 16, 17 6 -> 16 7 -> 14, 16 8 -> 1, 4, 6, 7, 14, 15 9 -> 1, 4, 6, 7, 14, 15 10 -> 1, 4, 6, 7, 14, 15 11 -> 1, 4, 6, 7, 14, 15 12 -> 1, 4, 6, 7, 14, 15, 16, 17 13 -> 1, 4, 6, 7, 14, 15, 16, 17 14 -> 8 15 -> 3, 11 16 -> 5, 12, 13 17 -> 5, 12, 13 18 -> 6, 14, 15 Where: 0) init#(x1, x2, x3, x4) -> f1#(rnd1, rnd2, rnd3, rnd4) 1) f2#(I0, I1, I2, I3) -> f2#(2, 1, 1, I4) [0 = I2 /\ 3 = I0] 2) f5#(I5, I6, I7, I8) -> f2#(I5 - 1, 0, I6, I9) [I6 = I7] 3) f4#(I10, I11, I12, I13) -> f2#(I10 - 1, 0, I11, I14) [I11 = I12] 4) f2#(I15, I16, I17, I18) -> f2#(0, 0, -1, I19) [0 = I17 /\ 0 = I15] 5) f3#(I20, I21, I22, I23) -> f2#(I20 - 1, I21, I22, I24) [I22 = I23] 6) f2#(I25, I26, I27, I28) -> f2#(I25, 1, 1, I29) [0 = I27 /\ 3 <= I25 - 1] 7) f2#(I30, I31, I32, I33) -> f2#(I30, 1, 1, I34) [0 = I32 /\ I30 <= 2 /\ 0 <= I30 - 1] 8) f5#(I35, I36, I37, I38) -> f2#(I35, 0, I36, I39) [I37 <= I36 - 1] 9) f5#(I40, I41, I42, I43) -> f2#(I40, 0, I41, I44) [I41 <= I42 - 1] 10) f4#(I45, I46, I47, I48) -> f2#(I45, 0, I46, I49) [I47 <= I46 - 1] 11) f4#(I50, I51, I52, I53) -> f2#(I50, 0, I51, I54) [I51 <= I52 - 1] 12) f3#(I55, I56, I57, I58) -> f2#(I55, I56, I57, I59) [I58 <= I57 - 1] 13) f3#(I60, I61, I62, I63) -> f2#(I60, I61, I62, I64) [I62 <= I63 - 1] 14) f2#(I65, I66, I67, I68) -> f5#(I65, I65 - 1, I65 - 2, I69) [I65 = I67 /\ 0 <= I65 - 1] 15) f2#(I70, I71, I72, I73) -> f4#(I70, I72 - 1, I70 - 2, I74) [0 = I71 /\ I72 <= I70 - 1 /\ 0 <= I72 - 1 /\ -1 <= I70 - 1] 16) f2#(I75, I76, I77, I78) -> f3#(I75, I76, I77 + 1, I75 - 2) [0 <= I76 - 1 /\ -1 <= I75 - 1 /\ I77 <= I75 - 1 /\ 0 <= I77 - 1] 17) f2#(I79, I80, I81, I82) -> f3#(I79, I80, I81 + 1, I79 - 2) [I80 <= -1 /\ -1 <= I79 - 1 /\ I81 <= I79 - 1 /\ 0 <= I81 - 1] 18) f1#(I83, I84, I85, I86) -> f2#(20, 0, I84, I87) [-1 <= I84 - 1 /\ 0 <= I83 - 1] We have the following SCCs. { 1, 3, 5, 6, 7, 8, 11, 12, 13, 14, 15, 16, 17 } DP problem for innermost termination. P = f2#(I0, I1, I2, I3) -> f2#(2, 1, 1, I4) [0 = I2 /\ 3 = I0] f4#(I10, I11, I12, I13) -> f2#(I10 - 1, 0, I11, I14) [I11 = I12] f3#(I20, I21, I22, I23) -> f2#(I20 - 1, I21, I22, I24) [I22 = I23] f2#(I25, I26, I27, I28) -> f2#(I25, 1, 1, I29) [0 = I27 /\ 3 <= I25 - 1] f2#(I30, I31, I32, I33) -> f2#(I30, 1, 1, I34) [0 = I32 /\ I30 <= 2 /\ 0 <= I30 - 1] f5#(I35, I36, I37, I38) -> f2#(I35, 0, I36, I39) [I37 <= I36 - 1] f4#(I50, I51, I52, I53) -> f2#(I50, 0, I51, I54) [I51 <= I52 - 1] f3#(I55, I56, I57, I58) -> f2#(I55, I56, I57, I59) [I58 <= I57 - 1] f3#(I60, I61, I62, I63) -> f2#(I60, I61, I62, I64) [I62 <= I63 - 1] f2#(I65, I66, I67, I68) -> f5#(I65, I65 - 1, I65 - 2, I69) [I65 = I67 /\ 0 <= I65 - 1] f2#(I70, I71, I72, I73) -> f4#(I70, I72 - 1, I70 - 2, I74) [0 = I71 /\ I72 <= I70 - 1 /\ 0 <= I72 - 1 /\ -1 <= I70 - 1] f2#(I75, I76, I77, I78) -> f3#(I75, I76, I77 + 1, I75 - 2) [0 <= I76 - 1 /\ -1 <= I75 - 1 /\ I77 <= I75 - 1 /\ 0 <= I77 - 1] f2#(I79, I80, I81, I82) -> f3#(I79, I80, I81 + 1, I79 - 2) [I80 <= -1 /\ -1 <= I79 - 1 /\ I81 <= I79 - 1 /\ 0 <= I81 - 1] R = init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) f2(I0, I1, I2, I3) -> f2(2, 1, 1, I4) [0 = I2 /\ 3 = I0] f5(I5, I6, I7, I8) -> f2(I5 - 1, 0, I6, I9) [I6 = I7] f4(I10, I11, I12, I13) -> f2(I10 - 1, 0, I11, I14) [I11 = I12] f2(I15, I16, I17, I18) -> f2(0, 0, -1, I19) [0 = I17 /\ 0 = I15] f3(I20, I21, I22, I23) -> f2(I20 - 1, I21, I22, I24) [I22 = I23] f2(I25, I26, I27, I28) -> f2(I25, 1, 1, I29) [0 = I27 /\ 3 <= I25 - 1] f2(I30, I31, I32, I33) -> f2(I30, 1, 1, I34) [0 = I32 /\ I30 <= 2 /\ 0 <= I30 - 1] f5(I35, I36, I37, I38) -> f2(I35, 0, I36, I39) [I37 <= I36 - 1] f5(I40, I41, I42, I43) -> f2(I40, 0, I41, I44) [I41 <= I42 - 1] f4(I45, I46, I47, I48) -> f2(I45, 0, I46, I49) [I47 <= I46 - 1] f4(I50, I51, I52, I53) -> f2(I50, 0, I51, I54) [I51 <= I52 - 1] f3(I55, I56, I57, I58) -> f2(I55, I56, I57, I59) [I58 <= I57 - 1] f3(I60, I61, I62, I63) -> f2(I60, I61, I62, I64) [I62 <= I63 - 1] f2(I65, I66, I67, I68) -> f5(I65, I65 - 1, I65 - 2, I69) [I65 = I67 /\ 0 <= I65 - 1] f2(I70, I71, I72, I73) -> f4(I70, I72 - 1, I70 - 2, I74) [0 = I71 /\ I72 <= I70 - 1 /\ 0 <= I72 - 1 /\ -1 <= I70 - 1] f2(I75, I76, I77, I78) -> f3(I75, I76, I77 + 1, I75 - 2) [0 <= I76 - 1 /\ -1 <= I75 - 1 /\ I77 <= I75 - 1 /\ 0 <= I77 - 1] f2(I79, I80, I81, I82) -> f3(I79, I80, I81 + 1, I79 - 2) [I80 <= -1 /\ -1 <= I79 - 1 /\ I81 <= I79 - 1 /\ 0 <= I81 - 1] f1(I83, I84, I85, I86) -> f2(20, 0, I84, I87) [-1 <= I84 - 1 /\ 0 <= I83 - 1] We use the reverse value criterion with the projection function NU: NU[f5#(z1,z2,z3,z4)] = z1 NU[f3#(z1,z2,z3,z4)] = z1 NU[f4#(z1,z2,z3,z4)] = z1 NU[f2#(z1,z2,z3,z4)] = z1 This gives the following inequalities: 0 = I2 /\ 3 = I0 ==> I0 > 2 with I0 >= 0 I11 = I12 ==> I10 >= I10 - 1 I22 = I23 ==> I20 >= I20 - 1 0 = I27 /\ 3 <= I25 - 1 ==> I25 >= I25 0 = I32 /\ I30 <= 2 /\ 0 <= I30 - 1 ==> I30 >= I30 I37 <= I36 - 1 ==> I35 >= I35 I51 <= I52 - 1 ==> I50 >= I50 I58 <= I57 - 1 ==> I55 >= I55 I62 <= I63 - 1 ==> I60 >= I60 I65 = I67 /\ 0 <= I65 - 1 ==> I65 >= I65 0 = I71 /\ I72 <= I70 - 1 /\ 0 <= I72 - 1 /\ -1 <= I70 - 1 ==> I70 >= I70 0 <= I76 - 1 /\ -1 <= I75 - 1 /\ I77 <= I75 - 1 /\ 0 <= I77 - 1 ==> I75 >= I75 I80 <= -1 /\ -1 <= I79 - 1 /\ I81 <= I79 - 1 /\ 0 <= I81 - 1 ==> I79 >= I79 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = f4#(I10, I11, I12, I13) -> f2#(I10 - 1, 0, I11, I14) [I11 = I12] f3#(I20, I21, I22, I23) -> f2#(I20 - 1, I21, I22, I24) [I22 = I23] f2#(I25, I26, I27, I28) -> f2#(I25, 1, 1, I29) [0 = I27 /\ 3 <= I25 - 1] f2#(I30, I31, I32, I33) -> f2#(I30, 1, 1, I34) [0 = I32 /\ I30 <= 2 /\ 0 <= I30 - 1] f5#(I35, I36, I37, I38) -> f2#(I35, 0, I36, I39) [I37 <= I36 - 1] f4#(I50, I51, I52, I53) -> f2#(I50, 0, I51, I54) [I51 <= I52 - 1] f3#(I55, I56, I57, I58) -> f2#(I55, I56, I57, I59) [I58 <= I57 - 1] f3#(I60, I61, I62, I63) -> f2#(I60, I61, I62, I64) [I62 <= I63 - 1] f2#(I65, I66, I67, I68) -> f5#(I65, I65 - 1, I65 - 2, I69) [I65 = I67 /\ 0 <= I65 - 1] f2#(I70, I71, I72, I73) -> f4#(I70, I72 - 1, I70 - 2, I74) [0 = I71 /\ I72 <= I70 - 1 /\ 0 <= I72 - 1 /\ -1 <= I70 - 1] f2#(I75, I76, I77, I78) -> f3#(I75, I76, I77 + 1, I75 - 2) [0 <= I76 - 1 /\ -1 <= I75 - 1 /\ I77 <= I75 - 1 /\ 0 <= I77 - 1] f2#(I79, I80, I81, I82) -> f3#(I79, I80, I81 + 1, I79 - 2) [I80 <= -1 /\ -1 <= I79 - 1 /\ I81 <= I79 - 1 /\ 0 <= I81 - 1] R = init(x1, x2, x3, x4) -> f1(rnd1, rnd2, rnd3, rnd4) f2(I0, I1, I2, I3) -> f2(2, 1, 1, I4) [0 = I2 /\ 3 = I0] f5(I5, I6, I7, I8) -> f2(I5 - 1, 0, I6, I9) [I6 = I7] f4(I10, I11, I12, I13) -> f2(I10 - 1, 0, I11, I14) [I11 = I12] f2(I15, I16, I17, I18) -> f2(0, 0, -1, I19) [0 = I17 /\ 0 = I15] f3(I20, I21, I22, I23) -> f2(I20 - 1, I21, I22, I24) [I22 = I23] f2(I25, I26, I27, I28) -> f2(I25, 1, 1, I29) [0 = I27 /\ 3 <= I25 - 1] f2(I30, I31, I32, I33) -> f2(I30, 1, 1, I34) [0 = I32 /\ I30 <= 2 /\ 0 <= I30 - 1] f5(I35, I36, I37, I38) -> f2(I35, 0, I36, I39) [I37 <= I36 - 1] f5(I40, I41, I42, I43) -> f2(I40, 0, I41, I44) [I41 <= I42 - 1] f4(I45, I46, I47, I48) -> f2(I45, 0, I46, I49) [I47 <= I46 - 1] f4(I50, I51, I52, I53) -> f2(I50, 0, I51, I54) [I51 <= I52 - 1] f3(I55, I56, I57, I58) -> f2(I55, I56, I57, I59) [I58 <= I57 - 1] f3(I60, I61, I62, I63) -> f2(I60, I61, I62, I64) [I62 <= I63 - 1] f2(I65, I66, I67, I68) -> f5(I65, I65 - 1, I65 - 2, I69) [I65 = I67 /\ 0 <= I65 - 1] f2(I70, I71, I72, I73) -> f4(I70, I72 - 1, I70 - 2, I74) [0 = I71 /\ I72 <= I70 - 1 /\ 0 <= I72 - 1 /\ -1 <= I70 - 1] f2(I75, I76, I77, I78) -> f3(I75, I76, I77 + 1, I75 - 2) [0 <= I76 - 1 /\ -1 <= I75 - 1 /\ I77 <= I75 - 1 /\ 0 <= I77 - 1] f2(I79, I80, I81, I82) -> f3(I79, I80, I81 + 1, I79 - 2) [I80 <= -1 /\ -1 <= I79 - 1 /\ I81 <= I79 - 1 /\ 0 <= I81 - 1] f1(I83, I84, I85, I86) -> f2(20, 0, I84, I87) [-1 <= I84 - 1 /\ 0 <= I83 - 1]