11.10/4.04	YES
11.19/4.07	proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar
11.19/4.07	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
11.19/4.07	
11.19/4.07	
11.19/4.07	termination of the given Bare JBC problem could be proven:
11.19/4.07	
11.19/4.07	(0) Bare JBC problem
11.19/4.07	(1) BareJBCToJBCProof [EQUIVALENT, 96 ms]
11.19/4.07	(2) JBC problem
11.19/4.07	(3) JBCToGraph [EQUIVALENT, 360 ms]
11.19/4.07	(4) JBCTerminationGraph
11.19/4.07	(5) TerminationGraphToSCCProof [SOUND, 0 ms]
11.19/4.07	(6) JBCTerminationSCC
11.19/4.07	(7) SCCToIRSProof [SOUND, 111 ms]
11.19/4.07	(8) IRSwT
11.19/4.07	(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
11.19/4.07	(10) IRSwT
11.19/4.07	(11) IRSwTTerminationDigraphProof [EQUIVALENT, 51 ms]
11.19/4.07	(12) IRSwT
11.19/4.07	(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
11.19/4.07	(14) IRSwT
11.19/4.07	(15) TempFilterProof [SOUND, 50 ms]
11.19/4.07	(16) IntTRS
11.19/4.07	(17) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
11.19/4.07	(18) IntTRS
11.19/4.07	(19) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
11.19/4.07	(20) YES
11.19/4.07	
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(0)
11.19/4.07	Obligation:
11.19/4.07	need to prove termination of the following program:
11.19/4.07	public class DivWithoutMinus{
11.19/4.07	  // adaption of the algorithm from [Kolbe 95]
11.19/4.07	  public static void main(String[] args) {
11.19/4.07	    Random.args = args;
11.19/4.07	
11.19/4.07	    int x = Random.random();
11.19/4.07	    int y = Random.random();
11.19/4.07	    int z = y;
11.19/4.07	    int res = 0;
11.19/4.07	
11.19/4.07	    while (z > 0 && (y == 0 || y > 0 && x > 0))	{
11.19/4.07	
11.19/4.07	      if (y == 0) {
11.19/4.07	        res++;
11.19/4.07	        y = z;
11.19/4.07	      }
11.19/4.07	      else {
11.19/4.07	        x--;
11.19/4.07	        y--;
11.19/4.07	      }
11.19/4.07	    }
11.19/4.07	  }
11.19/4.07	}
11.19/4.07	
11.19/4.07	
11.19/4.07	
11.19/4.07	public class Random {
11.19/4.07	  static String[] args;
11.19/4.07	  static int index = 0;
11.19/4.07	
11.19/4.07	  public static int random() {
11.19/4.07	    String string = args[index];
11.19/4.07	    index++;
11.19/4.07	    return string.length();
11.19/4.07	  }
11.19/4.07	}
11.19/4.07	
11.19/4.07	
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(1) BareJBCToJBCProof (EQUIVALENT)
11.19/4.07	initialized classpath
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(2)
11.19/4.07	Obligation:
11.19/4.07	need to prove termination of the following program:
11.19/4.07	public class DivWithoutMinus{
11.19/4.07	  // adaption of the algorithm from [Kolbe 95]
11.19/4.07	  public static void main(String[] args) {
11.19/4.07	    Random.args = args;
11.19/4.07	
11.19/4.07	    int x = Random.random();
11.19/4.07	    int y = Random.random();
11.19/4.07	    int z = y;
11.19/4.07	    int res = 0;
11.19/4.07	
11.19/4.07	    while (z > 0 && (y == 0 || y > 0 && x > 0))	{
11.19/4.07	
11.19/4.07	      if (y == 0) {
11.19/4.07	        res++;
11.19/4.07	        y = z;
11.19/4.07	      }
11.19/4.07	      else {
11.19/4.07	        x--;
11.19/4.07	        y--;
11.19/4.07	      }
11.19/4.07	    }
11.19/4.07	  }
11.19/4.07	}
11.19/4.07	
11.19/4.07	
11.19/4.07	
11.19/4.07	public class Random {
11.19/4.07	  static String[] args;
11.19/4.07	  static int index = 0;
11.19/4.07	
11.19/4.07	  public static int random() {
11.19/4.07	    String string = args[index];
11.19/4.07	    index++;
11.19/4.07	    return string.length();
11.19/4.07	  }
11.19/4.07	}
11.19/4.07	
11.19/4.07	
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(3) JBCToGraph (EQUIVALENT)
11.19/4.07	Constructed TerminationGraph.
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(4)
11.19/4.07	Obligation:
11.19/4.07	Termination Graph based on JBC Program:
11.19/4.07	DivWithoutMinus.main([Ljava/lang/String;)V: Graph of 202 nodes with 1 SCC.
11.19/4.07	
11.19/4.07	
11.19/4.07	
11.19/4.07	
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(5) TerminationGraphToSCCProof (SOUND)
11.19/4.07	Splitted TerminationGraph to 1 SCCs.
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(6)
11.19/4.07	Obligation:
11.19/4.07	SCC of termination graph based on JBC Program.
11.19/4.07	SCC contains nodes from the following methods: DivWithoutMinus.main([Ljava/lang/String;)V
11.19/4.07	SCC calls the following helper methods: 
11.19/4.07	Performed SCC analyses:
11.19/4.07	*Used field analysis yielded the following read fields:
11.19/4.07	
11.19/4.07	*Marker field analysis yielded the following relations that could be markers:
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(7) SCCToIRSProof (SOUND)
11.19/4.07	Transformed FIGraph SCCs to intTRSs. Log: 
11.19/4.07	Generated rules. Obtained 26 IRulesP rules:
11.19/4.07	f1916_0_main_LE(EOS(STATIC_1916), i72, i308, i336, i336) -> f1920_0_main_LE(EOS(STATIC_1920), i72, i308, i336, i336) :|: TRUE
11.19/4.07	f1920_0_main_LE(EOS(STATIC_1920), i72, i308, i336, i336) -> f1925_0_main_Load(EOS(STATIC_1925), i72, i308, i336) :|: i336 > 0
11.19/4.07	f1925_0_main_Load(EOS(STATIC_1925), i72, i308, i336) -> f1929_0_main_EQ(EOS(STATIC_1929), i72, i308, i336, i308) :|: TRUE
11.19/4.07	f1929_0_main_EQ(EOS(STATIC_1929), i72, i339, i336, i339) -> f1932_0_main_EQ(EOS(STATIC_1932), i72, i339, i336, i339) :|: TRUE
11.19/4.07	f1929_0_main_EQ(EOS(STATIC_1929), i72, matching1, i336, matching2) -> f1933_0_main_EQ(EOS(STATIC_1933), i72, 0, i336, 0) :|: TRUE && matching1 = 0 && matching2 = 0
11.19/4.07	f1932_0_main_EQ(EOS(STATIC_1932), i72, i339, i336, i339) -> f1935_0_main_Load(EOS(STATIC_1935), i72, i339, i336) :|: i339 > 0
11.19/4.07	f1935_0_main_Load(EOS(STATIC_1935), i72, i339, i336) -> f1940_0_main_LE(EOS(STATIC_1940), i72, i339, i336, i339) :|: TRUE
11.19/4.07	f1940_0_main_LE(EOS(STATIC_1940), i72, i339, i336, i339) -> f1945_0_main_Load(EOS(STATIC_1945), i72, i339, i336) :|: i339 > 0
11.19/4.07	f1945_0_main_Load(EOS(STATIC_1945), i72, i339, i336) -> f1951_0_main_LE(EOS(STATIC_1951), i72, i339, i336, i72) :|: TRUE
11.19/4.07	f1951_0_main_LE(EOS(STATIC_1951), i342, i339, i336, i342) -> f1959_0_main_LE(EOS(STATIC_1959), i342, i339, i336, i342) :|: TRUE
11.19/4.07	f1959_0_main_LE(EOS(STATIC_1959), i342, i339, i336, i342) -> f1971_0_main_Load(EOS(STATIC_1971), i342, i339, i336) :|: i342 > 0
11.19/4.07	f1971_0_main_Load(EOS(STATIC_1971), i342, i339, i336) -> f1978_0_main_NE(EOS(STATIC_1978), i342, i339, i336, i339) :|: TRUE
11.19/4.07	f1978_0_main_NE(EOS(STATIC_1978), i342, i339, i336, i339) -> f2053_0_main_Inc(EOS(STATIC_2053), i342, i339, i336) :|: i339 > 0
11.19/4.07	f2053_0_main_Inc(EOS(STATIC_2053), i342, i339, i336) -> f2055_0_main_Inc(EOS(STATIC_2055), i342 + -1, i339, i336) :|: TRUE
11.19/4.07	f2055_0_main_Inc(EOS(STATIC_2055), i350, i339, i336) -> f2058_0_main_JMP(EOS(STATIC_2058), i350, i339 + -1, i336) :|: TRUE
11.19/4.07	f2058_0_main_JMP(EOS(STATIC_2058), i350, i352, i336) -> f2118_0_main_Load(EOS(STATIC_2118), i350, i352, i336) :|: TRUE
11.19/4.07	f2118_0_main_Load(EOS(STATIC_2118), i350, i352, i336) -> f1910_0_main_Load(EOS(STATIC_1910), i350, i352, i336) :|: TRUE
11.19/4.07	f1910_0_main_Load(EOS(STATIC_1910), i72, i308, i309) -> f1916_0_main_LE(EOS(STATIC_1916), i72, i308, i309, i309) :|: TRUE
11.19/4.07	f1933_0_main_EQ(EOS(STATIC_1933), i72, matching1, i336, matching2) -> f1938_0_main_Load(EOS(STATIC_1938), i72, 0, i336) :|: TRUE && matching1 = 0 && matching2 = 0
11.19/4.07	f1938_0_main_Load(EOS(STATIC_1938), i72, matching1, i336) -> f1943_0_main_NE(EOS(STATIC_1943), i72, 0, i336, 0) :|: TRUE && matching1 = 0
11.19/4.07	f1943_0_main_NE(EOS(STATIC_1943), i72, matching1, i336, matching2) -> f1948_0_main_Inc(EOS(STATIC_1948), i72, i336) :|: TRUE && matching1 = 0 && matching2 = 0
11.19/4.07	f1948_0_main_Inc(EOS(STATIC_1948), i72, i336) -> f1954_0_main_Load(EOS(STATIC_1954), i72, i336) :|: TRUE
11.19/4.07	f1954_0_main_Load(EOS(STATIC_1954), i72, i336) -> f1962_0_main_Store(EOS(STATIC_1962), i72, i336, i336) :|: TRUE
11.19/4.07	f1962_0_main_Store(EOS(STATIC_1962), i72, i336, i336) -> f1974_0_main_JMP(EOS(STATIC_1974), i72, i336, i336) :|: TRUE
11.19/4.07	f1974_0_main_JMP(EOS(STATIC_1974), i72, i336, i336) -> f2050_0_main_Load(EOS(STATIC_2050), i72, i336, i336) :|: TRUE
11.19/4.07	f2050_0_main_Load(EOS(STATIC_2050), i72, i336, i336) -> f1910_0_main_Load(EOS(STATIC_1910), i72, i336, i336) :|: TRUE
11.19/4.07	Combined rules. Obtained 2 IRulesP rules:
11.19/4.07	f1916_0_main_LE(EOS(STATIC_1916), i72:0, 0, i336:0, i336:0) -> f1916_0_main_LE(EOS(STATIC_1916), i72:0, i336:0, i336:0, i336:0) :|: i336:0 > 0
11.19/4.07	f1916_0_main_LE(EOS(STATIC_1916), i72:0, i308:0, i336:0, i336:0) -> f1916_0_main_LE(EOS(STATIC_1916), i72:0 - 1, i308:0 - 1, i336:0, i336:0) :|: i336:0 > 0 && i308:0 > 0 && i72:0 > 0
11.19/4.07	Filtered constant ground arguments:
11.19/4.07	   f1916_0_main_LE(x1, x2, x3, x4, x5) -> f1916_0_main_LE(x2, x3, x4, x5)
11.19/4.07	   EOS(x1) -> EOS
11.19/4.07	Filtered duplicate arguments:
11.19/4.07	   f1916_0_main_LE(x1, x2, x3, x4) -> f1916_0_main_LE(x1, x2, x4)
11.19/4.07	Finished conversion. Obtained 2 rules.P rules:
11.19/4.07	f1916_0_main_LE(i72:0, cons_0, i336:0) -> f1916_0_main_LE(i72:0, i336:0, i336:0) :|: i336:0 > 0 && cons_0 = 0
11.19/4.07	f1916_0_main_LE(i72:0, i308:0, i336:0) -> f1916_0_main_LE(i72:0 - 1, i308:0 - 1, i336:0) :|: i308:0 > 0 && i72:0 > 0 && i336:0 > 0
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(8)
11.19/4.07	Obligation:
11.19/4.07	Rules:
11.19/4.07	f1916_0_main_LE(i72:0, cons_0, i336:0) -> f1916_0_main_LE(i72:0, i336:0, i336:0) :|: i336:0 > 0 && cons_0 = 0
11.19/4.07	f1916_0_main_LE(x, x1, x2) -> f1916_0_main_LE(x - 1, x1 - 1, x2) :|: x1 > 0 && x > 0 && x2 > 0
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(9) IRSFormatTransformerProof (EQUIVALENT)
11.19/4.07	Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %).
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(10)
11.19/4.07	Obligation:
11.19/4.07	Rules:
11.19/4.07	f1916_0_main_LE(i72:0, cons_0, i336:0) -> f1916_0_main_LE(i72:0, i336:0, i336:0) :|: i336:0 > 0 && cons_0 = 0
11.19/4.07	f1916_0_main_LE(x, x1, x2) -> f1916_0_main_LE(arith, arith1, x2) :|: x1 > 0 && x > 0 && x2 > 0 && arith = x - 1 && arith1 = x1 - 1
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(11) IRSwTTerminationDigraphProof (EQUIVALENT)
11.19/4.07	Constructed termination digraph!
11.19/4.07	Nodes:
11.19/4.07	(1) f1916_0_main_LE(i72:0, cons_0, i336:0) -> f1916_0_main_LE(i72:0, i336:0, i336:0) :|: i336:0 > 0 && cons_0 = 0
11.19/4.07	(2) f1916_0_main_LE(x, x1, x2) -> f1916_0_main_LE(arith, arith1, x2) :|: x1 > 0 && x > 0 && x2 > 0 && arith = x - 1 && arith1 = x1 - 1
11.19/4.07	
11.19/4.07	Arcs:
11.19/4.07	(1) -> (2)
11.19/4.07	(2) -> (1), (2)
11.19/4.07	
11.19/4.07	This digraph is fully evaluated!
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(12)
11.19/4.07	Obligation:
11.19/4.07	
11.19/4.07	Termination digraph:
11.19/4.07	Nodes:
11.19/4.07	(1) f1916_0_main_LE(i72:0, cons_0, i336:0) -> f1916_0_main_LE(i72:0, i336:0, i336:0) :|: i336:0 > 0 && cons_0 = 0
11.19/4.07	(2) f1916_0_main_LE(x, x1, x2) -> f1916_0_main_LE(arith, arith1, x2) :|: x1 > 0 && x > 0 && x2 > 0 && arith = x - 1 && arith1 = x1 - 1
11.19/4.07	
11.19/4.07	Arcs:
11.19/4.07	(1) -> (2)
11.19/4.07	(2) -> (1), (2)
11.19/4.07	
11.19/4.07	This digraph is fully evaluated!
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(13) IntTRSCompressionProof (EQUIVALENT)
11.19/4.07	Compressed rules.
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(14)
11.19/4.07	Obligation:
11.19/4.07	Rules:
11.19/4.07	f1916_0_main_LE(i72:0:0, cons_0, i336:0:0) -> f1916_0_main_LE(i72:0:0, i336:0:0, i336:0:0) :|: i336:0:0 > 0 && cons_0 = 0
11.19/4.07	f1916_0_main_LE(x:0, x1:0, x2:0) -> f1916_0_main_LE(x:0 - 1, x1:0 - 1, x2:0) :|: x1:0 > 0 && x:0 > 0 && x2:0 > 0
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(15) TempFilterProof (SOUND)
11.19/4.07	Used the following sort dictionary for filtering: 
11.19/4.07	f1916_0_main_LE(VARIABLE, INTEGER, INTEGER)
11.19/4.07	Replaced non-predefined constructor symbols by 0.
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(16)
11.19/4.07	Obligation:
11.19/4.07	Rules:
11.19/4.07	f1916_0_main_LE(i72:0:0, c, i336:0:0) -> f1916_0_main_LE(i72:0:0, i336:0:0, i336:0:0) :|: c = 0 && (i336:0:0 > 0 && cons_0 = 0)
11.19/4.07	f1916_0_main_LE(x:0, x1:0, x2:0) -> f1916_0_main_LE(c1, c2, x2:0) :|: c2 = x1:0 - 1 && c1 = x:0 - 1 && (x1:0 > 0 && x:0 > 0 && x2:0 > 0)
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(17) PolynomialOrderProcessor (EQUIVALENT)
11.19/4.07	Found the following polynomial interpretation:
11.19/4.07	[f1916_0_main_LE(x, x1, x2)] = -1 + x
11.19/4.07	
11.19/4.07	The following rules are decreasing:
11.19/4.07	f1916_0_main_LE(x:0, x1:0, x2:0) -> f1916_0_main_LE(c1, c2, x2:0) :|: c2 = x1:0 - 1 && c1 = x:0 - 1 && (x1:0 > 0 && x:0 > 0 && x2:0 > 0)
11.19/4.07	The following rules are bounded:
11.19/4.07	f1916_0_main_LE(x:0, x1:0, x2:0) -> f1916_0_main_LE(c1, c2, x2:0) :|: c2 = x1:0 - 1 && c1 = x:0 - 1 && (x1:0 > 0 && x:0 > 0 && x2:0 > 0)
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(18)
11.19/4.07	Obligation:
11.19/4.07	Rules:
11.19/4.07	f1916_0_main_LE(i72:0:0, c, i336:0:0) -> f1916_0_main_LE(i72:0:0, i336:0:0, i336:0:0) :|: c = 0 && (i336:0:0 > 0 && cons_0 = 0)
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(19) PolynomialOrderProcessor (EQUIVALENT)
11.19/4.07	Found the following polynomial interpretation:
11.19/4.07	[f1916_0_main_LE(x, x1, x2)] = -x1
11.19/4.07	
11.19/4.07	The following rules are decreasing:
11.19/4.07	f1916_0_main_LE(i72:0:0, c, i336:0:0) -> f1916_0_main_LE(i72:0:0, i336:0:0, i336:0:0) :|: c = 0 && (i336:0:0 > 0 && cons_0 = 0)
11.19/4.07	The following rules are bounded:
11.19/4.07	f1916_0_main_LE(i72:0:0, c, i336:0:0) -> f1916_0_main_LE(i72:0:0, i336:0:0, i336:0:0) :|: c = 0 && (i336:0:0 > 0 && cons_0 = 0)
11.19/4.07	
11.19/4.07	----------------------------------------
11.19/4.07	
11.19/4.07	(20)
11.19/4.07	YES
11.19/4.10	EOF