Integ Trans Syste 27634 pair #381737594

details
property	value
status	timeout (wallclock)
benchmark	Iterations.jar-obl-8.smt2
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
space	From_AProVE_2014
run statistics
property	value
solver	Ctrl
configuration	Transition
runtime (wallclock)	301.007961988 seconds
cpu usage	360.06510348
max memory	4.5092864E7
stage attributes
unavailable
output
/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
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions all output return to Integ Trans Syste 27634