6.79/2.71	YES
6.91/2.74	proof of /export/starexec/sandbox/benchmark/theBenchmark.jar
6.91/2.74	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.91/2.74	
6.91/2.74	
6.91/2.74	termination of the given Bare JBC problem could be proven:
6.91/2.74	
6.91/2.74	(0) Bare JBC problem
6.91/2.74	(1) BareJBCToJBCProof [EQUIVALENT, 96 ms]
6.91/2.74	(2) JBC problem
6.91/2.74	(3) JBCToGraph [EQUIVALENT, 345 ms]
6.91/2.74	(4) JBCTerminationGraph
6.91/2.74	(5) TerminationGraphToSCCProof [SOUND, 0 ms]
6.91/2.74	(6) JBCTerminationSCC
6.91/2.74	(7) SCCToIRSProof [SOUND, 55 ms]
6.91/2.74	(8) IRSwT
6.91/2.74	(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
6.91/2.74	(10) IRSwT
6.91/2.74	(11) IRSwTTerminationDigraphProof [EQUIVALENT, 37 ms]
6.91/2.74	(12) AND
6.91/2.74	    (13) IRSwT
6.91/2.74	        (14) IntTRSCompressionProof [EQUIVALENT, 0 ms]
6.91/2.74	        (15) IRSwT
6.91/2.74	        (16) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
6.91/2.74	        (17) IRSwT
6.91/2.74	        (18) TempFilterProof [SOUND, 23 ms]
6.91/2.74	        (19) IntTRS
6.91/2.74	        (20) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
6.91/2.74	        (21) YES
6.91/2.74	    (22) IRSwT
6.91/2.74	        (23) IntTRSCompressionProof [EQUIVALENT, 0 ms]
6.91/2.74	        (24) IRSwT
6.91/2.74	        (25) TempFilterProof [SOUND, 8 ms]
6.91/2.74	        (26) IntTRS
6.91/2.74	        (27) RankingReductionPairProof [EQUIVALENT, 0 ms]
6.91/2.74	        (28) YES
6.91/2.74	
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(0)
6.91/2.74	Obligation:
6.91/2.74	need to prove termination of the following program:
6.91/2.74	/**
6.91/2.74	 * Example taken from "A Term Rewriting Approach to the Automated Termination
6.91/2.74	 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf)
6.91/2.74	 * and converted to Java.
6.91/2.74	 */
6.91/2.74	
6.91/2.74	public class PastaB12 {
6.91/2.74	    public static void main(String[] args) {
6.91/2.74	        Random.args = args;
6.91/2.74	        int x = Random.random();
6.91/2.74	        int y = Random.random();
6.91/2.74	
6.91/2.74	        while (x > 0 || y > 0) {
6.91/2.74	            if (x > 0) {
6.91/2.74	                x--;
6.91/2.74	            } else if (y > 0) {
6.91/2.74	                y--;
6.91/2.74	            } else {
6.91/2.74	                continue;
6.91/2.74	            }
6.91/2.74	        }
6.91/2.74	    }
6.91/2.74	}
6.91/2.74	
6.91/2.74	
6.91/2.74	public class Random {
6.91/2.74	  static String[] args;
6.91/2.74	  static int index = 0;
6.91/2.74	
6.91/2.74	  public static int random() {
6.91/2.74	    String string = args[index];
6.91/2.74	    index++;
6.91/2.74	    return string.length();
6.91/2.74	  }
6.91/2.74	}
6.91/2.74	
6.91/2.74	
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(1) BareJBCToJBCProof (EQUIVALENT)
6.91/2.74	initialized classpath
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(2)
6.91/2.74	Obligation:
6.91/2.74	need to prove termination of the following program:
6.91/2.74	/**
6.91/2.74	 * Example taken from "A Term Rewriting Approach to the Automated Termination
6.91/2.74	 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf)
6.91/2.74	 * and converted to Java.
6.91/2.74	 */
6.91/2.74	
6.91/2.74	public class PastaB12 {
6.91/2.74	    public static void main(String[] args) {
6.91/2.74	        Random.args = args;
6.91/2.74	        int x = Random.random();
6.91/2.74	        int y = Random.random();
6.91/2.74	
6.91/2.74	        while (x > 0 || y > 0) {
6.91/2.74	            if (x > 0) {
6.91/2.74	                x--;
6.91/2.74	            } else if (y > 0) {
6.91/2.74	                y--;
6.91/2.74	            } else {
6.91/2.74	                continue;
6.91/2.74	            }
6.91/2.74	        }
6.91/2.74	    }
6.91/2.74	}
6.91/2.74	
6.91/2.74	
6.91/2.74	public class Random {
6.91/2.74	  static String[] args;
6.91/2.74	  static int index = 0;
6.91/2.74	
6.91/2.74	  public static int random() {
6.91/2.74	    String string = args[index];
6.91/2.74	    index++;
6.91/2.74	    return string.length();
6.91/2.74	  }
6.91/2.74	}
6.91/2.74	
6.91/2.74	
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(3) JBCToGraph (EQUIVALENT)
6.91/2.74	Constructed TerminationGraph.
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(4)
6.91/2.74	Obligation:
6.91/2.74	Termination Graph based on JBC Program:
6.91/2.74	PastaB12.main([Ljava/lang/String;)V: Graph of 186 nodes with 1 SCC.
6.91/2.74	
6.91/2.74	
6.91/2.74	
6.91/2.74	
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(5) TerminationGraphToSCCProof (SOUND)
6.91/2.74	Splitted TerminationGraph to 1 SCCs.
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(6)
6.91/2.74	Obligation:
6.91/2.74	SCC of termination graph based on JBC Program.
6.91/2.74	SCC contains nodes from the following methods: PastaB12.main([Ljava/lang/String;)V
6.91/2.74	SCC calls the following helper methods: 
6.91/2.74	Performed SCC analyses:
6.91/2.74	*Used field analysis yielded the following read fields:
6.91/2.74	
6.91/2.74	*Marker field analysis yielded the following relations that could be markers:
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(7) SCCToIRSProof (SOUND)
6.91/2.74	Transformed FIGraph SCCs to intTRSs. Log: 
6.91/2.74	Generated rules. Obtained 20 IRulesP rules:
6.91/2.74	f357_0_main_GT(EOS(STATIC_357), matching1, i47, matching2) -> f366_0_main_GT(EOS(STATIC_366), 0, i47, 0) :|: TRUE && matching1 = 0 && matching2 = 0
6.91/2.74	f357_0_main_GT(EOS(STATIC_357), i54, i47, i54) -> f367_0_main_GT(EOS(STATIC_367), i54, i47, i54) :|: TRUE
6.91/2.74	f366_0_main_GT(EOS(STATIC_366), matching1, i47, matching2) -> f381_0_main_Load(EOS(STATIC_381), 0, i47) :|: 0 <= 0 && matching1 = 0 && matching2 = 0
6.91/2.74	f381_0_main_Load(EOS(STATIC_381), matching1, i47) -> f396_0_main_LE(EOS(STATIC_396), 0, i47, i47) :|: TRUE && matching1 = 0
6.91/2.74	f396_0_main_LE(EOS(STATIC_396), matching1, i61, i61) -> f413_0_main_LE(EOS(STATIC_413), 0, i61, i61) :|: TRUE && matching1 = 0
6.91/2.74	f413_0_main_LE(EOS(STATIC_413), matching1, i61, i61) -> f464_0_main_Load(EOS(STATIC_464), 0, i61) :|: i61 > 0 && matching1 = 0
6.91/2.74	f464_0_main_Load(EOS(STATIC_464), matching1, i61) -> f478_0_main_LE(EOS(STATIC_478), 0, i61, 0) :|: TRUE && matching1 = 0
6.91/2.74	f478_0_main_LE(EOS(STATIC_478), matching1, i61, matching2) -> f551_0_main_Load(EOS(STATIC_551), 0, i61) :|: 0 <= 0 && matching1 = 0 && matching2 = 0
6.91/2.74	f551_0_main_Load(EOS(STATIC_551), matching1, i61) -> f1468_0_main_LE(EOS(STATIC_1468), 0, i61, i61) :|: TRUE && matching1 = 0
6.91/2.74	f1468_0_main_LE(EOS(STATIC_1468), matching1, i61, i61) -> f1483_0_main_Inc(EOS(STATIC_1483), 0, i61) :|: i61 > 0 && matching1 = 0
6.91/2.74	f1483_0_main_Inc(EOS(STATIC_1483), matching1, i61) -> f1497_0_main_JMP(EOS(STATIC_1497), 0, i61 + -1) :|: TRUE && matching1 = 0
6.91/2.74	f1497_0_main_JMP(EOS(STATIC_1497), matching1, i225) -> f2362_0_main_Load(EOS(STATIC_2362), 0, i225) :|: TRUE && matching1 = 0
6.91/2.74	f2362_0_main_Load(EOS(STATIC_2362), matching1, i225) -> f342_0_main_Load(EOS(STATIC_342), 0, i225) :|: TRUE && matching1 = 0
6.91/2.74	f342_0_main_Load(EOS(STATIC_342), i19, i47) -> f357_0_main_GT(EOS(STATIC_357), i19, i47, i19) :|: TRUE
6.91/2.74	f367_0_main_GT(EOS(STATIC_367), i54, i47, i54) -> f383_0_main_Load(EOS(STATIC_383), i54, i47) :|: i54 > 0
6.91/2.74	f383_0_main_Load(EOS(STATIC_383), i54, i47) -> f398_0_main_LE(EOS(STATIC_398), i54, i47, i54) :|: TRUE
6.91/2.74	f398_0_main_LE(EOS(STATIC_398), i54, i47, i54) -> f416_0_main_Inc(EOS(STATIC_416), i54, i47) :|: i54 > 0
6.91/2.74	f416_0_main_Inc(EOS(STATIC_416), i54, i47) -> f465_0_main_JMP(EOS(STATIC_465), i54 + -1, i47) :|: TRUE
6.91/2.74	f465_0_main_JMP(EOS(STATIC_465), i69, i47) -> f533_0_main_Load(EOS(STATIC_533), i69, i47) :|: TRUE
6.91/2.74	f533_0_main_Load(EOS(STATIC_533), i69, i47) -> f342_0_main_Load(EOS(STATIC_342), i69, i47) :|: TRUE
6.91/2.74	Combined rules. Obtained 2 IRulesP rules:
6.91/2.74	f357_0_main_GT(EOS(STATIC_357), i54:0, i47:0, i54:0) -> f357_0_main_GT(EOS(STATIC_357), i54:0 - 1, i47:0, i54:0 - 1) :|: i54:0 > 0
6.91/2.74	f357_0_main_GT(EOS(STATIC_357), 0, i47:0, 0) -> f357_0_main_GT(EOS(STATIC_357), 0, i47:0 - 1, 0) :|: i47:0 > 0
6.91/2.74	Filtered constant ground arguments:
6.91/2.74	   f357_0_main_GT(x1, x2, x3, x4) -> f357_0_main_GT(x2, x3, x4)
6.91/2.74	   EOS(x1) -> EOS
6.91/2.74	Filtered duplicate arguments:
6.91/2.74	   f357_0_main_GT(x1, x2, x3) -> f357_0_main_GT(x2, x3)
6.91/2.74	Finished conversion. Obtained 2 rules.P rules:
6.91/2.74	f357_0_main_GT(i47:0, i54:0) -> f357_0_main_GT(i47:0, i54:0 - 1) :|: i54:0 > 0
6.91/2.74	f357_0_main_GT(i47:0, cons_0) -> f357_0_main_GT(i47:0 - 1, 0) :|: i47:0 > 0 && cons_0 = 0
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(8)
6.91/2.74	Obligation:
6.91/2.74	Rules:
6.91/2.74	f357_0_main_GT(i47:0, i54:0) -> f357_0_main_GT(i47:0, i54:0 - 1) :|: i54:0 > 0
6.91/2.74	f357_0_main_GT(x, x1) -> f357_0_main_GT(x - 1, 0) :|: x > 0 && x1 = 0
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(9) IRSFormatTransformerProof (EQUIVALENT)
6.91/2.74	Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %).
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(10)
6.91/2.74	Obligation:
6.91/2.74	Rules:
6.91/2.74	f357_0_main_GT(i47:0, i54:0) -> f357_0_main_GT(i47:0, arith) :|: i54:0 > 0 && arith = i54:0 - 1
6.91/2.74	f357_0_main_GT(x2, x3) -> f357_0_main_GT(x4, 0) :|: x2 > 0 && x3 = 0 && x4 = x2 - 1
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(11) IRSwTTerminationDigraphProof (EQUIVALENT)
6.91/2.74	Constructed termination digraph!
6.91/2.74	Nodes:
6.91/2.74	(1) f357_0_main_GT(i47:0, i54:0) -> f357_0_main_GT(i47:0, arith) :|: i54:0 > 0 && arith = i54:0 - 1
6.91/2.74	(2) f357_0_main_GT(x2, x3) -> f357_0_main_GT(x4, 0) :|: x2 > 0 && x3 = 0 && x4 = x2 - 1
6.91/2.74	
6.91/2.74	Arcs:
6.91/2.74	(1) -> (1), (2)
6.91/2.74	(2) -> (2)
6.91/2.74	
6.91/2.74	This digraph is fully evaluated!
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(12)
6.91/2.74	Complex Obligation (AND)
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(13)
6.91/2.74	Obligation:
6.91/2.74	
6.91/2.74	Termination digraph:
6.91/2.74	Nodes:
6.91/2.74	(1) f357_0_main_GT(i47:0, i54:0) -> f357_0_main_GT(i47:0, arith) :|: i54:0 > 0 && arith = i54:0 - 1
6.91/2.74	
6.91/2.74	Arcs:
6.91/2.74	(1) -> (1)
6.91/2.74	
6.91/2.74	This digraph is fully evaluated!
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(14) IntTRSCompressionProof (EQUIVALENT)
6.91/2.74	Compressed rules.
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(15)
6.91/2.74	Obligation:
6.91/2.74	Rules:
6.91/2.74	f357_0_main_GT(i47:0:0, i54:0:0) -> f357_0_main_GT(i47:0:0, i54:0:0 - 1) :|: i54:0:0 > 0
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(16) IntTRSUnneededArgumentFilterProof (EQUIVALENT)
6.91/2.74	Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements:
6.91/2.74	
6.91/2.74	   f357_0_main_GT(x1, x2) -> f357_0_main_GT(x2)
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(17)
6.91/2.74	Obligation:
6.91/2.74	Rules:
6.91/2.74	f357_0_main_GT(i54:0:0) -> f357_0_main_GT(i54:0:0 - 1) :|: i54:0:0 > 0
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(18) TempFilterProof (SOUND)
6.91/2.74	Used the following sort dictionary for filtering: 
6.91/2.74	f357_0_main_GT(INTEGER)
6.91/2.74	Replaced non-predefined constructor symbols by 0.
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(19)
6.91/2.74	Obligation:
6.91/2.74	Rules:
6.91/2.74	f357_0_main_GT(i54:0:0) -> f357_0_main_GT(c) :|: c = i54:0:0 - 1 && i54:0:0 > 0
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(20) PolynomialOrderProcessor (EQUIVALENT)
6.91/2.74	Found the following polynomial interpretation:
6.91/2.74	[f357_0_main_GT(x)] = x
6.91/2.74	
6.91/2.74	The following rules are decreasing:
6.91/2.74	f357_0_main_GT(i54:0:0) -> f357_0_main_GT(c) :|: c = i54:0:0 - 1 && i54:0:0 > 0
6.91/2.74	The following rules are bounded:
6.91/2.74	f357_0_main_GT(i54:0:0) -> f357_0_main_GT(c) :|: c = i54:0:0 - 1 && i54:0:0 > 0
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(21)
6.91/2.74	YES
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(22)
6.91/2.74	Obligation:
6.91/2.74	
6.91/2.74	Termination digraph:
6.91/2.74	Nodes:
6.91/2.74	(1) f357_0_main_GT(x2, x3) -> f357_0_main_GT(x4, 0) :|: x2 > 0 && x3 = 0 && x4 = x2 - 1
6.91/2.74	
6.91/2.74	Arcs:
6.91/2.74	(1) -> (1)
6.91/2.74	
6.91/2.74	This digraph is fully evaluated!
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(23) IntTRSCompressionProof (EQUIVALENT)
6.91/2.74	Compressed rules.
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(24)
6.91/2.74	Obligation:
6.91/2.74	Rules:
6.91/2.74	f357_0_main_GT(x2:0, cons_0) -> f357_0_main_GT(x2:0 - 1, 0) :|: x2:0 > 0 && cons_0 = 0
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(25) TempFilterProof (SOUND)
6.91/2.74	Used the following sort dictionary for filtering: 
6.91/2.74	f357_0_main_GT(INTEGER, VARIABLE)
6.91/2.74	Replaced non-predefined constructor symbols by 0.
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(26)
6.91/2.74	Obligation:
6.91/2.74	Rules:
6.91/2.74	f357_0_main_GT(x2:0, c) -> f357_0_main_GT(c1, c2) :|: c2 = 0 && (c1 = x2:0 - 1 && c = 0) && (x2:0 > 0 && cons_0 = 0)
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(27) RankingReductionPairProof (EQUIVALENT)
6.91/2.74	Interpretation:
6.91/2.74	[ f357_0_main_GT ] = f357_0_main_GT_1
6.91/2.74	
6.91/2.74	The following rules are decreasing:
6.91/2.74	f357_0_main_GT(x2:0, c) -> f357_0_main_GT(c1, c2) :|: c2 = 0 && (c1 = x2:0 - 1 && c = 0) && (x2:0 > 0 && cons_0 = 0)
6.91/2.74	
6.91/2.74	The following rules are bounded:
6.91/2.74	f357_0_main_GT(x2:0, c) -> f357_0_main_GT(c1, c2) :|: c2 = 0 && (c1 = x2:0 - 1 && c = 0) && (x2:0 > 0 && cons_0 = 0)
6.91/2.74	
6.91/2.74	
6.91/2.74	----------------------------------------
6.91/2.74	
6.91/2.74	(28)
6.91/2.74	YES
6.91/2.78	EOF