/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, 309 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 6 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 135 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 69 ms]
(12) AND
    (13) IRSwT
        (14) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (15) IRSwT
        (16) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (17) IRSwT
        (18) TempFilterProof [SOUND, 29 ms]
        (19) IntTRS
        (20) PolynomialOrderProcessor [EQUIVALENT, 9 ms]
        (21) YES
    (22) IRSwT
        (23) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (24) IRSwT
        (25) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms]
        (26) IRSwT
        (27) TempFilterProof [SOUND, 19 ms]
        (28) IntTRS
        (29) PolynomialOrderProcessor [EQUIVALENT, 9 ms]
        (30) 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 PastaB18 {
    public static void main(String[] args) {
        Random.args = args;
        int x = Random.random();
        int y = Random.random();

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


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

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


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:
PastaB18.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: PastaB18.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 33 IRulesP rules:
f306_0_main_LE(EOS(STATIC_306), i46, i44, i46) -> f310_0_main_LE(EOS(STATIC_310), i46, i44, i46) :|: TRUE
f310_0_main_LE(EOS(STATIC_310), i46, i44, i46) -> f313_0_main_Load(EOS(STATIC_313), i46, i44) :|: i46 > 0
f313_0_main_Load(EOS(STATIC_313), i46, i44) -> f317_0_main_LE(EOS(STATIC_317), i46, i44, i44) :|: TRUE
f317_0_main_LE(EOS(STATIC_317), i46, i47, i47) -> f321_0_main_LE(EOS(STATIC_321), i46, i47, i47) :|: TRUE
f321_0_main_LE(EOS(STATIC_321), i46, i47, i47) -> f325_0_main_Load(EOS(STATIC_325), i46, i47) :|: i47 > 0
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_LE(EOS(STATIC_331), i46, i47, i46, i47) :|: TRUE
f331_0_main_LE(EOS(STATIC_331), i46, i47, i46, i47) -> f334_0_main_LE(EOS(STATIC_334), i46, i47, i46, i47) :|: i46 <= i47
f331_0_main_LE(EOS(STATIC_331), i46, i47, i46, i47) -> f336_0_main_LE(EOS(STATIC_336), i46, i47, i46, i47) :|: i46 > i47
f334_0_main_LE(EOS(STATIC_334), i46, i47, i46, i47) -> f343_0_main_Load(EOS(STATIC_343), i46, i47) :|: i46 <= i47
f343_0_main_Load(EOS(STATIC_343), i46, i47) -> f509_0_main_Load(EOS(STATIC_509), i46, i47) :|: TRUE
f509_0_main_Load(EOS(STATIC_509), i46, i73) -> f610_0_main_LE(EOS(STATIC_610), i46, i73, i73) :|: TRUE
f610_0_main_LE(EOS(STATIC_610), i46, matching1, matching2) -> f619_0_main_LE(EOS(STATIC_619), i46, 0, 0) :|: TRUE && matching1 = 0 && matching2 = 0
f610_0_main_LE(EOS(STATIC_610), i46, i99, i99) -> f620_0_main_LE(EOS(STATIC_620), i46, i99, i99) :|: TRUE
f619_0_main_LE(EOS(STATIC_619), i46, matching1, matching2) -> f730_0_main_Load(EOS(STATIC_730), i46, 0) :|: 0 <= 0 && matching1 = 0 && matching2 = 0
f730_0_main_Load(EOS(STATIC_730), i46, matching1) -> f303_0_main_Load(EOS(STATIC_303), i46, 0) :|: TRUE && matching1 = 0
f303_0_main_Load(EOS(STATIC_303), i17, i44) -> f306_0_main_LE(EOS(STATIC_306), i17, i44, i17) :|: TRUE
f620_0_main_LE(EOS(STATIC_620), i46, i99, i99) -> f734_0_main_Inc(EOS(STATIC_734), i46, i99) :|: i99 > 0
f734_0_main_Inc(EOS(STATIC_734), i46, i99) -> f740_0_main_JMP(EOS(STATIC_740), i46, i99 + -1) :|: TRUE
f740_0_main_JMP(EOS(STATIC_740), i46, i124) -> f787_0_main_Load(EOS(STATIC_787), i46, i124) :|: TRUE
f787_0_main_Load(EOS(STATIC_787), i46, i124) -> f509_0_main_Load(EOS(STATIC_509), i46, i124) :|: TRUE
f336_0_main_LE(EOS(STATIC_336), i46, i47, i46, i47) -> f345_0_main_Load(EOS(STATIC_345), i46, i47) :|: i46 > i47
f345_0_main_Load(EOS(STATIC_345), i46, i47) -> f604_0_main_Load(EOS(STATIC_604), i46, i47) :|: TRUE
f604_0_main_Load(EOS(STATIC_604), i87, i47) -> f775_0_main_Load(EOS(STATIC_775), i87, i47) :|: TRUE
f775_0_main_Load(EOS(STATIC_775), i126, i47) -> f789_0_main_LE(EOS(STATIC_789), i126, i47, i126) :|: TRUE
f789_0_main_LE(EOS(STATIC_789), matching1, i47, matching2) -> f793_0_main_LE(EOS(STATIC_793), 0, i47, 0) :|: TRUE && matching1 = 0 && matching2 = 0
f789_0_main_LE(EOS(STATIC_789), i137, i47, i137) -> f794_0_main_LE(EOS(STATIC_794), i137, i47, i137) :|: TRUE
f793_0_main_LE(EOS(STATIC_793), matching1, i47, matching2) -> f829_0_main_Load(EOS(STATIC_829), 0, i47) :|: 0 <= 0 && matching1 = 0 && matching2 = 0
f829_0_main_Load(EOS(STATIC_829), matching1, i47) -> f303_0_main_Load(EOS(STATIC_303), 0, i47) :|: TRUE && matching1 = 0
f794_0_main_LE(EOS(STATIC_794), i137, i47, i137) -> f830_0_main_Inc(EOS(STATIC_830), i137, i47) :|: i137 > 0
f830_0_main_Inc(EOS(STATIC_830), i137, i47) -> f831_0_main_JMP(EOS(STATIC_831), i137 + -1, i47) :|: TRUE
f831_0_main_JMP(EOS(STATIC_831), i146, i47) -> f832_0_main_Load(EOS(STATIC_832), i146, i47) :|: TRUE
f832_0_main_Load(EOS(STATIC_832), i146, i47) -> f775_0_main_Load(EOS(STATIC_775), i146, i47) :|: TRUE
Combined rules. Obtained 6 IRulesP rules:
f306_0_main_LE(EOS(STATIC_306), i46:0, i44:0, i46:0) -> f610_0_main_LE(EOS(STATIC_610), i46:0, i44:0, i44:0) :|: i46:0 > 0 && i44:0 > 0 && i46:0 <= i44:0
f306_0_main_LE(EOS(STATIC_306), i46:0, i44:0, i46:0) -> f789_0_main_LE(EOS(STATIC_789), i46:0, i44:0, i46:0) :|: i46:0 > 0 && i44:0 > 0 && i46:0 > i44:0
f610_0_main_LE(EOS(STATIC_610), i46:0, i99:0, i99:0) -> f610_0_main_LE(EOS(STATIC_610), i46:0, i99:0 - 1, i99:0 - 1) :|: i99:0 > 0
f789_0_main_LE(EOS(STATIC_789), i137:0, i47:0, i137:0) -> f789_0_main_LE(EOS(STATIC_789), i137:0 - 1, i47:0, i137:0 - 1) :|: i137:0 > 0
f610_0_main_LE(EOS(STATIC_610), i46:0, 0, 0) -> f306_0_main_LE(EOS(STATIC_306), i46:0, 0, i46:0) :|: TRUE
f789_0_main_LE(EOS(STATIC_789), 0, i47:0, 0) -> f306_0_main_LE(EOS(STATIC_306), 0, i47:0, 0) :|: TRUE
Filtered constant ground arguments:
   f306_0_main_LE(x1, x2, x3, x4) -> f306_0_main_LE(x2, x3, x4)
   f610_0_main_LE(x1, x2, x3, x4) -> f610_0_main_LE(x2, x3, x4)
   f789_0_main_LE(x1, x2, x3, x4) -> f789_0_main_LE(x2, x3, x4)
Filtered duplicate arguments:
   f306_0_main_LE(x1, x2, x3) -> f306_0_main_LE(x2, x3)
   f610_0_main_LE(x1, x2, x3) -> f610_0_main_LE(x1, x3)
   f789_0_main_LE(x1, x2, x3) -> f789_0_main_LE(x2, x3)
Finished conversion. Obtained 6 rules.P rules:
f306_0_main_LE(i44:0, i46:0) -> f610_0_main_LE(i46:0, i44:0) :|: i44:0 > 0 && i46:0 <= i44:0 && i46:0 > 0
f306_0_main_LE(i44:0, i46:0) -> f789_0_main_LE(i44:0, i46:0) :|: i44:0 > 0 && i46:0 > i44:0 && i46:0 > 0
f610_0_main_LE(i46:0, i99:0) -> f610_0_main_LE(i46:0, i99:0 - 1) :|: i99:0 > 0
f789_0_main_LE(i47:0, i137:0) -> f789_0_main_LE(i47:0, i137:0 - 1) :|: i137:0 > 0
f610_0_main_LE(i46:0, cons_0) -> f306_0_main_LE(0, i46:0) :|: TRUE && cons_0 = 0
f789_0_main_LE(i47:0, cons_0) -> f306_0_main_LE(i47:0, 0) :|: TRUE && cons_0 = 0

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

(8)
Obligation:
Rules:
f306_0_main_LE(i44:0, i46:0) -> f610_0_main_LE(i46:0, i44:0) :|: i44:0 > 0 && i46:0 <= i44:0 && i46:0 > 0
f306_0_main_LE(x, x1) -> f789_0_main_LE(x, x1) :|: x > 0 && x1 > x && x1 > 0
f610_0_main_LE(x2, x3) -> f610_0_main_LE(x2, x3 - 1) :|: x3 > 0
f789_0_main_LE(i47:0, i137:0) -> f789_0_main_LE(i47:0, i137:0 - 1) :|: i137:0 > 0
f610_0_main_LE(x4, x5) -> f306_0_main_LE(0, x4) :|: TRUE && x5 = 0
f789_0_main_LE(x6, x7) -> f306_0_main_LE(x6, 0) :|: TRUE && x7 = 0

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

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

(10)
Obligation:
Rules:
f306_0_main_LE(i44:0, i46:0) -> f610_0_main_LE(i46:0, i44:0) :|: i44:0 > 0 && i46:0 <= i44:0 && i46:0 > 0
f306_0_main_LE(x, x1) -> f789_0_main_LE(x, x1) :|: x > 0 && x1 > x && x1 > 0
f610_0_main_LE(x2, x3) -> f610_0_main_LE(x2, arith) :|: x3 > 0 && arith = x3 - 1
f789_0_main_LE(x8, x9) -> f789_0_main_LE(x8, x10) :|: x9 > 0 && x10 = x9 - 1
f610_0_main_LE(x4, x5) -> f306_0_main_LE(0, x4) :|: TRUE && x5 = 0
f789_0_main_LE(x6, x7) -> f306_0_main_LE(x6, 0) :|: TRUE && x7 = 0

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

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f306_0_main_LE(i44:0, i46:0) -> f610_0_main_LE(i46:0, i44:0) :|: i44:0 > 0 && i46:0 <= i44:0 && i46:0 > 0
(2) f306_0_main_LE(x, x1) -> f789_0_main_LE(x, x1) :|: x > 0 && x1 > x && x1 > 0
(3) f610_0_main_LE(x2, x3) -> f610_0_main_LE(x2, arith) :|: x3 > 0 && arith = x3 - 1
(4) f789_0_main_LE(x8, x9) -> f789_0_main_LE(x8, x10) :|: x9 > 0 && x10 = x9 - 1
(5) f610_0_main_LE(x4, x5) -> f306_0_main_LE(0, x4) :|: TRUE && x5 = 0
(6) f789_0_main_LE(x6, x7) -> f306_0_main_LE(x6, 0) :|: TRUE && x7 = 0

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

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

(12)
Complex Obligation (AND)

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

(13)
Obligation:

Termination digraph:
Nodes:
(1) f789_0_main_LE(x8, x9) -> f789_0_main_LE(x8, x10) :|: x9 > 0 && x10 = x9 - 1

Arcs:
(1) -> (1)

This digraph is fully evaluated!

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

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

(15)
Obligation:
Rules:
f789_0_main_LE(x8:0, x9:0) -> f789_0_main_LE(x8:0, x9:0 - 1) :|: x9:0 > 0

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

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

   f789_0_main_LE(x1, x2) -> f789_0_main_LE(x2)

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

(17)
Obligation:
Rules:
f789_0_main_LE(x9:0) -> f789_0_main_LE(x9:0 - 1) :|: x9:0 > 0

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

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

(19)
Obligation:
Rules:
f789_0_main_LE(x9:0) -> f789_0_main_LE(c) :|: c = x9:0 - 1 && x9:0 > 0

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

(20) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f789_0_main_LE(x)] = x

The following rules are decreasing:
f789_0_main_LE(x9:0) -> f789_0_main_LE(c) :|: c = x9:0 - 1 && x9:0 > 0
The following rules are bounded:
f789_0_main_LE(x9:0) -> f789_0_main_LE(c) :|: c = x9:0 - 1 && x9:0 > 0

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

(21)
YES

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

(22)
Obligation:

Termination digraph:
Nodes:
(1) f610_0_main_LE(x2, x3) -> f610_0_main_LE(x2, arith) :|: x3 > 0 && arith = x3 - 1

Arcs:
(1) -> (1)

This digraph is fully evaluated!

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

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

(24)
Obligation:
Rules:
f610_0_main_LE(x2:0, x3:0) -> f610_0_main_LE(x2:0, x3:0 - 1) :|: x3:0 > 0

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

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

   f610_0_main_LE(x1, x2) -> f610_0_main_LE(x2)

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

(26)
Obligation:
Rules:
f610_0_main_LE(x3:0) -> f610_0_main_LE(x3:0 - 1) :|: x3:0 > 0

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

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

(28)
Obligation:
Rules:
f610_0_main_LE(x3:0) -> f610_0_main_LE(c) :|: c = x3:0 - 1 && x3:0 > 0

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

(29) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f610_0_main_LE(x)] = x

The following rules are decreasing:
f610_0_main_LE(x3:0) -> f610_0_main_LE(c) :|: c = x3:0 - 1 && x3:0 > 0
The following rules are bounded:
f610_0_main_LE(x3:0) -> f610_0_main_LE(c) :|: c = x3:0 - 1 && x3:0 > 0

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

(30)
YES