/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, 376 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) JBCTerminationSCC (7) SCCToIRSProof [SOUND, 104 ms] (8) IRSwT (9) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (10) IRSwT (11) IRSwTTerminationDigraphProof [EQUIVALENT, 28 ms] (12) AND (13) IRSwT (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] (15) IRSwT (16) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (17) IRSwT (18) TempFilterProof [SOUND, 38 ms] (19) IntTRS (20) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (21) YES (22) IRSwT (23) IntTRSCompressionProof [EQUIVALENT, 0 ms] (24) IRSwT (25) TempFilterProof [SOUND, 4 ms] (26) IntTRS (27) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (28) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: /** * Example taken from "A Term Rewriting Approach to the Automated Termination * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) * and converted to Java. */ public class PastaC11 { public static void main(String[] args) { Random.args = args; int x = Random.random(); int y = Random.random(); while (true) { if (x >= 0) { x--; y = Random.random(); } else if (y >= 0) { y--; } else { break; } } } } 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: /** * Example taken from "A Term Rewriting Approach to the Automated Termination * Analysis of Imperative Programs" (http://www.cs.unm.edu/~spf/papers/2009-02.pdf) * and converted to Java. */ public class PastaC11 { public static void main(String[] args) { Random.args = args; int x = Random.random(); int y = Random.random(); while (true) { if (x >= 0) { x--; y = Random.random(); } else if (y >= 0) { y--; } else { break; } } } } 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: PastaC11.main([Ljava/lang/String;)V: Graph of 249 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: PastaC11.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *java.lang.String: [count] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (7) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 34 IRulesP rules: f1322_0_main_LT(EOS(STATIC_1322(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), matching1, i124, matching2) -> f1326_0_main_LT(EOS(STATIC_1326(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), -1, i124, -1) :|: TRUE && matching1 = -1 && matching2 = -1 f1322_0_main_LT(EOS(STATIC_1322(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i237, i124, i237) -> f1327_0_main_LT(EOS(STATIC_1327(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i237, i124, i237) :|: TRUE f1326_0_main_LT(EOS(STATIC_1326(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), matching1, i124, matching2) -> f1328_0_main_Load(EOS(STATIC_1328(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), -1, i124) :|: -1 < 0 && matching1 = -1 && matching2 = -1 f1328_0_main_Load(EOS(STATIC_1328(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), matching1, i124) -> f1333_0_main_LT(EOS(STATIC_1333(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), -1, i124, i124) :|: TRUE && matching1 = -1 f1333_0_main_LT(EOS(STATIC_1333(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), matching1, i240, i240) -> f1340_0_main_LT(EOS(STATIC_1340(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), -1, i240, i240) :|: TRUE && matching1 = -1 f1340_0_main_LT(EOS(STATIC_1340(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), matching1, i240, i240) -> f1347_0_main_Inc(EOS(STATIC_1347(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), -1, i240) :|: i240 >= 0 && matching1 = -1 f1347_0_main_Inc(EOS(STATIC_1347(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), matching1, i240) -> f1352_0_main_JMP(EOS(STATIC_1352(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), -1, i240 + -1) :|: TRUE && matching1 = -1 f1352_0_main_JMP(EOS(STATIC_1352(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), matching1, i242) -> f1511_0_main_Load(EOS(STATIC_1511(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), -1, i242) :|: TRUE && matching1 = -1 f1511_0_main_Load(EOS(STATIC_1511(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), matching1, i242) -> f1315_0_main_Load(EOS(STATIC_1315(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), -1, i242) :|: TRUE && matching1 = -1 f1315_0_main_Load(EOS(STATIC_1315(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i123, i124) -> f1322_0_main_LT(EOS(STATIC_1322(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i123, i124, i123) :|: TRUE f1327_0_main_LT(EOS(STATIC_1327(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i237, i124, i237) -> f1331_0_main_Inc(EOS(STATIC_1331(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i237) :|: i237 >= 0 f1331_0_main_Inc(EOS(STATIC_1331(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i237) -> f1336_0_main_InvokeMethod(EOS(STATIC_1336(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i237 + -1) :|: TRUE f1336_0_main_InvokeMethod(EOS(STATIC_1336(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239) -> f1341_0_random_FieldAccess(EOS(STATIC_1341(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239) :|: TRUE f1341_0_random_FieldAccess(EOS(STATIC_1341(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239) -> f1355_0_random_FieldAccess(EOS(STATIC_1355(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(ARRAY(i4))) :|: TRUE f1355_0_random_FieldAccess(EOS(STATIC_1355(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(ARRAY(i4))) -> f1524_0_random_ArrayAccess(EOS(STATIC_1524(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(ARRAY(i4))) :|: TRUE f1524_0_random_ArrayAccess(EOS(STATIC_1524(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(ARRAY(i4))) -> f1527_0_random_ArrayAccess(EOS(STATIC_1527(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(ARRAY(i4))) :|: TRUE f1527_0_random_ArrayAccess(EOS(STATIC_1527(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(ARRAY(i4))) -> f1534_0_random_Store(EOS(STATIC_1534(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) :|: TRUE f1534_0_random_Store(EOS(STATIC_1534(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) -> f1540_0_random_FieldAccess(EOS(STATIC_1540(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) :|: TRUE f1540_0_random_FieldAccess(EOS(STATIC_1540(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) -> f1544_0_random_ConstantStackPush(EOS(STATIC_1544(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) :|: TRUE f1544_0_random_ConstantStackPush(EOS(STATIC_1544(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) -> f1554_0_random_IntArithmetic(EOS(STATIC_1554(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) :|: TRUE f1554_0_random_IntArithmetic(EOS(STATIC_1554(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) -> f1562_0_random_FieldAccess(EOS(STATIC_1562(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) :|: TRUE f1562_0_random_FieldAccess(EOS(STATIC_1562(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) -> f1566_0_random_Load(EOS(STATIC_1566(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) :|: TRUE f1566_0_random_Load(EOS(STATIC_1566(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) -> f1580_0_random_InvokeMethod(EOS(STATIC_1580(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, o104) :|: TRUE f1580_0_random_InvokeMethod(EOS(STATIC_1580(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(o110sub)) -> f1586_0_random_InvokeMethod(EOS(STATIC_1586(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(o110sub)) :|: TRUE f1586_0_random_InvokeMethod(EOS(STATIC_1586(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(o111sub)) -> f1590_0_random_InvokeMethod(EOS(STATIC_1590(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(o111sub)) :|: TRUE f1590_0_random_InvokeMethod(EOS(STATIC_1590(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(o111sub)) -> f1600_0_length_Load(EOS(STATIC_1600(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(o111sub)) :|: TRUE f1600_0_length_Load(EOS(STATIC_1600(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(o111sub)) -> f1623_0_length_FieldAccess(EOS(STATIC_1623(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(o111sub)) :|: TRUE f1623_0_length_FieldAccess(EOS(STATIC_1623(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(java.lang.String(EOC, i310))) -> f1634_0_length_FieldAccess(EOS(STATIC_1634(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(java.lang.String(EOC, i310))) :|: i310 >= 0 f1634_0_length_FieldAccess(EOS(STATIC_1634(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, java.lang.Object(java.lang.String(EOC, i310))) -> f1644_0_length_Return(EOS(STATIC_1644(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) :|: TRUE f1644_0_length_Return(EOS(STATIC_1644(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) -> f1655_0_random_Return(EOS(STATIC_1655(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) :|: TRUE f1655_0_random_Return(EOS(STATIC_1655(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) -> f1667_0_main_Store(EOS(STATIC_1667(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) :|: TRUE f1667_0_main_Store(EOS(STATIC_1667(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) -> f1676_0_main_JMP(EOS(STATIC_1676(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) :|: TRUE f1676_0_main_JMP(EOS(STATIC_1676(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) -> f1707_0_main_Load(EOS(STATIC_1707(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) :|: TRUE f1707_0_main_Load(EOS(STATIC_1707(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) -> f1315_0_main_Load(EOS(STATIC_1315(java.lang.Object(ARRAY(i4)))), java.lang.Object(ARRAY(i4)), i239, i310) :|: TRUE Combined rules. Obtained 2 IRulesP rules: f1322_0_main_LT(EOS(STATIC_1322(java.lang.Object(ARRAY(i4:0)))), java.lang.Object(ARRAY(i4:0)), -1, i124:0, -1) -> f1322_0_main_LT(EOS(STATIC_1322(java.lang.Object(ARRAY(i4:0)))), java.lang.Object(ARRAY(i4:0)), -1, i124:0 - 1, -1) :|: i124:0 > -1 f1322_0_main_LT(EOS(STATIC_1322(java.lang.Object(ARRAY(i4:0)))), java.lang.Object(ARRAY(i4:0)), i237:0, i124:0, i237:0) -> f1322_0_main_LT(EOS(STATIC_1322(java.lang.Object(ARRAY(i4:0)))), java.lang.Object(ARRAY(i4:0)), i237:0 - 1, i310:0, i237:0 - 1) :|: i310:0 > -1 && i237:0 > -1 Filtered duplicate arguments: f1322_0_main_LT(x1, x2, x3, x4, x5) -> f1322_0_main_LT(x1, x2, x4, x5) Filtered unneeded arguments: f1322_0_main_LT(x1, x2, x3, x4) -> f1322_0_main_LT(x3, x4) Finished conversion. Obtained 2 rules.P rules: f1322_0_main_LT(i124:0, cons_-1) -> f1322_0_main_LT(i124:0 - 1, -1) :|: i124:0 > -1 && cons_-1 = -1 f1322_0_main_LT(i124:0, i237:0) -> f1322_0_main_LT(i310:0, i237:0 - 1) :|: i310:0 > -1 && i237:0 > -1 ---------------------------------------- (8) Obligation: Rules: f1322_0_main_LT(i124:0, cons_-1) -> f1322_0_main_LT(i124:0 - 1, -1) :|: i124:0 > -1 && cons_-1 = -1 f1322_0_main_LT(x, x1) -> f1322_0_main_LT(x2, x1 - 1) :|: x2 > -1 && x1 > -1 ---------------------------------------- (9) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (10) Obligation: Rules: f1322_0_main_LT(i124:0, cons_-1) -> f1322_0_main_LT(arith, -1) :|: i124:0 > -1 && cons_-1 = -1 && arith = i124:0 - 1 f1322_0_main_LT(x3, x4) -> f1322_0_main_LT(x5, x6) :|: x5 > -1 && x4 > -1 && x6 = x4 - 1 ---------------------------------------- (11) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1322_0_main_LT(i124:0, cons_-1) -> f1322_0_main_LT(arith, -1) :|: i124:0 > -1 && cons_-1 = -1 && arith = i124:0 - 1 (2) f1322_0_main_LT(x3, x4) -> f1322_0_main_LT(x5, x6) :|: x5 > -1 && x4 > -1 && x6 = x4 - 1 Arcs: (1) -> (1) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (12) Complex Obligation (AND) ---------------------------------------- (13) Obligation: Termination digraph: Nodes: (1) f1322_0_main_LT(x3, x4) -> f1322_0_main_LT(x5, x6) :|: x5 > -1 && x4 > -1 && x6 = x4 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (14) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (15) Obligation: Rules: f1322_0_main_LT(x3:0, x4:0) -> f1322_0_main_LT(x5:0, x4:0 - 1) :|: x5:0 > -1 && x4:0 > -1 ---------------------------------------- (16) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f1322_0_main_LT(x1, x2) -> f1322_0_main_LT(x2) ---------------------------------------- (17) Obligation: Rules: f1322_0_main_LT(x4:0) -> f1322_0_main_LT(x4:0 - 1) :|: x5:0 > -1 && x4:0 > -1 ---------------------------------------- (18) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1322_0_main_LT(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (19) Obligation: Rules: f1322_0_main_LT(x4:0) -> f1322_0_main_LT(c) :|: c = x4:0 - 1 && (x5:0 > -1 && x4:0 > -1) ---------------------------------------- (20) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1322_0_main_LT(x)] = x The following rules are decreasing: f1322_0_main_LT(x4:0) -> f1322_0_main_LT(c) :|: c = x4:0 - 1 && (x5:0 > -1 && x4:0 > -1) The following rules are bounded: f1322_0_main_LT(x4:0) -> f1322_0_main_LT(c) :|: c = x4:0 - 1 && (x5:0 > -1 && x4:0 > -1) ---------------------------------------- (21) YES ---------------------------------------- (22) Obligation: Termination digraph: Nodes: (1) f1322_0_main_LT(i124:0, cons_-1) -> f1322_0_main_LT(arith, -1) :|: i124:0 > -1 && cons_-1 = -1 && arith = i124:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (23) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (24) Obligation: Rules: f1322_0_main_LT(i124:0:0, cons_-1) -> f1322_0_main_LT(i124:0:0 - 1, -1) :|: i124:0:0 > -1 && cons_-1 = -1 ---------------------------------------- (25) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1322_0_main_LT(INTEGER, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (26) Obligation: Rules: f1322_0_main_LT(i124:0:0, c) -> f1322_0_main_LT(c1, c2) :|: c2 = -1 && (c1 = i124:0:0 - 1 && c = -1) && (i124:0:0 > -1 && cons_-1 = -1) ---------------------------------------- (27) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1322_0_main_LT(x, x1)] = x The following rules are decreasing: f1322_0_main_LT(i124:0:0, c) -> f1322_0_main_LT(c1, c2) :|: c2 = -1 && (c1 = i124:0:0 - 1 && c = -1) && (i124:0:0 > -1 && cons_-1 = -1) The following rules are bounded: f1322_0_main_LT(i124:0:0, c) -> f1322_0_main_LT(c1, c2) :|: c2 = -1 && (c1 = i124:0:0 - 1 && c = -1) && (i124:0:0 > -1 && cons_-1 = -1) ---------------------------------------- (28) YES