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


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

(0)
Obligation:
need to prove termination of the following program:
public class LogRecursive {
  public static void main(String[] args) {
    Random.args = args;
    log(Random.random(), Random.random());
  }

  public static int log(int x, int y) {
    if (x >= y && y > 1) {
      return 1 + log(x/y, y);
    }
    return 0;
  }
}


public class Random {
  static String[] args;
  static int index = 0;

  public static int random() {
    if (args.length <= index) {
      return 0;
    }
    String string = args[index];
    index++;
    if (string == null) {
      return 0;
    }
    return string.length();
  }
}



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

(1) BareJBCToJBCProof (EQUIVALENT)
initialized classpath
----------------------------------------

(2)
Obligation:
need to prove termination of the following program:
public class LogRecursive {
  public static void main(String[] args) {
    Random.args = args;
    log(Random.random(), Random.random());
  }

  public static int log(int x, int y) {
    if (x >= y && y > 1) {
      return 1 + log(x/y, y);
    }
    return 0;
  }
}


public class Random {
  static String[] args;
  static int index = 0;

  public static int random() {
    if (args.length <= index) {
      return 0;
    }
    String string = args[index];
    index++;
    if (string == null) {
      return 0;
    }
    return string.length();
  }
}



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

(3) JBCToGraph (EQUIVALENT)
Constructed TerminationGraph.
----------------------------------------

(4)
Obligation:
Termination Graph based on JBC Program:
LogRecursive.main([Ljava/lang/String;)V: Graph of 189 nodes with 0 SCCs.



LogRecursive.log(II)I: Graph of 31 nodes with 0 SCCs.





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

(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: LogRecursive.log(II)I
SCC calls the following helper methods: LogRecursive.log(II)I
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 17 IRulesP rules:
f858_0_log_Load(EOS(STATIC_858), i121, i122, i121, i122, i121) -> f864_0_log_LT(EOS(STATIC_864), i121, i122, i121, i122, i121, i122) :|: TRUE
f864_0_log_LT(EOS(STATIC_864), i121, i122, i121, i122, i121, i122) -> f870_0_log_LT(EOS(STATIC_870), i121, i122, i121, i122, i121, i122) :|: i121 >= i122
f870_0_log_LT(EOS(STATIC_870), i121, i122, i121, i122, i121, i122) -> f873_0_log_Load(EOS(STATIC_873), i121, i122, i121, i122) :|: i121 >= i122
f873_0_log_Load(EOS(STATIC_873), i121, i122, i121, i122) -> f876_0_log_ConstantStackPush(EOS(STATIC_876), i121, i122, i121, i122, i122) :|: TRUE
f876_0_log_ConstantStackPush(EOS(STATIC_876), i121, i122, i121, i122, i122) -> f879_0_log_LE(EOS(STATIC_879), i121, i122, i121, i122, i122, 1) :|: TRUE
f879_0_log_LE(EOS(STATIC_879), i147, i146, i147, i146, i146, matching1) -> f910_0_log_LE(EOS(STATIC_910), i147, i146, i147, i146, i146, 1) :|: TRUE && matching1 = 1
f910_0_log_LE(EOS(STATIC_910), i147, i146, i147, i146, i146, matching1) -> f918_0_log_ConstantStackPush(EOS(STATIC_918), i147, i146, i147, i146) :|: i146 > 1 && matching1 = 1
f918_0_log_ConstantStackPush(EOS(STATIC_918), i147, i146, i147, i146) -> f921_0_log_Load(EOS(STATIC_921), i147, i146, i147, i146) :|: TRUE
f921_0_log_Load(EOS(STATIC_921), i147, i146, i147, i146) -> f924_0_log_Load(EOS(STATIC_924), i147, i146, i146, i147) :|: TRUE
f924_0_log_Load(EOS(STATIC_924), i147, i146, i146, i147) -> f958_0_log_IntArithmetic(EOS(STATIC_958), i147, i146, i146, i147, i146) :|: TRUE
f958_0_log_IntArithmetic(EOS(STATIC_958), i147, i146, i146, i147, i146) -> f983_0_log_Load(EOS(STATIC_983), i147, i146, i146, i173) :|: i173 = i147 / i146 && i147 > 1 && i146 > 1 && i173 < i147
f983_0_log_Load(EOS(STATIC_983), i147, i146, i146, i173) -> f984_0_log_InvokeMethod(EOS(STATIC_984), i147, i146, i173, i146) :|: TRUE
f984_0_log_InvokeMethod(EOS(STATIC_984), i147, i146, i173, i146) -> f985_0_log_Load(EOS(STATIC_985), i173, i146, i173, i146) :|: i147 > 1 && i146 > 1 && i147 >= i146
f984_0_log_InvokeMethod(EOS(STATIC_984), i147, i146, i173, i146) -> f985_1_log_Load(EOS(STATIC_985), i147, i146, i173, i146) :|: i147 > 1 && i146 > 1 && i147 >= i146
f985_0_log_Load(EOS(STATIC_985), i173, i146, i173, i146) -> f986_0_log_Load(EOS(STATIC_986), i173, i146, i173, i146) :|: TRUE
f986_0_log_Load(EOS(STATIC_986), i173, i146, i173, i146) -> f853_0_log_Load(EOS(STATIC_853), i173, i146, i173, i146) :|: TRUE
f853_0_log_Load(EOS(STATIC_853), i121, i122, i121, i122) -> f858_0_log_Load(EOS(STATIC_858), i121, i122, i121, i122, i121) :|: TRUE
Combined rules. Obtained 3 IRulesP rules:
f858_0_log_Load(EOS(STATIC_858), i121:0, i122:0, i121:0, i122:0, i121:0) -> f858_0_log_Load'(EOS(STATIC_858), i121:0, i122:0, i121:0, i122:0, i121:0) :|: i122:0 <= i121:0 && i122:0 > 1 && i121:0 > 1 && i121:0 > div
f858_0_log_Load'(EOS(STATIC_858), i121:0, i122:0, i121:0, i122:0, i121:0) -> f858_0_log_Load(EOS(STATIC_858), div, i122:0, div, i122:0, div) :|: i122:0 <= i121:0 && i122:0 > 1 && i121:0 > 1 && i121:0 > div && i122:0 > i121:0 - i122:0 * div && i121:0 - i122:0 * div + i122:0 > 0
Removed following non-SCC rules:
f858_0_log_Load'(EOS(STATIC_858), i121:0, i122:0, i121:0, i122:0, i121:0) -> f985_1_log_Load(EOS(STATIC_985), i121:0, i122:0, div, i122:0) :|: i122:0 <= i121:0 && i122:0 > 1 && i121:0 > 1 && i121:0 > div && i122:0 > i121:0 - i122:0 * div && i121:0 - i122:0 * div + i122:0 > 0
Filtered constant ground arguments:
   f858_0_log_Load(x1, x2, x3, x4, x5, x6) -> f858_0_log_Load(x2, x3, x4, x5, x6)
   f858_0_log_Load'(x1, x2, x3, x4, x5, x6) -> f858_0_log_Load'(x2, x3, x4, x5, x6)
   EOS(x1) -> EOS
Filtered duplicate arguments:
   f858_0_log_Load(x1, x2, x3, x4, x5) -> f858_0_log_Load(x4, x5)
   f858_0_log_Load'(x1, x2, x3, x4, x5) -> f858_0_log_Load'(x4, x5)
Finished conversion. Obtained 2 rules.P rules:
f858_0_log_Load(i122:0, i121:0) -> f858_0_log_Load'(i122:0, i121:0) :|: i122:0 > 1 && i122:0 <= i121:0 && i121:0 > div && i121:0 > 1
f858_0_log_Load'(i122:0, i121:0) -> f858_0_log_Load(i122:0, div) :|: i122:0 > 1 && i122:0 <= i121:0 && i121:0 > 1 && i121:0 > div && i121:0 - i122:0 * div + i122:0 > 0 && i122:0 > i121:0 - i122:0 * div

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

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

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

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