/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, 96 ms]
(2) JBC problem
(3) JBCToGraph [EQUIVALENT, 343 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 10 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 25 ms]
(12) IRSwT
(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(14) IRSwT
(15) FilterProof [EQUIVALENT, 0 ms]
(16) IntTRS
(17) IntTRSCompressionProof [EQUIVALENT, 2 ms]
(18) IntTRS
(19) PolynomialOrderProcessor [EQUIVALENT, 14 ms]
(20) YES


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

(0)
Obligation:
need to prove termination of the following program:
public class LogIterative {
  public static int log(int x, int y) {
    int res = 0;
    while (x >= y && y > 1) {
      res++;
      x = x/y;
    }
    return res;
  } 

  public static void main(String[] args) {
    Random.args = args;
    int x = Random.random();
    int y = Random.random();
    log(x, 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:
public class LogIterative {
  public static int log(int x, int y) {
    int res = 0;
    while (x >= y && y > 1) {
      res++;
      x = x/y;
    }
    return res;
  } 

  public static void main(String[] args) {
    Random.args = args;
    int x = Random.random();
    int y = Random.random();
    log(x, 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:
LogIterative.main([Ljava/lang/String;)V: Graph of 195 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: LogIterative.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 15 IRulesP rules:
f616_0_log_Load(EOS(STATIC_616), i93, i94, i93) -> f617_0_log_LT(EOS(STATIC_617), i93, i94, i93, i94) :|: TRUE
f617_0_log_LT(EOS(STATIC_617), i93, i94, i93, i94) -> f623_0_log_LT(EOS(STATIC_623), i93, i94, i93, i94) :|: i93 >= i94
f623_0_log_LT(EOS(STATIC_623), i93, i94, i93, i94) -> f630_0_log_Load(EOS(STATIC_630), i93, i94) :|: i93 >= i94
f630_0_log_Load(EOS(STATIC_630), i93, i94) -> f635_0_log_ConstantStackPush(EOS(STATIC_635), i93, i94, i94) :|: TRUE
f635_0_log_ConstantStackPush(EOS(STATIC_635), i93, i94, i94) -> f640_0_log_LE(EOS(STATIC_640), i93, i94, i94, 1) :|: TRUE
f640_0_log_LE(EOS(STATIC_640), i105, i104, i104, matching1) -> f647_0_log_LE(EOS(STATIC_647), i105, i104, i104, 1) :|: TRUE && matching1 = 1
f647_0_log_LE(EOS(STATIC_647), i105, i104, i104, matching1) -> f659_0_log_Inc(EOS(STATIC_659), i105, i104) :|: i104 > 1 && matching1 = 1
f659_0_log_Inc(EOS(STATIC_659), i105, i104) -> f660_0_log_Load(EOS(STATIC_660), i105, i104) :|: TRUE
f660_0_log_Load(EOS(STATIC_660), i105, i104) -> f661_0_log_Load(EOS(STATIC_661), i104, i105) :|: TRUE
f661_0_log_Load(EOS(STATIC_661), i104, i105) -> f662_0_log_IntArithmetic(EOS(STATIC_662), i104, i105, i104) :|: TRUE
f662_0_log_IntArithmetic(EOS(STATIC_662), i104, i105, i104) -> f665_0_log_Store(EOS(STATIC_665), i104, i107) :|: i107 = i105 / i104 && i105 > 1 && i104 > 1 && i107 < i105
f665_0_log_Store(EOS(STATIC_665), i104, i107) -> f667_0_log_JMP(EOS(STATIC_667), i107, i104) :|: TRUE
f667_0_log_JMP(EOS(STATIC_667), i107, i104) -> f684_0_log_Load(EOS(STATIC_684), i107, i104) :|: TRUE
f684_0_log_Load(EOS(STATIC_684), i107, i104) -> f615_0_log_Load(EOS(STATIC_615), i107, i104) :|: TRUE
f615_0_log_Load(EOS(STATIC_615), i93, i94) -> f616_0_log_Load(EOS(STATIC_616), i93, i94, i93) :|: TRUE
Combined rules. Obtained 2 IRulesP rules:
f616_0_log_Load(EOS(STATIC_616), i93:0, i94:0, i93:0) -> f616_0_log_Load'(EOS(STATIC_616), i93:0, i94:0, i93:0) :|: i94:0 <= i93:0 && i94:0 > 1 && i93:0 > 1 && i93:0 > div
f616_0_log_Load'(EOS(STATIC_616), i93:0, i94:0, i93:0) -> f616_0_log_Load(EOS(STATIC_616), div, i94:0, div) :|: i94:0 <= i93:0 && i94:0 > 1 && i93:0 > 1 && i93:0 > div && i94:0 > i93:0 - i94:0 * div && i93:0 - i94:0 * div + i94:0 > 0
Filtered constant ground arguments:
   f616_0_log_Load(x1, x2, x3, x4) -> f616_0_log_Load(x2, x3, x4)
   f616_0_log_Load'(x1, x2, x3, x4) -> f616_0_log_Load'(x2, x3, x4)
   EOS(x1) -> EOS
Filtered duplicate arguments:
   f616_0_log_Load(x1, x2, x3) -> f616_0_log_Load(x2, x3)
   f616_0_log_Load'(x1, x2, x3) -> f616_0_log_Load'(x2, x3)
Finished conversion. Obtained 2 rules.P rules:
f616_0_log_Load(i94:0, i93:0) -> f616_0_log_Load'(i94:0, i93:0) :|: i94:0 > 1 && i94:0 <= i93:0 && i93:0 > div && i93:0 > 1
f616_0_log_Load'(i94:0, i93:0) -> f616_0_log_Load(i94:0, div) :|: i94:0 > 1 && i94:0 <= i93:0 && i93:0 > 1 && i93:0 > div && i93:0 - i94:0 * div + i94:0 > 0 && i94:0 > i93:0 - i94:0 * div

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

(8)
Obligation:
Rules:
f616_0_log_Load(x, x1) -> f616_0_log_Load'(x, x1) :|: x > 1 && x <= x1 && x1 > x2 && x1 > 1
f616_0_log_Load'(x3, x4) -> f616_0_log_Load(x3, x5) :|: x3 > 1 && x3 <= x4 && x4 > 1 && x4 > x5 && x4 - x3 * x5 + x3 > 0 && x3 > x4 - x3 * x5

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

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

(10)
Obligation:
Rules:
f616_0_log_Load(x, x1) -> f616_0_log_Load'(x, x1) :|: x > 1 && x <= x1 && x1 > x2 && x1 > 1
f616_0_log_Load'(x3, x4) -> f616_0_log_Load(x3, x5) :|: x3 > 1 && x3 <= x4 && x4 > 1 && x4 > x5 && x4 - x3 * x5 + x3 > 0 && x3 > x4 - x3 * x5

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

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f616_0_log_Load(x, x1) -> f616_0_log_Load'(x, x1) :|: x > 1 && x <= x1 && x1 > x2 && x1 > 1
(2) f616_0_log_Load'(x3, x4) -> f616_0_log_Load(x3, x5) :|: x3 > 1 && x3 <= x4 && x4 > 1 && x4 > x5 && x4 - x3 * x5 + x3 > 0 && x3 > x4 - x3 * x5

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

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

(12)
Obligation:

Termination digraph:
Nodes:
(1) f616_0_log_Load(x, x1) -> f616_0_log_Load'(x, x1) :|: x > 1 && x <= x1 && x1 > x2 && x1 > 1
(2) f616_0_log_Load'(x3, x4) -> f616_0_log_Load(x3, x5) :|: x3 > 1 && x3 <= x4 && x4 > 1 && x4 > x5 && x4 - x3 * x5 + x3 > 0 && x3 > x4 - x3 * x5

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

This digraph is fully evaluated!

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

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

(14)
Obligation:
Rules:
f616_0_log_Load(x:0, x1:0) -> f616_0_log_Load(x:0, x5:0) :|: x:0 > x1:0 - x:0 * x5:0 && x2:0 < x1:0 && x1:0 - x:0 * x5:0 + x:0 > 0 && x5:0 < x1:0 && x1:0 > 1 && x:0 <= x1:0 && x:0 > 1

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

(15) FilterProof (EQUIVALENT)
Used the following sort dictionary for filtering: 
f616_0_log_Load(INTEGER, INTEGER)
Replaced non-predefined constructor symbols by 0.
----------------------------------------

(16)
Obligation:
Rules:
f616_0_log_Load(x:0, x1:0) -> f616_0_log_Load(x:0, x5:0) :|: x:0 > x1:0 - x:0 * x5:0 && x2:0 < x1:0 && x1:0 - x:0 * x5:0 + x:0 > 0 && x5:0 < x1:0 && x1:0 > 1 && x:0 <= x1:0 && x:0 > 1

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

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

(18)
Obligation:
Rules:
f616_0_log_Load(x:0:0, x1:0:0) -> f616_0_log_Load(x:0:0, x5:0:0) :|: x:0:0 <= x1:0:0 && x:0:0 > 1 && x1:0:0 > 1 && x5:0:0 < x1:0:0 && x1:0:0 - x:0:0 * x5:0:0 + x:0:0 > 0 && x2:0:0 < x1:0:0 && x:0:0 > x1:0:0 - x:0:0 * x5:0:0

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

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

The following rules are decreasing:
f616_0_log_Load(x:0:0, x1:0:0) -> f616_0_log_Load(x:0:0, x5:0:0) :|: x:0:0 <= x1:0:0 && x:0:0 > 1 && x1:0:0 > 1 && x5:0:0 < x1:0:0 && x1:0:0 - x:0:0 * x5:0:0 + x:0:0 > 0 && x2:0:0 < x1:0:0 && x:0:0 > x1:0:0 - x:0:0 * x5:0:0
The following rules are bounded:
f616_0_log_Load(x:0:0, x1:0:0) -> f616_0_log_Load(x:0:0, x5:0:0) :|: x:0:0 <= x1:0:0 && x:0:0 > 1 && x1:0:0 > 1 && x5:0:0 < x1:0:0 && x1:0:0 - x:0:0 * x5:0:0 + x:0:0 > 0 && x2:0:0 < x1:0:0 && x:0:0 > x1:0:0 - x:0:0 * x5:0:0

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

(20)
YES