/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, 376 ms]
(4) JBCTerminationGraph
(5) TerminationGraphToSCCProof [SOUND, 0 ms]
(6) JBCTerminationSCC
(7) SCCToIRSProof [SOUND, 102 ms]
(8) IRSwT
(9) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
(10) IRSwT
(11) IRSwTTerminationDigraphProof [EQUIVALENT, 15 ms]
(12) IRSwT
(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(14) IRSwT
(15) TempFilterProof [SOUND, 14 ms]
(16) IntTRS
(17) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
(18) YES


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

(0)
Obligation:
need to prove termination of the following program:
package TwoWay;

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

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


package TwoWay;

public class TwoWay {
	public static void main(String[] args) {
		Random.args = args;
		twoWay(true, Random.random());
	}

	public static int twoWay(boolean terminate, int n) {
		if (n < 0) {
			return 1;
		} else {
			int m = n;
			if (terminate) {
				m--;
			} else {
				m++;
			}
			return m*twoWay(terminate, m);
		}
	}
}



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

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

(2)
Obligation:
need to prove termination of the following program:
package TwoWay;

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

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


package TwoWay;

public class TwoWay {
	public static void main(String[] args) {
		Random.args = args;
		twoWay(true, Random.random());
	}

	public static int twoWay(boolean terminate, int n) {
		if (n < 0) {
			return 1;
		} else {
			int m = n;
			if (terminate) {
				m--;
			} else {
				m++;
			}
			return m*twoWay(terminate, m);
		}
	}
}



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

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

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



TwoWay.TwoWay.twoWay(ZI)I: Graph of 29 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: TwoWay.TwoWay.twoWay(ZI)I
SCC calls the following helper methods: TwoWay.TwoWay.twoWay(ZI)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 16 IRulesP rules:
f302_0_twoWay_GE(EOS(STATIC_302), matching1, i38, matching2, i38, i38) -> f306_0_twoWay_GE(EOS(STATIC_306), 1, i38, 1, i38, i38) :|: TRUE && matching1 = 1 && matching2 = 1
f306_0_twoWay_GE(EOS(STATIC_306), matching1, i38, matching2, i38, i38) -> f311_0_twoWay_Load(EOS(STATIC_311), 1, i38, 1, i38) :|: i38 >= 0 && matching1 = 1 && matching2 = 1
f311_0_twoWay_Load(EOS(STATIC_311), matching1, i38, matching2, i38) -> f316_0_twoWay_Store(EOS(STATIC_316), 1, i38, 1, i38) :|: TRUE && matching1 = 1 && matching2 = 1
f316_0_twoWay_Store(EOS(STATIC_316), matching1, i38, matching2, i38) -> f320_0_twoWay_Load(EOS(STATIC_320), 1, i38, 1, i38) :|: TRUE && matching1 = 1 && matching2 = 1
f320_0_twoWay_Load(EOS(STATIC_320), matching1, i38, matching2, i38) -> f369_0_twoWay_EQ(EOS(STATIC_369), 1, i38, 1, i38, 1) :|: TRUE && matching1 = 1 && matching2 = 1
f369_0_twoWay_EQ(EOS(STATIC_369), matching1, i38, matching2, i38, matching3) -> f374_0_twoWay_Inc(EOS(STATIC_374), 1, i38, 1, i38) :|: 1 > 0 && matching1 = 1 && matching2 = 1 && matching3 = 1
f374_0_twoWay_Inc(EOS(STATIC_374), matching1, i38, matching2, i38) -> f392_0_twoWay_JMP(EOS(STATIC_392), 1, i38, 1, i38 + -1) :|: TRUE && matching1 = 1 && matching2 = 1
f392_0_twoWay_JMP(EOS(STATIC_392), matching1, i38, matching2, i60) -> f395_0_twoWay_Load(EOS(STATIC_395), 1, i38, 1, i60) :|: TRUE && matching1 = 1 && matching2 = 1
f395_0_twoWay_Load(EOS(STATIC_395), matching1, i38, matching2, i60) -> f397_0_twoWay_Load(EOS(STATIC_397), 1, i38, 1, i60, i60) :|: TRUE && matching1 = 1 && matching2 = 1
f397_0_twoWay_Load(EOS(STATIC_397), matching1, i38, matching2, i60, i60) -> f398_0_twoWay_Load(EOS(STATIC_398), 1, i38, i60, i60, 1) :|: TRUE && matching1 = 1 && matching2 = 1
f398_0_twoWay_Load(EOS(STATIC_398), matching1, i38, i60, i60, matching2) -> f399_0_twoWay_InvokeMethod(EOS(STATIC_399), 1, i38, i60, 1, i60) :|: TRUE && matching1 = 1 && matching2 = 1
f399_0_twoWay_InvokeMethod(EOS(STATIC_399), matching1, i38, i60, matching2, i60) -> f400_0_twoWay_Load(EOS(STATIC_400), 1, i60, 1, i60) :|: i10 >= 1 && i60 < i38 && matching1 = 1 && matching2 = 1
f399_0_twoWay_InvokeMethod(EOS(STATIC_399), matching1, i38, i60, matching2, i60) -> f400_1_twoWay_Load(EOS(STATIC_400), 1, i38, i60, 1, i60) :|: i10 >= 1 && i60 < i38 && matching1 = 1 && matching2 = 1
f400_0_twoWay_Load(EOS(STATIC_400), matching1, i60, matching2, i60) -> f401_0_twoWay_Load(EOS(STATIC_401), 1, i60, 1, i60) :|: TRUE && matching1 = 1 && matching2 = 1
f401_0_twoWay_Load(EOS(STATIC_401), matching1, i60, matching2, i60) -> f298_0_twoWay_Load(EOS(STATIC_298), 1, i60, 1, i60) :|: TRUE && matching1 = 1 && matching2 = 1
f298_0_twoWay_Load(EOS(STATIC_298), matching1, i35, matching2, i35) -> f302_0_twoWay_GE(EOS(STATIC_302), 1, i35, 1, i35, i35) :|: TRUE && matching1 = 1 && matching2 = 1
Combined rules. Obtained 2 IRulesP rules:
f302_0_twoWay_GE(EOS(STATIC_302), 1, i38:0, 1, i38:0, i38:0) -> f302_0_twoWay_GE(EOS(STATIC_302), 1, i38:0 - 1, 1, i38:0 - 1, i38:0 - 1) :|: i38:0 > -1 && i10:0 > 0 && i38:0 - 1 < i38:0
Removed following non-SCC rules:
f302_0_twoWay_GE(EOS(STATIC_302), 1, i38:0, 1, i38:0, i38:0) -> f400_1_twoWay_Load(EOS(STATIC_400), 1, i38:0, i38:0 - 1, 1, i38:0 - 1) :|: i38:0 > -1 && i10:0 > 0 && i38:0 - 1 < i38:0
Filtered constant ground arguments:
   f302_0_twoWay_GE(x1, x2, x3, x4, x5, x6) -> f302_0_twoWay_GE(x3, x5, x6)
   EOS(x1) -> EOS
Filtered duplicate arguments:
   f302_0_twoWay_GE(x1, x2, x3) -> f302_0_twoWay_GE(x3)
Finished conversion. Obtained 1 rules.P rules:
f302_0_twoWay_GE(i38:0) -> f302_0_twoWay_GE(i38:0 - 1) :|: i10:0 > 0 && i38:0 - 1 < i38:0 && i38:0 > -1

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

(8)
Obligation:
Rules:
f302_0_twoWay_GE(i38:0) -> f302_0_twoWay_GE(i38:0 - 1) :|: i10:0 > 0 && i38:0 - 1 < i38:0 && i38:0 > -1

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

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

(10)
Obligation:
Rules:
f302_0_twoWay_GE(i38:0) -> f302_0_twoWay_GE(arith) :|: i10:0 > 0 && i38:0 - 1 < i38:0 && i38:0 > -1 && arith = i38:0 - 1

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

(11) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f302_0_twoWay_GE(i38:0) -> f302_0_twoWay_GE(arith) :|: i10:0 > 0 && i38:0 - 1 < i38:0 && i38:0 > -1 && arith = i38:0 - 1

Arcs:
(1) -> (1)

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

(12)
Obligation:

Termination digraph:
Nodes:
(1) f302_0_twoWay_GE(i38:0) -> f302_0_twoWay_GE(arith) :|: i10:0 > 0 && i38:0 - 1 < i38:0 && i38:0 > -1 && arith = i38:0 - 1

Arcs:
(1) -> (1)

This digraph is fully evaluated!

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

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

(14)
Obligation:
Rules:
f302_0_twoWay_GE(i38:0:0) -> f302_0_twoWay_GE(i38:0:0 - 1) :|: i10:0:0 > 0 && i38:0:0 - 1 < i38:0:0 && i38:0:0 > -1

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

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

(16)
Obligation:
Rules:
f302_0_twoWay_GE(i38:0:0) -> f302_0_twoWay_GE(c) :|: c = i38:0:0 - 1 && (i10:0:0 > 0 && i38:0:0 - 1 < i38:0:0 && i38:0:0 > -1)

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

(17) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f302_0_twoWay_GE(x)] = x

The following rules are decreasing:
f302_0_twoWay_GE(i38:0:0) -> f302_0_twoWay_GE(c) :|: c = i38:0:0 - 1 && (i10:0:0 > 0 && i38:0:0 - 1 < i38:0:0 && i38:0:0 > -1)
The following rules are bounded:
f302_0_twoWay_GE(i38:0:0) -> f302_0_twoWay_GE(c) :|: c = i38:0:0 - 1 && (i10:0:0 > 0 && i38:0:0 - 1 < i38:0:0 && i38:0:0 > -1)

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

(18)
YES