/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: 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, 410 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) JBCTerminationSCC (7) SCCToIRSProof [SOUND, 12 ms] (8) IRSwT (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 100 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, 14 ms] (20) IntTRS (21) TerminationGraphProcessor [EQUIVALENT, 0 ms] (22) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: /** * Abstract class to provide some additional mathematical functions * which are not provided by java.lang.Math. * * @author fuhs */ public abstract class AProVEMath { /** * Returns base^exponent. * Works considerably faster than java.lang.Math.pow(double, double). * * @param base base of the power * @param exponent non-negative exponent of the power * @return base^exponent */ public static int power (int base, int exponent) { if (exponent == 0) { return 1; } else if (exponent == 1) { return base; } else if (base == 2) { return base << (exponent-1); } else { int result = 1; while (exponent > 0) { if (exponent % 2 == 1) { result *= base; } base *= base; exponent /= 2; } return result; } } public static void main(String[] args) { Random.args = args; int x = Random.random(); int y = Random.random(); power(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: /** * Abstract class to provide some additional mathematical functions * which are not provided by java.lang.Math. * * @author fuhs */ public abstract class AProVEMath { /** * Returns base^exponent. * Works considerably faster than java.lang.Math.pow(double, double). * * @param base base of the power * @param exponent non-negative exponent of the power * @return base^exponent */ public static int power (int base, int exponent) { if (exponent == 0) { return 1; } else if (exponent == 1) { return base; } else if (base == 2) { return base << (exponent-1); } else { int result = 1; while (exponent > 0) { if (exponent % 2 == 1) { result *= base; } base *= base; exponent /= 2; } return result; } } public static void main(String[] args) { Random.args = args; int x = Random.random(); int y = Random.random(); power(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: AProVEMath.main([Ljava/lang/String;)V: Graph of 237 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: AProVEMath.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 26 IRulesP rules: f1391_0_power_LE(EOS(STATIC_1391), i310, i310) -> f1393_0_power_Load(EOS(STATIC_1393), i310) :|: i310 > 0 f1393_0_power_Load(EOS(STATIC_1393), i310) -> f1395_0_power_ConstantStackPush(EOS(STATIC_1395), i310, i310) :|: TRUE f1395_0_power_ConstantStackPush(EOS(STATIC_1395), i310, i310) -> f1397_0_power_IntArithmetic(EOS(STATIC_1397), i310, i310, 2) :|: TRUE f1397_0_power_IntArithmetic(EOS(STATIC_1397), i310, i310, matching1) -> f1399_0_power_ConstantStackPush(EOS(STATIC_1399), i310, i310 % 2) :|: TRUE && matching1 = 2 f1399_0_power_ConstantStackPush(EOS(STATIC_1399), i310, i311) -> f1400_0_power_NE(EOS(STATIC_1400), i310, i311, 1) :|: TRUE f1400_0_power_NE(EOS(STATIC_1400), i310, matching1, matching2) -> f1401_0_power_NE(EOS(STATIC_1401), i310, 0, 1) :|: i311 = 0 && matching1 = 0 && matching2 = 1 f1400_0_power_NE(EOS(STATIC_1400), i310, matching1, matching2) -> f1402_0_power_NE(EOS(STATIC_1402), i310, 1, 1) :|: i311 = 1 && matching1 = 1 && matching2 = 1 f1401_0_power_NE(EOS(STATIC_1401), i310, matching1, matching2) -> f1403_0_power_Load(EOS(STATIC_1403), i310) :|: TRUE && matching1 = 0 && matching2 = 1 f1403_0_power_Load(EOS(STATIC_1403), i310) -> f1405_0_power_Load(EOS(STATIC_1405), i310) :|: TRUE f1405_0_power_Load(EOS(STATIC_1405), i310) -> f1407_0_power_IntArithmetic(EOS(STATIC_1407), i310) :|: TRUE f1407_0_power_IntArithmetic(EOS(STATIC_1407), i310) -> f1409_0_power_Store(EOS(STATIC_1409), i310) :|: TRUE f1409_0_power_Store(EOS(STATIC_1409), i310) -> f1411_0_power_Load(EOS(STATIC_1411), i310) :|: TRUE f1411_0_power_Load(EOS(STATIC_1411), i310) -> f1413_0_power_ConstantStackPush(EOS(STATIC_1413), i310) :|: TRUE f1413_0_power_ConstantStackPush(EOS(STATIC_1413), i310) -> f1414_0_power_IntArithmetic(EOS(STATIC_1414), i310, 2) :|: TRUE f1414_0_power_IntArithmetic(EOS(STATIC_1414), i310, matching1) -> f1415_0_power_Store(EOS(STATIC_1415), i315) :|: i315 = i310 / 2 && i310 >= 1 && i315 < i310 && matching1 = 2 f1415_0_power_Store(EOS(STATIC_1415), i315) -> f1416_0_power_JMP(EOS(STATIC_1416), i315) :|: TRUE f1416_0_power_JMP(EOS(STATIC_1416), i315) -> f1421_0_power_Load(EOS(STATIC_1421), i315) :|: TRUE f1421_0_power_Load(EOS(STATIC_1421), i315) -> f1388_0_power_Load(EOS(STATIC_1388), i315) :|: TRUE f1388_0_power_Load(EOS(STATIC_1388), i288) -> f1389_0_power_LE(EOS(STATIC_1389), i288, i288) :|: TRUE f1389_0_power_LE(EOS(STATIC_1389), i310, i310) -> f1391_0_power_LE(EOS(STATIC_1391), i310, i310) :|: TRUE f1402_0_power_NE(EOS(STATIC_1402), i310, matching1, matching2) -> f1404_0_power_Load(EOS(STATIC_1404), i310) :|: TRUE && matching1 = 1 && matching2 = 1 f1404_0_power_Load(EOS(STATIC_1404), i310) -> f1406_0_power_Load(EOS(STATIC_1406), i310) :|: TRUE f1406_0_power_Load(EOS(STATIC_1406), i310) -> f1408_0_power_IntArithmetic(EOS(STATIC_1408), i310) :|: TRUE f1408_0_power_IntArithmetic(EOS(STATIC_1408), i310) -> f1410_0_power_Store(EOS(STATIC_1410), i310) :|: TRUE f1410_0_power_Store(EOS(STATIC_1410), i310) -> f1412_0_power_Load(EOS(STATIC_1412), i310) :|: TRUE f1412_0_power_Load(EOS(STATIC_1412), i310) -> f1403_0_power_Load(EOS(STATIC_1403), i310) :|: TRUE Combined rules. Obtained 4 IRulesP rules: f1391_0_power_LE(EOS(STATIC_1391), i310:0, i310:0) -> f1391_0_power_LE'(EOS(STATIC_1391), i310:0, i310:0) :|: i310:0 > 0 && i310:0 - 2 * div = 0 && i310:0 > div1 f1391_0_power_LE'(EOS(STATIC_1391), i310:0, i310:0) -> f1391_0_power_LE(EOS(STATIC_1391), div1, div1) :|: i310:0 > 0 && i310:0 - 2 * div = 0 && i310:0 > div1 && i310:0 - 2 * div > -2 && i310:0 - 2 * div < 2 && i310:0 - 2 * div1 < 2 && i310:0 - 2 * div1 > -2 f1391_0_power_LE(EOS(STATIC_1391), i310:0, i310:0) -> f1391_0_power_LE'(EOS(STATIC_1391), i310:0, i310:0) :|: i310:0 > 0 && i310:0 - 2 * div = 1 && i310:0 > div1 f1391_0_power_LE'(EOS(STATIC_1391), i310:0, i310:0) -> f1391_0_power_LE(EOS(STATIC_1391), div1, div1) :|: i310:0 > 0 && i310:0 > div1 && i310:0 - 2 * div = 1 && i310:0 - 2 * div > -2 && i310:0 - 2 * div < 2 && i310:0 - 2 * div1 < 2 && i310:0 - 2 * div1 > -2 Filtered constant ground arguments: f1391_0_power_LE(x1, x2, x3) -> f1391_0_power_LE(x2, x3) f1391_0_power_LE'(x1, x2, x3) -> f1391_0_power_LE'(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f1391_0_power_LE(x1, x2) -> f1391_0_power_LE(x2) f1391_0_power_LE'(x1, x2) -> f1391_0_power_LE'(x2) Finished conversion. Obtained 4 rules.P rules: f1391_0_power_LE(i310:0) -> f1391_0_power_LE'(i310:0) :|: i310:0 - 2 * div = 0 && i310:0 > div1 && i310:0 > 0 f1391_0_power_LE'(i310:0) -> f1391_0_power_LE(div1) :|: i310:0 - 2 * div = 0 && i310:0 > 0 && i310:0 > div1 && i310:0 - 2 * div > -2 && i310:0 - 2 * div < 2 && i310:0 - 2 * div1 > -2 && i310:0 - 2 * div1 < 2 f1391_0_power_LE(i310:0) -> f1391_0_power_LE'(i310:0) :|: i310:0 - 2 * div = 1 && i310:0 > div1 && i310:0 > 0 f1391_0_power_LE'(i310:0) -> f1391_0_power_LE(div1) :|: i310:0 > div1 && i310:0 > 0 && i310:0 - 2 * div = 1 && i310:0 - 2 * div > -2 && i310:0 - 2 * div < 2 && i310:0 - 2 * div1 > -2 && i310:0 - 2 * div1 < 2 ---------------------------------------- (8) Obligation: Rules: f1391_0_power_LE(x) -> f1391_0_power_LE'(x) :|: x - 2 * x1 = 0 && x > x2 && x > 0 f1391_0_power_LE'(x3) -> f1391_0_power_LE(x4) :|: x3 - 2 * x5 = 0 && x3 > 0 && x3 > x4 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 f1391_0_power_LE(x6) -> f1391_0_power_LE'(x6) :|: x6 - 2 * x7 = 1 && x6 > x8 && x6 > 0 f1391_0_power_LE'(x9) -> f1391_0_power_LE(x10) :|: x9 > x10 && x9 > 0 && x9 - 2 * x11 = 1 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 ---------------------------------------- (9) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (10) Obligation: Rules: f1391_0_power_LE(x) -> f1391_0_power_LE'(x) :|: x - 2 * x1 = 0 && x > x2 && x > 0 f1391_0_power_LE'(x3) -> f1391_0_power_LE(x4) :|: x3 - 2 * x5 = 0 && x3 > 0 && x3 > x4 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 f1391_0_power_LE(x6) -> f1391_0_power_LE'(x6) :|: x6 - 2 * x7 = 1 && x6 > x8 && x6 > 0 f1391_0_power_LE'(x9) -> f1391_0_power_LE(x10) :|: x9 > x10 && x9 > 0 && x9 - 2 * x11 = 1 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1391_0_power_LE(x) -> f1391_0_power_LE'(x) :|: x - 2 * x1 = 0 && x > x2 && x > 0 (2) f1391_0_power_LE'(x3) -> f1391_0_power_LE(x4) :|: x3 - 2 * x5 = 0 && x3 > 0 && x3 > x4 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 (3) f1391_0_power_LE(x6) -> f1391_0_power_LE'(x6) :|: x6 - 2 * x7 = 1 && x6 > x8 && x6 > 0 (4) f1391_0_power_LE'(x9) -> f1391_0_power_LE(x10) :|: x9 > x10 && x9 > 0 && x9 - 2 * x11 = 1 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 Arcs: (1) -> (2) (2) -> (1), (3) (3) -> (4) (4) -> (1), (3) This digraph is fully evaluated! ---------------------------------------- (12) Obligation: Termination digraph: Nodes: (1) f1391_0_power_LE(x) -> f1391_0_power_LE'(x) :|: x - 2 * x1 = 0 && x > x2 && x > 0 (2) f1391_0_power_LE'(x9) -> f1391_0_power_LE(x10) :|: x9 > x10 && x9 > 0 && x9 - 2 * x11 = 1 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 (3) f1391_0_power_LE(x6) -> f1391_0_power_LE'(x6) :|: x6 - 2 * x7 = 1 && x6 > x8 && x6 > 0 (4) f1391_0_power_LE'(x3) -> f1391_0_power_LE(x4) :|: x3 - 2 * x5 = 0 && x3 > 0 && x3 > x4 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 Arcs: (1) -> (4) (2) -> (1), (3) (3) -> (2) (4) -> (1), (3) This digraph is fully evaluated! ---------------------------------------- (13) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (14) Obligation: Rules: f1391_0_power_LE(x:0) -> f1391_0_power_LE'(x:0) :|: x:0 - 2 * x1:0 = 0 && x:0 > x2:0 && x:0 > 0 f1391_0_power_LE(x6:0) -> f1391_0_power_LE'(x6:0) :|: x6:0 - 2 * x7:0 = 1 && x8:0 < x6:0 && x6:0 > 0 f1391_0_power_LE'(x9:0) -> f1391_0_power_LE(x10:0) :|: x9:0 - 2 * x10:0 > -2 && x9:0 - 2 * x10:0 < 2 && x9:0 - 2 * x11:0 < 2 && x9:0 - 2 * x11:0 > -2 && x9:0 - 2 * x11:0 = 1 && x9:0 > 0 && x9:0 > x10:0 f1391_0_power_LE'(x3:0) -> f1391_0_power_LE(x4:0) :|: x3:0 - 2 * x4:0 > -2 && x3:0 - 2 * x4:0 < 2 && x3:0 - 2 * x5:0 < 2 && x3:0 - 2 * x5:0 > -2 && x4:0 < x3:0 && x3:0 > 0 && x3:0 - 2 * x5:0 = 0 ---------------------------------------- (15) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f1391_0_power_LE(INTEGER) f1391_0_power_LE'(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f1391_0_power_LE(x:0) -> f1391_0_power_LE'(x:0) :|: x:0 - 2 * x1:0 = 0 && x:0 > x2:0 && x:0 > 0 f1391_0_power_LE(x6:0) -> f1391_0_power_LE'(x6:0) :|: x6:0 - 2 * x7:0 = 1 && x8:0 < x6:0 && x6:0 > 0 f1391_0_power_LE'(x9:0) -> f1391_0_power_LE(x10:0) :|: x9:0 - 2 * x10:0 > -2 && x9:0 - 2 * x10:0 < 2 && x9:0 - 2 * x11:0 < 2 && x9:0 - 2 * x11:0 > -2 && x9:0 - 2 * x11:0 = 1 && x9:0 > 0 && x9:0 > x10:0 f1391_0_power_LE'(x3:0) -> f1391_0_power_LE(x4:0) :|: x3:0 - 2 * x4:0 > -2 && x3:0 - 2 * x4:0 < 2 && x3:0 - 2 * x5:0 < 2 && x3:0 - 2 * x5:0 > -2 && x4:0 < x3:0 && x3:0 > 0 && x3:0 - 2 * x5:0 = 0 ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f1391_0_power_LE(x6:0:0) -> f1391_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x7:0:0 = 1 && x8:0:0 < x6:0:0 && x6:0:0 > 0 f1391_0_power_LE(x:0:0) -> f1391_0_power_LE'(x:0:0) :|: x:0:0 - 2 * x1:0:0 = 0 && x:0:0 > x2:0:0 && x:0:0 > 0 f1391_0_power_LE'(x9:0:0) -> f1391_0_power_LE(x10:0:0) :|: x9:0:0 > 0 && x9:0:0 > x10:0:0 && x9:0:0 - 2 * x11:0:0 = 1 && x9:0:0 - 2 * x11:0:0 > -2 && x9:0:0 - 2 * x11:0:0 < 2 && x9:0:0 - 2 * x10:0:0 < 2 && x9:0:0 - 2 * x10:0:0 > -2 f1391_0_power_LE'(x3:0:0) -> f1391_0_power_LE(x4:0:0) :|: x3:0:0 > 0 && x3:0:0 - 2 * x5:0:0 = 0 && x4:0:0 < x3:0:0 && x3:0:0 - 2 * x5:0:0 > -2 && x3:0:0 - 2 * x5:0:0 < 2 && x3:0:0 - 2 * x4:0:0 < 2 && x3:0:0 - 2 * x4:0:0 > -2 ---------------------------------------- (19) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1391_0_power_LE(x)] = -1 + x [f1391_0_power_LE'(x1)] = -1 + x1 The following rules are decreasing: f1391_0_power_LE'(x9:0:0) -> f1391_0_power_LE(x10:0:0) :|: x9:0:0 > 0 && x9:0:0 > x10:0:0 && x9:0:0 - 2 * x11:0:0 = 1 && x9:0:0 - 2 * x11:0:0 > -2 && x9:0:0 - 2 * x11:0:0 < 2 && x9:0:0 - 2 * x10:0:0 < 2 && x9:0:0 - 2 * x10:0:0 > -2 f1391_0_power_LE'(x3:0:0) -> f1391_0_power_LE(x4:0:0) :|: x3:0:0 > 0 && x3:0:0 - 2 * x5:0:0 = 0 && x4:0:0 < x3:0:0 && x3:0:0 - 2 * x5:0:0 > -2 && x3:0:0 - 2 * x5:0:0 < 2 && x3:0:0 - 2 * x4:0:0 < 2 && x3:0:0 - 2 * x4:0:0 > -2 The following rules are bounded: f1391_0_power_LE(x6:0:0) -> f1391_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x7:0:0 = 1 && x8:0:0 < x6:0:0 && x6:0:0 > 0 f1391_0_power_LE(x:0:0) -> f1391_0_power_LE'(x:0:0) :|: x:0:0 - 2 * x1:0:0 = 0 && x:0:0 > x2:0:0 && x:0:0 > 0 f1391_0_power_LE'(x9:0:0) -> f1391_0_power_LE(x10:0:0) :|: x9:0:0 > 0 && x9:0:0 > x10:0:0 && x9:0:0 - 2 * x11:0:0 = 1 && x9:0:0 - 2 * x11:0:0 > -2 && x9:0:0 - 2 * x11:0:0 < 2 && x9:0:0 - 2 * x10:0:0 < 2 && x9:0:0 - 2 * x10:0:0 > -2 f1391_0_power_LE'(x3:0:0) -> f1391_0_power_LE(x4:0:0) :|: x3:0:0 > 0 && x3:0:0 - 2 * x5:0:0 = 0 && x4:0:0 < x3:0:0 && x3:0:0 - 2 * x5:0:0 > -2 && x3:0:0 - 2 * x5:0:0 < 2 && x3:0:0 - 2 * x4:0:0 < 2 && x3:0:0 - 2 * x4:0:0 > -2 ---------------------------------------- (20) Obligation: Rules: f1391_0_power_LE(x6:0:0) -> f1391_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x7:0:0 = 1 && x8:0:0 < x6:0:0 && x6:0:0 > 0 f1391_0_power_LE(x:0:0) -> f1391_0_power_LE'(x:0:0) :|: x:0:0 - 2 * x1:0:0 = 0 && x:0:0 > x2:0:0 && x:0:0 > 0 ---------------------------------------- (21) TerminationGraphProcessor (EQUIVALENT) Constructed the termination graph and obtained no non-trivial SCC(s). ---------------------------------------- (22) YES