/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, 442 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) JBCTerminationSCC (7) SCCToIRSProof [SOUND, 82 ms] (8) IRSwT (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 128 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) 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 240 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: f1396_0_power_LE(EOS(STATIC_1396), i319, i319) -> f1398_0_power_Load(EOS(STATIC_1398), i319) :|: i319 > 0 f1398_0_power_Load(EOS(STATIC_1398), i319) -> f1400_0_power_ConstantStackPush(EOS(STATIC_1400), i319, i319) :|: TRUE f1400_0_power_ConstantStackPush(EOS(STATIC_1400), i319, i319) -> f1414_0_power_IntArithmetic(EOS(STATIC_1414), i319, i319, 2) :|: TRUE f1414_0_power_IntArithmetic(EOS(STATIC_1414), i319, i319, matching1) -> f1421_0_power_ConstantStackPush(EOS(STATIC_1421), i319, i319 % 2) :|: TRUE && matching1 = 2 f1421_0_power_ConstantStackPush(EOS(STATIC_1421), i319, i325) -> f1422_0_power_NE(EOS(STATIC_1422), i319, i325, 1) :|: TRUE f1422_0_power_NE(EOS(STATIC_1422), i319, matching1, matching2) -> f1423_0_power_NE(EOS(STATIC_1423), i319, 0, 1) :|: i325 = 0 && matching1 = 0 && matching2 = 1 f1422_0_power_NE(EOS(STATIC_1422), i319, matching1, matching2) -> f1424_0_power_NE(EOS(STATIC_1424), i319, 1, 1) :|: i325 = 1 && matching1 = 1 && matching2 = 1 f1423_0_power_NE(EOS(STATIC_1423), i319, matching1, matching2) -> f1427_0_power_Load(EOS(STATIC_1427), i319) :|: TRUE && matching1 = 0 && matching2 = 1 f1427_0_power_Load(EOS(STATIC_1427), i319) -> f1432_0_power_Load(EOS(STATIC_1432), i319) :|: TRUE f1432_0_power_Load(EOS(STATIC_1432), i319) -> f1435_0_power_IntArithmetic(EOS(STATIC_1435), i319) :|: TRUE f1435_0_power_IntArithmetic(EOS(STATIC_1435), i319) -> f1437_0_power_Store(EOS(STATIC_1437), i319) :|: TRUE f1437_0_power_Store(EOS(STATIC_1437), i319) -> f1439_0_power_Load(EOS(STATIC_1439), i319) :|: TRUE f1439_0_power_Load(EOS(STATIC_1439), i319) -> f1447_0_power_ConstantStackPush(EOS(STATIC_1447), i319) :|: TRUE f1447_0_power_ConstantStackPush(EOS(STATIC_1447), i319) -> f1450_0_power_IntArithmetic(EOS(STATIC_1450), i319, 2) :|: TRUE f1450_0_power_IntArithmetic(EOS(STATIC_1450), i319, matching1) -> f1452_0_power_Store(EOS(STATIC_1452), i329) :|: i329 = i319 / 2 && i319 >= 1 && i329 < i319 && matching1 = 2 f1452_0_power_Store(EOS(STATIC_1452), i329) -> f1454_0_power_JMP(EOS(STATIC_1454), i329) :|: TRUE f1454_0_power_JMP(EOS(STATIC_1454), i329) -> f1459_0_power_Load(EOS(STATIC_1459), i329) :|: TRUE f1459_0_power_Load(EOS(STATIC_1459), i329) -> f1383_0_power_Load(EOS(STATIC_1383), i329) :|: TRUE f1383_0_power_Load(EOS(STATIC_1383), i291) -> f1392_0_power_LE(EOS(STATIC_1392), i291, i291) :|: TRUE f1392_0_power_LE(EOS(STATIC_1392), i319, i319) -> f1396_0_power_LE(EOS(STATIC_1396), i319, i319) :|: TRUE f1424_0_power_NE(EOS(STATIC_1424), i319, matching1, matching2) -> f1430_0_power_Load(EOS(STATIC_1430), i319) :|: TRUE && matching1 = 1 && matching2 = 1 f1430_0_power_Load(EOS(STATIC_1430), i319) -> f1433_0_power_Load(EOS(STATIC_1433), i319) :|: TRUE f1433_0_power_Load(EOS(STATIC_1433), i319) -> f1436_0_power_IntArithmetic(EOS(STATIC_1436), i319) :|: TRUE f1436_0_power_IntArithmetic(EOS(STATIC_1436), i319) -> f1438_0_power_Store(EOS(STATIC_1438), i319) :|: TRUE f1438_0_power_Store(EOS(STATIC_1438), i319) -> f1445_0_power_Load(EOS(STATIC_1445), i319) :|: TRUE f1445_0_power_Load(EOS(STATIC_1445), i319) -> f1427_0_power_Load(EOS(STATIC_1427), i319) :|: TRUE Combined rules. Obtained 4 IRulesP rules: f1396_0_power_LE(EOS(STATIC_1396), i319:0, i319:0) -> f1396_0_power_LE'(EOS(STATIC_1396), i319:0, i319:0) :|: i319:0 > 0 && i319:0 - 2 * div = 1 && i319:0 > div1 f1396_0_power_LE'(EOS(STATIC_1396), i319:0, i319:0) -> f1396_0_power_LE(EOS(STATIC_1396), div1, div1) :|: i319:0 > 0 && i319:0 > div1 && i319:0 - 2 * div = 1 && i319:0 - 2 * div > -2 && i319:0 - 2 * div < 2 && i319:0 - 2 * div1 < 2 && i319:0 - 2 * div1 > -2 f1396_0_power_LE(EOS(STATIC_1396), i319:0, i319:0) -> f1396_0_power_LE'(EOS(STATIC_1396), i319:0, i319:0) :|: i319:0 > 0 && i319:0 - 2 * div = 0 && i319:0 > div1 f1396_0_power_LE'(EOS(STATIC_1396), i319:0, i319:0) -> f1396_0_power_LE(EOS(STATIC_1396), div1, div1) :|: i319:0 > 0 && i319:0 - 2 * div = 0 && i319:0 > div1 && i319:0 - 2 * div > -2 && i319:0 - 2 * div < 2 && i319:0 - 2 * div1 < 2 && i319:0 - 2 * div1 > -2 Filtered constant ground arguments: f1396_0_power_LE(x1, x2, x3) -> f1396_0_power_LE(x2, x3) f1396_0_power_LE'(x1, x2, x3) -> f1396_0_power_LE'(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f1396_0_power_LE(x1, x2) -> f1396_0_power_LE(x2) f1396_0_power_LE'(x1, x2) -> f1396_0_power_LE'(x2) Finished conversion. Obtained 4 rules.P rules: f1396_0_power_LE(i319:0) -> f1396_0_power_LE'(i319:0) :|: i319:0 - 2 * div = 1 && i319:0 > div1 && i319:0 > 0 f1396_0_power_LE'(i319:0) -> f1396_0_power_LE(div1) :|: i319:0 > div1 && i319:0 > 0 && i319:0 - 2 * div = 1 && i319:0 - 2 * div > -2 && i319:0 - 2 * div < 2 && i319:0 - 2 * div1 > -2 && i319:0 - 2 * div1 < 2 f1396_0_power_LE(i319:0) -> f1396_0_power_LE'(i319:0) :|: i319:0 - 2 * div = 0 && i319:0 > div1 && i319:0 > 0 f1396_0_power_LE'(i319:0) -> f1396_0_power_LE(div1) :|: i319:0 - 2 * div = 0 && i319:0 > 0 && i319:0 > div1 && i319:0 - 2 * div > -2 && i319:0 - 2 * div < 2 && i319:0 - 2 * div1 > -2 && i319:0 - 2 * div1 < 2 ---------------------------------------- (8) Obligation: Rules: f1396_0_power_LE(x) -> f1396_0_power_LE'(x) :|: x - 2 * x1 = 1 && x > x2 && x > 0 f1396_0_power_LE'(x3) -> f1396_0_power_LE(x4) :|: x3 > x4 && x3 > 0 && x3 - 2 * x5 = 1 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 f1396_0_power_LE(x6) -> f1396_0_power_LE'(x6) :|: x6 - 2 * x7 = 0 && x6 > x8 && x6 > 0 f1396_0_power_LE'(x9) -> f1396_0_power_LE(x10) :|: x9 - 2 * x11 = 0 && x9 > 0 && x9 > x10 && 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: f1396_0_power_LE(x) -> f1396_0_power_LE'(x) :|: x - 2 * x1 = 1 && x > x2 && x > 0 f1396_0_power_LE'(x3) -> f1396_0_power_LE(x4) :|: x3 > x4 && x3 > 0 && x3 - 2 * x5 = 1 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 f1396_0_power_LE(x6) -> f1396_0_power_LE'(x6) :|: x6 - 2 * x7 = 0 && x6 > x8 && x6 > 0 f1396_0_power_LE'(x9) -> f1396_0_power_LE(x10) :|: x9 - 2 * x11 = 0 && x9 > 0 && x9 > x10 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1396_0_power_LE(x) -> f1396_0_power_LE'(x) :|: x - 2 * x1 = 1 && x > x2 && x > 0 (2) f1396_0_power_LE'(x3) -> f1396_0_power_LE(x4) :|: x3 > x4 && x3 > 0 && x3 - 2 * x5 = 1 && x3 - 2 * x5 > -2 && x3 - 2 * x5 < 2 && x3 - 2 * x4 > -2 && x3 - 2 * x4 < 2 (3) f1396_0_power_LE(x6) -> f1396_0_power_LE'(x6) :|: x6 - 2 * x7 = 0 && x6 > x8 && x6 > 0 (4) f1396_0_power_LE'(x9) -> f1396_0_power_LE(x10) :|: x9 - 2 * x11 = 0 && x9 > 0 && x9 > x10 && 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) f1396_0_power_LE(x) -> f1396_0_power_LE'(x) :|: x - 2 * x1 = 1 && x > x2 && x > 0 (2) f1396_0_power_LE'(x9) -> f1396_0_power_LE(x10) :|: x9 - 2 * x11 = 0 && x9 > 0 && x9 > x10 && x9 - 2 * x11 > -2 && x9 - 2 * x11 < 2 && x9 - 2 * x10 > -2 && x9 - 2 * x10 < 2 (3) f1396_0_power_LE(x6) -> f1396_0_power_LE'(x6) :|: x6 - 2 * x7 = 0 && x6 > x8 && x6 > 0 (4) f1396_0_power_LE'(x3) -> f1396_0_power_LE(x4) :|: x3 > x4 && x3 > 0 && x3 - 2 * x5 = 1 && 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: f1396_0_power_LE'(x3:0) -> f1396_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 && x3:0 - 2 * x5:0 = 1 && x3:0 > 0 && x4:0 < x3:0 f1396_0_power_LE(x6:0) -> f1396_0_power_LE'(x6:0) :|: x6:0 - 2 * x7:0 = 0 && x8:0 < x6:0 && x6:0 > 0 f1396_0_power_LE(x:0) -> f1396_0_power_LE'(x:0) :|: x:0 - 2 * x1:0 = 1 && x:0 > x2:0 && x:0 > 0 f1396_0_power_LE'(x9:0) -> f1396_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 > x10:0 && x9:0 > 0 && x9:0 - 2 * x11:0 = 0 ---------------------------------------- (15) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f1396_0_power_LE'(INTEGER) f1396_0_power_LE(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f1396_0_power_LE'(x3:0) -> f1396_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 && x3:0 - 2 * x5:0 = 1 && x3:0 > 0 && x4:0 < x3:0 f1396_0_power_LE(x6:0) -> f1396_0_power_LE'(x6:0) :|: x6:0 - 2 * x7:0 = 0 && x8:0 < x6:0 && x6:0 > 0 f1396_0_power_LE(x:0) -> f1396_0_power_LE'(x:0) :|: x:0 - 2 * x1:0 = 1 && x:0 > x2:0 && x:0 > 0 f1396_0_power_LE'(x9:0) -> f1396_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 > x10:0 && x9:0 > 0 && x9:0 - 2 * x11:0 = 0 ---------------------------------------- (17) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (18) Obligation: Rules: f1396_0_power_LE'(x9:0:0) -> f1396_0_power_LE(x10:0:0) :|: x9:0:0 > 0 && x9:0:0 - 2 * x11:0:0 = 0 && x9:0:0 > x10:0:0 && 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 f1396_0_power_LE(x6:0:0) -> f1396_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x7:0:0 = 0 && x8:0:0 < x6:0:0 && x6:0:0 > 0 f1396_0_power_LE'(x3:0:0) -> f1396_0_power_LE(x4:0:0) :|: x3:0:0 > 0 && x4:0:0 < x3:0:0 && x3:0:0 - 2 * x5:0:0 = 1 && 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 f1396_0_power_LE(x:0:0) -> f1396_0_power_LE'(x:0:0) :|: x:0:0 - 2 * x1:0:0 = 1 && x:0:0 > x2:0:0 && x:0:0 > 0 ---------------------------------------- (19) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1396_0_power_LE'(x)] = x [f1396_0_power_LE(x1)] = x1 The following rules are decreasing: f1396_0_power_LE'(x9:0:0) -> f1396_0_power_LE(x10:0:0) :|: x9:0:0 > 0 && x9:0:0 - 2 * x11:0:0 = 0 && x9:0:0 > x10:0:0 && 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 f1396_0_power_LE'(x3:0:0) -> f1396_0_power_LE(x4:0:0) :|: x3:0:0 > 0 && x4:0:0 < x3:0:0 && x3:0:0 - 2 * x5:0:0 = 1 && 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: f1396_0_power_LE'(x9:0:0) -> f1396_0_power_LE(x10:0:0) :|: x9:0:0 > 0 && x9:0:0 - 2 * x11:0:0 = 0 && x9:0:0 > x10:0:0 && 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 f1396_0_power_LE(x6:0:0) -> f1396_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x7:0:0 = 0 && x8:0:0 < x6:0:0 && x6:0:0 > 0 f1396_0_power_LE'(x3:0:0) -> f1396_0_power_LE(x4:0:0) :|: x3:0:0 > 0 && x4:0:0 < x3:0:0 && x3:0:0 - 2 * x5:0:0 = 1 && 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 f1396_0_power_LE(x:0:0) -> f1396_0_power_LE'(x:0:0) :|: x:0:0 - 2 * x1:0:0 = 1 && x:0:0 > x2:0:0 && x:0:0 > 0 ---------------------------------------- (20) Obligation: Rules: f1396_0_power_LE(x6:0:0) -> f1396_0_power_LE'(x6:0:0) :|: x6:0:0 - 2 * x7:0:0 = 0 && x8:0:0 < x6:0:0 && x6:0:0 > 0 f1396_0_power_LE(x:0:0) -> f1396_0_power_LE'(x:0:0) :|: x:0:0 - 2 * x1:0:0 = 1 && 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