7.47/2.86	YES
7.47/2.92	proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar
7.47/2.92	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
7.47/2.92	
7.47/2.92	
7.47/2.92	termination of the given Bare JBC problem could be proven:
7.47/2.92	
7.47/2.92	(0) Bare JBC problem
7.47/2.92	(1) BareJBCToJBCProof [EQUIVALENT, 96 ms]
7.47/2.92	(2) JBC problem
7.47/2.92	(3) JBCToGraph [EQUIVALENT, 370 ms]
7.47/2.92	(4) JBCTerminationGraph
7.47/2.92	(5) TerminationGraphToSCCProof [SOUND, 0 ms]
7.47/2.92	(6) JBCTerminationSCC
7.47/2.92	(7) SCCToIRSProof [SOUND, 75 ms]
7.47/2.92	(8) IRSwT
7.47/2.92	(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
7.47/2.92	(10) IRSwT
7.47/2.92	(11) IRSwTTerminationDigraphProof [EQUIVALENT, 35 ms]
7.47/2.92	(12) AND
7.47/2.92	    (13) IRSwT
7.47/2.92	        (14) IntTRSCompressionProof [EQUIVALENT, 0 ms]
7.47/2.92	        (15) IRSwT
7.47/2.92	        (16) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
7.47/2.92	        (17) IRSwT
7.47/2.92	        (18) TempFilterProof [SOUND, 27 ms]
7.47/2.92	        (19) IntTRS
7.47/2.92	        (20) RankingReductionPairProof [EQUIVALENT, 0 ms]
7.47/2.92	        (21) YES
7.47/2.92	    (22) IRSwT
7.47/2.92	        (23) IntTRSCompressionProof [EQUIVALENT, 0 ms]
7.47/2.92	        (24) IRSwT
7.47/2.92	        (25) TempFilterProof [SOUND, 8 ms]
7.47/2.92	        (26) IntTRS
7.47/2.92	        (27) RankingReductionPairProof [EQUIVALENT, 0 ms]
7.47/2.92	        (28) YES
7.47/2.92	
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(0)
7.47/2.92	Obligation:
7.47/2.92	need to prove termination of the following program:
7.47/2.92	/**
7.47/2.92	 * Example taken from "A Term Rewriting Approach to the Automated Termination
7.47/2.92	 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf)
7.47/2.92	 * and converted to Java.
7.47/2.92	 */
7.47/2.92	
7.47/2.92	public class PastaB16 {
7.47/2.92	    public static void main(String[] args) {
7.47/2.92	        Random.args = args;
7.47/2.92	        int x = Random.random();
7.47/2.92	        int y = Random.random();
7.47/2.92	
7.47/2.92	        while (x > 0) {
7.47/2.92	            while (y > 0) {
7.47/2.92	                y--;
7.47/2.92	            }
7.47/2.92	            x--;
7.47/2.92	        }
7.47/2.92	    }
7.47/2.92	}
7.47/2.92	
7.47/2.92	
7.47/2.92	public class Random {
7.47/2.92	  static String[] args;
7.47/2.92	  static int index = 0;
7.47/2.92	
7.47/2.92	  public static int random() {
7.47/2.92	    String string = args[index];
7.47/2.92	    index++;
7.47/2.92	    return string.length();
7.47/2.92	  }
7.47/2.92	}
7.47/2.92	
7.47/2.92	
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(1) BareJBCToJBCProof (EQUIVALENT)
7.47/2.92	initialized classpath
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(2)
7.47/2.92	Obligation:
7.47/2.92	need to prove termination of the following program:
7.47/2.92	/**
7.47/2.92	 * Example taken from "A Term Rewriting Approach to the Automated Termination
7.47/2.92	 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf)
7.47/2.92	 * and converted to Java.
7.47/2.92	 */
7.47/2.92	
7.47/2.92	public class PastaB16 {
7.47/2.92	    public static void main(String[] args) {
7.47/2.92	        Random.args = args;
7.47/2.92	        int x = Random.random();
7.47/2.92	        int y = Random.random();
7.47/2.92	
7.47/2.92	        while (x > 0) {
7.47/2.92	            while (y > 0) {
7.47/2.92	                y--;
7.47/2.92	            }
7.47/2.92	            x--;
7.47/2.92	        }
7.47/2.92	    }
7.47/2.92	}
7.47/2.92	
7.47/2.92	
7.47/2.92	public class Random {
7.47/2.92	  static String[] args;
7.47/2.92	  static int index = 0;
7.47/2.92	
7.47/2.92	  public static int random() {
7.47/2.92	    String string = args[index];
7.47/2.92	    index++;
7.47/2.92	    return string.length();
7.47/2.92	  }
7.47/2.92	}
7.47/2.92	
7.47/2.92	
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(3) JBCToGraph (EQUIVALENT)
7.47/2.92	Constructed TerminationGraph.
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(4)
7.47/2.92	Obligation:
7.47/2.92	Termination Graph based on JBC Program:
7.47/2.92	PastaB16.main([Ljava/lang/String;)V: Graph of 180 nodes with 1 SCC.
7.47/2.92	
7.47/2.92	
7.47/2.92	
7.47/2.92	
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(5) TerminationGraphToSCCProof (SOUND)
7.47/2.92	Splitted TerminationGraph to 1 SCCs.
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(6)
7.47/2.92	Obligation:
7.47/2.92	SCC of termination graph based on JBC Program.
7.47/2.92	SCC contains nodes from the following methods: PastaB16.main([Ljava/lang/String;)V
7.47/2.92	SCC calls the following helper methods: 
7.47/2.92	Performed SCC analyses:
7.47/2.92	*Used field analysis yielded the following read fields:
7.47/2.92	
7.47/2.92	*Marker field analysis yielded the following relations that could be markers:
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(7) SCCToIRSProof (SOUND)
7.47/2.92	Transformed FIGraph SCCs to intTRSs. Log: 
7.47/2.92	Generated rules. Obtained 14 IRulesP rules:
7.47/2.92	f313_0_main_LE(EOS(STATIC_313), i50, i45, i50) -> f326_0_main_LE(EOS(STATIC_326), i50, i45, i50) :|: TRUE
7.47/2.92	f326_0_main_LE(EOS(STATIC_326), i50, i45, i50) -> f340_0_main_Load(EOS(STATIC_340), i50, i45) :|: i50 > 0
7.47/2.92	f340_0_main_Load(EOS(STATIC_340), i50, i45) -> f355_0_main_LE(EOS(STATIC_355), i50, i45, i45) :|: TRUE
7.47/2.92	f355_0_main_LE(EOS(STATIC_355), i50, matching1, matching2) -> f370_0_main_LE(EOS(STATIC_370), i50, 0, 0) :|: TRUE && matching1 = 0 && matching2 = 0
7.47/2.92	f355_0_main_LE(EOS(STATIC_355), i50, i59, i59) -> f371_0_main_LE(EOS(STATIC_371), i50, i59, i59) :|: TRUE
7.47/2.92	f370_0_main_LE(EOS(STATIC_370), i50, matching1, matching2) -> f382_0_main_Inc(EOS(STATIC_382), i50, 0) :|: 0 <= 0 && matching1 = 0 && matching2 = 0
7.47/2.92	f382_0_main_Inc(EOS(STATIC_382), i50, matching1) -> f395_0_main_JMP(EOS(STATIC_395), i50 + -1, 0) :|: TRUE && matching1 = 0
7.47/2.92	f395_0_main_JMP(EOS(STATIC_395), i64, matching1) -> f1028_0_main_Load(EOS(STATIC_1028), i64, 0) :|: TRUE && matching1 = 0
7.47/2.92	f1028_0_main_Load(EOS(STATIC_1028), i64, matching1) -> f303_0_main_Load(EOS(STATIC_303), i64, 0) :|: TRUE && matching1 = 0
7.47/2.92	f303_0_main_Load(EOS(STATIC_303), i19, i45) -> f313_0_main_LE(EOS(STATIC_313), i19, i45, i19) :|: TRUE
7.47/2.92	f371_0_main_LE(EOS(STATIC_371), i50, i59, i59) -> f383_0_main_Inc(EOS(STATIC_383), i50, i59) :|: i59 > 0
7.47/2.92	f383_0_main_Inc(EOS(STATIC_383), i50, i59) -> f398_0_main_JMP(EOS(STATIC_398), i50, i59 + -1) :|: TRUE
7.47/2.92	f398_0_main_JMP(EOS(STATIC_398), i50, i65) -> f1035_0_main_Load(EOS(STATIC_1035), i50, i65) :|: TRUE
7.47/2.92	f1035_0_main_Load(EOS(STATIC_1035), i50, i65) -> f340_0_main_Load(EOS(STATIC_340), i50, i65) :|: TRUE
7.47/2.92	Combined rules. Obtained 2 IRulesP rules:
7.47/2.92	f355_0_main_LE(EOS(STATIC_355), i50:0, i59:0, i59:0) -> f355_0_main_LE(EOS(STATIC_355), i50:0, i59:0 - 1, i59:0 - 1) :|: i59:0 > 0
7.47/2.92	f355_0_main_LE(EOS(STATIC_355), i50:0, 0, 0) -> f355_0_main_LE(EOS(STATIC_355), i50:0 - 1, 0, 0) :|: i50:0 > 1
7.47/2.92	Filtered constant ground arguments:
7.47/2.92	   f355_0_main_LE(x1, x2, x3, x4) -> f355_0_main_LE(x2, x3, x4)
7.47/2.92	   EOS(x1) -> EOS
7.47/2.92	Filtered duplicate arguments:
7.47/2.92	   f355_0_main_LE(x1, x2, x3) -> f355_0_main_LE(x1, x3)
7.47/2.92	Finished conversion. Obtained 2 rules.P rules:
7.47/2.92	f355_0_main_LE(i50:0, i59:0) -> f355_0_main_LE(i50:0, i59:0 - 1) :|: i59:0 > 0
7.47/2.92	f355_0_main_LE(i50:0, cons_0) -> f355_0_main_LE(i50:0 - 1, 0) :|: i50:0 > 1 && cons_0 = 0
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(8)
7.47/2.92	Obligation:
7.47/2.92	Rules:
7.47/2.92	f355_0_main_LE(i50:0, i59:0) -> f355_0_main_LE(i50:0, i59:0 - 1) :|: i59:0 > 0
7.47/2.92	f355_0_main_LE(x, x1) -> f355_0_main_LE(x - 1, 0) :|: x > 1 && x1 = 0
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(9) IRSFormatTransformerProof (EQUIVALENT)
7.47/2.92	Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %).
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(10)
7.47/2.92	Obligation:
7.47/2.92	Rules:
7.47/2.92	f355_0_main_LE(i50:0, i59:0) -> f355_0_main_LE(i50:0, arith) :|: i59:0 > 0 && arith = i59:0 - 1
7.47/2.92	f355_0_main_LE(x2, x3) -> f355_0_main_LE(x4, 0) :|: x2 > 1 && x3 = 0 && x4 = x2 - 1
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(11) IRSwTTerminationDigraphProof (EQUIVALENT)
7.47/2.92	Constructed termination digraph!
7.47/2.92	Nodes:
7.47/2.92	(1) f355_0_main_LE(i50:0, i59:0) -> f355_0_main_LE(i50:0, arith) :|: i59:0 > 0 && arith = i59:0 - 1
7.47/2.92	(2) f355_0_main_LE(x2, x3) -> f355_0_main_LE(x4, 0) :|: x2 > 1 && x3 = 0 && x4 = x2 - 1
7.47/2.92	
7.47/2.92	Arcs:
7.47/2.92	(1) -> (1), (2)
7.47/2.92	(2) -> (2)
7.47/2.92	
7.47/2.92	This digraph is fully evaluated!
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(12)
7.47/2.92	Complex Obligation (AND)
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(13)
7.47/2.92	Obligation:
7.47/2.92	
7.47/2.92	Termination digraph:
7.47/2.92	Nodes:
7.47/2.92	(1) f355_0_main_LE(i50:0, i59:0) -> f355_0_main_LE(i50:0, arith) :|: i59:0 > 0 && arith = i59:0 - 1
7.47/2.92	
7.47/2.92	Arcs:
7.47/2.92	(1) -> (1)
7.47/2.92	
7.47/2.92	This digraph is fully evaluated!
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(14) IntTRSCompressionProof (EQUIVALENT)
7.47/2.92	Compressed rules.
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(15)
7.47/2.92	Obligation:
7.47/2.92	Rules:
7.47/2.92	f355_0_main_LE(i50:0:0, i59:0:0) -> f355_0_main_LE(i50:0:0, i59:0:0 - 1) :|: i59:0:0 > 0
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(16) IntTRSUnneededArgumentFilterProof (EQUIVALENT)
7.47/2.92	Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements:
7.47/2.92	
7.47/2.92	   f355_0_main_LE(x1, x2) -> f355_0_main_LE(x2)
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(17)
7.47/2.92	Obligation:
7.47/2.92	Rules:
7.47/2.92	f355_0_main_LE(i59:0:0) -> f355_0_main_LE(i59:0:0 - 1) :|: i59:0:0 > 0
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(18) TempFilterProof (SOUND)
7.47/2.92	Used the following sort dictionary for filtering: 
7.47/2.92	f355_0_main_LE(INTEGER)
7.47/2.92	Replaced non-predefined constructor symbols by 0.
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(19)
7.47/2.92	Obligation:
7.47/2.92	Rules:
7.47/2.92	f355_0_main_LE(i59:0:0) -> f355_0_main_LE(c) :|: c = i59:0:0 - 1 && i59:0:0 > 0
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(20) RankingReductionPairProof (EQUIVALENT)
7.47/2.92	Interpretation:
7.47/2.92	[ f355_0_main_LE ] = f355_0_main_LE_1
7.47/2.92	
7.47/2.92	The following rules are decreasing:
7.47/2.92	f355_0_main_LE(i59:0:0) -> f355_0_main_LE(c) :|: c = i59:0:0 - 1 && i59:0:0 > 0
7.47/2.92	
7.47/2.92	The following rules are bounded:
7.47/2.92	f355_0_main_LE(i59:0:0) -> f355_0_main_LE(c) :|: c = i59:0:0 - 1 && i59:0:0 > 0
7.47/2.92	
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(21)
7.47/2.92	YES
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(22)
7.47/2.92	Obligation:
7.47/2.92	
7.47/2.92	Termination digraph:
7.47/2.92	Nodes:
7.47/2.92	(1) f355_0_main_LE(x2, x3) -> f355_0_main_LE(x4, 0) :|: x2 > 1 && x3 = 0 && x4 = x2 - 1
7.47/2.92	
7.47/2.92	Arcs:
7.47/2.92	(1) -> (1)
7.47/2.92	
7.47/2.92	This digraph is fully evaluated!
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(23) IntTRSCompressionProof (EQUIVALENT)
7.47/2.92	Compressed rules.
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(24)
7.47/2.92	Obligation:
7.47/2.92	Rules:
7.47/2.92	f355_0_main_LE(x2:0, cons_0) -> f355_0_main_LE(x2:0 - 1, 0) :|: x2:0 > 1 && cons_0 = 0
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(25) TempFilterProof (SOUND)
7.47/2.92	Used the following sort dictionary for filtering: 
7.47/2.92	f355_0_main_LE(INTEGER, VARIABLE)
7.47/2.92	Replaced non-predefined constructor symbols by 0.
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(26)
7.47/2.92	Obligation:
7.47/2.92	Rules:
7.47/2.92	f355_0_main_LE(x2:0, c) -> f355_0_main_LE(c1, c2) :|: c2 = 0 && (c1 = x2:0 - 1 && c = 0) && (x2:0 > 1 && cons_0 = 0)
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(27) RankingReductionPairProof (EQUIVALENT)
7.47/2.92	Interpretation:
7.47/2.92	[ f355_0_main_LE ] = f355_0_main_LE_1
7.47/2.92	
7.47/2.92	The following rules are decreasing:
7.47/2.92	f355_0_main_LE(x2:0, c) -> f355_0_main_LE(c1, c2) :|: c2 = 0 && (c1 = x2:0 - 1 && c = 0) && (x2:0 > 1 && cons_0 = 0)
7.47/2.92	
7.47/2.92	The following rules are bounded:
7.47/2.92	f355_0_main_LE(x2:0, c) -> f355_0_main_LE(c1, c2) :|: c2 = 0 && (c1 = x2:0 - 1 && c = 0) && (x2:0 > 1 && cons_0 = 0)
7.47/2.92	
7.47/2.92	
7.47/2.92	----------------------------------------
7.47/2.92	
7.47/2.92	(28)
7.47/2.92	YES
7.82/3.01	EOF