/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, 451 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToIRSProof [SOUND, 109 ms] (9) IRSwT (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (11) IRSwT (12) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (13) IRSwT (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] (15) IRSwT (16) TempFilterProof [SOUND, 29 ms] (17) IntTRS (18) RankingReductionPairProof [EQUIVALENT, 10 ms] (19) YES (20) JBCTerminationSCC (21) SCCToQDPProof [SOUND, 110 ms] (22) QDP (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] (24) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class ObjectList { Object value; ObjectList next; public ObjectList(Object value, ObjectList next) { this.value = value; this.next = next; } public static ObjectList createList() { ObjectList result = null; int length = Random.random(); while (length > 0) { result = new ObjectList(new Object(), result); length--; } return result; } } public class Random { static String[] args; static int index = 0; public static int random() { String string = args[index]; index++; return string.length(); } } /** * Allegedly based on an interview question at Microsoft. */ public class RunningPointers { public static boolean isCyclic(ObjectList l) { if (l == null) { return false; } ObjectList l1, l2; l1 = l; l2 = l.next; while (l2 != null && l1 != l2) { l2 = l2.next; if (l2 == null) { return false; } else if (l2 == l1) { return true; } else { l2 = l2.next; } l1 = l1.next; } return l2 != null; } public static void main(String[] args) { Random.args = args; ObjectList list = ObjectList.createList(); isCyclic(list); } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class ObjectList { Object value; ObjectList next; public ObjectList(Object value, ObjectList next) { this.value = value; this.next = next; } public static ObjectList createList() { ObjectList result = null; int length = Random.random(); while (length > 0) { result = new ObjectList(new Object(), result); length--; } return result; } } public class Random { static String[] args; static int index = 0; public static int random() { String string = args[index]; index++; return string.length(); } } /** * Allegedly based on an interview question at Microsoft. */ public class RunningPointers { public static boolean isCyclic(ObjectList l) { if (l == null) { return false; } ObjectList l1, l2; l1 = l; l2 = l.next; while (l2 != null && l1 != l2) { l2 = l2.next; if (l2 == null) { return false; } else if (l2 == l1) { return true; } else { l2 = l2.next; } l1 = l1.next; } return l2 != null; } public static void main(String[] args) { Random.args = args; ObjectList list = ObjectList.createList(); isCyclic(list); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: RunningPointers.main([Ljava/lang/String;)V: Graph of 129 nodes with 1 SCC. ObjectList.createList()LObjectList;: Graph of 151 nodes with 1 SCC. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 2 SCCss. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: ObjectList.createList()LObjectList; 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: ---------------------------------------- (8) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 23 IRulesP rules: f1404_0_createList_LE(EOS(STATIC_1404), i109, i109) -> f1415_0_createList_LE(EOS(STATIC_1415), i109, i109) :|: TRUE f1415_0_createList_LE(EOS(STATIC_1415), i109, i109) -> f1420_0_createList_New(EOS(STATIC_1420), i109) :|: i109 > 0 f1420_0_createList_New(EOS(STATIC_1420), i109) -> f1451_0_createList_Duplicate(EOS(STATIC_1451), i109) :|: TRUE f1451_0_createList_Duplicate(EOS(STATIC_1451), i109) -> f1467_0_createList_New(EOS(STATIC_1467), i109) :|: TRUE f1467_0_createList_New(EOS(STATIC_1467), i109) -> f1493_0_createList_Duplicate(EOS(STATIC_1493), i109) :|: TRUE f1493_0_createList_Duplicate(EOS(STATIC_1493), i109) -> f1513_0_createList_InvokeMethod(EOS(STATIC_1513), i109) :|: TRUE f1513_0_createList_InvokeMethod(EOS(STATIC_1513), i109) -> f1519_0_createList_Load(EOS(STATIC_1519), i109) :|: TRUE f1519_0_createList_Load(EOS(STATIC_1519), i109) -> f1526_0_createList_InvokeMethod(EOS(STATIC_1526), i109) :|: TRUE f1526_0_createList_InvokeMethod(EOS(STATIC_1526), i109) -> f1533_0__init__Load(EOS(STATIC_1533), i109) :|: TRUE f1533_0__init__Load(EOS(STATIC_1533), i109) -> f1549_0__init__InvokeMethod(EOS(STATIC_1549), i109) :|: TRUE f1549_0__init__InvokeMethod(EOS(STATIC_1549), i109) -> f1552_0__init__Load(EOS(STATIC_1552), i109) :|: TRUE f1552_0__init__Load(EOS(STATIC_1552), i109) -> f1554_0__init__Load(EOS(STATIC_1554), i109) :|: TRUE f1554_0__init__Load(EOS(STATIC_1554), i109) -> f1556_0__init__FieldAccess(EOS(STATIC_1556), i109) :|: TRUE f1556_0__init__FieldAccess(EOS(STATIC_1556), i109) -> f1558_0__init__Load(EOS(STATIC_1558), i109) :|: TRUE f1558_0__init__Load(EOS(STATIC_1558), i109) -> f1560_0__init__Load(EOS(STATIC_1560), i109) :|: TRUE f1560_0__init__Load(EOS(STATIC_1560), i109) -> f1562_0__init__FieldAccess(EOS(STATIC_1562), i109) :|: TRUE f1562_0__init__FieldAccess(EOS(STATIC_1562), i109) -> f1564_0__init__Return(EOS(STATIC_1564), i109) :|: TRUE f1564_0__init__Return(EOS(STATIC_1564), i109) -> f1566_0_createList_Store(EOS(STATIC_1566), i109) :|: TRUE f1566_0_createList_Store(EOS(STATIC_1566), i109) -> f1568_0_createList_Inc(EOS(STATIC_1568), i109) :|: TRUE f1568_0_createList_Inc(EOS(STATIC_1568), i109) -> f1601_0_createList_JMP(EOS(STATIC_1601), i109 + -1) :|: TRUE f1601_0_createList_JMP(EOS(STATIC_1601), i119) -> f1614_0_createList_Load(EOS(STATIC_1614), i119) :|: TRUE f1614_0_createList_Load(EOS(STATIC_1614), i119) -> f1351_0_createList_Load(EOS(STATIC_1351), i119) :|: TRUE f1351_0_createList_Load(EOS(STATIC_1351), i104) -> f1404_0_createList_LE(EOS(STATIC_1404), i104, i104) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f1404_0_createList_LE(EOS(STATIC_1404), i109:0, i109:0) -> f1404_0_createList_LE(EOS(STATIC_1404), i109:0 - 1, i109:0 - 1) :|: i109:0 > 0 Filtered constant ground arguments: f1404_0_createList_LE(x1, x2, x3) -> f1404_0_createList_LE(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f1404_0_createList_LE(x1, x2) -> f1404_0_createList_LE(x2) Finished conversion. Obtained 1 rules.P rules: f1404_0_createList_LE(i109:0) -> f1404_0_createList_LE(i109:0 - 1) :|: i109:0 > 0 ---------------------------------------- (9) Obligation: Rules: f1404_0_createList_LE(i109:0) -> f1404_0_createList_LE(i109:0 - 1) :|: i109:0 > 0 ---------------------------------------- (10) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (11) Obligation: Rules: f1404_0_createList_LE(i109:0) -> f1404_0_createList_LE(arith) :|: i109:0 > 0 && arith = i109:0 - 1 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1404_0_createList_LE(i109:0) -> f1404_0_createList_LE(arith) :|: i109:0 > 0 && arith = i109:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (13) Obligation: Termination digraph: Nodes: (1) f1404_0_createList_LE(i109:0) -> f1404_0_createList_LE(arith) :|: i109:0 > 0 && arith = i109:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (14) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (15) Obligation: Rules: f1404_0_createList_LE(i109:0:0) -> f1404_0_createList_LE(i109:0:0 - 1) :|: i109:0:0 > 0 ---------------------------------------- (16) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1404_0_createList_LE(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (17) Obligation: Rules: f1404_0_createList_LE(i109:0:0) -> f1404_0_createList_LE(c) :|: c = i109:0:0 - 1 && i109:0:0 > 0 ---------------------------------------- (18) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f1404_0_createList_LE ] = f1404_0_createList_LE_1 The following rules are decreasing: f1404_0_createList_LE(i109:0:0) -> f1404_0_createList_LE(c) :|: c = i109:0:0 - 1 && i109:0:0 > 0 The following rules are bounded: f1404_0_createList_LE(i109:0:0) -> f1404_0_createList_LE(c) :|: c = i109:0:0 - 1 && i109:0:0 > 0 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: RunningPointers.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *ObjectList: [next] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (21) SCCToQDPProof (SOUND) Transformed TerminationGraph SCC to QDP. Log: Generated 29 rules for P and 0 rules for R.P rules: f1675_0_isCyclic_NULL(EOS(STATIC_1675), o284, java.lang.Object(o289sub), java.lang.Object(o289sub)) -> f1677_0_isCyclic_Load(EOS(STATIC_1677), o284, java.lang.Object(o289sub)) :|: TRUE f1677_0_isCyclic_Load(EOS(STATIC_1677), o284, java.lang.Object(o289sub)) -> f1681_0_isCyclic_Load(EOS(STATIC_1681), o284, java.lang.Object(o289sub), o284) :|: TRUE f1681_0_isCyclic_Load(EOS(STATIC_1681), o284, java.lang.Object(o289sub), o284) -> f1685_0_isCyclic_EQ(EOS(STATIC_1685), o284, java.lang.Object(o289sub), o284, java.lang.Object(o289sub)) :|: TRUE f1685_0_isCyclic_EQ(EOS(STATIC_1685), java.lang.Object(o290sub), java.lang.Object(o289sub), java.lang.Object(o290sub), java.lang.Object(o289sub)) -> f1688_0_isCyclic_EQ(EOS(STATIC_1688), java.lang.Object(o290sub), java.lang.Object(o289sub), java.lang.Object(o290sub), java.lang.Object(o289sub)) :|: TRUE f1688_0_isCyclic_EQ(EOS(STATIC_1688), java.lang.Object(o290sub), java.lang.Object(o289sub), java.lang.Object(o290sub), java.lang.Object(o289sub)) -> f1709_0_isCyclic_EQ(EOS(STATIC_1709), java.lang.Object(o290sub), java.lang.Object(o289sub), java.lang.Object(o290sub), java.lang.Object(o289sub)) :|: TRUE f1709_0_isCyclic_EQ(EOS(STATIC_1709), java.lang.Object(o290sub), java.lang.Object(o289sub), java.lang.Object(o290sub), java.lang.Object(o289sub)) -> f1721_0_isCyclic_Load(EOS(STATIC_1721), java.lang.Object(o290sub), java.lang.Object(o289sub)) :|: TRUE f1721_0_isCyclic_Load(EOS(STATIC_1721), java.lang.Object(o290sub), java.lang.Object(o289sub)) -> f1724_0_isCyclic_FieldAccess(EOS(STATIC_1724), java.lang.Object(o290sub), java.lang.Object(o289sub)) :|: TRUE f1724_0_isCyclic_FieldAccess(EOS(STATIC_1724), java.lang.Object(o290sub), java.lang.Object(ObjectList(EOC, o310))) -> f1750_0_isCyclic_FieldAccess(EOS(STATIC_1750), java.lang.Object(o290sub), java.lang.Object(ObjectList(EOC, o310))) :|: TRUE f1750_0_isCyclic_FieldAccess(EOS(STATIC_1750), java.lang.Object(o290sub), java.lang.Object(ObjectList(EOC, o310))) -> f1753_0_isCyclic_Store(EOS(STATIC_1753), java.lang.Object(o290sub), o310) :|: TRUE f1753_0_isCyclic_Store(EOS(STATIC_1753), java.lang.Object(o290sub), o310) -> f1782_0_isCyclic_Load(EOS(STATIC_1782), java.lang.Object(o290sub), o310) :|: TRUE f1782_0_isCyclic_Load(EOS(STATIC_1782), java.lang.Object(o290sub), o310) -> f1793_0_isCyclic_NONNULL(EOS(STATIC_1793), java.lang.Object(o290sub), o310, o310) :|: TRUE f1793_0_isCyclic_NONNULL(EOS(STATIC_1793), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub)) -> f1802_0_isCyclic_NONNULL(EOS(STATIC_1802), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub)) :|: TRUE f1802_0_isCyclic_NONNULL(EOS(STATIC_1802), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub)) -> f1818_0_isCyclic_Load(EOS(STATIC_1818), java.lang.Object(o290sub), java.lang.Object(o318sub)) :|: TRUE f1818_0_isCyclic_Load(EOS(STATIC_1818), java.lang.Object(o290sub), java.lang.Object(o318sub)) -> f1824_0_isCyclic_Load(EOS(STATIC_1824), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub)) :|: TRUE f1824_0_isCyclic_Load(EOS(STATIC_1824), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub)) -> f1839_0_isCyclic_NE(EOS(STATIC_1839), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub), java.lang.Object(o290sub)) :|: TRUE f1839_0_isCyclic_NE(EOS(STATIC_1839), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub), java.lang.Object(o290sub)) -> f1841_0_isCyclic_NE(EOS(STATIC_1841), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub), java.lang.Object(o290sub)) :|: TRUE f1841_0_isCyclic_NE(EOS(STATIC_1841), java.lang.Object(o290sub), java.lang.Object(o318sub), java.lang.Object(o318sub), java.lang.Object(o290sub)) -> f1844_0_isCyclic_Load(EOS(STATIC_1844), java.lang.Object(o290sub), java.lang.Object(o318sub)) :|: TRUE f1844_0_isCyclic_Load(EOS(STATIC_1844), java.lang.Object(o290sub), java.lang.Object(o318sub)) -> f1855_0_isCyclic_FieldAccess(EOS(STATIC_1855), java.lang.Object(o290sub), java.lang.Object(o318sub)) :|: TRUE f1855_0_isCyclic_FieldAccess(EOS(STATIC_1855), java.lang.Object(o290sub), java.lang.Object(ObjectList(EOC, o342))) -> f1865_0_isCyclic_FieldAccess(EOS(STATIC_1865), java.lang.Object(o290sub), java.lang.Object(ObjectList(EOC, o342))) :|: TRUE f1865_0_isCyclic_FieldAccess(EOS(STATIC_1865), java.lang.Object(o290sub), java.lang.Object(ObjectList(EOC, o342))) -> f1879_0_isCyclic_Store(EOS(STATIC_1879), java.lang.Object(o290sub), o342) :|: TRUE f1879_0_isCyclic_Store(EOS(STATIC_1879), java.lang.Object(o290sub), o342) -> f1884_0_isCyclic_Load(EOS(STATIC_1884), java.lang.Object(o290sub), o342) :|: TRUE f1884_0_isCyclic_Load(EOS(STATIC_1884), java.lang.Object(o290sub), o342) -> f1886_0_isCyclic_FieldAccess(EOS(STATIC_1886), o342, java.lang.Object(o290sub)) :|: TRUE f1886_0_isCyclic_FieldAccess(EOS(STATIC_1886), o342, java.lang.Object(ObjectList(EOC, o357))) -> f1887_0_isCyclic_FieldAccess(EOS(STATIC_1887), o342, java.lang.Object(ObjectList(EOC, o357))) :|: TRUE f1887_0_isCyclic_FieldAccess(EOS(STATIC_1887), o342, java.lang.Object(ObjectList(EOC, o357))) -> f1889_0_isCyclic_Store(EOS(STATIC_1889), o342, o357) :|: TRUE f1889_0_isCyclic_Store(EOS(STATIC_1889), o342, o357) -> f1891_0_isCyclic_JMP(EOS(STATIC_1891), o357, o342) :|: TRUE f1891_0_isCyclic_JMP(EOS(STATIC_1891), o357, o342) -> f1892_0_isCyclic_Load(EOS(STATIC_1892), o357, o342) :|: TRUE f1892_0_isCyclic_Load(EOS(STATIC_1892), o357, o342) -> f1672_0_isCyclic_Load(EOS(STATIC_1672), o357, o342) :|: TRUE f1672_0_isCyclic_Load(EOS(STATIC_1672), o284, o285) -> f1674_0_isCyclic_NULL(EOS(STATIC_1674), o284, o285, o285) :|: TRUE f1674_0_isCyclic_NULL(EOS(STATIC_1674), o284, java.lang.Object(o289sub), java.lang.Object(o289sub)) -> f1675_0_isCyclic_NULL(EOS(STATIC_1675), o284, java.lang.Object(o289sub), java.lang.Object(o289sub)) :|: TRUE R rules: Combined rules. Obtained 1 conditional rules for P and 0 conditional rules for R.P rules: f1675_0_isCyclic_NULL(EOS(STATIC_1675), java.lang.Object(ObjectList(EOC, o357:0)), java.lang.Object(ObjectList(EOC, java.lang.Object(ObjectList(EOC, java.lang.Object(o289sub:0))))), java.lang.Object(ObjectList(EOC, java.lang.Object(ObjectList(EOC, java.lang.Object(o289sub:0)))))) -> f1675_0_isCyclic_NULL(EOS(STATIC_1675), o357:0, java.lang.Object(o289sub:0), java.lang.Object(o289sub:0)) :|: TRUE R rules: Filtered ground terms: f1675_0_isCyclic_NULL(x1, x2, x3, x4) -> f1675_0_isCyclic_NULL(x2, x3, x4) EOS(x1) -> EOS ObjectList(x1, x2) -> ObjectList(x2) Filtered duplicate args: f1675_0_isCyclic_NULL(x1, x2, x3) -> f1675_0_isCyclic_NULL(x1, x3) Combined rules. Obtained 1 conditional rules for P and 0 conditional rules for R.P rules: F1675_0_ISCYCLIC_NULL(java.lang.Object(ObjectList(o357:0:0)), java.lang.Object(ObjectList(java.lang.Object(ObjectList(java.lang.Object(o289sub:0:0)))))) -> F1675_0_ISCYCLIC_NULL(o357:0:0, java.lang.Object(o289sub:0:0)) :|: TRUE R rules: ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: F1675_0_ISCYCLIC_NULL(java.lang.Object(ObjectList(o357:0:0)), java.lang.Object(ObjectList(java.lang.Object(ObjectList(java.lang.Object(o289sub:0:0)))))) -> F1675_0_ISCYCLIC_NULL(o357:0:0, java.lang.Object(o289sub:0:0)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *F1675_0_ISCYCLIC_NULL(java.lang.Object(ObjectList(o357:0:0)), java.lang.Object(ObjectList(java.lang.Object(ObjectList(java.lang.Object(o289sub:0:0)))))) -> F1675_0_ISCYCLIC_NULL(o357:0:0, java.lang.Object(o289sub:0:0)) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (24) YES