/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


termination of the given Bare JBC problem could be proven:

(0) Bare JBC problem
(1) BareJBCToJBCProof [EQUIVALENT, 97 ms]
(2) JBC problem
(3) JBCToGraph [EQUIVALENT, 1357 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 45 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 51 ms]
(12) IRSwT
(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(14) IRSwT
(15) TempFilterProof [SOUND, 42 ms]
(16) IntTRS
(17) RankingReductionPairProof [EQUIVALENT, 0 ms]
(18) 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 199 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:
f419_0_main_Load(EOS(STATIC_419), i46, i52, i46) -> f420_0_main_EQ(EOS(STATIC_420), i46, i52, i46, i52) :|: TRUE
f420_0_main_EQ(EOS(STATIC_420), i46, i52, i46, i52) -> f424_0_main_EQ(EOS(STATIC_424), i46, i52, i46, i52) :|: !(i46 = i52)
f424_0_main_EQ(EOS(STATIC_424), i46, i52, i46, i52) -> f428_0_main_Load(EOS(STATIC_428), i46, i52) :|: !(i46 = i52)
f428_0_main_Load(EOS(STATIC_428), i46, i52) -> f431_0_main_Load(EOS(STATIC_431), i46, i52, i46) :|: TRUE
f431_0_main_Load(EOS(STATIC_431), i46, i52, i46) -> f432_0_main_LE(EOS(STATIC_432), i46, i52, i46, i52) :|: TRUE
f432_0_main_LE(EOS(STATIC_432), i46, i52, i46, i52) -> f439_0_main_LE(EOS(STATIC_439), i46, i52, i46, i52) :|: i46 <= i52
f432_0_main_LE(EOS(STATIC_432), i46, i52, i46, i52) -> f440_0_main_LE(EOS(STATIC_440), i46, i52, i46, i52) :|: i46 > i52
f439_0_main_LE(EOS(STATIC_439), i46, i52, i46, i52) -> f446_0_main_Load(EOS(STATIC_446), i46, i52) :|: i46 < i52
f446_0_main_Load(EOS(STATIC_446), i46, i52) -> f449_0_main_Load(EOS(STATIC_449), i46, i52) :|: TRUE
f449_0_main_Load(EOS(STATIC_449), i46, i52) -> f451_0_main_IntArithmetic(EOS(STATIC_451), i46, i52, i46) :|: TRUE
f451_0_main_IntArithmetic(EOS(STATIC_451), i46, i52, i46) -> f454_0_main_Store(EOS(STATIC_454), i46, i52 - i46) :|: i52 > 0 && i46 > 0
f454_0_main_Store(EOS(STATIC_454), i46, i56) -> f456_0_main_JMP(EOS(STATIC_456), i46, i56) :|: TRUE
f456_0_main_JMP(EOS(STATIC_456), i46, i56) -> f476_0_main_Load(EOS(STATIC_476), i46, i56) :|: TRUE
f476_0_main_Load(EOS(STATIC_476), i46, i56) -> f418_0_main_Load(EOS(STATIC_418), i46, i56) :|: TRUE
f418_0_main_Load(EOS(STATIC_418), i46, i52) -> f419_0_main_Load(EOS(STATIC_419), i46, i52, i46) :|: TRUE
f440_0_main_LE(EOS(STATIC_440), i46, i52, i46, i52) -> f447_0_main_Load(EOS(STATIC_447), i46, i52) :|: i46 > i52
f447_0_main_Load(EOS(STATIC_447), i46, i52) -> f450_0_main_Load(EOS(STATIC_450), i52, i46) :|: TRUE
f450_0_main_Load(EOS(STATIC_450), i52, i46) -> f452_0_main_IntArithmetic(EOS(STATIC_452), i52, i46, i52) :|: TRUE
f452_0_main_IntArithmetic(EOS(STATIC_452), i52, i46, i52) -> f455_0_main_Store(EOS(STATIC_455), i52, i46 - i52) :|: i46 > 0 && i52 > 0
f455_0_main_Store(EOS(STATIC_455), i52, i57) -> f457_0_main_JMP(EOS(STATIC_457), i57, i52) :|: TRUE
f457_0_main_JMP(EOS(STATIC_457), i57, i52) -> f479_0_main_Load(EOS(STATIC_479), i57, i52) :|: TRUE
f479_0_main_Load(EOS(STATIC_479), i57, i52) -> f418_0_main_Load(EOS(STATIC_418), i57, i52) :|: TRUE
Combined rules. Obtained 2 IRulesP rules:
f419_0_main_Load(EOS(STATIC_419), i46:0, i52:0, i46:0) -> f419_0_main_Load(EOS(STATIC_419), i46:0 - i52:0, i52:0, i46:0 - i52:0) :|: i52:0 < i46:0 && i46:0 > 0 && i52:0 > 0
f419_0_main_Load(EOS(STATIC_419), i46:0, i52:0, i46:0) -> f419_0_main_Load(EOS(STATIC_419), i46:0, i52:0 - i46:0, i46:0) :|: i52:0 > i46:0 && i52:0 > 0 && i46:0 > 0
Filtered constant ground arguments:
   f419_0_main_Load(x1, x2, x3, x4) -> f419_0_main_Load(x2, x3, x4)
   EOS(x1) -> EOS
Filtered duplicate arguments:
   f419_0_main_Load(x1, x2, x3) -> f419_0_main_Load(x2, x3)
Finished conversion. Obtained 2 rules.P rules:
f419_0_main_Load(i52:0, i46:0) -> f419_0_main_Load(i52:0, i46:0 - i52:0) :|: i46:0 > 0 && i52:0 > 0 && i52:0 < i46:0
f419_0_main_Load(i52:0, i46:0) -> f419_0_main_Load(i52:0 - i46:0, i46:0) :|: i52:0 > 0 && i46:0 > 0 && i52:0 > i46:0

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

(8)
Obligation:
Rules:
f419_0_main_Load(i52:0, i46:0) -> f419_0_main_Load(i52:0, i46:0 - i52:0) :|: i46:0 > 0 && i52:0 > 0 && i52:0 < i46:0
f419_0_main_Load(x, x1) -> f419_0_main_Load(x - x1, x1) :|: x > 0 && x1 > 0 && x > x1

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

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

(10)
Obligation:
Rules:
f419_0_main_Load(i52:0, i46:0) -> f419_0_main_Load(i52:0, arith) :|: i46:0 > 0 && i52:0 > 0 && i52:0 < i46:0 && arith = i46:0 - i52:0
f419_0_main_Load(x2, x3) -> f419_0_main_Load(x4, x3) :|: x2 > 0 && x3 > 0 && x2 > x3 && x4 = x2 - x3

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

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f419_0_main_Load(i52:0, i46:0) -> f419_0_main_Load(i52:0, arith) :|: i46:0 > 0 && i52:0 > 0 && i52:0 < i46:0 && arith = i46:0 - i52:0
(2) f419_0_main_Load(x2, x3) -> f419_0_main_Load(x4, x3) :|: x2 > 0 && x3 > 0 && x2 > x3 && x4 = x2 - x3

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

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

(12)
Obligation:

Termination digraph:
Nodes:
(1) f419_0_main_Load(i52:0, i46:0) -> f419_0_main_Load(i52:0, arith) :|: i46:0 > 0 && i52:0 > 0 && i52:0 < i46:0 && arith = i46:0 - i52:0
(2) f419_0_main_Load(x2, x3) -> f419_0_main_Load(x4, x3) :|: x2 > 0 && x3 > 0 && x2 > x3 && x4 = x2 - x3

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

This digraph is fully evaluated!

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

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

(14)
Obligation:
Rules:
f419_0_main_Load(x2:0, x3:0) -> f419_0_main_Load(x2:0 - x3:0, x3:0) :|: x2:0 > 0 && x3:0 > 0 && x3:0 < x2:0
f419_0_main_Load(i52:0:0, i46:0:0) -> f419_0_main_Load(i52:0:0, i46:0:0 - i52:0:0) :|: i46:0:0 > 0 && i52:0:0 > 0 && i52:0:0 < i46:0:0

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

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

(16)
Obligation:
Rules:
f419_0_main_Load(x2:0, x3:0) -> f419_0_main_Load(c, x3:0) :|: c = x2:0 - x3:0 && (x2:0 > 0 && x3:0 > 0 && x3:0 < x2:0)
f419_0_main_Load(i52:0:0, i46:0:0) -> f419_0_main_Load(i52:0:0, c1) :|: c1 = i46:0:0 - i52:0:0 && (i46:0:0 > 0 && i52:0:0 > 0 && i52:0:0 < i46:0:0)

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

(17) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ f419_0_main_Load ] = f419_0_main_Load_1 + f419_0_main_Load_2

The following rules are decreasing:
f419_0_main_Load(x2:0, x3:0) -> f419_0_main_Load(c, x3:0) :|: c = x2:0 - x3:0 && (x2:0 > 0 && x3:0 > 0 && x3:0 < x2:0)
f419_0_main_Load(i52:0:0, i46:0:0) -> f419_0_main_Load(i52:0:0, c1) :|: c1 = i46:0:0 - i52:0:0 && (i46:0:0 > 0 && i52:0:0 > 0 && i52:0:0 < i46:0:0)

The following rules are bounded:
f419_0_main_Load(x2:0, x3:0) -> f419_0_main_Load(c, x3:0) :|: c = x2:0 - x3:0 && (x2:0 > 0 && x3:0 > 0 && x3:0 < x2:0)
f419_0_main_Load(i52:0:0, i46:0:0) -> f419_0_main_Load(i52:0:0, c1) :|: c1 = i46:0:0 - i52:0:0 && (i46:0:0 > 0 && i52:0:0 > 0 && i52:0:0 < i46:0:0)


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

(18)
YES