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