/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, 457 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 0 ms] (6) AND (7) JBCTerminationSCC (8) SCCToQDPProof [SOUND, 205 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) JBCTerminationSCC (13) SCCToIRSProof [SOUND, 104 ms] (14) IRSwT (15) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (16) IRSwT (17) IRSwTTerminationDigraphProof [EQUIVALENT, 34 ms] (18) IRSwT (19) IntTRSCompressionProof [EQUIVALENT, 0 ms] (20) IRSwT (21) TempFilterProof [SOUND, 36 ms] (22) IntTRS (23) PolynomialOrderProcessor [EQUIVALENT, 12 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: f1820_0_duplicate_NULL(EOS(STATIC_1820), java.lang.Object(o355sub), i137, java.lang.Object(o355sub)) -> f1823_0_duplicate_NULL(EOS(STATIC_1823), java.lang.Object(o355sub), i137, java.lang.Object(o355sub)) :|: TRUE f1823_0_duplicate_NULL(EOS(STATIC_1823), java.lang.Object(o355sub), i137, java.lang.Object(o355sub)) -> f1826_0_duplicate_Load(EOS(STATIC_1826), java.lang.Object(o355sub), i137) :|: TRUE f1826_0_duplicate_Load(EOS(STATIC_1826), java.lang.Object(o355sub), i137) -> f1830_0_duplicate_EQ(EOS(STATIC_1830), java.lang.Object(o355sub), i137, i137) :|: TRUE f1830_0_duplicate_EQ(EOS(STATIC_1830), java.lang.Object(o355sub), matching1, matching2) -> f1836_0_duplicate_EQ(EOS(STATIC_1836), java.lang.Object(o355sub), 1, 1) :|: TRUE && matching1 = 1 && matching2 = 1 f1830_0_duplicate_EQ(EOS(STATIC_1830), java.lang.Object(o355sub), matching1, matching2) -> f1837_0_duplicate_EQ(EOS(STATIC_1837), java.lang.Object(o355sub), 0, 0) :|: TRUE && matching1 = 0 && matching2 = 0 f1836_0_duplicate_EQ(EOS(STATIC_1836), java.lang.Object(o355sub), matching1, matching2) -> f1854_0_duplicate_New(EOS(STATIC_1854), java.lang.Object(o355sub), 1) :|: 1 > 0 && matching1 = 1 && matching2 = 1 f1854_0_duplicate_New(EOS(STATIC_1854), java.lang.Object(o355sub), matching1) -> f1858_0_duplicate_Duplicate(EOS(STATIC_1858), java.lang.Object(o355sub), 1, java.lang.Object(ObjectList(EOC, NULL, NULL))) :|: TRUE && matching1 = 1 f1858_0_duplicate_Duplicate(EOS(STATIC_1858), java.lang.Object(o355sub), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL))) -> f1863_0_duplicate_Load(EOS(STATIC_1863), java.lang.Object(o355sub), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL))) :|: TRUE && matching1 = 1 f1863_0_duplicate_Load(EOS(STATIC_1863), java.lang.Object(o355sub), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL))) -> f1870_0_duplicate_FieldAccess(EOS(STATIC_1870), java.lang.Object(o355sub), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(o355sub)) :|: TRUE && matching1 = 1 f1870_0_duplicate_FieldAccess(EOS(STATIC_1870), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, o368, o369))) -> f1877_0_duplicate_FieldAccess(EOS(STATIC_1877), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, o368, o369))) :|: TRUE && matching1 = 1 f1877_0_duplicate_FieldAccess(EOS(STATIC_1877), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, o368, o369))) -> f1881_0_duplicate_Load(EOS(STATIC_1881), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368) :|: TRUE && matching1 = 1 f1881_0_duplicate_Load(EOS(STATIC_1881), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368) -> f1885_0_duplicate_FieldAccess(EOS(STATIC_1885), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, java.lang.Object(ObjectList(EOC, o368, o369))) :|: TRUE && matching1 = 1 f1885_0_duplicate_FieldAccess(EOS(STATIC_1885), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, java.lang.Object(ObjectList(EOC, o368, o369))) -> f1890_0_duplicate_InvokeMethod(EOS(STATIC_1890), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369) :|: TRUE && matching1 = 1 f1890_0_duplicate_InvokeMethod(EOS(STATIC_1890), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369) -> f1895_0__init__Load(EOS(STATIC_1895), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369) :|: TRUE && matching1 = 1 f1895_0__init__Load(EOS(STATIC_1895), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369) -> f1901_0__init__InvokeMethod(EOS(STATIC_1901), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369, java.lang.Object(ObjectList(EOC, NULL, NULL))) :|: TRUE && matching1 = 1 f1901_0__init__InvokeMethod(EOS(STATIC_1901), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369, java.lang.Object(ObjectList(EOC, NULL, NULL))) -> f1926_0__init__Load(EOS(STATIC_1926), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369) :|: TRUE && matching1 = 1 f1926_0__init__Load(EOS(STATIC_1926), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369) -> f1927_0__init__Load(EOS(STATIC_1927), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369, java.lang.Object(ObjectList(EOC, NULL, NULL))) :|: TRUE && matching1 = 1 f1927_0__init__Load(EOS(STATIC_1927), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o368, o369, java.lang.Object(ObjectList(EOC, NULL, NULL))) -> f1928_0__init__FieldAccess(EOS(STATIC_1928), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o369, java.lang.Object(ObjectList(EOC, NULL, NULL)), o368) :|: TRUE && matching1 = 1 f1928_0__init__FieldAccess(EOS(STATIC_1928), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, NULL, NULL)), java.lang.Object(ObjectList(EOC, NULL, NULL)), o369, java.lang.Object(ObjectList(EOC, NULL, NULL)), o368) -> f1936_0__init__Load(EOS(STATIC_1936), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, o368, NULL)), java.lang.Object(ObjectList(EOC, o368, NULL)), o369) :|: TRUE && matching1 = 1 f1936_0__init__Load(EOS(STATIC_1936), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, o368, NULL)), java.lang.Object(ObjectList(EOC, o368, NULL)), o369) -> f1939_0__init__Load(EOS(STATIC_1939), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, o368, NULL)), o369, java.lang.Object(ObjectList(EOC, o368, NULL))) :|: TRUE && matching1 = 1 f1939_0__init__Load(EOS(STATIC_1939), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, o368, NULL)), o369, java.lang.Object(ObjectList(EOC, o368, NULL))) -> f1940_0__init__FieldAccess(EOS(STATIC_1940), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, o368, NULL)), java.lang.Object(ObjectList(EOC, o368, NULL)), o369) :|: TRUE && matching1 = 1 f1940_0__init__FieldAccess(EOS(STATIC_1940), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, o368, NULL)), java.lang.Object(ObjectList(EOC, o368, NULL)), o369) -> f1947_0__init__Return(EOS(STATIC_1947), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, o368, o369))) :|: TRUE && matching1 = 1 f1947_0__init__Return(EOS(STATIC_1947), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, o368, o369))) -> f1949_0_duplicate_Store(EOS(STATIC_1949), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, o368, o369))) :|: TRUE && matching1 = 1 f1949_0_duplicate_Store(EOS(STATIC_1949), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, o368, o369))) -> f1951_0_duplicate_Load(EOS(STATIC_1951), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, o368, o369))) :|: TRUE && matching1 = 1 f1951_0_duplicate_Load(EOS(STATIC_1951), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, o368, o369))) -> f1953_0_duplicate_Load(EOS(STATIC_1953), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, o368, o369)), java.lang.Object(ObjectList(EOC, o368, o369))) :|: TRUE && matching1 = 1 f1953_0_duplicate_Load(EOS(STATIC_1953), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, o368, o369)), java.lang.Object(ObjectList(EOC, o368, o369))) -> f1955_0_duplicate_FieldAccess(EOS(STATIC_1955), java.lang.Object(ObjectList(EOC, o368, o369)), 1, java.lang.Object(ObjectList(EOC, o368, o369)), java.lang.Object(ObjectList(EOC, o368, o369))) :|: TRUE && matching1 = 1 f1955_0_duplicate_FieldAccess(EOS(STATIC_1955), java.lang.Object(ObjectList(EOC, o368, o369)), matching1, java.lang.Object(ObjectList(EOC, o368, o369)), java.lang.Object(ObjectList(EOC, o368, o369))) -> f1964_0_duplicate_Load(EOS(STATIC_1964), java.lang.Object(ObjectList(EOC, o368, java.lang.Object(ObjectList(EOC, o368, o369)))), 1) :|: TRUE && matching1 = 1 f1964_0_duplicate_Load(EOS(STATIC_1964), java.lang.Object(ObjectList(EOC, o368, java.lang.Object(ObjectList(EOC, o368, o369)))), matching1) -> f1968_0_duplicate_FieldAccess(EOS(STATIC_1968), 1, java.lang.Object(ObjectList(EOC, o368, java.lang.Object(ObjectList(EOC, o368, o369))))) :|: TRUE && matching1 = 1 f1968_0_duplicate_FieldAccess(EOS(STATIC_1968), matching1, java.lang.Object(ObjectList(EOC, o368, java.lang.Object(ObjectList(EOC, o368, o369))))) -> f1971_0_duplicate_Store(EOS(STATIC_1971), 1, java.lang.Object(ObjectList(EOC, o368, o369))) :|: TRUE && matching1 = 1 f1971_0_duplicate_Store(EOS(STATIC_1971), matching1, java.lang.Object(ObjectList(EOC, o368, o369))) -> f1974_0_duplicate_Load(EOS(STATIC_1974), java.lang.Object(ObjectList(EOC, o368, o369)), 1) :|: TRUE && matching1 = 1 f1974_0_duplicate_Load(EOS(STATIC_1974), java.lang.Object(ObjectList(EOC, o368, o369)), matching1) -> f1978_0_duplicate_NE(EOS(STATIC_1978), java.lang.Object(ObjectList(EOC, o368, o369)), 1) :|: TRUE && matching1 = 1 f1978_0_duplicate_NE(EOS(STATIC_1978), java.lang.Object(ObjectList(EOC, o368, o369)), matching1) -> f1980_0_duplicate_ConstantStackPush(EOS(STATIC_1980), java.lang.Object(ObjectList(EOC, o368, o369))) :|: 1 > 0 && matching1 = 1 f1980_0_duplicate_ConstantStackPush(EOS(STATIC_1980), java.lang.Object(ObjectList(EOC, o368, o369))) -> f1983_0_duplicate_Store(EOS(STATIC_1983), java.lang.Object(ObjectList(EOC, o368, o369)), 0) :|: TRUE f1983_0_duplicate_Store(EOS(STATIC_1983), java.lang.Object(ObjectList(EOC, o368, o369)), matching1) -> f1987_0_duplicate_JMP(EOS(STATIC_1987), java.lang.Object(ObjectList(EOC, o368, o369)), 0) :|: TRUE && matching1 = 0 f1987_0_duplicate_JMP(EOS(STATIC_1987), java.lang.Object(ObjectList(EOC, o368, o369)), matching1) -> f1999_0_duplicate_Load(EOS(STATIC_1999), java.lang.Object(ObjectList(EOC, o368, o369)), 0) :|: TRUE && matching1 = 0 f1999_0_duplicate_Load(EOS(STATIC_1999), java.lang.Object(ObjectList(EOC, o368, o369)), matching1) -> f1818_0_duplicate_Load(EOS(STATIC_1818), java.lang.Object(ObjectList(EOC, o368, o369)), 0) :|: TRUE && matching1 = 0 f1818_0_duplicate_Load(EOS(STATIC_1818), o346, i137) -> f1820_0_duplicate_NULL(EOS(STATIC_1820), o346, i137, o346) :|: TRUE f1837_0_duplicate_EQ(EOS(STATIC_1837), java.lang.Object(o355sub), matching1, matching2) -> f1855_0_duplicate_Load(EOS(STATIC_1855), java.lang.Object(o355sub), 0) :|: TRUE && matching1 = 0 && matching2 = 0 f1855_0_duplicate_Load(EOS(STATIC_1855), java.lang.Object(o355sub), matching1) -> f1860_0_duplicate_FieldAccess(EOS(STATIC_1860), 0, java.lang.Object(o355sub)) :|: TRUE && matching1 = 0 f1860_0_duplicate_FieldAccess(EOS(STATIC_1860), matching1, java.lang.Object(ObjectList(EOC, o365, o366))) -> f1868_0_duplicate_FieldAccess(EOS(STATIC_1868), 0, java.lang.Object(ObjectList(EOC, o365, o366))) :|: TRUE && matching1 = 0 f1868_0_duplicate_FieldAccess(EOS(STATIC_1868), matching1, java.lang.Object(ObjectList(EOC, o365, o366))) -> f1872_0_duplicate_Store(EOS(STATIC_1872), 0, o366) :|: TRUE && matching1 = 0 f1872_0_duplicate_Store(EOS(STATIC_1872), matching1, o366) -> f1879_0_duplicate_Load(EOS(STATIC_1879), o366, 0) :|: TRUE && matching1 = 0 f1879_0_duplicate_Load(EOS(STATIC_1879), o366, matching1) -> f1883_0_duplicate_NE(EOS(STATIC_1883), o366, 0) :|: TRUE && matching1 = 0 f1883_0_duplicate_NE(EOS(STATIC_1883), o366, matching1) -> f1887_0_duplicate_ConstantStackPush(EOS(STATIC_1887), o366) :|: TRUE && matching1 = 0 f1887_0_duplicate_ConstantStackPush(EOS(STATIC_1887), o366) -> f1892_0_duplicate_JMP(EOS(STATIC_1892), o366, 1) :|: TRUE f1892_0_duplicate_JMP(EOS(STATIC_1892), o366, matching1) -> f1897_0_duplicate_Store(EOS(STATIC_1897), o366, 1) :|: TRUE && matching1 = 1 f1897_0_duplicate_Store(EOS(STATIC_1897), o366, matching1) -> f1899_0_duplicate_JMP(EOS(STATIC_1899), o366, 1) :|: TRUE && matching1 = 1 f1899_0_duplicate_JMP(EOS(STATIC_1899), o366, matching1) -> f1914_0_duplicate_Load(EOS(STATIC_1914), o366, 1) :|: TRUE && matching1 = 1 f1914_0_duplicate_Load(EOS(STATIC_1914), o366, matching1) -> f1818_0_duplicate_Load(EOS(STATIC_1818), o366, 1) :|: TRUE && matching1 = 1 Combined rules. Obtained 2 IRulesP rules: f1820_0_duplicate_NULL(EOS(STATIC_1820), java.lang.Object(ObjectList(EOC, o368:0, o369:0)), 1, java.lang.Object(ObjectList(EOC, o368:0, o369:0))) -> f1820_0_duplicate_NULL(EOS(STATIC_1820), java.lang.Object(ObjectList(EOC, o368:0, o369:0)), 0, java.lang.Object(ObjectList(EOC, o368:0, o369:0))) :|: TRUE f1820_0_duplicate_NULL(EOS(STATIC_1820), java.lang.Object(ObjectList(EOC, o365:0, o366:0)), 0, java.lang.Object(ObjectList(EOC, o365:0, o366:0))) -> f1820_0_duplicate_NULL(EOS(STATIC_1820), o366:0, 1, o366:0) :|: TRUE Filtered constant ground arguments: f1820_0_duplicate_NULL(x1, x2, x3, x4) -> f1820_0_duplicate_NULL(x2, x3, x4) EOS(x1) -> EOS ObjectList(x1, x2, x3) -> ObjectList(x2, x3) Filtered duplicate arguments: f1820_0_duplicate_NULL(x1, x2, x3) -> f1820_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: f1820_0_duplicate_NULL(1, java.lang.Object(ObjectList(o369:0))) -> f1820_0_duplicate_NULL(0, java.lang.Object(ObjectList(o369:0))) f1820_0_duplicate_NULL(0, java.lang.Object(ObjectList(o366:0))) -> f1820_0_duplicate_NULL(1, o366: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: *f1820_0_duplicate_NULL(0, java.lang.Object(ObjectList(o366:0))) -> f1820_0_duplicate_NULL(1, o366:0) The graph contains the following edges 2 > 2 *f1820_0_duplicate_NULL(1, java.lang.Object(ObjectList(o369:0))) -> f1820_0_duplicate_NULL(0, java.lang.Object(ObjectList(o369: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: f1525_0_createList_LE(EOS(STATIC_1525), i117, i117) -> f1533_0_createList_LE(EOS(STATIC_1533), i117, i117) :|: TRUE f1533_0_createList_LE(EOS(STATIC_1533), i117, i117) -> f1545_0_createList_New(EOS(STATIC_1545), i117) :|: i117 > 0 f1545_0_createList_New(EOS(STATIC_1545), i117) -> f1551_0_createList_Duplicate(EOS(STATIC_1551), i117) :|: TRUE f1551_0_createList_Duplicate(EOS(STATIC_1551), i117) -> f1561_0_createList_New(EOS(STATIC_1561), i117) :|: TRUE f1561_0_createList_New(EOS(STATIC_1561), i117) -> f1612_0_createList_Duplicate(EOS(STATIC_1612), i117) :|: TRUE f1612_0_createList_Duplicate(EOS(STATIC_1612), i117) -> f1638_0_createList_InvokeMethod(EOS(STATIC_1638), i117) :|: TRUE f1638_0_createList_InvokeMethod(EOS(STATIC_1638), i117) -> f1640_0_createList_Load(EOS(STATIC_1640), i117) :|: TRUE f1640_0_createList_Load(EOS(STATIC_1640), i117) -> f1642_0_createList_InvokeMethod(EOS(STATIC_1642), i117) :|: TRUE f1642_0_createList_InvokeMethod(EOS(STATIC_1642), i117) -> f1643_0__init__Load(EOS(STATIC_1643), i117) :|: TRUE f1643_0__init__Load(EOS(STATIC_1643), i117) -> f1646_0__init__InvokeMethod(EOS(STATIC_1646), i117) :|: TRUE f1646_0__init__InvokeMethod(EOS(STATIC_1646), i117) -> f1648_0__init__Load(EOS(STATIC_1648), i117) :|: TRUE f1648_0__init__Load(EOS(STATIC_1648), i117) -> f1650_0__init__Load(EOS(STATIC_1650), i117) :|: TRUE f1650_0__init__Load(EOS(STATIC_1650), i117) -> f1653_0__init__FieldAccess(EOS(STATIC_1653), i117) :|: TRUE f1653_0__init__FieldAccess(EOS(STATIC_1653), i117) -> f1659_0__init__Load(EOS(STATIC_1659), i117) :|: TRUE f1659_0__init__Load(EOS(STATIC_1659), i117) -> f1661_0__init__Load(EOS(STATIC_1661), i117) :|: TRUE f1661_0__init__Load(EOS(STATIC_1661), i117) -> f1666_0__init__FieldAccess(EOS(STATIC_1666), i117) :|: TRUE f1666_0__init__FieldAccess(EOS(STATIC_1666), i117) -> f1677_0__init__Return(EOS(STATIC_1677), i117) :|: TRUE f1677_0__init__Return(EOS(STATIC_1677), i117) -> f1684_0_createList_Store(EOS(STATIC_1684), i117) :|: TRUE f1684_0_createList_Store(EOS(STATIC_1684), i117) -> f1690_0_createList_Inc(EOS(STATIC_1690), i117) :|: TRUE f1690_0_createList_Inc(EOS(STATIC_1690), i117) -> f1695_0_createList_JMP(EOS(STATIC_1695), i117 + -1) :|: TRUE f1695_0_createList_JMP(EOS(STATIC_1695), i127) -> f1700_0_createList_Load(EOS(STATIC_1700), i127) :|: TRUE f1700_0_createList_Load(EOS(STATIC_1700), i127) -> f1479_0_createList_Load(EOS(STATIC_1479), i127) :|: TRUE f1479_0_createList_Load(EOS(STATIC_1479), i110) -> f1525_0_createList_LE(EOS(STATIC_1525), i110, i110) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f1525_0_createList_LE(EOS(STATIC_1525), i117:0, i117:0) -> f1525_0_createList_LE(EOS(STATIC_1525), i117:0 - 1, i117:0 - 1) :|: i117:0 > 0 Filtered constant ground arguments: f1525_0_createList_LE(x1, x2, x3) -> f1525_0_createList_LE(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f1525_0_createList_LE(x1, x2) -> f1525_0_createList_LE(x2) Finished conversion. Obtained 1 rules.P rules: f1525_0_createList_LE(i117:0) -> f1525_0_createList_LE(i117:0 - 1) :|: i117:0 > 0 ---------------------------------------- (14) Obligation: Rules: f1525_0_createList_LE(i117:0) -> f1525_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: f1525_0_createList_LE(i117:0) -> f1525_0_createList_LE(arith) :|: i117:0 > 0 && arith = i117:0 - 1 ---------------------------------------- (17) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1525_0_createList_LE(i117:0) -> f1525_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) f1525_0_createList_LE(i117:0) -> f1525_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: f1525_0_createList_LE(i117:0:0) -> f1525_0_createList_LE(i117:0:0 - 1) :|: i117:0:0 > 0 ---------------------------------------- (21) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1525_0_createList_LE(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (22) Obligation: Rules: f1525_0_createList_LE(i117:0:0) -> f1525_0_createList_LE(c) :|: c = i117:0:0 - 1 && i117:0:0 > 0 ---------------------------------------- (23) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1525_0_createList_LE(x)] = x The following rules are decreasing: f1525_0_createList_LE(i117:0:0) -> f1525_0_createList_LE(c) :|: c = i117:0:0 - 1 && i117:0:0 > 0 The following rules are bounded: f1525_0_createList_LE(i117:0:0) -> f1525_0_createList_LE(c) :|: c = i117:0:0 - 1 && i117:0:0 > 0 ---------------------------------------- (24) YES