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


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


YES
proof of /export/starexec/sandbox/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, 97 ms]
(2) JBC problem
(3) JBCToGraph [EQUIVALENT, 388 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 108 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 47 ms]
(12) AND
    (13) IRSwT
        (14) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (15) IRSwT
        (16) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (17) IRSwT
        (18) TempFilterProof [SOUND, 35 ms]
        (19) IntTRS
        (20) PolynomialOrderProcessor [EQUIVALENT, 11 ms]
        (21) YES
    (22) IRSwT
        (23) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (24) IRSwT
        (25) TempFilterProof [SOUND, 16 ms]
        (26) IntTRS
        (27) PolynomialOrderProcessor [EQUIVALENT, 3 ms]
        (28) 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 PastaB13 {
    public static void main(String[] args) {
        Random.args = args;
        int x = Random.random();
        int y = Random.random();
        int z = Random.random();

        while (x > z || y > z) {
            if (x > z) {
                x--;
            } else if (y > z) {
                y--;
            } else {
                continue;
            }
        }
    }
}


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 PastaB13 {
    public static void main(String[] args) {
        Random.args = args;
        int x = Random.random();
        int y = Random.random();
        int z = Random.random();

        while (x > z || y > z) {
            if (x > z) {
                x--;
            } else if (y > z) {
                y--;
            } else {
                continue;
            }
        }
    }
}


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:
PastaB13.main([Ljava/lang/String;)V: Graph of 261 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: PastaB13.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 28 IRulesP rules:
f416_0_main_Load(EOS(STATIC_416), i17, i43, i71, i17) -> f419_0_main_GT(EOS(STATIC_419), i17, i43, i71, i17, i71) :|: TRUE
f419_0_main_GT(EOS(STATIC_419), i17, i43, i71, i17, i71) -> f422_0_main_GT(EOS(STATIC_422), i17, i43, i71, i17, i71) :|: i17 > i71
f419_0_main_GT(EOS(STATIC_419), i17, i43, i71, i17, i71) -> f424_0_main_GT(EOS(STATIC_424), i17, i43, i71, i17, i71) :|: i17 <= i71
f422_0_main_GT(EOS(STATIC_422), i17, i43, i71, i17, i71) -> f430_0_main_Load(EOS(STATIC_430), i17, i43, i71) :|: i17 > i71
f430_0_main_Load(EOS(STATIC_430), i17, i43, i71) -> f445_0_main_Load(EOS(STATIC_445), i17, i43, i71, i17) :|: TRUE
f445_0_main_Load(EOS(STATIC_445), i17, i43, i71, i17) -> f450_0_main_LE(EOS(STATIC_450), i17, i43, i71, i17, i71) :|: TRUE
f450_0_main_LE(EOS(STATIC_450), i17, i43, i71, i17, i71) -> f454_0_main_LE(EOS(STATIC_454), i17, i43, i71, i17, i71) :|: i17 > i71
f454_0_main_LE(EOS(STATIC_454), i17, i43, i71, i17, i71) -> f468_0_main_Inc(EOS(STATIC_468), i17, i43, i71) :|: i17 > i71
f468_0_main_Inc(EOS(STATIC_468), i17, i43, i71) -> f483_0_main_JMP(EOS(STATIC_483), i17 + -1, i43, i71) :|: TRUE
f483_0_main_JMP(EOS(STATIC_483), i75, i43, i71) -> f509_0_main_Load(EOS(STATIC_509), i75, i43, i71) :|: TRUE
f509_0_main_Load(EOS(STATIC_509), i75, i43, i71) -> f413_0_main_Load(EOS(STATIC_413), i75, i43, i71) :|: TRUE
f413_0_main_Load(EOS(STATIC_413), i17, i43, i71) -> f416_0_main_Load(EOS(STATIC_416), i17, i43, i71, i17) :|: TRUE
f424_0_main_GT(EOS(STATIC_424), i17, i43, i71, i17, i71) -> f442_0_main_Load(EOS(STATIC_442), i17, i43, i71) :|: i17 <= i71
f442_0_main_Load(EOS(STATIC_442), i17, i43, i71) -> f446_0_main_Load(EOS(STATIC_446), i17, i43, i71, i43) :|: TRUE
f446_0_main_Load(EOS(STATIC_446), i17, i43, i71, i43) -> f451_0_main_LE(EOS(STATIC_451), i17, i43, i71, i43, i71) :|: TRUE
f451_0_main_LE(EOS(STATIC_451), i17, i43, i71, i43, i71) -> f461_0_main_LE(EOS(STATIC_461), i17, i43, i71, i43, i71) :|: i43 > i71
f461_0_main_LE(EOS(STATIC_461), i17, i43, i71, i43, i71) -> f480_0_main_Load(EOS(STATIC_480), i17, i43, i71) :|: i43 > i71
f480_0_main_Load(EOS(STATIC_480), i17, i43, i71) -> f485_0_main_Load(EOS(STATIC_485), i17, i43, i71, i17) :|: TRUE
f485_0_main_Load(EOS(STATIC_485), i17, i43, i71, i17) -> f520_0_main_LE(EOS(STATIC_520), i17, i43, i71, i17, i71) :|: TRUE
f520_0_main_LE(EOS(STATIC_520), i17, i43, i71, i17, i71) -> f642_0_main_LE(EOS(STATIC_642), i17, i43, i71, i17, i71) :|: i17 <= i71
f642_0_main_LE(EOS(STATIC_642), i17, i43, i71, i17, i71) -> f646_0_main_Load(EOS(STATIC_646), i17, i43, i71) :|: i17 <= i71
f646_0_main_Load(EOS(STATIC_646), i17, i43, i71) -> f649_0_main_Load(EOS(STATIC_649), i17, i43, i71, i43) :|: TRUE
f649_0_main_Load(EOS(STATIC_649), i17, i43, i71, i43) -> f651_0_main_LE(EOS(STATIC_651), i17, i43, i71, i43, i71) :|: TRUE
f651_0_main_LE(EOS(STATIC_651), i17, i43, i71, i43, i71) -> f659_0_main_LE(EOS(STATIC_659), i17, i43, i71, i43, i71) :|: i43 > i71
f659_0_main_LE(EOS(STATIC_659), i17, i43, i71, i43, i71) -> f663_0_main_Inc(EOS(STATIC_663), i17, i43, i71) :|: i43 > i71
f663_0_main_Inc(EOS(STATIC_663), i17, i43, i71) -> f666_0_main_JMP(EOS(STATIC_666), i17, i43 + -1, i71) :|: TRUE
f666_0_main_JMP(EOS(STATIC_666), i17, i88, i71) -> f670_0_main_Load(EOS(STATIC_670), i17, i88, i71) :|: TRUE
f670_0_main_Load(EOS(STATIC_670), i17, i88, i71) -> f413_0_main_Load(EOS(STATIC_413), i17, i88, i71) :|: TRUE
Combined rules. Obtained 2 IRulesP rules:
f416_0_main_Load(EOS(STATIC_416), i17:0, i43:0, i71:0, i17:0) -> f416_0_main_Load(EOS(STATIC_416), i17:0 - 1, i43:0, i71:0, i17:0 - 1) :|: i71:0 < i17:0
f416_0_main_Load(EOS(STATIC_416), i17:0, i43:0, i71:0, i17:0) -> f416_0_main_Load(EOS(STATIC_416), i17:0, i43:0 - 1, i71:0, i17:0) :|: i71:0 >= i17:0 && i71:0 < i43:0
Filtered constant ground arguments:
   f416_0_main_Load(x1, x2, x3, x4, x5) -> f416_0_main_Load(x2, x3, x4, x5)
   EOS(x1) -> EOS
Filtered duplicate arguments:
   f416_0_main_Load(x1, x2, x3, x4) -> f416_0_main_Load(x2, x3, x4)
Finished conversion. Obtained 2 rules.P rules:
f416_0_main_Load(i43:0, i71:0, i17:0) -> f416_0_main_Load(i43:0, i71:0, i17:0 - 1) :|: i71:0 < i17:0
f416_0_main_Load(i43:0, i71:0, i17:0) -> f416_0_main_Load(i43:0 - 1, i71:0, i17:0) :|: i71:0 >= i17:0 && i71:0 < i43:0

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

(8)
Obligation:
Rules:
f416_0_main_Load(i43:0, i71:0, i17:0) -> f416_0_main_Load(i43:0, i71:0, i17:0 - 1) :|: i71:0 < i17:0
f416_0_main_Load(x, x1, x2) -> f416_0_main_Load(x - 1, x1, x2) :|: x1 >= x2 && x1 < x

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

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

(10)
Obligation:
Rules:
f416_0_main_Load(i43:0, i71:0, i17:0) -> f416_0_main_Load(i43:0, i71:0, arith) :|: i71:0 < i17:0 && arith = i17:0 - 1
f416_0_main_Load(x3, x4, x5) -> f416_0_main_Load(x6, x4, x5) :|: x4 >= x5 && x4 < x3 && x6 = x3 - 1

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

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f416_0_main_Load(i43:0, i71:0, i17:0) -> f416_0_main_Load(i43:0, i71:0, arith) :|: i71:0 < i17:0 && arith = i17:0 - 1
(2) f416_0_main_Load(x3, x4, x5) -> f416_0_main_Load(x6, x4, x5) :|: x4 >= x5 && x4 < x3 && x6 = x3 - 1

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

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

(12)
Complex Obligation (AND)

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

(13)
Obligation:

Termination digraph:
Nodes:
(1) f416_0_main_Load(i43:0, i71:0, i17:0) -> f416_0_main_Load(i43:0, i71:0, arith) :|: i71:0 < i17:0 && arith = i17:0 - 1

Arcs:
(1) -> (1)

This digraph is fully evaluated!

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

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

(15)
Obligation:
Rules:
f416_0_main_Load(i43:0:0, i71:0:0, i17:0:0) -> f416_0_main_Load(i43:0:0, i71:0:0, i17:0:0 - 1) :|: i71:0:0 < i17:0:0

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

(16) IntTRSUnneededArgumentFilterProof (EQUIVALENT)
Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements:

   f416_0_main_Load(x1, x2, x3) -> f416_0_main_Load(x2, x3)

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

(17)
Obligation:
Rules:
f416_0_main_Load(i71:0:0, i17:0:0) -> f416_0_main_Load(i71:0:0, i17:0:0 - 1) :|: i71:0:0 < i17:0:0

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

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

(19)
Obligation:
Rules:
f416_0_main_Load(i71:0:0, i17:0:0) -> f416_0_main_Load(i71:0:0, c) :|: c = i17:0:0 - 1 && i71:0:0 < i17:0:0

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

(20) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f416_0_main_Load(x, x1)] = -x + x1

The following rules are decreasing:
f416_0_main_Load(i71:0:0, i17:0:0) -> f416_0_main_Load(i71:0:0, c) :|: c = i17:0:0 - 1 && i71:0:0 < i17:0:0
The following rules are bounded:
f416_0_main_Load(i71:0:0, i17:0:0) -> f416_0_main_Load(i71:0:0, c) :|: c = i17:0:0 - 1 && i71:0:0 < i17:0:0

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

(21)
YES

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

(22)
Obligation:

Termination digraph:
Nodes:
(1) f416_0_main_Load(x3, x4, x5) -> f416_0_main_Load(x6, x4, x5) :|: x4 >= x5 && x4 < x3 && x6 = x3 - 1

Arcs:
(1) -> (1)

This digraph is fully evaluated!

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

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

(24)
Obligation:
Rules:
f416_0_main_Load(x3:0, x4:0, x5:0) -> f416_0_main_Load(x3:0 - 1, x4:0, x5:0) :|: x5:0 <= x4:0 && x4:0 < x3:0

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

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

(26)
Obligation:
Rules:
f416_0_main_Load(x3:0, x4:0, x5:0) -> f416_0_main_Load(c, x4:0, x5:0) :|: c = x3:0 - 1 && (x5:0 <= x4:0 && x4:0 < x3:0)

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

(27) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f416_0_main_Load(x, x1, x2)] = x - x1

The following rules are decreasing:
f416_0_main_Load(x3:0, x4:0, x5:0) -> f416_0_main_Load(c, x4:0, x5:0) :|: c = x3:0 - 1 && (x5:0 <= x4:0 && x4:0 < x3:0)
The following rules are bounded:
f416_0_main_Load(x3:0, x4:0, x5:0) -> f416_0_main_Load(c, x4:0, x5:0) :|: c = x3:0 - 1 && (x5:0 <= x4:0 && x4:0 < x3:0)

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

(28)
YES