6.91/2.70	YES
7.15/2.80	proof of /export/starexec/sandbox/benchmark/theBenchmark.jar
7.15/2.80	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
7.15/2.80	
7.15/2.80	
7.15/2.80	termination of the given Bare JBC problem could be proven:
7.15/2.80	
7.15/2.80	(0) Bare JBC problem
7.15/2.80	(1) BareJBCToJBCProof [EQUIVALENT, 96 ms]
7.15/2.80	(2) JBC problem
7.15/2.80	(3) JBCToGraph [EQUIVALENT, 352 ms]
7.15/2.80	(4) JBCTerminationGraph
7.15/2.80	(5) TerminationGraphToSCCProof [SOUND, 0 ms]
7.15/2.80	(6) JBCTerminationSCC
7.15/2.80	(7) SCCToIRSProof [SOUND, 144 ms]
7.15/2.80	(8) IRSwT
7.15/2.80	(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
7.15/2.80	(10) IRSwT
7.15/2.80	(11) IRSwTTerminationDigraphProof [EQUIVALENT, 23 ms]
7.15/2.80	(12) IRSwT
7.15/2.80	(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
7.15/2.80	(14) IRSwT
7.15/2.80	(15) TempFilterProof [SOUND, 59 ms]
7.15/2.80	(16) IntTRS
7.15/2.80	(17) PolynomialOrderProcessor [EQUIVALENT, 6 ms]
7.15/2.80	(18) IntTRS
7.15/2.80	(19) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
7.15/2.80	(20) YES
7.15/2.80	
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(0)
7.15/2.80	Obligation:
7.15/2.80	need to prove termination of the following program:
7.15/2.80	public class GCD3 {
7.15/2.80	  public static int mod(int a, int b) {
7.15/2.80	    if(b == 0) {
7.15/2.80	      return b;
7.15/2.80	    }
7.15/2.80	    if(b < 0) {
7.15/2.80	      a = -a;
7.15/2.80	    }
7.15/2.80	    if(a > 0) {
7.15/2.80	      while(a>=b) {
7.15/2.80	        a -= b;
7.15/2.80	      }
7.15/2.80	      return a;
7.15/2.80	    } else {
7.15/2.80	      while(a < 0) {
7.15/2.80	        a -= b;
7.15/2.80	      }
7.15/2.80	      return a;
7.15/2.80	    }
7.15/2.80	  }
7.15/2.80	
7.15/2.80	  public static int gcd(int a, int b) {
7.15/2.80	    int tmp;
7.15/2.80	    while(b > 0 && a > 0) {
7.15/2.80	      tmp = b;
7.15/2.80	      b = mod(a, b);
7.15/2.80	      a = tmp;
7.15/2.80	    }
7.15/2.80	    return a;
7.15/2.80	  }
7.15/2.80	
7.15/2.80	  public static void main(String[] args) {
7.15/2.80	    Random.args = args;
7.15/2.80	    int x = Random.random();
7.15/2.80	    int y = Random.random();
7.15/2.80	    gcd(x, y);
7.15/2.80	  }
7.15/2.80	}
7.15/2.80	
7.15/2.80	
7.15/2.80	public class Random {
7.15/2.80	  static String[] args;
7.15/2.80	  static int index = 0;
7.15/2.80	
7.15/2.80	  public static int random() {
7.15/2.80	    String string = args[index];
7.15/2.80	    index++;
7.15/2.80	    return string.length();
7.15/2.80	  }
7.15/2.80	}
7.15/2.80	
7.15/2.80	
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(1) BareJBCToJBCProof (EQUIVALENT)
7.15/2.80	initialized classpath
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(2)
7.15/2.80	Obligation:
7.15/2.80	need to prove termination of the following program:
7.15/2.80	public class GCD3 {
7.15/2.80	  public static int mod(int a, int b) {
7.15/2.80	    if(b == 0) {
7.15/2.80	      return b;
7.15/2.80	    }
7.15/2.80	    if(b < 0) {
7.15/2.80	      a = -a;
7.15/2.80	    }
7.15/2.80	    if(a > 0) {
7.15/2.80	      while(a>=b) {
7.15/2.80	        a -= b;
7.15/2.80	      }
7.15/2.80	      return a;
7.15/2.80	    } else {
7.15/2.80	      while(a < 0) {
7.15/2.80	        a -= b;
7.15/2.80	      }
7.15/2.80	      return a;
7.15/2.80	    }
7.15/2.80	  }
7.15/2.80	
7.15/2.80	  public static int gcd(int a, int b) {
7.15/2.80	    int tmp;
7.15/2.80	    while(b > 0 && a > 0) {
7.15/2.80	      tmp = b;
7.15/2.80	      b = mod(a, b);
7.15/2.80	      a = tmp;
7.15/2.80	    }
7.15/2.80	    return a;
7.15/2.80	  }
7.15/2.80	
7.15/2.80	  public static void main(String[] args) {
7.15/2.80	    Random.args = args;
7.15/2.80	    int x = Random.random();
7.15/2.80	    int y = Random.random();
7.15/2.80	    gcd(x, y);
7.15/2.80	  }
7.15/2.80	}
7.15/2.80	
7.15/2.80	
7.15/2.80	public class Random {
7.15/2.80	  static String[] args;
7.15/2.80	  static int index = 0;
7.15/2.80	
7.15/2.80	  public static int random() {
7.15/2.80	    String string = args[index];
7.15/2.80	    index++;
7.15/2.80	    return string.length();
7.15/2.80	  }
7.15/2.80	}
7.15/2.80	
7.15/2.80	
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(3) JBCToGraph (EQUIVALENT)
7.15/2.80	Constructed TerminationGraph.
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(4)
7.15/2.80	Obligation:
7.15/2.80	Termination Graph based on JBC Program:
7.15/2.80	GCD3.main([Ljava/lang/String;)V: Graph of 214 nodes with 1 SCC.
7.15/2.80	
7.15/2.80	
7.15/2.80	
7.15/2.80	
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(5) TerminationGraphToSCCProof (SOUND)
7.15/2.80	Splitted TerminationGraph to 1 SCCs.
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(6)
7.15/2.80	Obligation:
7.15/2.80	SCC of termination graph based on JBC Program.
7.15/2.80	SCC contains nodes from the following methods: GCD3.main([Ljava/lang/String;)V
7.15/2.80	SCC calls the following helper methods: 
7.15/2.80	Performed SCC analyses:
7.15/2.80	*Used field analysis yielded the following read fields:
7.15/2.80	
7.15/2.80	*Marker field analysis yielded the following relations that could be markers:
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(7) SCCToIRSProof (SOUND)
7.15/2.80	Transformed FIGraph SCCs to intTRSs. Log: 
7.15/2.80	Generated rules. Obtained 37 IRulesP rules:
7.15/2.80	f326_0_gcd_LE(EOS(STATIC_326), i19, i46, i46) -> f341_0_gcd_LE(EOS(STATIC_341), i19, i46, i46) :|: TRUE
7.15/2.80	f341_0_gcd_LE(EOS(STATIC_341), i19, i46, i46) -> f353_0_gcd_Load(EOS(STATIC_353), i19, i46) :|: i46 > 0
7.15/2.80	f353_0_gcd_Load(EOS(STATIC_353), i19, i46) -> f360_0_gcd_LE(EOS(STATIC_360), i19, i46, i19) :|: TRUE
7.15/2.80	f360_0_gcd_LE(EOS(STATIC_360), i47, i46, i47) -> f365_0_gcd_LE(EOS(STATIC_365), i47, i46, i47) :|: TRUE
7.15/2.80	f365_0_gcd_LE(EOS(STATIC_365), i47, i46, i47) -> f370_0_gcd_Load(EOS(STATIC_370), i47, i46) :|: i47 > 0
7.15/2.80	f370_0_gcd_Load(EOS(STATIC_370), i47, i46) -> f375_0_gcd_Store(EOS(STATIC_375), i47, i46, i46) :|: TRUE
7.15/2.80	f375_0_gcd_Store(EOS(STATIC_375), i47, i46, i46) -> f379_0_gcd_Load(EOS(STATIC_379), i47, i46, i46) :|: TRUE
7.15/2.80	f379_0_gcd_Load(EOS(STATIC_379), i47, i46, i46) -> f383_0_gcd_Load(EOS(STATIC_383), i46, i46, i47) :|: TRUE
7.15/2.80	f383_0_gcd_Load(EOS(STATIC_383), i46, i46, i47) -> f385_0_gcd_InvokeMethod(EOS(STATIC_385), i46, i47, i46) :|: TRUE
7.15/2.80	f385_0_gcd_InvokeMethod(EOS(STATIC_385), i46, i47, i46) -> f387_0_mod_Load(EOS(STATIC_387), i46, i47, i46) :|: TRUE
7.15/2.80	f387_0_mod_Load(EOS(STATIC_387), i46, i47, i46) -> f390_0_mod_NE(EOS(STATIC_390), i46, i47, i46, i46) :|: TRUE
7.15/2.80	f390_0_mod_NE(EOS(STATIC_390), i46, i47, i46, i46) -> f391_0_mod_Load(EOS(STATIC_391), i46, i47, i46) :|: i46 > 0
7.15/2.80	f391_0_mod_Load(EOS(STATIC_391), i46, i47, i46) -> f392_0_mod_GE(EOS(STATIC_392), i46, i47, i46, i46) :|: TRUE
7.15/2.80	f392_0_mod_GE(EOS(STATIC_392), i46, i47, i46, i46) -> f393_0_mod_Load(EOS(STATIC_393), i46, i47, i46) :|: i46 >= 0
7.15/2.80	f393_0_mod_Load(EOS(STATIC_393), i46, i47, i46) -> f394_0_mod_LE(EOS(STATIC_394), i46, i47, i46, i47) :|: TRUE
7.15/2.80	f394_0_mod_LE(EOS(STATIC_394), i46, i47, i46, i47) -> f395_0_mod_Load(EOS(STATIC_395), i46, i47, i46) :|: i47 > 0
7.15/2.80	f395_0_mod_Load(EOS(STATIC_395), i46, i47, i46) -> f435_0_mod_Load(EOS(STATIC_435), i46, i47, i46) :|: TRUE
7.15/2.80	f435_0_mod_Load(EOS(STATIC_435), i46, i50, i46) -> f436_0_mod_Load(EOS(STATIC_436), i46, i50, i46, i50) :|: TRUE
7.15/2.80	f436_0_mod_Load(EOS(STATIC_436), i46, i50, i46, i50) -> f437_0_mod_LT(EOS(STATIC_437), i46, i50, i46, i50, i46) :|: TRUE
7.15/2.80	f437_0_mod_LT(EOS(STATIC_437), i46, i50, i46, i50, i46) -> f462_0_mod_LT(EOS(STATIC_462), i46, i50, i46, i50, i46) :|: i50 < i46
7.15/2.80	f437_0_mod_LT(EOS(STATIC_437), i46, i50, i46, i50, i46) -> f463_0_mod_LT(EOS(STATIC_463), i46, i50, i46, i50, i46) :|: i50 >= i46
7.15/2.80	f462_0_mod_LT(EOS(STATIC_462), i46, i50, i46, i50, i46) -> f464_0_mod_Load(EOS(STATIC_464), i46, i50) :|: i50 < i46
7.15/2.80	f464_0_mod_Load(EOS(STATIC_464), i46, i50) -> f471_0_mod_Return(EOS(STATIC_471), i46, i50) :|: TRUE
7.15/2.80	f471_0_mod_Return(EOS(STATIC_471), i46, i50) -> f473_0_gcd_Store(EOS(STATIC_473), i46, i50) :|: TRUE
7.15/2.80	f473_0_gcd_Store(EOS(STATIC_473), i46, i50) -> f475_0_gcd_Load(EOS(STATIC_475), i50, i46) :|: TRUE
7.15/2.80	f475_0_gcd_Load(EOS(STATIC_475), i50, i46) -> f480_0_gcd_Store(EOS(STATIC_480), i50, i46) :|: TRUE
7.15/2.80	f480_0_gcd_Store(EOS(STATIC_480), i50, i46) -> f485_0_gcd_JMP(EOS(STATIC_485), i46, i50) :|: TRUE
7.15/2.80	f485_0_gcd_JMP(EOS(STATIC_485), i46, i50) -> f511_0_gcd_Load(EOS(STATIC_511), i46, i50) :|: TRUE
7.15/2.80	f511_0_gcd_Load(EOS(STATIC_511), i46, i50) -> f320_0_gcd_Load(EOS(STATIC_320), i46, i50) :|: TRUE
7.15/2.80	f320_0_gcd_Load(EOS(STATIC_320), i19, i43) -> f326_0_gcd_LE(EOS(STATIC_326), i19, i43, i43) :|: TRUE
7.15/2.80	f463_0_mod_LT(EOS(STATIC_463), i46, i50, i46, i50, i46) -> f468_0_mod_Load(EOS(STATIC_468), i46, i50, i46) :|: i50 >= i46
7.15/2.80	f468_0_mod_Load(EOS(STATIC_468), i46, i50, i46) -> f472_0_mod_Load(EOS(STATIC_472), i46, i46, i50) :|: TRUE
7.15/2.80	f472_0_mod_Load(EOS(STATIC_472), i46, i46, i50) -> f474_0_mod_IntArithmetic(EOS(STATIC_474), i46, i46, i50, i46) :|: TRUE
7.15/2.80	f474_0_mod_IntArithmetic(EOS(STATIC_474), i46, i46, i50, i46) -> f477_0_mod_Store(EOS(STATIC_477), i46, i46, i50 - i46) :|: i50 > 0 && i46 > 0
7.15/2.80	f477_0_mod_Store(EOS(STATIC_477), i46, i46, i55) -> f483_0_mod_JMP(EOS(STATIC_483), i46, i55, i46) :|: TRUE
7.15/2.80	f483_0_mod_JMP(EOS(STATIC_483), i46, i55, i46) -> f509_0_mod_Load(EOS(STATIC_509), i46, i55, i46) :|: TRUE
7.15/2.80	f509_0_mod_Load(EOS(STATIC_509), i46, i55, i46) -> f435_0_mod_Load(EOS(STATIC_435), i46, i55, i46) :|: TRUE
7.15/2.80	Combined rules. Obtained 2 IRulesP rules:
7.15/2.80	f437_0_mod_LT(EOS(STATIC_437), i46:0, i50:0, i46:0, i50:0, i46:0) -> f437_0_mod_LT(EOS(STATIC_437), i50:0, i46:0, i50:0, i46:0, i50:0) :|: i50:0 > 0 && i46:0 > 0 && i50:0 < i46:0
7.15/2.80	f437_0_mod_LT(EOS(STATIC_437), i46:0, i50:0, i46:0, i50:0, i46:0) -> f437_0_mod_LT(EOS(STATIC_437), i46:0, i50:0 - i46:0, i46:0, i50:0 - i46:0, i46:0) :|: i50:0 >= i46:0 && i50:0 > 0 && i46:0 > 0
7.15/2.80	Filtered constant ground arguments:
7.15/2.80	   f437_0_mod_LT(x1, x2, x3, x4, x5, x6) -> f437_0_mod_LT(x2, x3, x4, x5, x6)
7.15/2.80	   EOS(x1) -> EOS
7.15/2.80	Filtered duplicate arguments:
7.15/2.80	   f437_0_mod_LT(x1, x2, x3, x4, x5) -> f437_0_mod_LT(x4, x5)
7.15/2.80	Finished conversion. Obtained 2 rules.P rules:
7.15/2.80	f437_0_mod_LT(i50:0, i46:0) -> f437_0_mod_LT(i46:0, i50:0) :|: i46:0 > 0 && i50:0 < i46:0 && i50:0 > 0
7.15/2.80	f437_0_mod_LT(i50:0, i46:0) -> f437_0_mod_LT(i50:0 - i46:0, i46:0) :|: i50:0 > 0 && i46:0 > 0 && i50:0 >= i46:0
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(8)
7.15/2.80	Obligation:
7.15/2.80	Rules:
7.15/2.80	f437_0_mod_LT(i50:0, i46:0) -> f437_0_mod_LT(i46:0, i50:0) :|: i46:0 > 0 && i50:0 < i46:0 && i50:0 > 0
7.15/2.80	f437_0_mod_LT(x, x1) -> f437_0_mod_LT(x - x1, x1) :|: x > 0 && x1 > 0 && x >= x1
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(9) IRSFormatTransformerProof (EQUIVALENT)
7.15/2.80	Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %).
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(10)
7.15/2.80	Obligation:
7.15/2.80	Rules:
7.15/2.80	f437_0_mod_LT(i50:0, i46:0) -> f437_0_mod_LT(i46:0, i50:0) :|: i46:0 > 0 && i50:0 < i46:0 && i50:0 > 0
7.15/2.80	f437_0_mod_LT(x, x1) -> f437_0_mod_LT(arith, x1) :|: x > 0 && x1 > 0 && x >= x1 && arith = x - x1
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(11) IRSwTTerminationDigraphProof (EQUIVALENT)
7.15/2.80	Constructed termination digraph!
7.15/2.80	Nodes:
7.15/2.80	(1) f437_0_mod_LT(i50:0, i46:0) -> f437_0_mod_LT(i46:0, i50:0) :|: i46:0 > 0 && i50:0 < i46:0 && i50:0 > 0
7.15/2.80	(2) f437_0_mod_LT(x, x1) -> f437_0_mod_LT(arith, x1) :|: x > 0 && x1 > 0 && x >= x1 && arith = x - x1
7.15/2.80	
7.15/2.80	Arcs:
7.15/2.80	(1) -> (2)
7.15/2.80	(2) -> (1), (2)
7.15/2.80	
7.15/2.80	This digraph is fully evaluated!
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(12)
7.15/2.80	Obligation:
7.15/2.80	
7.15/2.80	Termination digraph:
7.15/2.80	Nodes:
7.15/2.80	(1) f437_0_mod_LT(i50:0, i46:0) -> f437_0_mod_LT(i46:0, i50:0) :|: i46:0 > 0 && i50:0 < i46:0 && i50:0 > 0
7.15/2.80	(2) f437_0_mod_LT(x, x1) -> f437_0_mod_LT(arith, x1) :|: x > 0 && x1 > 0 && x >= x1 && arith = x - x1
7.15/2.80	
7.15/2.80	Arcs:
7.15/2.80	(1) -> (2)
7.15/2.80	(2) -> (1), (2)
7.15/2.80	
7.15/2.80	This digraph is fully evaluated!
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(13) IntTRSCompressionProof (EQUIVALENT)
7.15/2.80	Compressed rules.
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(14)
7.15/2.80	Obligation:
7.15/2.80	Rules:
7.15/2.80	f437_0_mod_LT(i50:0:0, i46:0:0) -> f437_0_mod_LT(i46:0:0, i50:0:0) :|: i46:0:0 > 0 && i50:0:0 < i46:0:0 && i50:0:0 > 0
7.15/2.80	f437_0_mod_LT(x:0, x1:0) -> f437_0_mod_LT(x:0 - x1:0, x1:0) :|: x:0 > 0 && x1:0 > 0 && x:0 >= x1:0
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(15) TempFilterProof (SOUND)
7.15/2.80	Used the following sort dictionary for filtering: 
7.15/2.80	f437_0_mod_LT(INTEGER, INTEGER)
7.15/2.80	Replaced non-predefined constructor symbols by 0.
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(16)
7.15/2.80	Obligation:
7.15/2.80	Rules:
7.15/2.80	f437_0_mod_LT(i50:0:0, i46:0:0) -> f437_0_mod_LT(i46:0:0, i50:0:0) :|: i46:0:0 > 0 && i50:0:0 < i46:0:0 && i50:0:0 > 0
7.15/2.80	f437_0_mod_LT(x:0, x1:0) -> f437_0_mod_LT(c, x1:0) :|: c = x:0 - x1:0 && (x:0 > 0 && x1:0 > 0 && x:0 >= x1:0)
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(17) PolynomialOrderProcessor (EQUIVALENT)
7.15/2.80	Found the following polynomial interpretation:
7.15/2.80	[f437_0_mod_LT(x, x1)] = x1
7.15/2.80	
7.15/2.80	The following rules are decreasing:
7.15/2.80	f437_0_mod_LT(i50:0:0, i46:0:0) -> f437_0_mod_LT(i46:0:0, i50:0:0) :|: i46:0:0 > 0 && i50:0:0 < i46:0:0 && i50:0:0 > 0
7.15/2.80	The following rules are bounded:
7.15/2.80	f437_0_mod_LT(i50:0:0, i46:0:0) -> f437_0_mod_LT(i46:0:0, i50:0:0) :|: i46:0:0 > 0 && i50:0:0 < i46:0:0 && i50:0:0 > 0
7.15/2.80	f437_0_mod_LT(x:0, x1:0) -> f437_0_mod_LT(c, x1:0) :|: c = x:0 - x1:0 && (x:0 > 0 && x1:0 > 0 && x:0 >= x1:0)
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(18)
7.15/2.80	Obligation:
7.15/2.80	Rules:
7.15/2.80	f437_0_mod_LT(x:0, x1:0) -> f437_0_mod_LT(c, x1:0) :|: c = x:0 - x1:0 && (x:0 > 0 && x1:0 > 0 && x:0 >= x1:0)
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(19) PolynomialOrderProcessor (EQUIVALENT)
7.15/2.80	Found the following polynomial interpretation:
7.15/2.80	[f437_0_mod_LT(x, x1)] = x
7.15/2.80	
7.15/2.80	The following rules are decreasing:
7.15/2.80	f437_0_mod_LT(x:0, x1:0) -> f437_0_mod_LT(c, x1:0) :|: c = x:0 - x1:0 && (x:0 > 0 && x1:0 > 0 && x:0 >= x1:0)
7.15/2.80	The following rules are bounded:
7.15/2.80	f437_0_mod_LT(x:0, x1:0) -> f437_0_mod_LT(c, x1:0) :|: c = x:0 - x1:0 && (x:0 > 0 && x1:0 > 0 && x:0 >= x1:0)
7.15/2.80	
7.15/2.80	----------------------------------------
7.15/2.80	
7.15/2.80	(20)
7.15/2.80	YES
7.28/2.93	EOF