5.65/2.38	YES
5.96/2.40	proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar
5.96/2.40	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.96/2.40	
5.96/2.40	
5.96/2.40	termination of the given Bare JBC problem could be proven:
5.96/2.40	
5.96/2.40	(0) Bare JBC problem
5.96/2.40	(1) BareJBCToJBCProof [EQUIVALENT, 96 ms]
5.96/2.40	(2) JBC problem
5.96/2.40	(3) JBCToGraph [EQUIVALENT, 172 ms]
5.96/2.40	(4) JBCTerminationGraph
5.96/2.40	(5) TerminationGraphToSCCProof [SOUND, 0 ms]
5.96/2.40	(6) JBCTerminationSCC
5.96/2.40	(7) SCCToIRSProof [SOUND, 37 ms]
5.96/2.40	(8) IRSwT
5.96/2.40	(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
5.96/2.40	(10) IRSwT
5.96/2.40	(11) IRSwTTerminationDigraphProof [EQUIVALENT, 60 ms]
5.96/2.40	(12) IRSwT
5.96/2.40	(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
5.96/2.40	(14) IRSwT
5.96/2.40	(15) TempFilterProof [SOUND, 30 ms]
5.96/2.40	(16) IntTRS
5.96/2.40	(17) RankingReductionPairProof [EQUIVALENT, 0 ms]
5.96/2.40	(18) YES
5.96/2.40	
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(0)
5.96/2.40	Obligation:
5.96/2.40	need to prove termination of the following program:
5.96/2.40	public class GCD5 {
5.96/2.40	  public static int gcd(int a, int b) {
5.96/2.40	    int tmp;
5.96/2.40	    while(b > 0 && a > 0) {
5.96/2.40	      tmp = b;
5.96/2.40	      b = a % b;
5.96/2.40	      a = tmp;
5.96/2.40	    }
5.96/2.40	    return a;
5.96/2.40	  }
5.96/2.40	
5.96/2.40	  public static void main(String[] args) {
5.96/2.40	    Random.args = args;
5.96/2.40	    int x = Random.random();
5.96/2.40	    int y = Random.random();
5.96/2.40	    gcd(x, y);
5.96/2.40	  }
5.96/2.40	}
5.96/2.40	
5.96/2.40	
5.96/2.40	public class Random {
5.96/2.40	  static String[] args;
5.96/2.40	  static int index = 0;
5.96/2.40	
5.96/2.40	  public static int random() {
5.96/2.40	    String string = args[index];
5.96/2.40	    index++;
5.96/2.40	    return string.length();
5.96/2.40	  }
5.96/2.40	}
5.96/2.40	
5.96/2.40	
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(1) BareJBCToJBCProof (EQUIVALENT)
5.96/2.40	initialized classpath
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(2)
5.96/2.40	Obligation:
5.96/2.40	need to prove termination of the following program:
5.96/2.40	public class GCD5 {
5.96/2.40	  public static int gcd(int a, int b) {
5.96/2.40	    int tmp;
5.96/2.40	    while(b > 0 && a > 0) {
5.96/2.40	      tmp = b;
5.96/2.40	      b = a % b;
5.96/2.40	      a = tmp;
5.96/2.40	    }
5.96/2.40	    return a;
5.96/2.40	  }
5.96/2.40	
5.96/2.40	  public static void main(String[] args) {
5.96/2.40	    Random.args = args;
5.96/2.40	    int x = Random.random();
5.96/2.40	    int y = Random.random();
5.96/2.40	    gcd(x, y);
5.96/2.40	  }
5.96/2.40	}
5.96/2.40	
5.96/2.40	
5.96/2.40	public class Random {
5.96/2.40	  static String[] args;
5.96/2.40	  static int index = 0;
5.96/2.40	
5.96/2.40	  public static int random() {
5.96/2.40	    String string = args[index];
5.96/2.40	    index++;
5.96/2.40	    return string.length();
5.96/2.40	  }
5.96/2.40	}
5.96/2.40	
5.96/2.40	
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(3) JBCToGraph (EQUIVALENT)
5.96/2.40	Constructed TerminationGraph.
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(4)
5.96/2.40	Obligation:
5.96/2.40	Termination Graph based on JBC Program:
5.96/2.40	GCD5.main([Ljava/lang/String;)V: Graph of 194 nodes with 1 SCC.
5.96/2.40	
5.96/2.40	
5.96/2.40	
5.96/2.40	
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(5) TerminationGraphToSCCProof (SOUND)
5.96/2.40	Splitted TerminationGraph to 1 SCCs.
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(6)
5.96/2.40	Obligation:
5.96/2.40	SCC of termination graph based on JBC Program.
5.96/2.40	SCC contains nodes from the following methods: GCD5.main([Ljava/lang/String;)V
5.96/2.40	SCC calls the following helper methods: 
5.96/2.40	Performed SCC analyses:
5.96/2.40	*Used field analysis yielded the following read fields:
5.96/2.40	
5.96/2.40	*Marker field analysis yielded the following relations that could be markers:
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(7) SCCToIRSProof (SOUND)
5.96/2.40	Transformed FIGraph SCCs to intTRSs. Log: 
5.96/2.40	Generated rules. Obtained 16 IRulesP rules:
5.96/2.40	f389_0_gcd_LE(EOS(STATIC_389), i19, i52, i52) -> f403_0_gcd_LE(EOS(STATIC_403), i19, i52, i52) :|: TRUE
5.96/2.40	f403_0_gcd_LE(EOS(STATIC_403), i19, i52, i52) -> f418_0_gcd_Load(EOS(STATIC_418), i19, i52) :|: i52 > 0
5.96/2.40	f418_0_gcd_Load(EOS(STATIC_418), i19, i52) -> f437_0_gcd_LE(EOS(STATIC_437), i19, i52, i19) :|: TRUE
5.96/2.40	f437_0_gcd_LE(EOS(STATIC_437), i57, i52, i57) -> f454_0_gcd_LE(EOS(STATIC_454), i57, i52, i57) :|: TRUE
5.96/2.40	f454_0_gcd_LE(EOS(STATIC_454), i57, i52, i57) -> f470_0_gcd_Load(EOS(STATIC_470), i57, i52) :|: i57 > 0
5.96/2.40	f470_0_gcd_Load(EOS(STATIC_470), i57, i52) -> f486_0_gcd_Store(EOS(STATIC_486), i57, i52, i52) :|: TRUE
5.96/2.40	f486_0_gcd_Store(EOS(STATIC_486), i57, i52, i52) -> f499_0_gcd_Load(EOS(STATIC_499), i57, i52, i52) :|: TRUE
5.96/2.40	f499_0_gcd_Load(EOS(STATIC_499), i57, i52, i52) -> f525_0_gcd_Load(EOS(STATIC_525), i52, i52, i57) :|: TRUE
5.96/2.40	f525_0_gcd_Load(EOS(STATIC_525), i52, i52, i57) -> f531_0_gcd_IntArithmetic(EOS(STATIC_531), i52, i57, i52) :|: TRUE
5.96/2.40	f531_0_gcd_IntArithmetic(EOS(STATIC_531), i52, i57, i52) -> f536_0_gcd_Store(EOS(STATIC_536), i52, i57 % i52) :|: TRUE
5.96/2.40	f536_0_gcd_Store(EOS(STATIC_536), i52, i64) -> f541_0_gcd_Load(EOS(STATIC_541), i64, i52) :|: TRUE
5.96/2.40	f541_0_gcd_Load(EOS(STATIC_541), i64, i52) -> f546_0_gcd_Store(EOS(STATIC_546), i64, i52) :|: TRUE
5.96/2.40	f546_0_gcd_Store(EOS(STATIC_546), i64, i52) -> f548_0_gcd_JMP(EOS(STATIC_548), i52, i64) :|: TRUE
5.96/2.40	f548_0_gcd_JMP(EOS(STATIC_548), i52, i64) -> f610_0_gcd_Load(EOS(STATIC_610), i52, i64) :|: TRUE
5.96/2.40	f610_0_gcd_Load(EOS(STATIC_610), i52, i64) -> f365_0_gcd_Load(EOS(STATIC_365), i52, i64) :|: TRUE
5.96/2.40	f365_0_gcd_Load(EOS(STATIC_365), i19, i44) -> f389_0_gcd_LE(EOS(STATIC_389), i19, i44, i44) :|: TRUE
5.96/2.40	Combined rules. Obtained 2 IRulesP rules:
5.96/2.40	f389_0_gcd_LE(EOS(STATIC_389), i19:0, i52:0, i52:0) -> f389_0_gcd_LE'(EOS(STATIC_389), i19:0, i52:0, i52:0) :|: i19:0 > 0 && i52:0 > 0
5.96/2.40	f389_0_gcd_LE'(EOS(STATIC_389), i19:0, i52:0, i52:0) -> f389_0_gcd_LE(EOS(STATIC_389), i52:0, i19:0 - i52:0 * div, i19:0 - i52:0 * div1) :|: i52:0 > 0 && i19:0 > 0 && i19:0 - i52:0 * div + i52:0 > 0 && i52:0 > i19:0 - i52:0 * div && i52:0 > i19:0 - i52:0 * div1 && i19:0 - i52:0 * div1 + i52:0 > 0
5.96/2.40	Filtered constant ground arguments:
5.96/2.40	   f389_0_gcd_LE(x1, x2, x3, x4) -> f389_0_gcd_LE(x2, x3, x4)
5.96/2.40	   f389_0_gcd_LE'(x1, x2, x3, x4) -> f389_0_gcd_LE'(x2, x3, x4)
5.96/2.40	   EOS(x1) -> EOS
5.96/2.40	Filtered duplicate arguments:
5.96/2.40	   f389_0_gcd_LE'(x1, x2, x3) -> f389_0_gcd_LE'(x1, x3)
5.96/2.40	Finished conversion. Obtained 2 rules.P rules:
5.96/2.40	f389_0_gcd_LE(i19:0, i52:0, i52:0) -> f389_0_gcd_LE'(i19:0, i52:0) :|: i19:0 > 0 && i52:0 > 0
5.96/2.40	f389_0_gcd_LE'(i19:0, i52:0) -> f389_0_gcd_LE(i52:0, i19:0 - i52:0 * div, i19:0 - i52:0 * div1) :|: i19:0 > 0 && i52:0 > 0 && i19:0 - i52:0 * div + i52:0 > 0 && i52:0 > i19:0 - i52:0 * div && i19:0 - i52:0 * div1 + i52:0 > 0 && i52:0 > i19:0 - i52:0 * div1
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(8)
5.96/2.40	Obligation:
5.96/2.40	Rules:
5.96/2.40	f389_0_gcd_LE(i19:0, i52:0, i52:0) -> f389_0_gcd_LE'(i19:0, i52:0) :|: i19:0 > 0 && i52:0 > 0
5.96/2.40	f389_0_gcd_LE'(x, x1) -> f389_0_gcd_LE(x1, x - x1 * x2, x - x1 * x3) :|: x > 0 && x1 > 0 && x - x1 * x2 + x1 > 0 && x1 > x - x1 * x2 && x - x1 * x3 + x1 > 0 && x1 > x - x1 * x3
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(9) IRSFormatTransformerProof (EQUIVALENT)
5.96/2.40	Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %).
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(10)
5.96/2.40	Obligation:
5.96/2.40	Rules:
5.96/2.40	f389_0_gcd_LE(i19:0, i52:0, i52:0) -> f389_0_gcd_LE'(i19:0, i52:0) :|: i19:0 > 0 && i52:0 > 0
5.96/2.40	f389_0_gcd_LE'(x, x1) -> f389_0_gcd_LE(x1, arith, arith1) :|: x > 0 && x1 > 0 && x - x1 * x2 + x1 > 0 && x1 > x - x1 * x2 && x - x1 * x3 + x1 > 0 && x1 > x - x1 * x3 && arith = x - x1 * x2 && arith1 = x - x1 * x3
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(11) IRSwTTerminationDigraphProof (EQUIVALENT)
5.96/2.40	Constructed termination digraph!
5.96/2.40	Nodes:
5.96/2.40	(1) f389_0_gcd_LE(i19:0, i52:0, i52:0) -> f389_0_gcd_LE'(i19:0, i52:0) :|: i19:0 > 0 && i52:0 > 0
5.96/2.40	(2) f389_0_gcd_LE'(x, x1) -> f389_0_gcd_LE(x1, arith, arith1) :|: x > 0 && x1 > 0 && x - x1 * x2 + x1 > 0 && x1 > x - x1 * x2 && x - x1 * x3 + x1 > 0 && x1 > x - x1 * x3 && arith = x - x1 * x2 && arith1 = x - x1 * x3
5.96/2.40	
5.96/2.40	Arcs:
5.96/2.40	(1) -> (2)
5.96/2.40	(2) -> (1)
5.96/2.40	
5.96/2.40	This digraph is fully evaluated!
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(12)
5.96/2.40	Obligation:
5.96/2.40	
5.96/2.40	Termination digraph:
5.96/2.40	Nodes:
5.96/2.40	(1) f389_0_gcd_LE(i19:0, i52:0, i52:0) -> f389_0_gcd_LE'(i19:0, i52:0) :|: i19:0 > 0 && i52:0 > 0
5.96/2.40	(2) f389_0_gcd_LE'(x, x1) -> f389_0_gcd_LE(x1, arith, arith1) :|: x > 0 && x1 > 0 && x - x1 * x2 + x1 > 0 && x1 > x - x1 * x2 && x - x1 * x3 + x1 > 0 && x1 > x - x1 * x3 && arith = x - x1 * x2 && arith1 = x - x1 * x3
5.96/2.40	
5.96/2.40	Arcs:
5.96/2.40	(1) -> (2)
5.96/2.40	(2) -> (1)
5.96/2.40	
5.96/2.40	This digraph is fully evaluated!
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(13) IntTRSCompressionProof (EQUIVALENT)
5.96/2.40	Compressed rules.
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(14)
5.96/2.40	Obligation:
5.96/2.40	Rules:
5.96/2.40	f389_0_gcd_LE(i19:0:0, i52:0:0, i52:0:0) -> f389_0_gcd_LE(i52:0:0, i19:0:0 - i52:0:0 * x2:0, i19:0:0 - i52:0:0 * x3:0) :|: i52:0:0 > i19:0:0 - i52:0:0 * x3:0 && i19:0:0 - i52:0:0 * x3:0 + i52:0:0 > 0 && i52:0:0 > i19:0:0 - i52:0:0 * x2:0 && i19:0:0 - i52:0:0 * x2:0 + i52:0:0 > 0 && i52:0:0 > 0 && i19:0:0 > 0
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(15) TempFilterProof (SOUND)
5.96/2.40	Used the following sort dictionary for filtering: 
5.96/2.40	f389_0_gcd_LE(INTEGER, INTEGER, INTEGER)
5.96/2.40	Replaced non-predefined constructor symbols by 0.
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(16)
5.96/2.40	Obligation:
5.96/2.40	Rules:
5.96/2.40	f389_0_gcd_LE(i19:0:0, i52:0:0, i52:0:0) -> f389_0_gcd_LE(i52:0:0, c, c1) :|: c1 = i19:0:0 - i52:0:0 * x3:0 && c = i19:0:0 - i52:0:0 * x2:0 && (i52:0:0 > i19:0:0 - i52:0:0 * x3:0 && i19:0:0 - i52:0:0 * x3:0 + i52:0:0 > 0 && i52:0:0 > i19:0:0 - i52:0:0 * x2:0 && i19:0:0 - i52:0:0 * x2:0 + i52:0:0 > 0 && i52:0:0 > 0 && i19:0:0 > 0)
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(17) RankingReductionPairProof (EQUIVALENT)
5.96/2.40	Interpretation:
5.96/2.40	[ f389_0_gcd_LE ] = f389_0_gcd_LE_3
5.96/2.40	
5.96/2.40	The following rules are decreasing:
5.96/2.40	f389_0_gcd_LE(i19:0:0, i52:0:0, i52:0:0) -> f389_0_gcd_LE(i52:0:0, c, c1) :|: c1 = i19:0:0 - i52:0:0 * x3:0 && c = i19:0:0 - i52:0:0 * x2:0 && (i52:0:0 > i19:0:0 - i52:0:0 * x3:0 && i19:0:0 - i52:0:0 * x3:0 + i52:0:0 > 0 && i52:0:0 > i19:0:0 - i52:0:0 * x2:0 && i19:0:0 - i52:0:0 * x2:0 + i52:0:0 > 0 && i52:0:0 > 0 && i19:0:0 > 0)
5.96/2.40	
5.96/2.40	The following rules are bounded:
5.96/2.40	f389_0_gcd_LE(i19:0:0, i52:0:0, i52:0:0) -> f389_0_gcd_LE(i52:0:0, c, c1) :|: c1 = i19:0:0 - i52:0:0 * x3:0 && c = i19:0:0 - i52:0:0 * x2:0 && (i52:0:0 > i19:0:0 - i52:0:0 * x3:0 && i19:0:0 - i52:0:0 * x3:0 + i52:0:0 > 0 && i52:0:0 > i19:0:0 - i52:0:0 * x2:0 && i19:0:0 - i52:0:0 * x2:0 + i52:0:0 > 0 && i52:0:0 > 0 && i19:0:0 > 0)
5.96/2.40	
5.96/2.40	
5.96/2.40	----------------------------------------
5.96/2.40	
5.96/2.40	(18)
5.96/2.40	YES
6.04/2.44	EOF