/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.jar /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.jar
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


termination of the given Bare JBC problem could be proven:

(0) Bare JBC problem
(1) BareJBCToJBCProof [EQUIVALENT, 96 ms]
(2) JBC problem
(3) JBCToGraph [EQUIVALENT, 520 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 134 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms]
(12) IRSwT
(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(14) IRSwT
(15) IRSwTChainingProof [EQUIVALENT, 0 ms]
(16) IRSwT
(17) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms]
(18) IRSwT
(19) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(20) IRSwT
(21) TempFilterProof [SOUND, 26 ms]
(22) IntTRS
(23) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
(24) YES


----------------------------------------

(0)
Obligation:
need to prove termination of the following program:
public class Et1 {
    public static void main(String[] args) {
		Random.args = args;
	    int a = - Random.random(); 
	   	int b = - Random.random();	
	   	loop(a,b);
	}
	public static void loop(int a, int b){
	   	if (a > b) {
	   		b = b + a;
 			a = a + 1;
 			loop(a,b);
	   	}
    }
}


public class Random {
  static String[] args;
  static int index = 0;

  public static int random() {
      if (index >= args.length)
	  return 0;

      String string = args[index];
      index++;
      return string.length();
  }
}



----------------------------------------

(1) BareJBCToJBCProof (EQUIVALENT)
initialized classpath
----------------------------------------

(2)
Obligation:
need to prove termination of the following program:
public class Et1 {
    public static void main(String[] args) {
		Random.args = args;
	    int a = - Random.random(); 
	   	int b = - Random.random();	
	   	loop(a,b);
	}
	public static void loop(int a, int b){
	   	if (a > b) {
	   		b = b + a;
 			a = a + 1;
 			loop(a,b);
	   	}
    }
}


public class Random {
  static String[] args;
  static int index = 0;

  public static int random() {
      if (index >= args.length)
	  return 0;

      String string = args[index];
      index++;
      return string.length();
  }
}



----------------------------------------

(3) JBCToGraph (EQUIVALENT)
Constructed TerminationGraph.
----------------------------------------

(4)
Obligation:
Termination Graph based on JBC Program:
Et1.main([Ljava/lang/String;)V: Graph of 234 nodes with 0 SCCs.



Et1.loop(II)V: Graph of 24 nodes with 0 SCCs.





----------------------------------------

(5) TerminationGraphToSCCProof (SOUND)
Splitted TerminationGraph to 1 SCCs.
----------------------------------------

(6)
Obligation:
SCC of termination graph based on JBC Program.
SCC contains nodes from the following methods: Et1.loop(II)V
SCC calls the following helper methods: Et1.loop(II)V
Performed SCC analyses:
*Used field analysis yielded the following read fields:

*Marker field analysis yielded the following relations that could be markers:

----------------------------------------

(7) SCCToIRSProof (SOUND)
Transformed FIGraph SCCs to intTRSs. Log: 
Generated rules. Obtained 18 IRulesP rules:
f1036_0_loop_Load(EOS(STATIC_1036), i208, i209, i208, i209, i208) -> f1038_0_loop_LE(EOS(STATIC_1038), i208, i209, i208, i209, i208, i209) :|: TRUE
f1038_0_loop_LE(EOS(STATIC_1038), i208, i209, i208, i209, i208, i209) -> f1051_0_loop_LE(EOS(STATIC_1051), i208, i209, i208, i209, i208, i209) :|: i208 > i209
f1051_0_loop_LE(EOS(STATIC_1051), i208, i209, i208, i209, i208, i209) -> f1061_0_loop_Load(EOS(STATIC_1061), i208, i209, i208, i209) :|: i208 > i209
f1061_0_loop_Load(EOS(STATIC_1061), i208, i209, i208, i209) -> f1063_0_loop_Load(EOS(STATIC_1063), i208, i209, i208, i209) :|: TRUE
f1063_0_loop_Load(EOS(STATIC_1063), i208, i209, i208, i209) -> f1085_0_loop_IntArithmetic(EOS(STATIC_1085), i208, i209, i208, i209, i208) :|: TRUE
f1085_0_loop_IntArithmetic(EOS(STATIC_1085), i208, i209, i208, i209, i208) -> f1114_0_loop_Store(EOS(STATIC_1114), i208, i209, i208, i209 + i208) :|: TRUE
f1114_0_loop_Store(EOS(STATIC_1114), i208, i209, i208, i238) -> f1117_0_loop_Load(EOS(STATIC_1117), i208, i209, i208, i238) :|: TRUE
f1117_0_loop_Load(EOS(STATIC_1117), i208, i209, i208, i238) -> f1187_0_loop_ConstantStackPush(EOS(STATIC_1187), i208, i209, i238, i208) :|: TRUE
f1187_0_loop_ConstantStackPush(EOS(STATIC_1187), i208, i209, i238, i208) -> f1188_0_loop_IntArithmetic(EOS(STATIC_1188), i208, i209, i238, i208, 1) :|: TRUE
f1188_0_loop_IntArithmetic(EOS(STATIC_1188), i208, i209, i238, i208, matching1) -> f1189_0_loop_Store(EOS(STATIC_1189), i208, i209, i238, i208 + 1) :|: TRUE && matching1 = 1
f1189_0_loop_Store(EOS(STATIC_1189), i208, i209, i238, i243) -> f1190_0_loop_Load(EOS(STATIC_1190), i208, i209, i243, i238) :|: TRUE
f1190_0_loop_Load(EOS(STATIC_1190), i208, i209, i243, i238) -> f1191_0_loop_Load(EOS(STATIC_1191), i208, i209, i238, i243) :|: TRUE
f1191_0_loop_Load(EOS(STATIC_1191), i208, i209, i238, i243) -> f1192_0_loop_InvokeMethod(EOS(STATIC_1192), i208, i209, i243, i238) :|: TRUE
f1192_0_loop_InvokeMethod(EOS(STATIC_1192), i208, i209, i243, i238) -> f1193_0_loop_Load(EOS(STATIC_1193), i243, i238, i243, i238) :|: i208 > i209 && i243 > i208 && i243 > i209
f1192_0_loop_InvokeMethod(EOS(STATIC_1192), i208, i209, i243, i238) -> f1193_1_loop_Load(EOS(STATIC_1193), i208, i209, i243, i238) :|: i208 > i209 && i243 > i208 && i243 > i209
f1193_0_loop_Load(EOS(STATIC_1193), i243, i238, i243, i238) -> f1194_0_loop_Load(EOS(STATIC_1194), i243, i238, i243, i238) :|: TRUE
f1194_0_loop_Load(EOS(STATIC_1194), i243, i238, i243, i238) -> f1032_0_loop_Load(EOS(STATIC_1032), i243, i238, i243, i238) :|: TRUE
f1032_0_loop_Load(EOS(STATIC_1032), i208, i209, i208, i209) -> f1036_0_loop_Load(EOS(STATIC_1036), i208, i209, i208, i209, i208) :|: TRUE
Combined rules. Obtained 2 IRulesP rules:
f1036_0_loop_Load(EOS(STATIC_1036), i208:0, i209:0, i208:0, i209:0, i208:0) -> f1036_0_loop_Load(EOS(STATIC_1036), i208:0 + 1, i209:0 + i208:0, i208:0 + 1, i209:0 + i208:0, i208:0 + 1) :|: i209:0 < i208:0 && i208:0 + 1 > i208:0 && i209:0 < i208:0 + 1
Removed following non-SCC rules:
f1036_0_loop_Load(EOS(STATIC_1036), i208:0, i209:0, i208:0, i209:0, i208:0) -> f1193_1_loop_Load(EOS(STATIC_1193), i208:0, i209:0, i208:0 + 1, i209:0 + i208:0) :|: i209:0 < i208:0 && i208:0 + 1 > i208:0 && i209:0 < i208:0 + 1
Filtered constant ground arguments:
   f1036_0_loop_Load(x1, x2, x3, x4, x5, x6) -> f1036_0_loop_Load(x2, x3, x4, x5, x6)
   EOS(x1) -> EOS
Filtered duplicate arguments:
   f1036_0_loop_Load(x1, x2, x3, x4, x5) -> f1036_0_loop_Load(x4, x5)
Finished conversion. Obtained 1 rules.P rules:
f1036_0_loop_Load(i209:0, i208:0) -> f1036_0_loop_Load(i209:0 + i208:0, i208:0 + 1) :|: i208:0 + 1 > i208:0 && i209:0 < i208:0 + 1 && i209:0 < i208:0

----------------------------------------

(8)
Obligation:
Rules:
f1036_0_loop_Load(i209:0, i208:0) -> f1036_0_loop_Load(i209:0 + i208:0, i208:0 + 1) :|: i208:0 + 1 > i208:0 && i209:0 < i208:0 + 1 && i209:0 < i208:0

----------------------------------------

(9) IRSFormatTransformerProof (EQUIVALENT)
Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %).
----------------------------------------

(10)
Obligation:
Rules:
f1036_0_loop_Load(i209:0, i208:0) -> f1036_0_loop_Load(arith, arith1) :|: i208:0 + 1 > i208:0 && i209:0 < i208:0 + 1 && i209:0 < i208:0 && arith = i209:0 + i208:0 && arith1 = i208:0 + 1

----------------------------------------

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f1036_0_loop_Load(i209:0, i208:0) -> f1036_0_loop_Load(arith, arith1) :|: i208:0 + 1 > i208:0 && i209:0 < i208:0 + 1 && i209:0 < i208:0 && arith = i209:0 + i208:0 && arith1 = i208:0 + 1

Arcs:
(1) -> (1)

This digraph is fully evaluated!
----------------------------------------

(12)
Obligation:

Termination digraph:
Nodes:
(1) f1036_0_loop_Load(i209:0, i208:0) -> f1036_0_loop_Load(arith, arith1) :|: i208:0 + 1 > i208:0 && i209:0 < i208:0 + 1 && i209:0 < i208:0 && arith = i209:0 + i208:0 && arith1 = i208:0 + 1

Arcs:
(1) -> (1)

This digraph is fully evaluated!

----------------------------------------

(13) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(14)
Obligation:
Rules:
f1036_0_loop_Load(i209:0:0, i208:0:0) -> f1036_0_loop_Load(i209:0:0 + i208:0:0, i208:0:0 + 1) :|: i208:0:0 + 1 > i208:0:0 && i209:0:0 < i208:0:0 + 1 && i209:0:0 < i208:0:0

----------------------------------------

(15) IRSwTChainingProof (EQUIVALENT)
Chaining!
----------------------------------------

(16)
Obligation:
Rules:
f1036_0_loop_Load(x, x1) -> f1036_0_loop_Load(x + 2 * x1 + 1, x1 + 2) :|: TRUE && x + -1 * x1 <= -1 && x <= 0

----------------------------------------

(17) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f1036_0_loop_Load(x, x1) -> f1036_0_loop_Load(x + 2 * x1 + 1, x1 + 2) :|: TRUE && x + -1 * x1 <= -1 && x <= 0

Arcs:
(1) -> (1)

This digraph is fully evaluated!
----------------------------------------

(18)
Obligation:

Termination digraph:
Nodes:
(1) f1036_0_loop_Load(x, x1) -> f1036_0_loop_Load(x + 2 * x1 + 1, x1 + 2) :|: TRUE && x + -1 * x1 <= -1 && x <= 0

Arcs:
(1) -> (1)

This digraph is fully evaluated!

----------------------------------------

(19) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(20)
Obligation:
Rules:
f1036_0_loop_Load(x:0, x1:0) -> f1036_0_loop_Load(x:0 + 2 * x1:0 + 1, x1:0 + 2) :|: x:0 < 1 && x:0 + -1 * x1:0 <= -1

----------------------------------------

(21) TempFilterProof (SOUND)
Used the following sort dictionary for filtering: 
f1036_0_loop_Load(INTEGER, INTEGER)
Replaced non-predefined constructor symbols by 0.
----------------------------------------

(22)
Obligation:
Rules:
f1036_0_loop_Load(x:0, x1:0) -> f1036_0_loop_Load(c, c1) :|: c1 = x1:0 + 2 && c = x:0 + 2 * x1:0 + 1 && (x:0 < 1 && x:0 + -1 * x1:0 <= -1)

----------------------------------------

(23) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f1036_0_loop_Load(x, x1)] = 1 - 2*x - 2*x1 + x1^2

The following rules are decreasing:
f1036_0_loop_Load(x:0, x1:0) -> f1036_0_loop_Load(c, c1) :|: c1 = x1:0 + 2 && c = x:0 + 2 * x1:0 + 1 && (x:0 < 1 && x:0 + -1 * x1:0 <= -1)
The following rules are bounded:
f1036_0_loop_Load(x:0, x1:0) -> f1036_0_loop_Load(c, c1) :|: c1 = x1:0 + 2 && c = x:0 + 2 * x1:0 + 1 && (x:0 < 1 && x:0 + -1 * x1:0 <= -1)

----------------------------------------

(24)
YES