/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, 97 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 438 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToQDPProof [SOUND, 289 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) JBCTerminationSCC (13) SCCToIRSProof [SOUND, 50 ms] (14) IRSwT (15) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IRSwTTerminationDigraphProof [EQUIVALENT, 39 ms] (18) IRSwT (19) IntTRSCompressionProof [EQUIVALENT, 0 ms] (20) IRSwT (21) TempFilterProof [SOUND, 28 ms] (22) IntTRS (23) RankingReductionPairProof [EQUIVALENT, 3 ms] (24) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: /** * This class represents a list, where the function duplicate() can be used to * duplicate all elements in the list. * @author cotto */ public class ListDuplicate { /** * Walk through the list and, for each original element, copy it and append * this copy after the original. This transforms abc to aabbcc. */ public static void duplicate(ObjectList list) { ObjectList current = list; boolean even = true; while (current != null) { // only copy the original elements! if (even) { final ObjectList copy = new ObjectList(current.value, current.next); current.next = copy; } current = current.next; even = !even; } } public static void main(String[] args) { Random.args = args; ObjectList list = ObjectList.createList(); duplicate(list); } } 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(); } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: /** * This class represents a list, where the function duplicate() can be used to * duplicate all elements in the list. * @author cotto */ public class ListDuplicate { /** * Walk through the list and, for each original element, copy it and append * this copy after the original. This transforms abc to aabbcc. */ public static void duplicate(ObjectList list) { ObjectList current = list; boolean even = true; while (current != null) { // only copy the original elements! if (even) { final ObjectList copy = new ObjectList(current.value, current.next); current.next = copy; } current = current.next; even = !even; } } public static void main(String[] args) { Random.args = args; ObjectList list = ObjectList.createList(); duplicate(list); } } 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(); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: ListDuplicate.main([Ljava/lang/String;)V: Graph of 30 nodes with 0 SCCs. ObjectList.createList()LObjectList;: Graph of 151 nodes with 1 SCC. ListDuplicate.duplicate(LObjectList;)V: Graph of 57 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: ListDuplicate.duplicate(LObjectList;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *ObjectList: [value, next] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (8) SCCToQDPProof (SOUND) Transformed TerminationGraph SCC to QDP. Log: Generated rules. Obtained 49 IRulesP rules: f1723_0_duplicate_NULL(EOS(STATIC_1723), java.lang.Object(o417sub), i139, java.lang.Object(o417sub)) -> f1724_0_duplicate_NULL(EOS(STATIC_1724), java.lang.Object(o417sub), i139, java.lang.Object(o417sub)) :|: TRUE f1724_0_duplicate_NULL(EOS(STATIC_1724), java.lang.Object(o417sub), i139, java.lang.Object(o417sub)) -> f1726_0_duplicate_Load(EOS(STATIC_1726), java.lang.Object(o417sub), i139) :|: TRUE f1726_0_duplicate_Load(EOS(STATIC_1726), java.lang.Object(o417sub), i139) -> f1728_0_duplicate_EQ(EOS(STATIC_1728), java.lang.Object(o417sub), i139, i139) :|: TRUE f1728_0_duplicate_EQ(EOS(STATIC_1728), java.lang.Object(o417sub), matching1, matching2) -> f1732_0_duplicate_EQ(EOS(STATIC_1732), java.lang.Object(o417sub), 1, 1) :|: TRUE && matching1 = 1 && matching2 = 1 f1728_0_duplicate_EQ(EOS(STATIC_1728), java.lang.Object(o417sub), matching1, matching2) -> f1733_0_duplicate_EQ(EOS(STATIC_1733), java.lang.Object(o417sub), 0, 0) :|: TRUE && matching1 = 0 && matching2 = 0 f1732_0_duplicate_EQ(EOS(STATIC_1732), java.lang.Object(o417sub), matching1, matching2) -> f1736_0_duplicate_New(EOS(STATIC_1736), java.lang.Object(o417sub), 1) :|: 1 > 0 && matching1 = 1 && matching2 = 1 f1736_0_duplicate_New(EOS(STATIC_1736), java.lang.Object(o417sub), matching1) -> f1740_0_duplicate_Duplicate(EOS(STATIC_1740), java.lang.Object(o417sub), 1, java.lang.Object(ObjectList(EOC, NULL, NULL))) :|: TRUE && matching1 = 1 f1740_0_duplicate_Duplicate(EOS(STATIC_1740), java.lang.Object(o417sub), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL))) -> f1742_0_duplicate_Load(EOS(STATIC_1742), java.lang.Object(o417sub), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL))) :|: TRUE && matching1 = 1 f1742_0_duplicate_Load(EOS(STATIC_1742), java.lang.Object(o417sub), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL))) -> f1744_0_duplicate_FieldAccess(EOS(STATIC_1744), java.lang.Object(o417sub), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(o417sub)) :|: TRUE && matching1 = 1 f1744_0_duplicate_FieldAccess(EOS(STATIC_1744), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, o426, o427))) -> f1746_0_duplicate_FieldAccess(EOS(STATIC_1746), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, o426, o427))) :|: TRUE && matching1 = 1 f1746_0_duplicate_FieldAccess(EOS(STATIC_1746), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, o426, o427))) -> f1748_0_duplicate_Load(EOS(STATIC_1748), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426) :|: TRUE && matching1 = 1 f1748_0_duplicate_Load(EOS(STATIC_1748), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426) -> f1750_0_duplicate_FieldAccess(EOS(STATIC_1750), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, java.lang.Object(ObjectList(EOC, o426, o427))) :|: TRUE && matching1 = 1 f1750_0_duplicate_FieldAccess(EOS(STATIC_1750), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, java.lang.Object(ObjectList(EOC, o426, o427))) -> f1752_0_duplicate_InvokeMethod(EOS(STATIC_1752), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427) :|: TRUE && matching1 = 1 f1752_0_duplicate_InvokeMethod(EOS(STATIC_1752), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427) -> f1754_0__init__Load(EOS(STATIC_1754), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427) :|: TRUE && matching1 = 1 f1754_0__init__Load(EOS(STATIC_1754), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427) -> f1757_0__init__InvokeMethod(EOS(STATIC_1757), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427, java.lang.Object(ObjectList(EOC, NULL, NULL))) :|: TRUE && matching1 = 1 f1757_0__init__InvokeMethod(EOS(STATIC_1757), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427, java.lang.Object(ObjectList(EOC, NULL, NULL))) -> f1759_0__init__Load(EOS(STATIC_1759), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427) :|: TRUE && matching1 = 1 f1759_0__init__Load(EOS(STATIC_1759), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427) -> f1760_0__init__Load(EOS(STATIC_1760), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427, java.lang.Object(ObjectList(EOC, NULL, NULL))) :|: TRUE && matching1 = 1 f1760_0__init__Load(EOS(STATIC_1760), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o426, o427, java.lang.Object(ObjectList(EOC, NULL, NULL))) -> f1761_0__init__FieldAccess(EOS(STATIC_1761), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o427, java.lang.Object(ObjectList(EOC, NULL, NULL)), o426) :|: TRUE && matching1 = 1 f1761_0__init__FieldAccess(EOS(STATIC_1761), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o427, java.lang.Object(ObjectList(EOC, NULL, NULL)), o426) -> f1762_0__init__Load(EOS(STATIC_1762), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, o426, NULL)), java.lang.Object(ObjectList(EOC, o426, NULL)), o427) :|: TRUE && matching1 = 1 f1762_0__init__Load(EOS(STATIC_1762), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, o426, NULL)), java.lang.Object(ObjectList(EOC, o426, NULL)), o427) -> f1763_0__init__Load(EOS(STATIC_1763), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, o426, NULL)), o427, java.lang.Object(ObjectList(EOC, o426, NULL))) :|: TRUE && matching1 = 1 f1763_0__init__Load(EOS(STATIC_1763), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, o426, NULL)), o427, java.lang.Object(ObjectList(EOC, o426, NULL))) -> f1764_0__init__FieldAccess(EOS(STATIC_1764), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, o426, NULL)), java.lang.Object(ObjectList(EOC, o426, NULL)), o427) :|: TRUE && matching1 = 1 f1764_0__init__FieldAccess(EOS(STATIC_1764), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, o426, NULL)), java.lang.Object(ObjectList(EOC, o426, NULL)), o427) -> f1765_0__init__Return(EOS(STATIC_1765), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, o426, o427))) :|: TRUE && matching1 = 1 f1765_0__init__Return(EOS(STATIC_1765), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, o426, o427))) -> f1766_0_duplicate_Store(EOS(STATIC_1766), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, o426, o427))) :|: TRUE && matching1 = 1 f1766_0_duplicate_Store(EOS(STATIC_1766), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, o426, o427))) -> f1767_0_duplicate_Load(EOS(STATIC_1767), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, o426, o427))) :|: TRUE && matching1 = 1 f1767_0_duplicate_Load(EOS(STATIC_1767), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, o426, o427))) -> f1768_0_duplicate_Load(EOS(STATIC_1768), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, o426, o427)), java.lang.Object(ObjectList(EOC, o426, o427))) :|: TRUE && matching1 = 1 f1768_0_duplicate_Load(EOS(STATIC_1768), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, o426, o427)), java.lang.Object(ObjectList(EOC, o426, o427))) -> f1769_0_duplicate_FieldAccess(EOS(STATIC_1769), java.lang.Object(ObjectList(EOC, o426, o427)), 1, java.lang.Object(ObjectList(EOC, o426, o427)), java.lang.Object(ObjectList(EOC, o426, o427))) :|: TRUE && matching1 = 1 f1769_0_duplicate_FieldAccess(EOS(STATIC_1769), java.lang.Object(ObjectList(EOC, o426, o427)), matching1, java.lang.Object(ObjectList(EOC, o426, o427)), java.lang.Object(ObjectList(EOC, o426, o427))) -> f1773_0_duplicate_Load(EOS(STATIC_1773), java.lang.Object(ObjectList(EOC, o426, java.lang.Object(ObjectList(EOC, o426, o427)))), 1) :|: TRUE && matching1 = 1 f1773_0_duplicate_Load(EOS(STATIC_1773), java.lang.Object(ObjectList(EOC, o426, java.lang.Object(ObjectList(EOC, o426, o427)))), matching1) -> f1774_0_duplicate_FieldAccess(EOS(STATIC_1774), 1, java.lang.Object(ObjectList(EOC, o426, java.lang.Object(ObjectList(EOC, o426, o427))))) :|: TRUE && matching1 = 1 f1774_0_duplicate_FieldAccess(EOS(STATIC_1774), matching1, java.lang.Object(ObjectList(EOC, o426, java.lang.Object(ObjectList(EOC, o426, o427))))) -> f1775_0_duplicate_Store(EOS(STATIC_1775), 1, java.lang.Object(ObjectList(EOC, o426, o427))) :|: TRUE && matching1 = 1 f1775_0_duplicate_Store(EOS(STATIC_1775), matching1, java.lang.Object(ObjectList(EOC, o426, o427))) -> f1776_0_duplicate_Load(EOS(STATIC_1776), java.lang.Object(ObjectList(EOC, o426, o427)), 1) :|: TRUE && matching1 = 1 f1776_0_duplicate_Load(EOS(STATIC_1776), java.lang.Object(ObjectList(EOC, o426, o427)), matching1) -> f1777_0_duplicate_NE(EOS(STATIC_1777), java.lang.Object(ObjectList(EOC, o426, o427)), 1) :|: TRUE && matching1 = 1 f1777_0_duplicate_NE(EOS(STATIC_1777), java.lang.Object(ObjectList(EOC, o426, o427)), matching1) -> f1778_0_duplicate_ConstantStackPush(EOS(STATIC_1778), java.lang.Object(ObjectList(EOC, o426, o427))) :|: 1 > 0 && matching1 = 1 f1778_0_duplicate_ConstantStackPush(EOS(STATIC_1778), java.lang.Object(ObjectList(EOC, o426, o427))) -> f1779_0_duplicate_Store(EOS(STATIC_1779), java.lang.Object(ObjectList(EOC, o426, o427)), 0) :|: TRUE f1779_0_duplicate_Store(EOS(STATIC_1779), java.lang.Object(ObjectList(EOC, o426, o427)), matching1) -> f1780_0_duplicate_JMP(EOS(STATIC_1780), java.lang.Object(ObjectList(EOC, o426, o427)), 0) :|: TRUE && matching1 = 0 f1780_0_duplicate_JMP(EOS(STATIC_1780), java.lang.Object(ObjectList(EOC, o426, o427)), matching1) -> f1781_0_duplicate_Load(EOS(STATIC_1781), java.lang.Object(ObjectList(EOC, o426, o427)), 0) :|: TRUE && matching1 = 0 f1781_0_duplicate_Load(EOS(STATIC_1781), java.lang.Object(ObjectList(EOC, o426, o427)), matching1) -> f1722_0_duplicate_Load(EOS(STATIC_1722), java.lang.Object(ObjectList(EOC, o426, o427)), 0) :|: TRUE && matching1 = 0 f1722_0_duplicate_Load(EOS(STATIC_1722), o407, i139) -> f1723_0_duplicate_NULL(EOS(STATIC_1723), o407, i139, o407) :|: TRUE f1733_0_duplicate_EQ(EOS(STATIC_1733), java.lang.Object(o417sub), matching1, matching2) -> f1737_0_duplicate_Load(EOS(STATIC_1737), java.lang.Object(o417sub), 0) :|: TRUE && matching1 = 0 && matching2 = 0 f1737_0_duplicate_Load(EOS(STATIC_1737), java.lang.Object(o417sub), matching1) -> f1741_0_duplicate_FieldAccess(EOS(STATIC_1741), 0, java.lang.Object(o417sub)) :|: TRUE && matching1 = 0 f1741_0_duplicate_FieldAccess(EOS(STATIC_1741), matching1, java.lang.Object(ObjectList(EOC, o423, o424))) -> f1743_0_duplicate_FieldAccess(EOS(STATIC_1743), 0, java.lang.Object(ObjectList(EOC, o423, o424))) :|: TRUE && matching1 = 0 f1743_0_duplicate_FieldAccess(EOS(STATIC_1743), matching1, java.lang.Object(ObjectList(EOC, o423, o424))) -> f1745_0_duplicate_Store(EOS(STATIC_1745), 0, o424) :|: TRUE && matching1 = 0 f1745_0_duplicate_Store(EOS(STATIC_1745), matching1, o424) -> f1747_0_duplicate_Load(EOS(STATIC_1747), o424, 0) :|: TRUE && matching1 = 0 f1747_0_duplicate_Load(EOS(STATIC_1747), o424, matching1) -> f1749_0_duplicate_NE(EOS(STATIC_1749), o424, 0) :|: TRUE && matching1 = 0 f1749_0_duplicate_NE(EOS(STATIC_1749), o424, matching1) -> f1751_0_duplicate_ConstantStackPush(EOS(STATIC_1751), o424) :|: TRUE && matching1 = 0 f1751_0_duplicate_ConstantStackPush(EOS(STATIC_1751), o424) -> f1753_0_duplicate_JMP(EOS(STATIC_1753), o424, 1) :|: TRUE f1753_0_duplicate_JMP(EOS(STATIC_1753), o424, matching1) -> f1755_0_duplicate_Store(EOS(STATIC_1755), o424, 1) :|: TRUE && matching1 = 1 f1755_0_duplicate_Store(EOS(STATIC_1755), o424, matching1) -> f1756_0_duplicate_JMP(EOS(STATIC_1756), o424, 1) :|: TRUE && matching1 = 1 f1756_0_duplicate_JMP(EOS(STATIC_1756), o424, matching1) -> f1758_0_duplicate_Load(EOS(STATIC_1758), o424, 1) :|: TRUE && matching1 = 1 f1758_0_duplicate_Load(EOS(STATIC_1758), o424, matching1) -> f1722_0_duplicate_Load(EOS(STATIC_1722), o424, 1) :|: TRUE && matching1 = 1 Combined rules. Obtained 2 IRulesP rules: f1723_0_duplicate_NULL(EOS(STATIC_1723), java.lang.Object(ObjectList(EOC, o423:0, o424:0)), 0, java.lang.Object(ObjectList(EOC, o423:0, o424:0))) -> f1723_0_duplicate_NULL(EOS(STATIC_1723), o424:0, 1, o424:0) :|: TRUE f1723_0_duplicate_NULL(EOS(STATIC_1723), java.lang.Object(ObjectList(EOC, o426:0, o427:0)), 1, java.lang.Object(ObjectList(EOC, o426:0, o427:0))) -> f1723_0_duplicate_NULL(EOS(STATIC_1723), java.lang.Object(ObjectList(EOC, o426:0, o427:0)), 0, java.lang.Object(ObjectList(EOC, o426:0, o427:0))) :|: TRUE Filtered constant ground arguments: f1723_0_duplicate_NULL(x1, x2, x3, x4) -> f1723_0_duplicate_NULL(x2, x3, x4) EOS(x1) -> EOS ObjectList(x1, x2, x3) -> ObjectList(x2, x3) Filtered duplicate arguments: f1723_0_duplicate_NULL(x1, x2, x3) -> f1723_0_duplicate_NULL(x2, x3) Filtered unneeded arguments: ObjectList(x1, x2) -> ObjectList(x2) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: f1723_0_duplicate_NULL(0, java.lang.Object(ObjectList(o424:0))) -> f1723_0_duplicate_NULL(1, o424:0) f1723_0_duplicate_NULL(1, java.lang.Object(ObjectList(o427:0))) -> f1723_0_duplicate_NULL(0, java.lang.Object(ObjectList(o427:0))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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: *f1723_0_duplicate_NULL(1, java.lang.Object(ObjectList(o427:0))) -> f1723_0_duplicate_NULL(0, java.lang.Object(ObjectList(o427:0))) The graph contains the following edges 2 >= 2 *f1723_0_duplicate_NULL(0, java.lang.Object(ObjectList(o424:0))) -> f1723_0_duplicate_NULL(1, o424:0) The graph contains the following edges 2 > 2 ---------------------------------------- (11) YES ---------------------------------------- (12) 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: ---------------------------------------- (13) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 23 IRulesP rules: f1341_0_createList_LE(EOS(STATIC_1341), i117, i117) -> f1346_0_createList_LE(EOS(STATIC_1346), i117, i117) :|: TRUE f1346_0_createList_LE(EOS(STATIC_1346), i117, i117) -> f1356_0_createList_New(EOS(STATIC_1356), i117) :|: i117 > 0 f1356_0_createList_New(EOS(STATIC_1356), i117) -> f1366_0_createList_Duplicate(EOS(STATIC_1366), i117) :|: TRUE f1366_0_createList_Duplicate(EOS(STATIC_1366), i117) -> f1375_0_createList_New(EOS(STATIC_1375), i117) :|: TRUE f1375_0_createList_New(EOS(STATIC_1375), i117) -> f1390_0_createList_Duplicate(EOS(STATIC_1390), i117) :|: TRUE f1390_0_createList_Duplicate(EOS(STATIC_1390), i117) -> f1408_0_createList_InvokeMethod(EOS(STATIC_1408), i117) :|: TRUE f1408_0_createList_InvokeMethod(EOS(STATIC_1408), i117) -> f1415_0_createList_Load(EOS(STATIC_1415), i117) :|: TRUE f1415_0_createList_Load(EOS(STATIC_1415), i117) -> f1421_0_createList_InvokeMethod(EOS(STATIC_1421), i117) :|: TRUE f1421_0_createList_InvokeMethod(EOS(STATIC_1421), i117) -> f1423_0__init__Load(EOS(STATIC_1423), i117) :|: TRUE f1423_0__init__Load(EOS(STATIC_1423), i117) -> f1432_0__init__InvokeMethod(EOS(STATIC_1432), i117) :|: TRUE f1432_0__init__InvokeMethod(EOS(STATIC_1432), i117) -> f1438_0__init__Load(EOS(STATIC_1438), i117) :|: TRUE f1438_0__init__Load(EOS(STATIC_1438), i117) -> f1444_0__init__Load(EOS(STATIC_1444), i117) :|: TRUE f1444_0__init__Load(EOS(STATIC_1444), i117) -> f1452_0__init__FieldAccess(EOS(STATIC_1452), i117) :|: TRUE f1452_0__init__FieldAccess(EOS(STATIC_1452), i117) -> f1460_0__init__Load(EOS(STATIC_1460), i117) :|: TRUE f1460_0__init__Load(EOS(STATIC_1460), i117) -> f1465_0__init__Load(EOS(STATIC_1465), i117) :|: TRUE f1465_0__init__Load(EOS(STATIC_1465), i117) -> f1472_0__init__FieldAccess(EOS(STATIC_1472), i117) :|: TRUE f1472_0__init__FieldAccess(EOS(STATIC_1472), i117) -> f1479_0__init__Return(EOS(STATIC_1479), i117) :|: TRUE f1479_0__init__Return(EOS(STATIC_1479), i117) -> f1483_0_createList_Store(EOS(STATIC_1483), i117) :|: TRUE f1483_0_createList_Store(EOS(STATIC_1483), i117) -> f1487_0_createList_Inc(EOS(STATIC_1487), i117) :|: TRUE f1487_0_createList_Inc(EOS(STATIC_1487), i117) -> f1490_0_createList_JMP(EOS(STATIC_1490), i117 + -1) :|: TRUE f1490_0_createList_JMP(EOS(STATIC_1490), i127) -> f1509_0_createList_Load(EOS(STATIC_1509), i127) :|: TRUE f1509_0_createList_Load(EOS(STATIC_1509), i127) -> f1327_0_createList_Load(EOS(STATIC_1327), i127) :|: TRUE f1327_0_createList_Load(EOS(STATIC_1327), i110) -> f1341_0_createList_LE(EOS(STATIC_1341), i110, i110) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f1341_0_createList_LE(EOS(STATIC_1341), i117:0, i117:0) -> f1341_0_createList_LE(EOS(STATIC_1341), i117:0 - 1, i117:0 - 1) :|: i117:0 > 0 Filtered constant ground arguments: f1341_0_createList_LE(x1, x2, x3) -> f1341_0_createList_LE(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f1341_0_createList_LE(x1, x2) -> f1341_0_createList_LE(x2) Finished conversion. Obtained 1 rules.P rules: f1341_0_createList_LE(i117:0) -> f1341_0_createList_LE(i117:0 - 1) :|: i117:0 > 0 ---------------------------------------- (14) Obligation: Rules: f1341_0_createList_LE(i117:0) -> f1341_0_createList_LE(i117:0 - 1) :|: i117:0 > 0 ---------------------------------------- (15) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (16) Obligation: Rules: f1341_0_createList_LE(i117:0) -> f1341_0_createList_LE(arith) :|: i117:0 > 0 && arith = i117:0 - 1 ---------------------------------------- (17) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1341_0_createList_LE(i117:0) -> f1341_0_createList_LE(arith) :|: i117:0 > 0 && arith = i117:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (18) Obligation: Termination digraph: Nodes: (1) f1341_0_createList_LE(i117:0) -> f1341_0_createList_LE(arith) :|: i117:0 > 0 && arith = i117:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (19) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (20) Obligation: Rules: f1341_0_createList_LE(i117:0:0) -> f1341_0_createList_LE(i117:0:0 - 1) :|: i117:0:0 > 0 ---------------------------------------- (21) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1341_0_createList_LE(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (22) Obligation: Rules: f1341_0_createList_LE(i117:0:0) -> f1341_0_createList_LE(c) :|: c = i117:0:0 - 1 && i117:0:0 > 0 ---------------------------------------- (23) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f1341_0_createList_LE ] = f1341_0_createList_LE_1 The following rules are decreasing: f1341_0_createList_LE(i117:0:0) -> f1341_0_createList_LE(c) :|: c = i117:0:0 - 1 && i117:0:0 > 0 The following rules are bounded: f1341_0_createList_LE(i117:0:0) -> f1341_0_createList_LE(c) :|: c = i117:0:0 - 1 && i117:0:0 > 0 ---------------------------------------- (24) YES