/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, 97 ms]
(2) JBC problem
(3) JBCToGraph [EQUIVALENT, 434 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 166 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 39 ms]
(12) IRSwT
(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(14) IRSwT
(15) TempFilterProof [SOUND, 53 ms]
(16) IntTRS
(17) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
(18) IntTRS
(19) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
(20) YES


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

(0)
Obligation:
need to prove termination of the following program:
/**
 * The classical Ackermann function.
 *
 * All calls terminate.
 *
 * Julia + BinTerm prove that all calls terminate
 *
 * Note that we have to express the basic cases as m <= 0 and n <= 0
 * in order to prove termination.
 *
 * @author <A HREF="mailto:fausto.spoto@univr.it">Fausto Spoto</A>
 */

public class Ackermann {

    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) {
	ack(10,12);
    }
}


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

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

(2)
Obligation:
need to prove termination of the following program:
/**
 * The classical Ackermann function.
 *
 * All calls terminate.
 *
 * Julia + BinTerm prove that all calls terminate
 *
 * Note that we have to express the basic cases as m <= 0 and n <= 0
 * in order to prove termination.
 *
 * @author <A HREF="mailto:fausto.spoto@univr.it">Fausto Spoto</A>
 */

public class Ackermann {

    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) {
	ack(10,12);
    }
}


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

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

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



Ackermann.ack(II)I: Graph of 52 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: Ackermann.ack(II)I
SCC calls the following helper methods: Ackermann.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 39 IRulesP rules:
f730_0_ack_GT(EOS(STATIC_730), i39, i40, i44, i42, i44) -> f734_0_ack_GT(EOS(STATIC_734), i39, i40, i44, i42, i44) :|: TRUE
f734_0_ack_GT(EOS(STATIC_734), i39, i40, i44, i42, i44) -> f737_0_ack_Load(EOS(STATIC_737), i39, i40, i44, i42) :|: i44 > 0
f737_0_ack_Load(EOS(STATIC_737), i39, i40, i44, i42) -> f739_0_ack_GT(EOS(STATIC_739), i39, i40, i44, i42, i42) :|: TRUE
f739_0_ack_GT(EOS(STATIC_739), i39, i40, i44, i45, i45) -> f741_0_ack_GT(EOS(STATIC_741), i39, i40, i44, i45, i45) :|: TRUE
f739_0_ack_GT(EOS(STATIC_739), i39, i40, i44, i46, i46) -> f742_0_ack_GT(EOS(STATIC_742), i39, i40, i44, i46, i46) :|: TRUE
f741_0_ack_GT(EOS(STATIC_741), i39, i40, i44, i45, i45) -> f744_0_ack_Load(EOS(STATIC_744), i39, i40, i44) :|: i45 <= 0
f744_0_ack_Load(EOS(STATIC_744), i39, i40, i44) -> f747_0_ack_ConstantStackPush(EOS(STATIC_747), i39, i40, i44) :|: TRUE
f747_0_ack_ConstantStackPush(EOS(STATIC_747), i39, i40, i44) -> f779_0_ack_IntArithmetic(EOS(STATIC_779), i39, i40, i44, 1) :|: TRUE
f779_0_ack_IntArithmetic(EOS(STATIC_779), i39, i40, i44, matching1) -> f782_0_ack_ConstantStackPush(EOS(STATIC_782), i39, i40, i44 - 1) :|: i44 > 0 && matching1 = 1
f782_0_ack_ConstantStackPush(EOS(STATIC_782), i39, i40, i51) -> f785_0_ack_InvokeMethod(EOS(STATIC_785), i39, i40, i51, 1) :|: TRUE
f785_0_ack_InvokeMethod(EOS(STATIC_785), i39, i40, i51, matching1) -> f788_0_ack_Load(EOS(STATIC_788), i51, 1, i51, 1) :|: TRUE && matching1 = 1
f785_0_ack_InvokeMethod(EOS(STATIC_785), i39, i40, i51, matching1) -> f788_1_ack_Load(EOS(STATIC_788), i39, i40, i51, 1) :|: TRUE && matching1 = 1
f788_0_ack_Load(EOS(STATIC_788), i51, matching1, i51, matching2) -> f791_0_ack_Load(EOS(STATIC_791), i51, 1, i51, 1) :|: TRUE && matching1 = 1 && matching2 = 1
f791_0_ack_Load(EOS(STATIC_791), i51, matching1, i51, matching2) -> f692_0_ack_Load(EOS(STATIC_692), i51, 1, i51, 1) :|: TRUE && matching1 = 1 && matching2 = 1
f692_0_ack_Load(EOS(STATIC_692), i39, i40, i41, i42) -> f730_0_ack_GT(EOS(STATIC_730), i39, i40, i41, i42, i41) :|: TRUE
f742_0_ack_GT(EOS(STATIC_742), i39, i40, i44, i46, i46) -> f745_0_ack_Load(EOS(STATIC_745), i39, i40, i44, i46) :|: i46 > 0
f745_0_ack_Load(EOS(STATIC_745), i39, i40, i44, i46) -> f748_0_ack_ConstantStackPush(EOS(STATIC_748), i39, i40, i44, i46, i44) :|: TRUE
f748_0_ack_ConstantStackPush(EOS(STATIC_748), i39, i40, i44, i46, i44) -> f780_0_ack_IntArithmetic(EOS(STATIC_780), i39, i40, i44, i46, i44, 1) :|: TRUE
f780_0_ack_IntArithmetic(EOS(STATIC_780), i39, i40, i44, i46, i44, matching1) -> f783_0_ack_Load(EOS(STATIC_783), i39, i40, i44, i46, i44 - 1) :|: i44 > 0 && matching1 = 1
f783_0_ack_Load(EOS(STATIC_783), i39, i40, i44, i46, i52) -> f786_0_ack_Load(EOS(STATIC_786), i39, i40, i46, i52, i44) :|: TRUE
f786_0_ack_Load(EOS(STATIC_786), i39, i40, i46, i52, i44) -> f789_0_ack_ConstantStackPush(EOS(STATIC_789), i39, i40, i52, i44, i46) :|: TRUE
f789_0_ack_ConstantStackPush(EOS(STATIC_789), i39, i40, i52, i44, i46) -> f792_0_ack_IntArithmetic(EOS(STATIC_792), i39, i40, i52, i44, i46, 1) :|: TRUE
f792_0_ack_IntArithmetic(EOS(STATIC_792), i39, i40, i52, i44, i46, matching1) -> f793_0_ack_InvokeMethod(EOS(STATIC_793), i39, i40, i52, i44, i46 - 1) :|: i46 > 0 && matching1 = 1
f793_0_ack_InvokeMethod(EOS(STATIC_793), i39, i40, i52, i44, i53) -> f794_0_ack_Load(EOS(STATIC_794), i44, i53, i44, i53) :|: i44 >= 1 && i52 < i44
f793_0_ack_InvokeMethod(EOS(STATIC_793), i39, i40, i52, i44, i53) -> f794_1_ack_Load(EOS(STATIC_794), i39, i40, i52, i44, i53) :|: i44 >= 1 && i52 < i44
f794_0_ack_Load(EOS(STATIC_794), i44, i53, i44, i53) -> f795_0_ack_Load(EOS(STATIC_795), i44, i53, i44, i53) :|: TRUE
f795_0_ack_Load(EOS(STATIC_795), i44, i53, i44, i53) -> f692_0_ack_Load(EOS(STATIC_692), i44, i53, i44, i53) :|: TRUE
f2648_0_ack_Return(EOS(STATIC_2648), i39, i40, i52, i73) -> f2653_0_ack_InvokeMethod(EOS(STATIC_2653), i39, i40, i52, i73) :|: TRUE
f2653_0_ack_InvokeMethod(EOS(STATIC_2653), i39, i40, i52, i73) -> f2681_0_ack_Load(EOS(STATIC_2681), i52, i73, i52, i73) :|: TRUE
f2653_0_ack_InvokeMethod(EOS(STATIC_2653), i39, i40, i52, i73) -> f2681_1_ack_Load(EOS(STATIC_2681), i39, i40, i52, i73) :|: TRUE
f2681_0_ack_Load(EOS(STATIC_2681), i52, i73, i52, i73) -> f2684_0_ack_Load(EOS(STATIC_2684), i52, i73, i52, i73) :|: TRUE
f2684_0_ack_Load(EOS(STATIC_2684), i52, i73, i52, i73) -> f692_0_ack_Load(EOS(STATIC_692), i52, i73, i52, i73) :|: TRUE
f2649_0_ack_Return(EOS(STATIC_2649), i39, i40, i52, i80) -> f2662_0_ack_InvokeMethod(EOS(STATIC_2662), i39, i40, i52, i80) :|: TRUE
f2662_0_ack_InvokeMethod(EOS(STATIC_2662), i39, i40, i52, i80) -> f2653_0_ack_InvokeMethod(EOS(STATIC_2653), i39, i40, i52, i80) :|: TRUE
f5270_0_ack_Return(EOS(STATIC_5270), i39, i40, i52, i127) -> f5336_0_ack_InvokeMethod(EOS(STATIC_5336), i39, i40, i52, i127) :|: TRUE
f5336_0_ack_InvokeMethod(EOS(STATIC_5336), i39, i40, i52, i127) -> f2653_0_ack_InvokeMethod(EOS(STATIC_2653), i39, i40, i52, i127) :|: TRUE
f794_1_ack_Load(EOS(STATIC_794), i39, i40, i52, i44, i53) -> f2648_0_ack_Return(EOS(STATIC_2648), i39, i40, i52, i73) :|: TRUE
f794_1_ack_Load(EOS(STATIC_794), i39, i40, i52, i44, i53) -> f2649_0_ack_Return(EOS(STATIC_2649), i39, i40, i52, i80) :|: TRUE
f794_1_ack_Load(EOS(STATIC_794), i39, i40, i52, i44, i53) -> f5270_0_ack_Return(EOS(STATIC_5270), i39, i40, i52, i127) :|: TRUE
Combined rules. Obtained 6 IRulesP rules:
f730_0_ack_GT(EOS(STATIC_730), i39:0, i40:0, i44:0, i42:0, i44:0) -> f730_0_ack_GT(EOS(STATIC_730), i44:0, i42:0 - 1, i44:0, i42:0 - 1, i44:0) :|: i44:0 > 0 && i42:0 > 0 && i44:0 - 1 < i44:0
f730_0_ack_GT(EOS(STATIC_730), i39:0, i40:0, i44:0, i42:0, i44:0) -> f2653_0_ack_InvokeMethod(EOS(STATIC_2653), i39:0, i40:0, i44:0 - 1, i80:0) :|: i44:0 > 0 && i42:0 > 0 && i44:0 - 1 < i44:0
f730_0_ack_GT(EOS(STATIC_730), i39:0, i40:0, i44:0, i42:0, i44:0) -> f730_0_ack_GT(EOS(STATIC_730), i44:0 - 1, 1, i44:0 - 1, 1, i44:0 - 1) :|: i44:0 > 0 && i42:0 < 1
f2653_0_ack_InvokeMethod(EOS(STATIC_2653), i39:0, i40:0, i52:0, i73:0) -> f730_0_ack_GT(EOS(STATIC_730), i52:0, i73:0, i52:0, i73:0, i52:0) :|: TRUE
Removed following non-SCC rules:
f730_0_ack_GT(EOS(STATIC_730), i39:0, i40:0, i44:0, i42:0, i44:0) -> f788_1_ack_Load(EOS(STATIC_788), i39:0, i40:0, i44:0 - 1, 1) :|: i44:0 > 0 && i42:0 < 1
f2653_0_ack_InvokeMethod(EOS(STATIC_2653), i39:0, i40:0, i52:0, i73:0) -> f2681_1_ack_Load(EOS(STATIC_2681), i39:0, i40:0, i52:0, i73:0) :|: TRUE
Filtered constant ground arguments:
   f730_0_ack_GT(x1, x2, x3, x4, x5, x6) -> f730_0_ack_GT(x2, x3, x4, x5, x6)
   f2653_0_ack_InvokeMethod(x1, x2, x3, x4, x5) -> f2653_0_ack_InvokeMethod(x2, x3, x4, x5)
Filtered duplicate arguments:
   f730_0_ack_GT(x1, x2, x3, x4, x5) -> f730_0_ack_GT(x1, x2, x4, x5)
Filtered unneeded arguments:
   f730_0_ack_GT(x1, x2, x3, x4) -> f730_0_ack_GT(x3, x4)
   f2653_0_ack_InvokeMethod(x1, x2, x3, x4) -> f2653_0_ack_InvokeMethod(x3, x4)
Finished conversion. Obtained 4 rules.P rules:
f730_0_ack_GT(i42:0, i44:0) -> f730_0_ack_GT(i42:0 - 1, i44:0) :|: i42:0 > 0 && i44:0 - 1 < i44:0 && i44:0 > 0
f730_0_ack_GT(i42:0, i44:0) -> f2653_0_ack_InvokeMethod(i44:0 - 1, i80:0) :|: i42:0 > 0 && i44:0 - 1 < i44:0 && i44:0 > 0
f730_0_ack_GT(i42:0, i44:0) -> f730_0_ack_GT(1, i44:0 - 1) :|: i44:0 > 0 && i42:0 < 1
f2653_0_ack_InvokeMethod(i52:0, i73:0) -> f730_0_ack_GT(i73:0, i52:0) :|: TRUE

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

(8)
Obligation:
Rules:
f730_0_ack_GT(i42:0, i44:0) -> f730_0_ack_GT(i42:0 - 1, i44:0) :|: i42:0 > 0 && i44:0 - 1 < i44:0 && i44:0 > 0
f730_0_ack_GT(x, x1) -> f2653_0_ack_InvokeMethod(x1 - 1, x2) :|: x > 0 && x1 - 1 < x1 && x1 > 0
f730_0_ack_GT(x3, x4) -> f730_0_ack_GT(1, x4 - 1) :|: x4 > 0 && x3 < 1
f2653_0_ack_InvokeMethod(i52:0, i73:0) -> f730_0_ack_GT(i73:0, i52:0) :|: TRUE

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

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

(10)
Obligation:
Rules:
f730_0_ack_GT(i42:0, i44:0) -> f730_0_ack_GT(arith, i44:0) :|: i42:0 > 0 && i44:0 - 1 < i44:0 && i44:0 > 0 && arith = i42:0 - 1
f730_0_ack_GT(x5, x6) -> f2653_0_ack_InvokeMethod(x7, x8) :|: x5 > 0 && x6 - 1 < x6 && x6 > 0 && x7 = x6 - 1
f730_0_ack_GT(x9, x10) -> f730_0_ack_GT(1, x11) :|: x10 > 0 && x9 < 1 && x11 = x10 - 1
f2653_0_ack_InvokeMethod(i52:0, i73:0) -> f730_0_ack_GT(i73:0, i52:0) :|: TRUE

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

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f730_0_ack_GT(i42:0, i44:0) -> f730_0_ack_GT(arith, i44:0) :|: i42:0 > 0 && i44:0 - 1 < i44:0 && i44:0 > 0 && arith = i42:0 - 1
(2) f730_0_ack_GT(x5, x6) -> f2653_0_ack_InvokeMethod(x7, x8) :|: x5 > 0 && x6 - 1 < x6 && x6 > 0 && x7 = x6 - 1
(3) f730_0_ack_GT(x9, x10) -> f730_0_ack_GT(1, x11) :|: x10 > 0 && x9 < 1 && x11 = x10 - 1
(4) f2653_0_ack_InvokeMethod(i52:0, i73:0) -> f730_0_ack_GT(i73:0, i52:0) :|: TRUE

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

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

(12)
Obligation:

Termination digraph:
Nodes:
(1) f730_0_ack_GT(i42:0, i44:0) -> f730_0_ack_GT(arith, i44:0) :|: i42:0 > 0 && i44:0 - 1 < i44:0 && i44:0 > 0 && arith = i42:0 - 1
(2) f730_0_ack_GT(x9, x10) -> f730_0_ack_GT(1, x11) :|: x10 > 0 && x9 < 1 && x11 = x10 - 1
(3) f2653_0_ack_InvokeMethod(i52:0, i73:0) -> f730_0_ack_GT(i73:0, i52:0) :|: TRUE
(4) f730_0_ack_GT(x5, x6) -> f2653_0_ack_InvokeMethod(x7, x8) :|: x5 > 0 && x6 - 1 < x6 && x6 > 0 && x7 = x6 - 1

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

This digraph is fully evaluated!

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

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

(14)
Obligation:
Rules:
f730_0_ack_GT(x9:0, x10:0) -> f730_0_ack_GT(1, x10:0 - 1) :|: x10:0 > 0 && x9:0 < 1
f730_0_ack_GT(x5:0, x6:0) -> f730_0_ack_GT(x8:0, x6:0 - 1) :|: x5:0 > 0 && x6:0 - 1 < x6:0 && x6:0 > 0
f730_0_ack_GT(i42:0:0, i44:0:0) -> f730_0_ack_GT(i42:0:0 - 1, i44:0:0) :|: i42:0:0 > 0 && i44:0:0 - 1 < i44:0:0 && i44:0:0 > 0

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

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

(16)
Obligation:
Rules:
f730_0_ack_GT(x9:0, x10:0) -> f730_0_ack_GT(c, c1) :|: c1 = x10:0 - 1 && c = 1 && (x10:0 > 0 && x9:0 < 1)
f730_0_ack_GT(x5:0, x6:0) -> f730_0_ack_GT(x8:0, c2) :|: c2 = x6:0 - 1 && (x5:0 > 0 && x6:0 - 1 < x6:0 && x6:0 > 0)
f730_0_ack_GT(i42:0:0, i44:0:0) -> f730_0_ack_GT(c3, i44:0:0) :|: c3 = i42:0:0 - 1 && (i42:0:0 > 0 && i44:0:0 - 1 < i44:0:0 && i44:0:0 > 0)

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

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

The following rules are decreasing:
f730_0_ack_GT(x9:0, x10:0) -> f730_0_ack_GT(c, c1) :|: c1 = x10:0 - 1 && c = 1 && (x10:0 > 0 && x9:0 < 1)
f730_0_ack_GT(x5:0, x6:0) -> f730_0_ack_GT(x8:0, c2) :|: c2 = x6:0 - 1 && (x5:0 > 0 && x6:0 - 1 < x6:0 && x6:0 > 0)
The following rules are bounded:
f730_0_ack_GT(x9:0, x10:0) -> f730_0_ack_GT(c, c1) :|: c1 = x10:0 - 1 && c = 1 && (x10:0 > 0 && x9:0 < 1)
f730_0_ack_GT(x5:0, x6:0) -> f730_0_ack_GT(x8:0, c2) :|: c2 = x6:0 - 1 && (x5:0 > 0 && x6:0 - 1 < x6:0 && x6:0 > 0)
f730_0_ack_GT(i42:0:0, i44:0:0) -> f730_0_ack_GT(c3, i44:0:0) :|: c3 = i42:0:0 - 1 && (i42:0:0 > 0 && i44:0:0 - 1 < i44:0:0 && i44:0:0 > 0)

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

(18)
Obligation:
Rules:
f730_0_ack_GT(i42:0:0, i44:0:0) -> f730_0_ack_GT(c3, i44:0:0) :|: c3 = i42:0:0 - 1 && (i42:0:0 > 0 && i44:0:0 - 1 < i44:0:0 && i44:0:0 > 0)

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

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

The following rules are decreasing:
f730_0_ack_GT(i42:0:0, i44:0:0) -> f730_0_ack_GT(c3, i44:0:0) :|: c3 = i42:0:0 - 1 && (i42:0:0 > 0 && i44:0:0 - 1 < i44:0:0 && i44:0:0 > 0)
The following rules are bounded:
f730_0_ack_GT(i42:0:0, i44:0:0) -> f730_0_ack_GT(c3, i44:0:0) :|: c3 = i42:0:0 - 1 && (i42:0:0 > 0 && i44:0:0 - 1 < i44:0:0 && i44:0:0 > 0)

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

(20)
YES