/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.jar /export/starexec/sandbox2/output/output_files


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


YES
proof of /export/starexec/sandbox2/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, 96 ms]
(2) JBC problem
(3) JBCToGraph [EQUIVALENT, 1266 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 118 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 143 ms]
(12) IRSwT
(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(14) IRSwT
(15) TempFilterProof [SOUND, 66 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:
/**
 * Example taken from "A Term Rewriting Approach to the Automated Termination
 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf)
 * and converted to Java.
 */

public class PastaC5 {
    public static void main(String[] args) {
        Random.args = args;
        int x = Random.random();
        int y = Random.random();

        if (x > 0 && y > 0) {
            while (x != y) {
                if (x > y) {
                    x = x - y;
                } else {
                    y = y - x;
                }
            }
        }
    }
}


public class Random {
  static String[] args;
  static int index = 0;

  public static int random() {
    String string = args[index];
    index++;
    return string.length();
  }
}



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

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

(2)
Obligation:
need to prove termination of the following program:
/**
 * Example taken from "A Term Rewriting Approach to the Automated Termination
 * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf)
 * and converted to Java.
 */

public class PastaC5 {
    public static void main(String[] args) {
        Random.args = args;
        int x = Random.random();
        int y = Random.random();

        if (x > 0 && y > 0) {
            while (x != y) {
                if (x > y) {
                    x = x - y;
                } else {
                    y = y - x;
                }
            }
        }
    }
}


public class Random {
  static String[] args;
  static int index = 0;

  public static int random() {
    String string = args[index];
    index++;
    return string.length();
  }
}



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

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

(4)
Obligation:
Termination Graph based on JBC Program:
PastaC5.main([Ljava/lang/String;)V: Graph of 198 nodes with 1 SCC.





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

(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: PastaC5.main([Ljava/lang/String;)V
SCC calls the following helper methods: 
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 22 IRulesP rules:
f337_0_main_EQ(EOS(STATIC_337), i46, i47, i46, i47) -> f352_0_main_Load(EOS(STATIC_352), i46, i47) :|: !(i46 = i47)
f352_0_main_Load(EOS(STATIC_352), i46, i47) -> f357_0_main_Load(EOS(STATIC_357), i46, i47, i46) :|: TRUE
f357_0_main_Load(EOS(STATIC_357), i46, i47, i46) -> f360_0_main_LE(EOS(STATIC_360), i46, i47, i46, i47) :|: TRUE
f360_0_main_LE(EOS(STATIC_360), i46, i47, i46, i47) -> f363_0_main_LE(EOS(STATIC_363), i46, i47, i46, i47) :|: i46 <= i47
f360_0_main_LE(EOS(STATIC_360), i46, i47, i46, i47) -> f364_0_main_LE(EOS(STATIC_364), i46, i47, i46, i47) :|: i46 > i47
f363_0_main_LE(EOS(STATIC_363), i46, i47, i46, i47) -> f369_0_main_Load(EOS(STATIC_369), i46, i47) :|: i46 < i47
f369_0_main_Load(EOS(STATIC_369), i46, i47) -> f376_0_main_Load(EOS(STATIC_376), i46, i47) :|: TRUE
f376_0_main_Load(EOS(STATIC_376), i46, i47) -> f384_0_main_IntArithmetic(EOS(STATIC_384), i46, i47, i46) :|: TRUE
f384_0_main_IntArithmetic(EOS(STATIC_384), i46, i47, i46) -> f388_0_main_Store(EOS(STATIC_388), i46, i47 - i46) :|: i47 > 0 && i46 > 0
f388_0_main_Store(EOS(STATIC_388), i46, i49) -> f392_0_main_JMP(EOS(STATIC_392), i46, i49) :|: TRUE
f392_0_main_JMP(EOS(STATIC_392), i46, i49) -> f403_0_main_Load(EOS(STATIC_403), i46, i49) :|: TRUE
f403_0_main_Load(EOS(STATIC_403), i46, i49) -> f325_0_main_Load(EOS(STATIC_325), i46, i49) :|: TRUE
f325_0_main_Load(EOS(STATIC_325), i46, i47) -> f328_0_main_Load(EOS(STATIC_328), i46, i47, i46) :|: TRUE
f328_0_main_Load(EOS(STATIC_328), i46, i47, i46) -> f331_0_main_EQ(EOS(STATIC_331), i46, i47, i46, i47) :|: TRUE
f331_0_main_EQ(EOS(STATIC_331), i46, i47, i46, i47) -> f337_0_main_EQ(EOS(STATIC_337), i46, i47, i46, i47) :|: !(i46 = i47)
f364_0_main_LE(EOS(STATIC_364), i46, i47, i46, i47) -> f371_0_main_Load(EOS(STATIC_371), i46, i47) :|: i46 > i47
f371_0_main_Load(EOS(STATIC_371), i46, i47) -> f378_0_main_Load(EOS(STATIC_378), i47, i46) :|: TRUE
f378_0_main_Load(EOS(STATIC_378), i47, i46) -> f385_0_main_IntArithmetic(EOS(STATIC_385), i47, i46, i47) :|: TRUE
f385_0_main_IntArithmetic(EOS(STATIC_385), i47, i46, i47) -> f391_0_main_Store(EOS(STATIC_391), i47, i46 - i47) :|: i46 > 0 && i47 > 0
f391_0_main_Store(EOS(STATIC_391), i47, i51) -> f393_0_main_JMP(EOS(STATIC_393), i51, i47) :|: TRUE
f393_0_main_JMP(EOS(STATIC_393), i51, i47) -> f408_0_main_Load(EOS(STATIC_408), i51, i47) :|: TRUE
f408_0_main_Load(EOS(STATIC_408), i51, i47) -> f325_0_main_Load(EOS(STATIC_325), i51, i47) :|: TRUE
Combined rules. Obtained 4 IRulesP rules:
f337_0_main_EQ(EOS(STATIC_337), i46:0, i47:0, i46:0, i47:0) -> f337_0_main_EQ(EOS(STATIC_337), i46:0 - i47:0, i47:0, i46:0 - i47:0, i47:0) :|: i47:0 < i46:0 && i47:0 > 0 && i47:0 > i46:0 - i47:0 && i46:0 > 0
f337_0_main_EQ(EOS(STATIC_337), i46:0, i47:0, i46:0, i47:0) -> f337_0_main_EQ(EOS(STATIC_337), i46:0 - i47:0, i47:0, i46:0 - i47:0, i47:0) :|: i47:0 < i46:0 && i47:0 > 0 && i47:0 < i46:0 - i47:0 && i46:0 > 0
f337_0_main_EQ(EOS(STATIC_337), i46:0, i47:0, i46:0, i47:0) -> f337_0_main_EQ(EOS(STATIC_337), i46:0, i47:0 - i46:0, i46:0, i47:0 - i46:0) :|: i47:0 > i46:0 && i46:0 > 0 && i47:0 - i46:0 > i46:0 && i47:0 > 0
f337_0_main_EQ(EOS(STATIC_337), i46:0, i47:0, i46:0, i47:0) -> f337_0_main_EQ(EOS(STATIC_337), i46:0, i47:0 - i46:0, i46:0, i47:0 - i46:0) :|: i47:0 > i46:0 && i46:0 > 0 && i47:0 - i46:0 < i46:0 && i47:0 > 0
Filtered constant ground arguments:
   f337_0_main_EQ(x1, x2, x3, x4, x5) -> f337_0_main_EQ(x2, x3, x4, x5)
   EOS(x1) -> EOS
Filtered duplicate arguments:
   f337_0_main_EQ(x1, x2, x3, x4) -> f337_0_main_EQ(x3, x4)
Finished conversion. Obtained 4 rules.P rules:
f337_0_main_EQ(i46:0, i47:0) -> f337_0_main_EQ(i46:0 - i47:0, i47:0) :|: i47:0 > 0 && i47:0 < i46:0 && i46:0 > 0 && i47:0 > i46:0 - i47:0
f337_0_main_EQ(i46:0, i47:0) -> f337_0_main_EQ(i46:0 - i47:0, i47:0) :|: i47:0 > 0 && i47:0 < i46:0 && i46:0 > 0 && i47:0 < i46:0 - i47:0
f337_0_main_EQ(i46:0, i47:0) -> f337_0_main_EQ(i46:0, i47:0 - i46:0) :|: i46:0 > 0 && i47:0 > i46:0 && i47:0 > 0 && i47:0 - i46:0 > i46:0
f337_0_main_EQ(i46:0, i47:0) -> f337_0_main_EQ(i46:0, i47:0 - i46:0) :|: i46:0 > 0 && i47:0 > i46:0 && i47:0 > 0 && i47:0 - i46:0 < i46:0

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

(8)
Obligation:
Rules:
f337_0_main_EQ(i46:0, i47:0) -> f337_0_main_EQ(i46:0 - i47:0, i47:0) :|: i47:0 > 0 && i47:0 < i46:0 && i46:0 > 0 && i47:0 > i46:0 - i47:0
f337_0_main_EQ(x, x1) -> f337_0_main_EQ(x - x1, x1) :|: x1 > 0 && x1 < x && x > 0 && x1 < x - x1
f337_0_main_EQ(x2, x3) -> f337_0_main_EQ(x2, x3 - x2) :|: x2 > 0 && x3 > x2 && x3 > 0 && x3 - x2 > x2
f337_0_main_EQ(x4, x5) -> f337_0_main_EQ(x4, x5 - x4) :|: x4 > 0 && x5 > x4 && x5 > 0 && x5 - x4 < x4

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

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

(10)
Obligation:
Rules:
f337_0_main_EQ(i46:0, i47:0) -> f337_0_main_EQ(arith, i47:0) :|: i47:0 > 0 && i47:0 < i46:0 && i46:0 > 0 && i47:0 > i46:0 - i47:0 && arith = i46:0 - i47:0
f337_0_main_EQ(x6, x7) -> f337_0_main_EQ(x8, x7) :|: x7 > 0 && x7 < x6 && x6 > 0 && x7 < x6 - x7 && x8 = x6 - x7
f337_0_main_EQ(x9, x10) -> f337_0_main_EQ(x9, x11) :|: x9 > 0 && x10 > x9 && x10 > 0 && x10 - x9 > x9 && x11 = x10 - x9
f337_0_main_EQ(x12, x13) -> f337_0_main_EQ(x12, x14) :|: x12 > 0 && x13 > x12 && x13 > 0 && x13 - x12 < x12 && x14 = x13 - x12

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

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f337_0_main_EQ(i46:0, i47:0) -> f337_0_main_EQ(arith, i47:0) :|: i47:0 > 0 && i47:0 < i46:0 && i46:0 > 0 && i47:0 > i46:0 - i47:0 && arith = i46:0 - i47:0
(2) f337_0_main_EQ(x6, x7) -> f337_0_main_EQ(x8, x7) :|: x7 > 0 && x7 < x6 && x6 > 0 && x7 < x6 - x7 && x8 = x6 - x7
(3) f337_0_main_EQ(x9, x10) -> f337_0_main_EQ(x9, x11) :|: x9 > 0 && x10 > x9 && x10 > 0 && x10 - x9 > x9 && x11 = x10 - x9
(4) f337_0_main_EQ(x12, x13) -> f337_0_main_EQ(x12, x14) :|: x12 > 0 && x13 > x12 && x13 > 0 && x13 - x12 < x12 && x14 = x13 - x12

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

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

(12)
Obligation:

Termination digraph:
Nodes:
(1) f337_0_main_EQ(i46:0, i47:0) -> f337_0_main_EQ(arith, i47:0) :|: i47:0 > 0 && i47:0 < i46:0 && i46:0 > 0 && i47:0 > i46:0 - i47:0 && arith = i46:0 - i47:0
(2) f337_0_main_EQ(x6, x7) -> f337_0_main_EQ(x8, x7) :|: x7 > 0 && x7 < x6 && x6 > 0 && x7 < x6 - x7 && x8 = x6 - x7
(3) f337_0_main_EQ(x12, x13) -> f337_0_main_EQ(x12, x14) :|: x12 > 0 && x13 > x12 && x13 > 0 && x13 - x12 < x12 && x14 = x13 - x12
(4) f337_0_main_EQ(x9, x10) -> f337_0_main_EQ(x9, x11) :|: x9 > 0 && x10 > x9 && x10 > 0 && x10 - x9 > x9 && x11 = x10 - x9

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

This digraph is fully evaluated!

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

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

(14)
Obligation:
Rules:
f337_0_main_EQ(x9:0, x10:0) -> f337_0_main_EQ(x9:0, x10:0 - x9:0) :|: x10:0 > 0 && x9:0 < x10:0 - x9:0 && x9:0 < x10:0 && x9:0 > 0
f337_0_main_EQ(x6:0, x7:0) -> f337_0_main_EQ(x6:0 - x7:0, x7:0) :|: x6:0 > 0 && x7:0 < x6:0 - x7:0 && x7:0 < x6:0 && x7:0 > 0
f337_0_main_EQ(i46:0:0, i47:0:0) -> f337_0_main_EQ(i46:0:0 - i47:0:0, i47:0:0) :|: i46:0:0 > 0 && i47:0:0 > i46:0:0 - i47:0:0 && i47:0:0 < i46:0:0 && i47:0:0 > 0
f337_0_main_EQ(x12:0, x13:0) -> f337_0_main_EQ(x12:0, x13:0 - x12:0) :|: x13:0 > 0 && x13:0 - x12:0 < x12:0 && x13:0 > x12:0 && x12:0 > 0

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

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

(16)
Obligation:
Rules:
f337_0_main_EQ(x9:0, x10:0) -> f337_0_main_EQ(x9:0, c) :|: c = x10:0 - x9:0 && (x10:0 > 0 && x9:0 < x10:0 - x9:0 && x9:0 < x10:0 && x9:0 > 0)
f337_0_main_EQ(x6:0, x7:0) -> f337_0_main_EQ(c1, x7:0) :|: c1 = x6:0 - x7:0 && (x6:0 > 0 && x7:0 < x6:0 - x7:0 && x7:0 < x6:0 && x7:0 > 0)
f337_0_main_EQ(i46:0:0, i47:0:0) -> f337_0_main_EQ(c2, i47:0:0) :|: c2 = i46:0:0 - i47:0:0 && (i46:0:0 > 0 && i47:0:0 > i46:0:0 - i47:0:0 && i47:0:0 < i46:0:0 && i47:0:0 > 0)
f337_0_main_EQ(x12:0, x13:0) -> f337_0_main_EQ(x12:0, c3) :|: c3 = x13:0 - x12:0 && (x13:0 > 0 && x13:0 - x12:0 < x12:0 && x13:0 > x12:0 && x12:0 > 0)

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

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

The following rules are decreasing:
f337_0_main_EQ(x9:0, x10:0) -> f337_0_main_EQ(x9:0, c) :|: c = x10:0 - x9:0 && (x10:0 > 0 && x9:0 < x10:0 - x9:0 && x9:0 < x10:0 && x9:0 > 0)
f337_0_main_EQ(x12:0, x13:0) -> f337_0_main_EQ(x12:0, c3) :|: c3 = x13:0 - x12:0 && (x13:0 > 0 && x13:0 - x12:0 < x12:0 && x13:0 > x12:0 && x12:0 > 0)
The following rules are bounded:
f337_0_main_EQ(x9:0, x10:0) -> f337_0_main_EQ(x9:0, c) :|: c = x10:0 - x9:0 && (x10:0 > 0 && x9:0 < x10:0 - x9:0 && x9:0 < x10:0 && x9:0 > 0)
f337_0_main_EQ(x6:0, x7:0) -> f337_0_main_EQ(c1, x7:0) :|: c1 = x6:0 - x7:0 && (x6:0 > 0 && x7:0 < x6:0 - x7:0 && x7:0 < x6:0 && x7:0 > 0)
f337_0_main_EQ(i46:0:0, i47:0:0) -> f337_0_main_EQ(c2, i47:0:0) :|: c2 = i46:0:0 - i47:0:0 && (i46:0:0 > 0 && i47:0:0 > i46:0:0 - i47:0:0 && i47:0:0 < i46:0:0 && i47:0:0 > 0)
f337_0_main_EQ(x12:0, x13:0) -> f337_0_main_EQ(x12:0, c3) :|: c3 = x13:0 - x12:0 && (x13:0 > 0 && x13:0 - x12:0 < x12:0 && x13:0 > x12:0 && x12:0 > 0)

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

(18)
Obligation:
Rules:
f337_0_main_EQ(x6:0, x7:0) -> f337_0_main_EQ(c1, x7:0) :|: c1 = x6:0 - x7:0 && (x6:0 > 0 && x7:0 < x6:0 - x7:0 && x7:0 < x6:0 && x7:0 > 0)
f337_0_main_EQ(i46:0:0, i47:0:0) -> f337_0_main_EQ(c2, i47:0:0) :|: c2 = i46:0:0 - i47:0:0 && (i46:0:0 > 0 && i47:0:0 > i46:0:0 - i47:0:0 && i47:0:0 < i46:0:0 && i47:0:0 > 0)

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

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

The following rules are decreasing:
f337_0_main_EQ(x6:0, x7:0) -> f337_0_main_EQ(c1, x7:0) :|: c1 = x6:0 - x7:0 && (x6:0 > 0 && x7:0 < x6:0 - x7:0 && x7:0 < x6:0 && x7:0 > 0)
f337_0_main_EQ(i46:0:0, i47:0:0) -> f337_0_main_EQ(c2, i47:0:0) :|: c2 = i46:0:0 - i47:0:0 && (i46:0:0 > 0 && i47:0:0 > i46:0:0 - i47:0:0 && i47:0:0 < i46:0:0 && i47:0:0 > 0)
The following rules are bounded:
f337_0_main_EQ(x6:0, x7:0) -> f337_0_main_EQ(c1, x7:0) :|: c1 = x6:0 - x7:0 && (x6:0 > 0 && x7:0 < x6:0 - x7:0 && x7:0 < x6:0 && x7:0 > 0)
f337_0_main_EQ(i46:0:0, i47:0:0) -> f337_0_main_EQ(c2, i47:0:0) :|: c2 = i46:0:0 - i47:0:0 && (i46:0:0 > 0 && i47:0:0 > i46:0:0 - i47:0:0 && i47:0:0 < i46:0:0 && i47:0:0 > 0)

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

(20)
YES