/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, x5) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5) f13#(I0, I1, I2, I3, I4) -> f11#(I3, I1, 2 * I3 + 1, I5, I6) [I3 <= y1 - 1 /\ I1 <= y2 - 1 /\ 0 <= 2 * I3 /\ I0 <= y1 - 1 /\ 0 <= I2 - 1] f11#(I7, I8, I9, I10, I11) -> f13#(I7, I8, I12, 2 * I7 + 2, I13) [I9 <= I13 - 1 /\ 0 <= 2 * I7 /\ 2 * I7 + 2 <= I13 - 1 /\ 2 * I7 + 2 <= I14 - 1 /\ I15 <= y3 - 1 /\ 0 <= I12 - 1 /\ 2 * I7 + 1 <= I14 - 1] f11#(I16, I17, I18, I19, I20) -> f13#(I16, I17, I21, 2 * I16 + 1, I22) [I18 <= I22 - 1 /\ 0 <= 2 * I16 /\ 2 * I16 + 2 <= I22 - 1 /\ 2 * I16 + 2 <= I23 - 1 /\ I24 <= I25 /\ 0 <= I21 - 1 /\ 2 * I16 + 1 <= I23 - 1] f11#(I36, I37, I38, I39, I40) -> f13#(I36, I37, I41, 2 * I36 + 1, I42) [I38 <= I42 - 1 /\ 0 <= I41 - 1 /\ 0 <= 2 * I36 /\ I42 <= 2 * I36 + 2] f5#(I52, I53, I54, I55, I56) -> f11#(0, I57, 1, I58, I59) [-1 <= I52 - 1 /\ I53 - 1 <= I60 - 1 /\ 0 <= I60 - 1] f8#(I72, I73, I74, I75, I76) -> f9#(I72, I73, I77, I78, I79) [I80 <= I73 - 1 /\ 0 <= I73 - 1 /\ I80 <= I81 - 1 /\ I82 <= I73 - 1 /\ I83 <= I72 /\ I82 <= I81 - 1 /\ I84 <= I73 - 1 /\ I73 <= I84 /\ 0 <= y6 - 1 /\ I73 <= I81 - 1] f8#(I96, I97, I98, I99, I100) -> f9#(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] f9#(I108, I109, I110, I111, I112) -> f8#(I108, I113, I114, I115, I116) [I117 <= I109 - 1 /\ 0 <= I109 - 1 /\ I117 <= I118 - 1 /\ I119 <= I109 - 1 /\ I120 <= I108 /\ I119 <= I118 - 1 /\ I113 <= I109 - 1 /\ I113 <= I109 - 1 /\ I109 <= I118 - 1 /\ 0 <= I109 - 1 - 2 * I117 /\ I109 - 1 - 2 * I117 <= 1 /\ 0 <= I109 - 1 - 2 * I119 /\ I109 - 1 - 2 * I119 <= 1 /\ I109 - 1 - 2 * I113 <= 1 /\ 0 <= I109 - 1 - 2 * I113] f8#(I121, I122, I123, I124, I125) -> f9#(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] f4#(I134, I135, I136, I137, I138) -> f8#(I139, I135, I140, I141, I142) [I134 <= I143 - 1 /\ 0 <= I143 - 1] f7#(I144, I145, I146, I147, I148) -> f5#(I145 - 1, I146, I149, I150, I151) [0 <= I144 - 1 /\ I145 <= I152 - 1] f5#(I153, I154, I155, I156, I157) -> f7#(I158, I153, I159, I160, I161) [-1 <= I153 - 1 /\ 0 <= I158 - 1 /\ 0 <= I162 - 1] f6#(I163, I164, I165, I166, I167) -> f7#(I168, I163, I164, I169, I170) [0 <= I168 - 1] f4#(I171, I172, I173, I174, I175) -> f4#(I171 + 1, I176, I177, I178, I179) [I171 <= I180 - 1 /\ 0 <= I180 - 1] f4#(I181, I182, I183, I184, I185) -> f5#(I186, I182, I187, I188, I189) [I190 <= I181 /\ I190 - 1 = I186] f2#(I191, I192, I193, I194, I195) -> f4#(0, 0, I196, I197, I198) [I199 <= I192 /\ I193 <= I199 /\ 0 <= I191 - 1] f3#(I200, I201, I202, I203, I204) -> f2#(I205, I200 + 1, I201, I206, I207) [I200 <= I208 - 1 /\ 0 <= I205 - 1] f2#(I209, I210, I211, I212, I213) -> f3#(I210, I211 + 1, I214, I215, I216) [-1 <= I217 - 1 /\ I210 <= I217 - 1 /\ I211 <= I217 - 1 /\ -1 <= I218 - 1 /\ -1 <= I211 - 1 /\ 0 <= I209 - 1] f2#(I219, I220, I221, I222, I223) -> f3#(I220, I221, I224, I225, I226) [I227 <= I221 /\ I220 <= I227 - 1 /\ -1 <= I227 - 1 /\ 0 <= I219 - 1] f1#(I228, I229, I230, I231, I232) -> f2#(I233, 0, 0, I234, I235) [0 <= I233 - 1 /\ 0 <= I228 - 1 /\ -1 <= I229 - 1 /\ I233 <= I228] R = init(x1, x2, x3, x4, x5) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5) f13(I0, I1, I2, I3, I4) -> f11(I3, I1, 2 * I3 + 1, I5, I6) [I3 <= y1 - 1 /\ I1 <= y2 - 1 /\ 0 <= 2 * I3 /\ I0 <= y1 - 1 /\ 0 <= I2 - 1] f11(I7, I8, I9, I10, I11) -> f13(I7, I8, I12, 2 * I7 + 2, I13) [I9 <= I13 - 1 /\ 0 <= 2 * I7 /\ 2 * I7 + 2 <= I13 - 1 /\ 2 * I7 + 2 <= I14 - 1 /\ I15 <= y3 - 1 /\ 0 <= I12 - 1 /\ 2 * I7 + 1 <= I14 - 1] f11(I16, I17, I18, I19, I20) -> f13(I16, I17, I21, 2 * I16 + 1, I22) [I18 <= I22 - 1 /\ 0 <= 2 * I16 /\ 2 * I16 + 2 <= I22 - 1 /\ 2 * I16 + 2 <= I23 - 1 /\ I24 <= I25 /\ 0 <= I21 - 1 /\ 2 * I16 + 1 <= I23 - 1] f13(I26, I27, I28, I29, I30) -> f12(I31, I26, I27, I32, I33) [I34 <= I27 /\ I29 <= I35 - 1 /\ I31 <= I28 /\ 0 <= I28 - 1 /\ 0 <= I31 - 1] f11(I36, I37, I38, I39, I40) -> f13(I36, I37, I41, 2 * I36 + 1, I42) [I38 <= I42 - 1 /\ 0 <= I41 - 1 /\ 0 <= 2 * I36 /\ I42 <= 2 * I36 + 2] f11(I43, I44, I45, I46, I47) -> f12(I48, I43, I44, I49, I50) [I51 <= I45 /\ 0 <= I48 - 1] f5(I52, I53, I54, I55, I56) -> f11(0, I57, 1, I58, I59) [-1 <= I52 - 1 /\ I53 - 1 <= I60 - 1 /\ 0 <= I60 - 1] f9(I61, I62, I63, I64, I65) -> f10(I66, I62, I61, I67, I68) [I69 <= I62 - 1 /\ 0 <= I62 - 1 /\ I69 <= I70 - 1 /\ I71 <= I62 - 1 /\ y4 <= I61 /\ I71 <= I70 - 1 /\ y5 <= I62 - 1 /\ I62 <= y5 /\ I62 <= I70 - 1 /\ 0 <= I66 - 1 /\ 0 <= I62 - 1 - 2 * I69 /\ I62 - 1 - 2 * I69 <= 1 /\ 0 <= I62 - 1 - 2 * I71 /\ I62 - 1 - 2 * I71 <= 1 /\ I62 - 1 - 2 * y5 <= 1 /\ 0 <= I62 - 1 - 2 * y5] f8(I72, I73, I74, I75, I76) -> f9(I72, I73, I77, I78, I79) [I80 <= I73 - 1 /\ 0 <= I73 - 1 /\ I80 <= I81 - 1 /\ I82 <= I73 - 1 /\ I83 <= I72 /\ I82 <= I81 - 1 /\ I84 <= I73 - 1 /\ I73 <= I84 /\ 0 <= y6 - 1 /\ I73 <= I81 - 1] f9(I85, I86, I87, I88, I89) -> f10(I90, I86, I85, I91, I92) [I93 <= I86 - 1 /\ 0 <= I86 - 1 /\ I85 <= I94 - 1 /\ I93 <= I95 - 1 /\ 0 <= I90 - 1 /\ I86 - 1 - 2 * I93 <= 1 /\ 0 <= I86 - 1 - 2 * I93] f8(I96, I97, I98, I99, I100) -> f9(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] f9(I108, I109, I110, I111, I112) -> f8(I108, I113, I114, I115, I116) [I117 <= I109 - 1 /\ 0 <= I109 - 1 /\ I117 <= I118 - 1 /\ I119 <= I109 - 1 /\ I120 <= I108 /\ I119 <= I118 - 1 /\ I113 <= I109 - 1 /\ I113 <= I109 - 1 /\ I109 <= I118 - 1 /\ 0 <= I109 - 1 - 2 * I117 /\ I109 - 1 - 2 * I117 <= 1 /\ 0 <= I109 - 1 - 2 * I119 /\ I109 - 1 - 2 * I119 <= 1 /\ I109 - 1 - 2 * I113 <= 1 /\ 0 <= I109 - 1 - 2 * I113] f8(I121, I122, I123, I124, I125) -> f9(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] f4(I134, I135, I136, I137, I138) -> f8(I139, I135, I140, I141, I142) [I134 <= I143 - 1 /\ 0 <= I143 - 1] f7(I144, I145, I146, I147, I148) -> f5(I145 - 1, I146, I149, I150, I151) [0 <= I144 - 1 /\ I145 <= I152 - 1] f5(I153, I154, I155, I156, I157) -> f7(I158, I153, I159, I160, I161) [-1 <= I153 - 1 /\ 0 <= I158 - 1 /\ 0 <= I162 - 1] f6(I163, I164, I165, I166, I167) -> f7(I168, I163, I164, I169, I170) [0 <= I168 - 1] f4(I171, I172, I173, I174, I175) -> f4(I171 + 1, I176, I177, I178, I179) [I171 <= I180 - 1 /\ 0 <= I180 - 1] f4(I181, I182, I183, I184, I185) -> f5(I186, I182, I187, I188, I189) [I190 <= I181 /\ I190 - 1 = I186] f2(I191, I192, I193, I194, I195) -> f4(0, 0, I196, I197, I198) [I199 <= I192 /\ I193 <= I199 /\ 0 <= I191 - 1] f3(I200, I201, I202, I203, I204) -> f2(I205, I200 + 1, I201, I206, I207) [I200 <= I208 - 1 /\ 0 <= I205 - 1] f2(I209, I210, I211, I212, I213) -> f3(I210, I211 + 1, I214, I215, I216) [-1 <= I217 - 1 /\ I210 <= I217 - 1 /\ I211 <= I217 - 1 /\ -1 <= I218 - 1 /\ -1 <= I211 - 1 /\ 0 <= I209 - 1] f2(I219, I220, I221, I222, I223) -> f3(I220, I221, I224, I225, I226) [I227 <= I221 /\ I220 <= I227 - 1 /\ -1 <= I227 - 1 /\ 0 <= I219 - 1] f1(I228, I229, I230, I231, I232) -> f2(I233, 0, 0, I234, I235) [0 <= I233 - 1 /\ 0 <= I228 - 1 /\ -1 <= I229 - 1 /\ I233 <= I228] The dependency graph for this problem is: 0 -> 20 1 -> 2, 3, 4 2 -> 1 3 -> 1 4 -> 1 5 -> 2, 3, 4 6 -> 7 -> 8 8 -> 7, 9 9 -> 8 10 -> 7, 9 11 -> 5, 12 12 -> 11 13 -> 11 14 -> 10, 14, 15 15 -> 5, 12 16 -> 10, 14, 15 17 -> 16, 18, 19 18 -> 17 19 -> 17 20 -> 16, 18 Where: 0) init#(x1, x2, x3, x4, x5) -> f1#(rnd1, rnd2, rnd3, rnd4, rnd5) 1) f13#(I0, I1, I2, I3, I4) -> f11#(I3, I1, 2 * I3 + 1, I5, I6) [I3 <= y1 - 1 /\ I1 <= y2 - 1 /\ 0 <= 2 * I3 /\ I0 <= y1 - 1 /\ 0 <= I2 - 1] 2) f11#(I7, I8, I9, I10, I11) -> f13#(I7, I8, I12, 2 * I7 + 2, I13) [I9 <= I13 - 1 /\ 0 <= 2 * I7 /\ 2 * I7 + 2 <= I13 - 1 /\ 2 * I7 + 2 <= I14 - 1 /\ I15 <= y3 - 1 /\ 0 <= I12 - 1 /\ 2 * I7 + 1 <= I14 - 1] 3) f11#(I16, I17, I18, I19, I20) -> f13#(I16, I17, I21, 2 * I16 + 1, I22) [I18 <= I22 - 1 /\ 0 <= 2 * I16 /\ 2 * I16 + 2 <= I22 - 1 /\ 2 * I16 + 2 <= I23 - 1 /\ I24 <= I25 /\ 0 <= I21 - 1 /\ 2 * I16 + 1 <= I23 - 1] 4) f11#(I36, I37, I38, I39, I40) -> f13#(I36, I37, I41, 2 * I36 + 1, I42) [I38 <= I42 - 1 /\ 0 <= I41 - 1 /\ 0 <= 2 * I36 /\ I42 <= 2 * I36 + 2] 5) f5#(I52, I53, I54, I55, I56) -> f11#(0, I57, 1, I58, I59) [-1 <= I52 - 1 /\ I53 - 1 <= I60 - 1 /\ 0 <= I60 - 1] 6) f8#(I72, I73, I74, I75, I76) -> f9#(I72, I73, I77, I78, I79) [I80 <= I73 - 1 /\ 0 <= I73 - 1 /\ I80 <= I81 - 1 /\ I82 <= I73 - 1 /\ I83 <= I72 /\ I82 <= I81 - 1 /\ I84 <= I73 - 1 /\ I73 <= I84 /\ 0 <= y6 - 1 /\ I73 <= I81 - 1] 7) f8#(I96, I97, I98, I99, I100) -> f9#(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] 8) f9#(I108, I109, I110, I111, I112) -> f8#(I108, I113, I114, I115, I116) [I117 <= I109 - 1 /\ 0 <= I109 - 1 /\ I117 <= I118 - 1 /\ I119 <= I109 - 1 /\ I120 <= I108 /\ I119 <= I118 - 1 /\ I113 <= I109 - 1 /\ I113 <= I109 - 1 /\ I109 <= I118 - 1 /\ 0 <= I109 - 1 - 2 * I117 /\ I109 - 1 - 2 * I117 <= 1 /\ 0 <= I109 - 1 - 2 * I119 /\ I109 - 1 - 2 * I119 <= 1 /\ I109 - 1 - 2 * I113 <= 1 /\ 0 <= I109 - 1 - 2 * I113] 9) f8#(I121, I122, I123, I124, I125) -> f9#(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] 10) f4#(I134, I135, I136, I137, I138) -> f8#(I139, I135, I140, I141, I142) [I134 <= I143 - 1 /\ 0 <= I143 - 1] 11) f7#(I144, I145, I146, I147, I148) -> f5#(I145 - 1, I146, I149, I150, I151) [0 <= I144 - 1 /\ I145 <= I152 - 1] 12) f5#(I153, I154, I155, I156, I157) -> f7#(I158, I153, I159, I160, I161) [-1 <= I153 - 1 /\ 0 <= I158 - 1 /\ 0 <= I162 - 1] 13) f6#(I163, I164, I165, I166, I167) -> f7#(I168, I163, I164, I169, I170) [0 <= I168 - 1] 14) f4#(I171, I172, I173, I174, I175) -> f4#(I171 + 1, I176, I177, I178, I179) [I171 <= I180 - 1 /\ 0 <= I180 - 1] 15) f4#(I181, I182, I183, I184, I185) -> f5#(I186, I182, I187, I188, I189) [I190 <= I181 /\ I190 - 1 = I186] 16) f2#(I191, I192, I193, I194, I195) -> f4#(0, 0, I196, I197, I198) [I199 <= I192 /\ I193 <= I199 /\ 0 <= I191 - 1] 17) f3#(I200, I201, I202, I203, I204) -> f2#(I205, I200 + 1, I201, I206, I207) [I200 <= I208 - 1 /\ 0 <= I205 - 1] 18) f2#(I209, I210, I211, I212, I213) -> f3#(I210, I211 + 1, I214, I215, I216) [-1 <= I217 - 1 /\ I210 <= I217 - 1 /\ I211 <= I217 - 1 /\ -1 <= I218 - 1 /\ -1 <= I211 - 1 /\ 0 <= I209 - 1] 19) f2#(I219, I220, I221, I222, I223) -> f3#(I220, I221, I224, I225, I226) [I227 <= I221 /\ I220 <= I227 - 1 /\ -1 <= I227 - 1 /\ 0 <= I219 - 1] 20) f1#(I228, I229, I230, I231, I232) -> f2#(I233, 0, 0, I234, I235) [0 <= I233 - 1 /\ 0 <= I228 - 1 /\ -1 <= I229 - 1 /\ I233 <= I228] We have the following SCCs. { 17, 18, 19 } { 14 } { 11, 12 } { 1, 2, 3, 4 } { 7, 8, 9 } DP problem for innermost termination. P = f8#(I96, I97, I98, I99, I100) -> f9#(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] f9#(I108, I109, I110, I111, I112) -> f8#(I108, I113, I114, I115, I116) [I117 <= I109 - 1 /\ 0 <= I109 - 1 /\ I117 <= I118 - 1 /\ I119 <= I109 - 1 /\ I120 <= I108 /\ I119 <= I118 - 1 /\ I113 <= I109 - 1 /\ I113 <= I109 - 1 /\ I109 <= I118 - 1 /\ 0 <= I109 - 1 - 2 * I117 /\ I109 - 1 - 2 * I117 <= 1 /\ 0 <= I109 - 1 - 2 * I119 /\ I109 - 1 - 2 * I119 <= 1 /\ I109 - 1 - 2 * I113 <= 1 /\ 0 <= I109 - 1 - 2 * I113] f8#(I121, I122, I123, I124, I125) -> f9#(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] R = init(x1, x2, x3, x4, x5) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5) f13(I0, I1, I2, I3, I4) -> f11(I3, I1, 2 * I3 + 1, I5, I6) [I3 <= y1 - 1 /\ I1 <= y2 - 1 /\ 0 <= 2 * I3 /\ I0 <= y1 - 1 /\ 0 <= I2 - 1] f11(I7, I8, I9, I10, I11) -> f13(I7, I8, I12, 2 * I7 + 2, I13) [I9 <= I13 - 1 /\ 0 <= 2 * I7 /\ 2 * I7 + 2 <= I13 - 1 /\ 2 * I7 + 2 <= I14 - 1 /\ I15 <= y3 - 1 /\ 0 <= I12 - 1 /\ 2 * I7 + 1 <= I14 - 1] f11(I16, I17, I18, I19, I20) -> f13(I16, I17, I21, 2 * I16 + 1, I22) [I18 <= I22 - 1 /\ 0 <= 2 * I16 /\ 2 * I16 + 2 <= I22 - 1 /\ 2 * I16 + 2 <= I23 - 1 /\ I24 <= I25 /\ 0 <= I21 - 1 /\ 2 * I16 + 1 <= I23 - 1] f13(I26, I27, I28, I29, I30) -> f12(I31, I26, I27, I32, I33) [I34 <= I27 /\ I29 <= I35 - 1 /\ I31 <= I28 /\ 0 <= I28 - 1 /\ 0 <= I31 - 1] f11(I36, I37, I38, I39, I40) -> f13(I36, I37, I41, 2 * I36 + 1, I42) [I38 <= I42 - 1 /\ 0 <= I41 - 1 /\ 0 <= 2 * I36 /\ I42 <= 2 * I36 + 2] f11(I43, I44, I45, I46, I47) -> f12(I48, I43, I44, I49, I50) [I51 <= I45 /\ 0 <= I48 - 1] f5(I52, I53, I54, I55, I56) -> f11(0, I57, 1, I58, I59) [-1 <= I52 - 1 /\ I53 - 1 <= I60 - 1 /\ 0 <= I60 - 1] f9(I61, I62, I63, I64, I65) -> f10(I66, I62, I61, I67, I68) [I69 <= I62 - 1 /\ 0 <= I62 - 1 /\ I69 <= I70 - 1 /\ I71 <= I62 - 1 /\ y4 <= I61 /\ I71 <= I70 - 1 /\ y5 <= I62 - 1 /\ I62 <= y5 /\ I62 <= I70 - 1 /\ 0 <= I66 - 1 /\ 0 <= I62 - 1 - 2 * I69 /\ I62 - 1 - 2 * I69 <= 1 /\ 0 <= I62 - 1 - 2 * I71 /\ I62 - 1 - 2 * I71 <= 1 /\ I62 - 1 - 2 * y5 <= 1 /\ 0 <= I62 - 1 - 2 * y5] f8(I72, I73, I74, I75, I76) -> f9(I72, I73, I77, I78, I79) [I80 <= I73 - 1 /\ 0 <= I73 - 1 /\ I80 <= I81 - 1 /\ I82 <= I73 - 1 /\ I83 <= I72 /\ I82 <= I81 - 1 /\ I84 <= I73 - 1 /\ I73 <= I84 /\ 0 <= y6 - 1 /\ I73 <= I81 - 1] f9(I85, I86, I87, I88, I89) -> f10(I90, I86, I85, I91, I92) [I93 <= I86 - 1 /\ 0 <= I86 - 1 /\ I85 <= I94 - 1 /\ I93 <= I95 - 1 /\ 0 <= I90 - 1 /\ I86 - 1 - 2 * I93 <= 1 /\ 0 <= I86 - 1 - 2 * I93] f8(I96, I97, I98, I99, I100) -> f9(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] f9(I108, I109, I110, I111, I112) -> f8(I108, I113, I114, I115, I116) [I117 <= I109 - 1 /\ 0 <= I109 - 1 /\ I117 <= I118 - 1 /\ I119 <= I109 - 1 /\ I120 <= I108 /\ I119 <= I118 - 1 /\ I113 <= I109 - 1 /\ I113 <= I109 - 1 /\ I109 <= I118 - 1 /\ 0 <= I109 - 1 - 2 * I117 /\ I109 - 1 - 2 * I117 <= 1 /\ 0 <= I109 - 1 - 2 * I119 /\ I109 - 1 - 2 * I119 <= 1 /\ I109 - 1 - 2 * I113 <= 1 /\ 0 <= I109 - 1 - 2 * I113] f8(I121, I122, I123, I124, I125) -> f9(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] f4(I134, I135, I136, I137, I138) -> f8(I139, I135, I140, I141, I142) [I134 <= I143 - 1 /\ 0 <= I143 - 1] f7(I144, I145, I146, I147, I148) -> f5(I145 - 1, I146, I149, I150, I151) [0 <= I144 - 1 /\ I145 <= I152 - 1] f5(I153, I154, I155, I156, I157) -> f7(I158, I153, I159, I160, I161) [-1 <= I153 - 1 /\ 0 <= I158 - 1 /\ 0 <= I162 - 1] f6(I163, I164, I165, I166, I167) -> f7(I168, I163, I164, I169, I170) [0 <= I168 - 1] f4(I171, I172, I173, I174, I175) -> f4(I171 + 1, I176, I177, I178, I179) [I171 <= I180 - 1 /\ 0 <= I180 - 1] f4(I181, I182, I183, I184, I185) -> f5(I186, I182, I187, I188, I189) [I190 <= I181 /\ I190 - 1 = I186] f2(I191, I192, I193, I194, I195) -> f4(0, 0, I196, I197, I198) [I199 <= I192 /\ I193 <= I199 /\ 0 <= I191 - 1] f3(I200, I201, I202, I203, I204) -> f2(I205, I200 + 1, I201, I206, I207) [I200 <= I208 - 1 /\ 0 <= I205 - 1] f2(I209, I210, I211, I212, I213) -> f3(I210, I211 + 1, I214, I215, I216) [-1 <= I217 - 1 /\ I210 <= I217 - 1 /\ I211 <= I217 - 1 /\ -1 <= I218 - 1 /\ -1 <= I211 - 1 /\ 0 <= I209 - 1] f2(I219, I220, I221, I222, I223) -> f3(I220, I221, I224, I225, I226) [I227 <= I221 /\ I220 <= I227 - 1 /\ -1 <= I227 - 1 /\ 0 <= I219 - 1] f1(I228, I229, I230, I231, I232) -> f2(I233, 0, 0, I234, I235) [0 <= I233 - 1 /\ 0 <= I228 - 1 /\ -1 <= I229 - 1 /\ I233 <= I228] We use the basic value criterion with the projection function NU: NU[f9#(z1,z2,z3,z4,z5)] = z2 NU[f8#(z1,z2,z3,z4,z5)] = z2 This gives the following inequalities: I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1 ==> I97 (>! \union =) I97 I117 <= I109 - 1 /\ 0 <= I109 - 1 /\ I117 <= I118 - 1 /\ I119 <= I109 - 1 /\ I120 <= I108 /\ I119 <= I118 - 1 /\ I113 <= I109 - 1 /\ I113 <= I109 - 1 /\ I109 <= I118 - 1 /\ 0 <= I109 - 1 - 2 * I117 /\ I109 - 1 - 2 * I117 <= 1 /\ 0 <= I109 - 1 - 2 * I119 /\ I109 - 1 - 2 * I119 <= 1 /\ I109 - 1 - 2 * I113 <= 1 /\ 0 <= I109 - 1 - 2 * I113 ==> I109 >! I113 I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1 ==> I122 (>! \union =) I122 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = f8#(I96, I97, I98, I99, I100) -> f9#(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] f8#(I121, I122, I123, I124, I125) -> f9#(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] R = init(x1, x2, x3, x4, x5) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5) f13(I0, I1, I2, I3, I4) -> f11(I3, I1, 2 * I3 + 1, I5, I6) [I3 <= y1 - 1 /\ I1 <= y2 - 1 /\ 0 <= 2 * I3 /\ I0 <= y1 - 1 /\ 0 <= I2 - 1] f11(I7, I8, I9, I10, I11) -> f13(I7, I8, I12, 2 * I7 + 2, I13) [I9 <= I13 - 1 /\ 0 <= 2 * I7 /\ 2 * I7 + 2 <= I13 - 1 /\ 2 * I7 + 2 <= I14 - 1 /\ I15 <= y3 - 1 /\ 0 <= I12 - 1 /\ 2 * I7 + 1 <= I14 - 1] f11(I16, I17, I18, I19, I20) -> f13(I16, I17, I21, 2 * I16 + 1, I22) [I18 <= I22 - 1 /\ 0 <= 2 * I16 /\ 2 * I16 + 2 <= I22 - 1 /\ 2 * I16 + 2 <= I23 - 1 /\ I24 <= I25 /\ 0 <= I21 - 1 /\ 2 * I16 + 1 <= I23 - 1] f13(I26, I27, I28, I29, I30) -> f12(I31, I26, I27, I32, I33) [I34 <= I27 /\ I29 <= I35 - 1 /\ I31 <= I28 /\ 0 <= I28 - 1 /\ 0 <= I31 - 1] f11(I36, I37, I38, I39, I40) -> f13(I36, I37, I41, 2 * I36 + 1, I42) [I38 <= I42 - 1 /\ 0 <= I41 - 1 /\ 0 <= 2 * I36 /\ I42 <= 2 * I36 + 2] f11(I43, I44, I45, I46, I47) -> f12(I48, I43, I44, I49, I50) [I51 <= I45 /\ 0 <= I48 - 1] f5(I52, I53, I54, I55, I56) -> f11(0, I57, 1, I58, I59) [-1 <= I52 - 1 /\ I53 - 1 <= I60 - 1 /\ 0 <= I60 - 1] f9(I61, I62, I63, I64, I65) -> f10(I66, I62, I61, I67, I68) [I69 <= I62 - 1 /\ 0 <= I62 - 1 /\ I69 <= I70 - 1 /\ I71 <= I62 - 1 /\ y4 <= I61 /\ I71 <= I70 - 1 /\ y5 <= I62 - 1 /\ I62 <= y5 /\ I62 <= I70 - 1 /\ 0 <= I66 - 1 /\ 0 <= I62 - 1 - 2 * I69 /\ I62 - 1 - 2 * I69 <= 1 /\ 0 <= I62 - 1 - 2 * I71 /\ I62 - 1 - 2 * I71 <= 1 /\ I62 - 1 - 2 * y5 <= 1 /\ 0 <= I62 - 1 - 2 * y5] f8(I72, I73, I74, I75, I76) -> f9(I72, I73, I77, I78, I79) [I80 <= I73 - 1 /\ 0 <= I73 - 1 /\ I80 <= I81 - 1 /\ I82 <= I73 - 1 /\ I83 <= I72 /\ I82 <= I81 - 1 /\ I84 <= I73 - 1 /\ I73 <= I84 /\ 0 <= y6 - 1 /\ I73 <= I81 - 1] f9(I85, I86, I87, I88, I89) -> f10(I90, I86, I85, I91, I92) [I93 <= I86 - 1 /\ 0 <= I86 - 1 /\ I85 <= I94 - 1 /\ I93 <= I95 - 1 /\ 0 <= I90 - 1 /\ I86 - 1 - 2 * I93 <= 1 /\ 0 <= I86 - 1 - 2 * I93] f8(I96, I97, I98, I99, I100) -> f9(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] f9(I108, I109, I110, I111, I112) -> f8(I108, I113, I114, I115, I116) [I117 <= I109 - 1 /\ 0 <= I109 - 1 /\ I117 <= I118 - 1 /\ I119 <= I109 - 1 /\ I120 <= I108 /\ I119 <= I118 - 1 /\ I113 <= I109 - 1 /\ I113 <= I109 - 1 /\ I109 <= I118 - 1 /\ 0 <= I109 - 1 - 2 * I117 /\ I109 - 1 - 2 * I117 <= 1 /\ 0 <= I109 - 1 - 2 * I119 /\ I109 - 1 - 2 * I119 <= 1 /\ I109 - 1 - 2 * I113 <= 1 /\ 0 <= I109 - 1 - 2 * I113] f8(I121, I122, I123, I124, I125) -> f9(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] f4(I134, I135, I136, I137, I138) -> f8(I139, I135, I140, I141, I142) [I134 <= I143 - 1 /\ 0 <= I143 - 1] f7(I144, I145, I146, I147, I148) -> f5(I145 - 1, I146, I149, I150, I151) [0 <= I144 - 1 /\ I145 <= I152 - 1] f5(I153, I154, I155, I156, I157) -> f7(I158, I153, I159, I160, I161) [-1 <= I153 - 1 /\ 0 <= I158 - 1 /\ 0 <= I162 - 1] f6(I163, I164, I165, I166, I167) -> f7(I168, I163, I164, I169, I170) [0 <= I168 - 1] f4(I171, I172, I173, I174, I175) -> f4(I171 + 1, I176, I177, I178, I179) [I171 <= I180 - 1 /\ 0 <= I180 - 1] f4(I181, I182, I183, I184, I185) -> f5(I186, I182, I187, I188, I189) [I190 <= I181 /\ I190 - 1 = I186] f2(I191, I192, I193, I194, I195) -> f4(0, 0, I196, I197, I198) [I199 <= I192 /\ I193 <= I199 /\ 0 <= I191 - 1] f3(I200, I201, I202, I203, I204) -> f2(I205, I200 + 1, I201, I206, I207) [I200 <= I208 - 1 /\ 0 <= I205 - 1] f2(I209, I210, I211, I212, I213) -> f3(I210, I211 + 1, I214, I215, I216) [-1 <= I217 - 1 /\ I210 <= I217 - 1 /\ I211 <= I217 - 1 /\ -1 <= I218 - 1 /\ -1 <= I211 - 1 /\ 0 <= I209 - 1] f2(I219, I220, I221, I222, I223) -> f3(I220, I221, I224, I225, I226) [I227 <= I221 /\ I220 <= I227 - 1 /\ -1 <= I227 - 1 /\ 0 <= I219 - 1] f1(I228, I229, I230, I231, I232) -> f2(I233, 0, 0, I234, I235) [0 <= I233 - 1 /\ 0 <= I228 - 1 /\ -1 <= I229 - 1 /\ I233 <= I228] The dependency graph for this problem is: 7 -> 9 -> Where: 7) f8#(I96, I97, I98, I99, I100) -> f9#(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] 9) f8#(I121, I122, I123, I124, I125) -> f9#(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] We have the following SCCs. DP problem for innermost termination. P = f13#(I0, I1, I2, I3, I4) -> f11#(I3, I1, 2 * I3 + 1, I5, I6) [I3 <= y1 - 1 /\ I1 <= y2 - 1 /\ 0 <= 2 * I3 /\ I0 <= y1 - 1 /\ 0 <= I2 - 1] f11#(I7, I8, I9, I10, I11) -> f13#(I7, I8, I12, 2 * I7 + 2, I13) [I9 <= I13 - 1 /\ 0 <= 2 * I7 /\ 2 * I7 + 2 <= I13 - 1 /\ 2 * I7 + 2 <= I14 - 1 /\ I15 <= y3 - 1 /\ 0 <= I12 - 1 /\ 2 * I7 + 1 <= I14 - 1] f11#(I16, I17, I18, I19, I20) -> f13#(I16, I17, I21, 2 * I16 + 1, I22) [I18 <= I22 - 1 /\ 0 <= 2 * I16 /\ 2 * I16 + 2 <= I22 - 1 /\ 2 * I16 + 2 <= I23 - 1 /\ I24 <= I25 /\ 0 <= I21 - 1 /\ 2 * I16 + 1 <= I23 - 1] f11#(I36, I37, I38, I39, I40) -> f13#(I36, I37, I41, 2 * I36 + 1, I42) [I38 <= I42 - 1 /\ 0 <= I41 - 1 /\ 0 <= 2 * I36 /\ I42 <= 2 * I36 + 2] R = init(x1, x2, x3, x4, x5) -> f1(rnd1, rnd2, rnd3, rnd4, rnd5) f13(I0, I1, I2, I3, I4) -> f11(I3, I1, 2 * I3 + 1, I5, I6) [I3 <= y1 - 1 /\ I1 <= y2 - 1 /\ 0 <= 2 * I3 /\ I0 <= y1 - 1 /\ 0 <= I2 - 1] f11(I7, I8, I9, I10, I11) -> f13(I7, I8, I12, 2 * I7 + 2, I13) [I9 <= I13 - 1 /\ 0 <= 2 * I7 /\ 2 * I7 + 2 <= I13 - 1 /\ 2 * I7 + 2 <= I14 - 1 /\ I15 <= y3 - 1 /\ 0 <= I12 - 1 /\ 2 * I7 + 1 <= I14 - 1] f11(I16, I17, I18, I19, I20) -> f13(I16, I17, I21, 2 * I16 + 1, I22) [I18 <= I22 - 1 /\ 0 <= 2 * I16 /\ 2 * I16 + 2 <= I22 - 1 /\ 2 * I16 + 2 <= I23 - 1 /\ I24 <= I25 /\ 0 <= I21 - 1 /\ 2 * I16 + 1 <= I23 - 1] f13(I26, I27, I28, I29, I30) -> f12(I31, I26, I27, I32, I33) [I34 <= I27 /\ I29 <= I35 - 1 /\ I31 <= I28 /\ 0 <= I28 - 1 /\ 0 <= I31 - 1] f11(I36, I37, I38, I39, I40) -> f13(I36, I37, I41, 2 * I36 + 1, I42) [I38 <= I42 - 1 /\ 0 <= I41 - 1 /\ 0 <= 2 * I36 /\ I42 <= 2 * I36 + 2] f11(I43, I44, I45, I46, I47) -> f12(I48, I43, I44, I49, I50) [I51 <= I45 /\ 0 <= I48 - 1] f5(I52, I53, I54, I55, I56) -> f11(0, I57, 1, I58, I59) [-1 <= I52 - 1 /\ I53 - 1 <= I60 - 1 /\ 0 <= I60 - 1] f9(I61, I62, I63, I64, I65) -> f10(I66, I62, I61, I67, I68) [I69 <= I62 - 1 /\ 0 <= I62 - 1 /\ I69 <= I70 - 1 /\ I71 <= I62 - 1 /\ y4 <= I61 /\ I71 <= I70 - 1 /\ y5 <= I62 - 1 /\ I62 <= y5 /\ I62 <= I70 - 1 /\ 0 <= I66 - 1 /\ 0 <= I62 - 1 - 2 * I69 /\ I62 - 1 - 2 * I69 <= 1 /\ 0 <= I62 - 1 - 2 * I71 /\ I62 - 1 - 2 * I71 <= 1 /\ I62 - 1 - 2 * y5 <= 1 /\ 0 <= I62 - 1 - 2 * y5] f8(I72, I73, I74, I75, I76) -> f9(I72, I73, I77, I78, I79) [I80 <= I73 - 1 /\ 0 <= I73 - 1 /\ I80 <= I81 - 1 /\ I82 <= I73 - 1 /\ I83 <= I72 /\ I82 <= I81 - 1 /\ I84 <= I73 - 1 /\ I73 <= I84 /\ 0 <= y6 - 1 /\ I73 <= I81 - 1] f9(I85, I86, I87, I88, I89) -> f10(I90, I86, I85, I91, I92) [I93 <= I86 - 1 /\ 0 <= I86 - 1 /\ I85 <= I94 - 1 /\ I93 <= I95 - 1 /\ 0 <= I90 - 1 /\ I86 - 1 - 2 * I93 <= 1 /\ 0 <= I86 - 1 - 2 * I93] f8(I96, I97, I98, I99, I100) -> f9(I96, I97, I101, I102, I103) [I104 <= I97 - 1 /\ 0 <= I97 - 1 /\ I96 <= I105 - 1 /\ 0 <= I106 - 1 /\ I104 <= I107 - 1] f9(I108, I109, I110, I111, I112) -> f8(I108, I113, I114, I115, I116) [I117 <= I109 - 1 /\ 0 <= I109 - 1 /\ I117 <= I118 - 1 /\ I119 <= I109 - 1 /\ I120 <= I108 /\ I119 <= I118 - 1 /\ I113 <= I109 - 1 /\ I113 <= I109 - 1 /\ I109 <= I118 - 1 /\ 0 <= I109 - 1 - 2 * I117 /\ I109 - 1 - 2 * I117 <= 1 /\ 0 <= I109 - 1 - 2 * I119 /\ I109 - 1 - 2 * I119 <= 1 /\ I109 - 1 - 2 * I113 <= 1 /\ 0 <= I109 - 1 - 2 * I113] f8(I121, I122, I123, I124, I125) -> f9(I121, I122, I126, I127, I128) [I129 <= I122 - 1 /\ 0 <= I122 - 1 /\ I129 <= I130 - 1 /\ I131 <= I122 - 1 /\ I132 <= I121 /\ I131 <= I130 - 1 /\ I133 <= I122 - 1 /\ I122 <= I130 - 1 /\ I133 <= I122 - 1] f4(I134, I135, I136, I137, I138) -> f8(I139, I135, I140, I141, I142) [I134 <= I143 - 1 /\ 0 <= I143 - 1] f7(I144, I145, I146, I147, I148) -> f5(I145 - 1, I146, I149, I150, I151) [0 <= I144 - 1 /\ I145 <= I152 - 1] f5(I153, I154, I155, I156, I157) -> f7(I158, I153, I159, I160, I161) [-1 <= I153 - 1 /\ 0 <= I158 - 1 /\ 0 <= I162 - 1] f6(I163, I164, I165, I166, I167) -> f7(I168, I163, I164, I169, I170) [0 <= I168 - 1] f4(I171, I172, I173, I174, I175) -> f4(I171 + 1, I176, I177, I178, I179) [I171 <= I180 - 1 /\ 0 <= I180 - 1] f4(I181, I182, I183, I184, I185) -> f5(I186, I182, I187, I188, I189) [I190 <= I181 /\ I190 - 1 = I186] f2(I191, I192, I193, I194, I195) -> f4(0, 0, I196, I197, I198) [I199 <= I192 /\ I193 <= I199 /\ 0 <= I191 - 1] f3(I200, I201, I202, I203, I204) -> f2(I205, I200 + 1, I201, I206, I207) [I200 <= I208 - 1 /\ 0 <= I205 - 1] f2(I209, I210, I211, I212, I213) -> f3(I210, I211 + 1, I214, I215, I216) [-1 <= I217 - 1 /\ I210 <= I217 - 1 /\ I211 <= I217 - 1 /\ -1 <= I218 - 1 /\ -1 <= I211 - 1 /\ 0 <= I209 - 1] f2(I219, I220, I221, I222, I223) -> f3(I220, I221, I224, I225, I226) [I227 <= I221 /\ I220 <= I227 - 1 /\ -1 <= I227 - 1 /\ 0 <= I219 - 1] f1(I228, I229, I230, I231, I232) -> f2(I233, 0, 0, I234, I235) [0 <= I233 - 1 /\ 0 <= I228 - 1 /\ -1 <= I229 - 1 /\ I233 <= I228]