/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, 539 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 152 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 45 ms]
(12) IRSwT
(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(14) IRSwT
(15) TempFilterProof [SOUND, 55 ms]
(16) IntTRS
(17) PolynomialOrderProcessor [EQUIVALENT, 18 ms]
(18) IntTRS
(19) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
(20) YES


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

(0)
Obligation:
need to prove termination of the following program:
public class AckermannR {

    public static int ack(int m, int n) {
	if (m <= 0) return n + 1;
	else if (n <= 0) return ack(m - 1,1);
	else return ack(m - 1,ack(m,n - 1));
    }

    public static void main(String[] args) {
	Random.args = args;
	ack(Random.random(),Random.random());
    }
}

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 AckermannR {

    public static int ack(int m, int n) {
	if (m <= 0) return n + 1;
	else if (n <= 0) return ack(m - 1,1);
	else return ack(m - 1,ack(m,n - 1));
    }

    public static void main(String[] args) {
	Random.args = args;
	ack(Random.random(),Random.random());
    }
}

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:
AckermannR.main([Ljava/lang/String;)V: Graph of 229 nodes with 0 SCCs.



AckermannR.ack(II)I: Graph of 50 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: AckermannR.ack(II)I
SCC calls the following helper methods: AckermannR.ack(II)I
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 36 IRulesP rules:
f777_0_ack_GT(EOS(STATIC_777), i131, i127, i131, i128, i131) -> f789_0_ack_GT(EOS(STATIC_789), i131, i127, i131, i128, i131) :|: TRUE
f789_0_ack_GT(EOS(STATIC_789), i131, i127, i131, i128, i131) -> f802_0_ack_Load(EOS(STATIC_802), i131, i127, i131, i128) :|: i131 > 0
f802_0_ack_Load(EOS(STATIC_802), i131, i127, i131, i128) -> f819_0_ack_GT(EOS(STATIC_819), i131, i127, i131, i128, i128) :|: TRUE
f819_0_ack_GT(EOS(STATIC_819), i131, i127, i131, matching1, matching2) -> f833_0_ack_GT(EOS(STATIC_833), i131, i127, i131, 0, 0) :|: TRUE && matching1 = 0 && matching2 = 0
f819_0_ack_GT(EOS(STATIC_819), i131, i127, i131, i134, i134) -> f835_0_ack_GT(EOS(STATIC_835), i131, i127, i131, i134, i134) :|: TRUE
f833_0_ack_GT(EOS(STATIC_833), i131, i127, i131, matching1, matching2) -> f847_0_ack_Load(EOS(STATIC_847), i131, i127, i131) :|: 0 <= 0 && matching1 = 0 && matching2 = 0
f847_0_ack_Load(EOS(STATIC_847), i131, i127, i131) -> f860_0_ack_ConstantStackPush(EOS(STATIC_860), i131, i127, i131) :|: TRUE
f860_0_ack_ConstantStackPush(EOS(STATIC_860), i131, i127, i131) -> f908_0_ack_IntArithmetic(EOS(STATIC_908), i131, i127, i131, 1) :|: TRUE
f908_0_ack_IntArithmetic(EOS(STATIC_908), i131, i127, i131, matching1) -> f998_0_ack_ConstantStackPush(EOS(STATIC_998), i131, i127, i131 - 1) :|: i131 > 0 && matching1 = 1
f998_0_ack_ConstantStackPush(EOS(STATIC_998), i131, i127, i178) -> f1015_0_ack_InvokeMethod(EOS(STATIC_1015), i131, i127, i178, 1) :|: TRUE
f1015_0_ack_InvokeMethod(EOS(STATIC_1015), i131, i127, i178, matching1) -> f1025_0_ack_Load(EOS(STATIC_1025), i178, 1, i178, 1) :|: i131 >= 1 && i178 < i131 && matching1 = 1
f1015_0_ack_InvokeMethod(EOS(STATIC_1015), i131, i127, i178, matching1) -> f1025_1_ack_Load(EOS(STATIC_1025), i131, i127, i178, 1) :|: i131 >= 1 && i178 < i131 && matching1 = 1
f1025_0_ack_Load(EOS(STATIC_1025), i178, matching1, i178, matching2) -> f1033_0_ack_Load(EOS(STATIC_1033), i178, 1, i178, 1) :|: TRUE && matching1 = 1 && matching2 = 1
f1033_0_ack_Load(EOS(STATIC_1033), i178, matching1, i178, matching2) -> f765_0_ack_Load(EOS(STATIC_765), i178, 1, i178, 1) :|: TRUE && matching1 = 1 && matching2 = 1
f765_0_ack_Load(EOS(STATIC_765), i126, i127, i126, i128) -> f777_0_ack_GT(EOS(STATIC_777), i126, i127, i126, i128, i126) :|: TRUE
f835_0_ack_GT(EOS(STATIC_835), i131, i127, i131, i134, i134) -> f849_0_ack_Load(EOS(STATIC_849), i131, i127, i131, i134) :|: i134 > 0
f849_0_ack_Load(EOS(STATIC_849), i131, i127, i131, i134) -> f862_0_ack_ConstantStackPush(EOS(STATIC_862), i131, i127, i131, i134, i131) :|: TRUE
f862_0_ack_ConstantStackPush(EOS(STATIC_862), i131, i127, i131, i134, i131) -> f911_0_ack_IntArithmetic(EOS(STATIC_911), i131, i127, i131, i134, i131, 1) :|: TRUE
f911_0_ack_IntArithmetic(EOS(STATIC_911), i131, i127, i131, i134, i131, matching1) -> f1001_0_ack_Load(EOS(STATIC_1001), i131, i127, i131, i134, i131 - 1) :|: i131 > 0 && matching1 = 1
f1001_0_ack_Load(EOS(STATIC_1001), i131, i127, i131, i134, i179) -> f1017_0_ack_Load(EOS(STATIC_1017), i131, i127, i134, i179, i131) :|: TRUE
f1017_0_ack_Load(EOS(STATIC_1017), i131, i127, i134, i179, i131) -> f1026_0_ack_ConstantStackPush(EOS(STATIC_1026), i131, i127, i179, i131, i134) :|: TRUE
f1026_0_ack_ConstantStackPush(EOS(STATIC_1026), i131, i127, i179, i131, i134) -> f1034_0_ack_IntArithmetic(EOS(STATIC_1034), i131, i127, i179, i131, i134, 1) :|: TRUE
f1034_0_ack_IntArithmetic(EOS(STATIC_1034), i131, i127, i179, i131, i134, matching1) -> f1036_0_ack_InvokeMethod(EOS(STATIC_1036), i131, i127, i179, i131, i134 - 1) :|: i134 > 0 && matching1 = 1
f1036_0_ack_InvokeMethod(EOS(STATIC_1036), i131, i127, i179, i131, i182) -> f1037_0_ack_Load(EOS(STATIC_1037), i131, i182, i131, i182) :|: i131 >= 1 && i179 < i131
f1036_0_ack_InvokeMethod(EOS(STATIC_1036), i131, i127, i179, i131, i182) -> f1037_1_ack_Load(EOS(STATIC_1037), i131, i127, i179, i131, i182) :|: i131 >= 1 && i179 < i131
f1037_0_ack_Load(EOS(STATIC_1037), i131, i182, i131, i182) -> f1062_0_ack_Load(EOS(STATIC_1062), i131, i182, i131, i182) :|: TRUE
f1062_0_ack_Load(EOS(STATIC_1062), i131, i182, i131, i182) -> f765_0_ack_Load(EOS(STATIC_765), i131, i182, i131, i182) :|: TRUE
f3739_0_ack_Return(EOS(STATIC_3739), i341, i127, i179, i336) -> f3747_0_ack_InvokeMethod(EOS(STATIC_3747), i341, i127, i179, i336) :|: TRUE
f3747_0_ack_InvokeMethod(EOS(STATIC_3747), i341, i127, i179, i336) -> f3878_0_ack_Load(EOS(STATIC_3878), i179, i336, i179, i336) :|: i341 >= 1 && i336 >= 1 && i179 < i341
f3747_0_ack_InvokeMethod(EOS(STATIC_3747), i341, i127, i179, i336) -> f3878_1_ack_Load(EOS(STATIC_3878), i341, i127, i179, i336) :|: i341 >= 1 && i336 >= 1 && i179 < i341
f3878_0_ack_Load(EOS(STATIC_3878), i179, i336, i179, i336) -> f3883_0_ack_Load(EOS(STATIC_3883), i179, i336, i179, i336) :|: TRUE
f3883_0_ack_Load(EOS(STATIC_3883), i179, i336, i179, i336) -> f765_0_ack_Load(EOS(STATIC_765), i179, i336, i179, i336) :|: TRUE
f5775_0_ack_Return(EOS(STATIC_5775), i780, i127, i179, i774) -> f5988_0_ack_InvokeMethod(EOS(STATIC_5988), i780, i127, i179, i774) :|: TRUE
f5988_0_ack_InvokeMethod(EOS(STATIC_5988), i780, i127, i179, i774) -> f3747_0_ack_InvokeMethod(EOS(STATIC_3747), i780, i127, i179, i774) :|: TRUE
f1037_1_ack_Load(EOS(STATIC_1037), i341, i127, i179, i341, i182) -> f3739_0_ack_Return(EOS(STATIC_3739), i341, i127, i179, i336) :|: TRUE
f1037_1_ack_Load(EOS(STATIC_1037), i780, i127, i179, i780, i182) -> f5775_0_ack_Return(EOS(STATIC_5775), i780, i127, i179, i774) :|: TRUE
Combined rules. Obtained 6 IRulesP rules:
f777_0_ack_GT(EOS(STATIC_777), i131:0, i127:0, i131:0, i128:0, i131:0) -> f3747_0_ack_InvokeMethod(EOS(STATIC_3747), i131:0, i127:0, i131:0 - 1, i336:0) :|: i131:0 > 0 && i128:0 > 0 && i131:0 - 1 < i131:0
f3747_0_ack_InvokeMethod(EOS(STATIC_3747), i341:0, i127:0, i179:0, i336:0) -> f777_0_ack_GT(EOS(STATIC_777), i179:0, i336:0, i179:0, i336:0, i179:0) :|: i336:0 > 0 && i341:0 > i179:0 && i341:0 > 0
f777_0_ack_GT(EOS(STATIC_777), i131:0, i127:0, i131:0, i128:0, i131:0) -> f777_0_ack_GT(EOS(STATIC_777), i131:0, i128:0 - 1, i131:0, i128:0 - 1, i131:0) :|: i131:0 > 0 && i128:0 > 0 && i131:0 - 1 < i131:0
f777_0_ack_GT(EOS(STATIC_777), i131:0, i127:0, i131:0, 0, i131:0) -> f777_0_ack_GT(EOS(STATIC_777), i131:0 - 1, 1, i131:0 - 1, 1, i131:0 - 1) :|: i131:0 > 0 && i131:0 - 1 < i131:0
Removed following non-SCC rules:
f777_0_ack_GT(EOS(STATIC_777), i131:0, i127:0, i131:0, 0, i131:0) -> f1025_1_ack_Load(EOS(STATIC_1025), i131:0, i127:0, i131:0 - 1, 1) :|: i131:0 > 0 && i131:0 - 1 < i131:0
f3747_0_ack_InvokeMethod(EOS(STATIC_3747), i341:0, i127:0, i179:0, i336:0) -> f3878_1_ack_Load(EOS(STATIC_3878), i341:0, i127:0, i179:0, i336:0) :|: i336:0 > 0 && i341:0 > i179:0 && i341:0 > 0
Filtered constant ground arguments:
   f777_0_ack_GT(x1, x2, x3, x4, x5, x6) -> f777_0_ack_GT(x2, x3, x4, x5, x6)
   f3747_0_ack_InvokeMethod(x1, x2, x3, x4, x5) -> f3747_0_ack_InvokeMethod(x2, x3, x4, x5)
Filtered duplicate arguments:
   f777_0_ack_GT(x1, x2, x3, x4, x5) -> f777_0_ack_GT(x2, x4, x5)
Filtered unneeded arguments:
   f777_0_ack_GT(x1, x2, x3) -> f777_0_ack_GT(x2, x3)
   f3747_0_ack_InvokeMethod(x1, x2, x3, x4) -> f3747_0_ack_InvokeMethod(x1, x3, x4)
Finished conversion. Obtained 4 rules.P rules:
f777_0_ack_GT(i128:0, i131:0) -> f3747_0_ack_InvokeMethod(i131:0, i131:0 - 1, i336:0) :|: i128:0 > 0 && i131:0 - 1 < i131:0 && i131:0 > 0
f3747_0_ack_InvokeMethod(i341:0, i179:0, i336:0) -> f777_0_ack_GT(i336:0, i179:0) :|: i341:0 > i179:0 && i341:0 > 0 && i336:0 > 0
f777_0_ack_GT(i128:0, i131:0) -> f777_0_ack_GT(i128:0 - 1, i131:0) :|: i128:0 > 0 && i131:0 - 1 < i131:0 && i131:0 > 0
f777_0_ack_GT(cons_0, i131:0) -> f777_0_ack_GT(1, i131:0 - 1) :|: i131:0 > 0 && i131:0 - 1 < i131:0 && cons_0 = 0

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

(8)
Obligation:
Rules:
f777_0_ack_GT(i128:0, i131:0) -> f3747_0_ack_InvokeMethod(i131:0, i131:0 - 1, i336:0) :|: i128:0 > 0 && i131:0 - 1 < i131:0 && i131:0 > 0
f3747_0_ack_InvokeMethod(x, x1, x2) -> f777_0_ack_GT(x2, x1) :|: x > x1 && x > 0 && x2 > 0
f777_0_ack_GT(x3, x4) -> f777_0_ack_GT(x3 - 1, x4) :|: x3 > 0 && x4 - 1 < x4 && x4 > 0
f777_0_ack_GT(x5, x6) -> f777_0_ack_GT(1, x6 - 1) :|: x6 > 0 && x6 - 1 < x6 && x5 = 0

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

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

(10)
Obligation:
Rules:
f777_0_ack_GT(i128:0, i131:0) -> f3747_0_ack_InvokeMethod(i131:0, arith, i336:0) :|: i128:0 > 0 && i131:0 - 1 < i131:0 && i131:0 > 0 && arith = i131:0 - 1
f3747_0_ack_InvokeMethod(x, x1, x2) -> f777_0_ack_GT(x2, x1) :|: x > x1 && x > 0 && x2 > 0
f777_0_ack_GT(x7, x8) -> f777_0_ack_GT(x9, x8) :|: x7 > 0 && x8 - 1 < x8 && x8 > 0 && x9 = x7 - 1
f777_0_ack_GT(x10, x11) -> f777_0_ack_GT(1, x12) :|: x11 > 0 && x11 - 1 < x11 && x10 = 0 && x12 = x11 - 1

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

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f777_0_ack_GT(i128:0, i131:0) -> f3747_0_ack_InvokeMethod(i131:0, arith, i336:0) :|: i128:0 > 0 && i131:0 - 1 < i131:0 && i131:0 > 0 && arith = i131:0 - 1
(2) f3747_0_ack_InvokeMethod(x, x1, x2) -> f777_0_ack_GT(x2, x1) :|: x > x1 && x > 0 && x2 > 0
(3) f777_0_ack_GT(x7, x8) -> f777_0_ack_GT(x9, x8) :|: x7 > 0 && x8 - 1 < x8 && x8 > 0 && x9 = x7 - 1
(4) f777_0_ack_GT(x10, x11) -> f777_0_ack_GT(1, x12) :|: x11 > 0 && x11 - 1 < x11 && x10 = 0 && x12 = x11 - 1

Arcs:
(1) -> (2)
(2) -> (1), (3)
(3) -> (1), (3), (4)
(4) -> (1), (3)

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

(12)
Obligation:

Termination digraph:
Nodes:
(1) f777_0_ack_GT(i128:0, i131:0) -> f3747_0_ack_InvokeMethod(i131:0, arith, i336:0) :|: i128:0 > 0 && i131:0 - 1 < i131:0 && i131:0 > 0 && arith = i131:0 - 1
(2) f777_0_ack_GT(x7, x8) -> f777_0_ack_GT(x9, x8) :|: x7 > 0 && x8 - 1 < x8 && x8 > 0 && x9 = x7 - 1
(3) f777_0_ack_GT(x10, x11) -> f777_0_ack_GT(1, x12) :|: x11 > 0 && x11 - 1 < x11 && x10 = 0 && x12 = x11 - 1
(4) f3747_0_ack_InvokeMethod(x, x1, x2) -> f777_0_ack_GT(x2, x1) :|: x > x1 && x > 0 && x2 > 0

Arcs:
(1) -> (4)
(2) -> (1), (2), (3)
(3) -> (1), (2)
(4) -> (1), (2)

This digraph is fully evaluated!

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

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

(14)
Obligation:
Rules:
f777_0_ack_GT(x7:0, x8:0) -> f777_0_ack_GT(x7:0 - 1, x8:0) :|: x7:0 > 0 && x8:0 - 1 < x8:0 && x8:0 > 0
f777_0_ack_GT(i128:0:0, i131:0:0) -> f777_0_ack_GT(i336:0:0, i131:0:0 - 1) :|: i336:0:0 > 0 && i131:0:0 > 0 && i131:0:0 - 1 < i131:0:0 && i128:0:0 > 0
f777_0_ack_GT(cons_0, x11:0) -> f777_0_ack_GT(1, x11:0 - 1) :|: x11:0 > 0 && x11:0 - 1 < x11:0 && cons_0 = 0

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

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

(16)
Obligation:
Rules:
f777_0_ack_GT(x7:0, x8:0) -> f777_0_ack_GT(c, x8:0) :|: c = x7:0 - 1 && (x7:0 > 0 && x8:0 - 1 < x8:0 && x8:0 > 0)
f777_0_ack_GT(i128:0:0, i131:0:0) -> f777_0_ack_GT(i336:0:0, c1) :|: c1 = i131:0:0 - 1 && (i336:0:0 > 0 && i131:0:0 > 0 && i131:0:0 - 1 < i131:0:0 && i128:0:0 > 0)
f777_0_ack_GT(c2, x11:0) -> f777_0_ack_GT(c3, c4) :|: c4 = x11:0 - 1 && (c3 = 1 && c2 = 0) && (x11:0 > 0 && x11:0 - 1 < x11:0 && cons_0 = 0)

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

(17) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f777_0_ack_GT(x, x1)] = -1 + x1

The following rules are decreasing:
f777_0_ack_GT(i128:0:0, i131:0:0) -> f777_0_ack_GT(i336:0:0, c1) :|: c1 = i131:0:0 - 1 && (i336:0:0 > 0 && i131:0:0 > 0 && i131:0:0 - 1 < i131:0:0 && i128:0:0 > 0)
f777_0_ack_GT(c2, x11:0) -> f777_0_ack_GT(c3, c4) :|: c4 = x11:0 - 1 && (c3 = 1 && c2 = 0) && (x11:0 > 0 && x11:0 - 1 < x11:0 && cons_0 = 0)
The following rules are bounded:
f777_0_ack_GT(x7:0, x8:0) -> f777_0_ack_GT(c, x8:0) :|: c = x7:0 - 1 && (x7:0 > 0 && x8:0 - 1 < x8:0 && x8:0 > 0)
f777_0_ack_GT(i128:0:0, i131:0:0) -> f777_0_ack_GT(i336:0:0, c1) :|: c1 = i131:0:0 - 1 && (i336:0:0 > 0 && i131:0:0 > 0 && i131:0:0 - 1 < i131:0:0 && i128:0:0 > 0)
f777_0_ack_GT(c2, x11:0) -> f777_0_ack_GT(c3, c4) :|: c4 = x11:0 - 1 && (c3 = 1 && c2 = 0) && (x11:0 > 0 && x11:0 - 1 < x11:0 && cons_0 = 0)

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

(18)
Obligation:
Rules:
f777_0_ack_GT(x7:0, x8:0) -> f777_0_ack_GT(c, x8:0) :|: c = x7:0 - 1 && (x7:0 > 0 && x8:0 - 1 < x8:0 && x8:0 > 0)

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

(19) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f777_0_ack_GT(x, x1)] = x

The following rules are decreasing:
f777_0_ack_GT(x7:0, x8:0) -> f777_0_ack_GT(c, x8:0) :|: c = x7:0 - 1 && (x7:0 > 0 && x8:0 - 1 < x8:0 && x8:0 > 0)
The following rules are bounded:
f777_0_ack_GT(x7:0, x8:0) -> f777_0_ack_GT(c, x8:0) :|: c = x7:0 - 1 && (x7:0 > 0 && x8:0 - 1 < x8:0 && x8:0 > 0)

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

(20)
YES