/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, 351 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, 30 ms]
(12) IRSwT
(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(14) IRSwT
(15) FilterProof [EQUIVALENT, 3 ms]
(16) IntTRS
(17) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(18) IntTRS
(19) PolynomialOrderProcessor [EQUIVALENT, 11 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:
f583_0_log_Load(EOS(STATIC_583), i92, i93, i92) -> f584_0_log_LT(EOS(STATIC_584), i92, i93, i92, i93) :|: TRUE
f584_0_log_LT(EOS(STATIC_584), i92, i93, i92, i93) -> f596_0_log_LT(EOS(STATIC_596), i92, i93, i92, i93) :|: i92 >= i93
f596_0_log_LT(EOS(STATIC_596), i92, i93, i92, i93) -> f600_0_log_Load(EOS(STATIC_600), i92, i93) :|: i92 >= i93
f600_0_log_Load(EOS(STATIC_600), i92, i93) -> f602_0_log_ConstantStackPush(EOS(STATIC_602), i92, i93, i93) :|: TRUE
f602_0_log_ConstantStackPush(EOS(STATIC_602), i92, i93, i93) -> f605_0_log_LE(EOS(STATIC_605), i92, i93, i93, 1) :|: TRUE
f605_0_log_LE(EOS(STATIC_605), i103, i102, i102, matching1) -> f613_0_log_LE(EOS(STATIC_613), i103, i102, i102, 1) :|: TRUE && matching1 = 1
f613_0_log_LE(EOS(STATIC_613), i103, i102, i102, matching1) -> f618_0_log_Inc(EOS(STATIC_618), i103, i102) :|: i102 > 1 && matching1 = 1
f618_0_log_Inc(EOS(STATIC_618), i103, i102) -> f621_0_log_Load(EOS(STATIC_621), i103, i102) :|: TRUE
f621_0_log_Load(EOS(STATIC_621), i103, i102) -> f623_0_log_Load(EOS(STATIC_623), i102, i103) :|: TRUE
f623_0_log_Load(EOS(STATIC_623), i102, i103) -> f625_0_log_IntArithmetic(EOS(STATIC_625), i102, i103, i102) :|: TRUE
f625_0_log_IntArithmetic(EOS(STATIC_625), i102, i103, i102) -> f628_0_log_Store(EOS(STATIC_628), i102, i106) :|: i106 = i103 / i102 && i103 > 1 && i102 > 1 && i106 < i103
f628_0_log_Store(EOS(STATIC_628), i102, i106) -> f631_0_log_JMP(EOS(STATIC_631), i106, i102) :|: TRUE
f631_0_log_JMP(EOS(STATIC_631), i106, i102) -> f652_0_log_Load(EOS(STATIC_652), i106, i102) :|: TRUE
f652_0_log_Load(EOS(STATIC_652), i106, i102) -> f582_0_log_Load(EOS(STATIC_582), i106, i102) :|: TRUE
f582_0_log_Load(EOS(STATIC_582), i92, i93) -> f583_0_log_Load(EOS(STATIC_583), i92, i93, i92) :|: TRUE
Combined rules. Obtained 2 IRulesP rules:
f583_0_log_Load(EOS(STATIC_583), i92:0, i93:0, i92:0) -> f583_0_log_Load'(EOS(STATIC_583), i92:0, i93:0, i92:0) :|: i93:0 <= i92:0 && i93:0 > 1 && i92:0 > 1 && i92:0 > div
f583_0_log_Load'(EOS(STATIC_583), i92:0, i93:0, i92:0) -> f583_0_log_Load(EOS(STATIC_583), div, i93:0, div) :|: i93:0 <= i92:0 && i93:0 > 1 && i92:0 > 1 && i92:0 > div && i93:0 > i92:0 - i93:0 * div && i92:0 - i93:0 * div + i93:0 > 0
Filtered constant ground arguments:
   f583_0_log_Load(x1, x2, x3, x4) -> f583_0_log_Load(x2, x3, x4)
   f583_0_log_Load'(x1, x2, x3, x4) -> f583_0_log_Load'(x2, x3, x4)
   EOS(x1) -> EOS
Filtered duplicate arguments:
   f583_0_log_Load(x1, x2, x3) -> f583_0_log_Load(x2, x3)
   f583_0_log_Load'(x1, x2, x3) -> f583_0_log_Load'(x2, x3)
Finished conversion. Obtained 2 rules.P rules:
f583_0_log_Load(i93:0, i92:0) -> f583_0_log_Load'(i93:0, i92:0) :|: i93:0 > 1 && i93:0 <= i92:0 && i92:0 > div && i92:0 > 1
f583_0_log_Load'(i93:0, i92:0) -> f583_0_log_Load(i93:0, div) :|: i93:0 > 1 && i93:0 <= i92:0 && i92:0 > 1 && i92:0 > div && i92:0 - i93:0 * div + i93:0 > 0 && i93:0 > i92:0 - i93:0 * div

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

(8)
Obligation:
Rules:
f583_0_log_Load(x, x1) -> f583_0_log_Load'(x, x1) :|: x > 1 && x <= x1 && x1 > x2 && x1 > 1
f583_0_log_Load'(x3, x4) -> f583_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:
f583_0_log_Load(x, x1) -> f583_0_log_Load'(x, x1) :|: x > 1 && x <= x1 && x1 > x2 && x1 > 1
f583_0_log_Load'(x3, x4) -> f583_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) f583_0_log_Load(x, x1) -> f583_0_log_Load'(x, x1) :|: x > 1 && x <= x1 && x1 > x2 && x1 > 1
(2) f583_0_log_Load'(x3, x4) -> f583_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) f583_0_log_Load(x, x1) -> f583_0_log_Load'(x, x1) :|: x > 1 && x <= x1 && x1 > x2 && x1 > 1
(2) f583_0_log_Load'(x3, x4) -> f583_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:
f583_0_log_Load(x:0, x1:0) -> f583_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: 
f583_0_log_Load(INTEGER, INTEGER)
Replaced non-predefined constructor symbols by 0.
----------------------------------------

(16)
Obligation:
Rules:
f583_0_log_Load(x:0, x1:0) -> f583_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:
f583_0_log_Load(x:0:0, x1:0:0) -> f583_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:
[f583_0_log_Load(x, x1)] = x1

The following rules are decreasing:
f583_0_log_Load(x:0:0, x1:0:0) -> f583_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:
f583_0_log_Load(x:0:0, x1:0:0) -> f583_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