/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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, 602 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) AND (14) IRSwT (15) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (16) IRSwT (17) TempFilterProof [SOUND, 21 ms] (18) IRSwT (19) IRSwTToQDPProof [SOUND, 0 ms] (20) QDP (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] (22) YES (23) IRSwT (24) IntTRSCompressionProof [EQUIVALENT, 0 ms] (25) IRSwT (26) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (27) IRSwT (28) TempFilterProof [SOUND, 7 ms] (29) IntTRS (30) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (31) YES (32) JBCTerminationSCC (33) SCCToIRSProof [SOUND, 94 ms] (34) IRSwT (35) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (36) IRSwT (37) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (38) IRSwT (39) IntTRSCompressionProof [EQUIVALENT, 0 ms] (40) IRSwT (41) TempFilterProof [SOUND, 37 ms] (42) IntTRS (43) RankingReductionPairProof [EQUIVALENT, 20 ms] (44) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class AppE { AppE next; public static void main(String[] args) { Random.args = args; AppE list = createList(); list.appE(Random.random()); } public void appE(int i) { if (next == null) { if (i <= 0) { return; } else { next = new AppE(); } i--; } next.appE(i); } public static AppE createList() { AppE result = null; int length = Random.random(); while (length > 0) { result = new AppE(result); length--; } return result; } public AppE() { this.next = null; } public AppE(AppE n) { this.next = n; } } 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: public class AppE { AppE next; public static void main(String[] args) { Random.args = args; AppE list = createList(); list.appE(Random.random()); } public void appE(int i) { if (next == null) { if (i <= 0) { return; } else { next = new AppE(); } i--; } next.appE(i); } public static AppE createList() { AppE result = null; int length = Random.random(); while (length > 0) { result = new AppE(result); length--; } return result; } public AppE() { this.next = null; } public AppE(AppE n) { this.next = n; } } 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: AppE.main([Ljava/lang/String;)V: Graph of 118 nodes with 0 SCCs. AppE.createList()LAppE;: Graph of 118 nodes with 1 SCC. AppE.appE(I)V: Graph of 50 nodes with 0 SCCs. ---------------------------------------- (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: AppE.appE(I)V SCC calls the following helper methods: AppE.appE(I)V Performed SCC analyses: *Used field analysis yielded the following read fields: *AppE: [next] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (8) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 36 IRulesP rules: f1623_0_appE_FieldAccess(EOS(STATIC_1623), i171, java.lang.Object(AppE(EOC, o212)), i171, java.lang.Object(AppE(EOC, o212))) -> f1627_0_appE_FieldAccess(EOS(STATIC_1627), i171, java.lang.Object(AppE(EOC, o212)), i171, java.lang.Object(AppE(EOC, o212))) :|: TRUE f1627_0_appE_FieldAccess(EOS(STATIC_1627), i171, java.lang.Object(AppE(EOC, o212)), i171, java.lang.Object(AppE(EOC, o212))) -> f1631_0_appE_NONNULL(EOS(STATIC_1631), i171, java.lang.Object(AppE(EOC, o212)), i171, o212) :|: TRUE f1631_0_appE_NONNULL(EOS(STATIC_1631), i171, java.lang.Object(AppE(EOC, java.lang.Object(o213sub))), i171, java.lang.Object(o213sub)) -> f1634_0_appE_NONNULL(EOS(STATIC_1634), i171, java.lang.Object(AppE(EOC, java.lang.Object(o213sub))), i171, java.lang.Object(o213sub)) :|: TRUE f1631_0_appE_NONNULL(EOS(STATIC_1631), i171, java.lang.Object(AppE(EOC, NULL)), i171, NULL) -> f1635_0_appE_NONNULL(EOS(STATIC_1635), i171, java.lang.Object(AppE(EOC, NULL)), i171, NULL) :|: TRUE f1634_0_appE_NONNULL(EOS(STATIC_1634), i171, java.lang.Object(AppE(EOC, java.lang.Object(o213sub))), i171, java.lang.Object(o213sub)) -> f1639_0_appE_Load(EOS(STATIC_1639), i171, java.lang.Object(AppE(EOC, java.lang.Object(o213sub))), i171) :|: TRUE f1639_0_appE_Load(EOS(STATIC_1639), i171, java.lang.Object(AppE(EOC, java.lang.Object(o213sub))), i171) -> f1644_0_appE_FieldAccess(EOS(STATIC_1644), i171, i171, java.lang.Object(AppE(EOC, java.lang.Object(o213sub)))) :|: TRUE f1644_0_appE_FieldAccess(EOS(STATIC_1644), i171, i171, java.lang.Object(AppE(EOC, java.lang.Object(o213sub)))) -> f1648_0_appE_Load(EOS(STATIC_1648), i171, i171, java.lang.Object(o213sub)) :|: TRUE f1648_0_appE_Load(EOS(STATIC_1648), i171, i171, java.lang.Object(o213sub)) -> f1654_0_appE_InvokeMethod(EOS(STATIC_1654), i171, java.lang.Object(o213sub), i171) :|: TRUE f1654_0_appE_InvokeMethod(EOS(STATIC_1654), i171, java.lang.Object(o213sub), i171) -> f1659_0_appE_Load(EOS(STATIC_1659), i171, java.lang.Object(o213sub), i171) :|: i165 > 1 f1654_0_appE_InvokeMethod(EOS(STATIC_1654), i171, java.lang.Object(o213sub), i171) -> f1659_1_appE_Load(EOS(STATIC_1659), i171, java.lang.Object(o213sub), i171) :|: i165 > 1 f1659_0_appE_Load(EOS(STATIC_1659), i171, java.lang.Object(o213sub), i171) -> f1730_0_appE_Load(EOS(STATIC_1730), i171, java.lang.Object(o213sub), i171) :|: TRUE f1730_0_appE_Load(EOS(STATIC_1730), i171, java.lang.Object(o213sub), i171) -> f1554_0_appE_Load(EOS(STATIC_1554), i171, java.lang.Object(o213sub), i171) :|: TRUE f1554_0_appE_Load(EOS(STATIC_1554), i171, java.lang.Object(o204sub), i171) -> f1623_0_appE_FieldAccess(EOS(STATIC_1623), i171, java.lang.Object(o204sub), i171, java.lang.Object(o204sub)) :|: TRUE f1635_0_appE_NONNULL(EOS(STATIC_1635), i171, java.lang.Object(AppE(EOC, NULL)), i171, NULL) -> f1640_0_appE_Load(EOS(STATIC_1640), i171, java.lang.Object(AppE(EOC, NULL)), i171) :|: TRUE f1640_0_appE_Load(EOS(STATIC_1640), i171, java.lang.Object(AppE(EOC, NULL)), i171) -> f1645_0_appE_GT(EOS(STATIC_1645), i171, java.lang.Object(AppE(EOC, NULL)), i171, i171) :|: TRUE f1645_0_appE_GT(EOS(STATIC_1645), i179, java.lang.Object(AppE(EOC, NULL)), i179, i179) -> f1650_0_appE_GT(EOS(STATIC_1650), i179, java.lang.Object(AppE(EOC, NULL)), i179, i179) :|: TRUE f1650_0_appE_GT(EOS(STATIC_1650), i179, java.lang.Object(AppE(EOC, NULL)), i179, i179) -> f1656_0_appE_Load(EOS(STATIC_1656), i179, java.lang.Object(AppE(EOC, NULL)), i179) :|: i179 > 0 f1656_0_appE_Load(EOS(STATIC_1656), i179, java.lang.Object(AppE(EOC, NULL)), i179) -> f1661_0_appE_New(EOS(STATIC_1661), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL))) :|: TRUE f1661_0_appE_New(EOS(STATIC_1661), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL))) -> f1731_0_appE_Duplicate(EOS(STATIC_1731), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) :|: TRUE f1731_0_appE_Duplicate(EOS(STATIC_1731), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) -> f1761_0_appE_InvokeMethod(EOS(STATIC_1761), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) :|: TRUE f1761_0_appE_InvokeMethod(EOS(STATIC_1761), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) -> f1772_0__init__Load(EOS(STATIC_1772), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) :|: TRUE f1772_0__init__Load(EOS(STATIC_1772), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) -> f3278_0__init__InvokeMethod(EOS(STATIC_3278), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) :|: TRUE f3278_0__init__InvokeMethod(EOS(STATIC_3278), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) -> f3288_0__init__Load(EOS(STATIC_3288), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) :|: TRUE f3288_0__init__Load(EOS(STATIC_3288), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) -> f3296_0__init__ConstantStackPush(EOS(STATIC_3296), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) :|: TRUE f3296_0__init__ConstantStackPush(EOS(STATIC_3296), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) -> f3319_0__init__FieldAccess(EOS(STATIC_3319), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), NULL) :|: TRUE f3319_0__init__FieldAccess(EOS(STATIC_3319), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL)), NULL) -> f3327_0__init__Return(EOS(STATIC_3327), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) :|: TRUE f3327_0__init__Return(EOS(STATIC_3327), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) -> f3349_0_appE_FieldAccess(EOS(STATIC_3349), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) :|: TRUE f3349_0_appE_FieldAccess(EOS(STATIC_3349), i179, java.lang.Object(AppE(EOC, NULL)), i179, java.lang.Object(AppE(EOC, NULL)), java.lang.Object(AppE(EOC, NULL))) -> f3357_0_appE_Inc(EOS(STATIC_3357), i179, java.lang.Object(AppE(EOC, java.lang.Object(AppE(EOC, NULL)))), i179) :|: TRUE f3357_0_appE_Inc(EOS(STATIC_3357), i179, java.lang.Object(AppE(EOC, java.lang.Object(AppE(EOC, NULL)))), i179) -> f3361_0_appE_Load(EOS(STATIC_3361), i179, java.lang.Object(AppE(EOC, java.lang.Object(AppE(EOC, NULL)))), i179 + -1) :|: TRUE f3361_0_appE_Load(EOS(STATIC_3361), i179, java.lang.Object(AppE(EOC, java.lang.Object(AppE(EOC, NULL)))), i362) -> f3363_0_appE_FieldAccess(EOS(STATIC_3363), i179, i362, java.lang.Object(AppE(EOC, java.lang.Object(AppE(EOC, NULL))))) :|: TRUE f3363_0_appE_FieldAccess(EOS(STATIC_3363), i179, i362, java.lang.Object(AppE(EOC, java.lang.Object(AppE(EOC, NULL))))) -> f3366_0_appE_Load(EOS(STATIC_3366), i179, i362, java.lang.Object(AppE(EOC, NULL))) :|: TRUE f3366_0_appE_Load(EOS(STATIC_3366), i179, i362, java.lang.Object(AppE(EOC, NULL))) -> f3370_0_appE_InvokeMethod(EOS(STATIC_3370), i179, java.lang.Object(AppE(EOC, NULL)), i362) :|: TRUE f3370_0_appE_InvokeMethod(EOS(STATIC_3370), i179, java.lang.Object(AppE(EOC, NULL)), i362) -> f3373_0_appE_Load(EOS(STATIC_3373), i362, java.lang.Object(AppE(EOC, NULL)), i362) :|: i179 >= 1 && i165 > 1 && i362 < i179 f3370_0_appE_InvokeMethod(EOS(STATIC_3370), i179, java.lang.Object(AppE(EOC, NULL)), i362) -> f3373_1_appE_Load(EOS(STATIC_3373), i179, java.lang.Object(AppE(EOC, NULL)), i362) :|: i179 >= 1 && i165 > 1 && i362 < i179 f3373_0_appE_Load(EOS(STATIC_3373), i362, java.lang.Object(AppE(EOC, NULL)), i362) -> f3377_0_appE_Load(EOS(STATIC_3377), i362, java.lang.Object(AppE(EOC, NULL)), i362) :|: TRUE f3377_0_appE_Load(EOS(STATIC_3377), i362, java.lang.Object(AppE(EOC, NULL)), i362) -> f1554_0_appE_Load(EOS(STATIC_1554), i362, java.lang.Object(AppE(EOC, NULL)), i362) :|: TRUE Combined rules. Obtained 4 IRulesP rules: f1623_0_appE_FieldAccess(EOS(STATIC_1623), i171:0, java.lang.Object(AppE(EOC, java.lang.Object(o213sub:0))), i171:0, java.lang.Object(AppE(EOC, java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(EOS(STATIC_1623), i171:0, java.lang.Object(o213sub:0), i171:0, java.lang.Object(o213sub:0)) :|: TRUE f1623_0_appE_FieldAccess(EOS(STATIC_1623), i171:0, java.lang.Object(AppE(EOC, NULL)), i171:0, java.lang.Object(AppE(EOC, NULL))) -> f1623_0_appE_FieldAccess(EOS(STATIC_1623), i171:0 - 1, java.lang.Object(AppE(EOC, NULL)), i171:0 - 1, java.lang.Object(AppE(EOC, NULL))) :|: i171:0 > 0 && i165:0 > 1 && i171:0 - 1 < i171:0 Removed following non-SCC rules: f1623_0_appE_FieldAccess(EOS(STATIC_1623), i171:0, java.lang.Object(AppE(EOC, NULL)), i171:0, java.lang.Object(AppE(EOC, NULL))) -> f3373_1_appE_Load(EOS(STATIC_3373), i171:0, java.lang.Object(AppE(EOC, NULL)), i171:0 - 1) :|: i171:0 > 0 && i165:0 > 1 && i171:0 - 1 < i171:0 f1623_0_appE_FieldAccess(EOS(STATIC_1623), i171:0, java.lang.Object(AppE(EOC, java.lang.Object(o213sub:0))), i171:0, java.lang.Object(AppE(EOC, java.lang.Object(o213sub:0)))) -> f1659_1_appE_Load(EOS(STATIC_1659), i171:0, java.lang.Object(o213sub:0), i171:0) :|: TRUE Filtered constant ground arguments: f1623_0_appE_FieldAccess(x1, x2, x3, x4, x5) -> f1623_0_appE_FieldAccess(x2, x3, x4, x5) EOS(x1) -> EOS AppE(x1, x2) -> AppE(x2) Filtered duplicate arguments: f1623_0_appE_FieldAccess(x1, x2, x3, x4) -> f1623_0_appE_FieldAccess(x3, x4) Finished conversion. Obtained 2 rules.P rules: f1623_0_appE_FieldAccess(i171:0, java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(i171:0, java.lang.Object(o213sub:0)) :|: TRUE f1623_0_appE_FieldAccess(i171:0, java.lang.Object(AppE(NULL))) -> f1623_0_appE_FieldAccess(i171:0 - 1, java.lang.Object(AppE(NULL))) :|: i165:0 > 1 && i171:0 - 1 < i171:0 && i171:0 > 0 ---------------------------------------- (9) Obligation: Rules: f1623_0_appE_FieldAccess(i171:0, java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(i171:0, java.lang.Object(o213sub:0)) :|: TRUE f1623_0_appE_FieldAccess(x, java.lang.Object(AppE(NULL))) -> f1623_0_appE_FieldAccess(x - 1, java.lang.Object(AppE(NULL))) :|: x1 > 1 && x - 1 < x && x > 0 ---------------------------------------- (10) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (11) Obligation: Rules: f1623_0_appE_FieldAccess(i171:0, java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(i171:0, java.lang.Object(o213sub:0)) :|: TRUE f1623_0_appE_FieldAccess(x, java.lang.Object(AppE(NULL))) -> f1623_0_appE_FieldAccess(arith, java.lang.Object(AppE(NULL))) :|: x1 > 1 && x - 1 < x && x > 0 && arith = x - 1 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1623_0_appE_FieldAccess(i171:0, java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(i171:0, java.lang.Object(o213sub:0)) :|: TRUE (2) f1623_0_appE_FieldAccess(x, java.lang.Object(AppE(NULL))) -> f1623_0_appE_FieldAccess(arith, java.lang.Object(AppE(NULL))) :|: x1 > 1 && x - 1 < x && x > 0 && arith = x - 1 Arcs: (1) -> (1), (2) (2) -> (2) This digraph is fully evaluated! ---------------------------------------- (13) Complex Obligation (AND) ---------------------------------------- (14) Obligation: Termination digraph: Nodes: (1) f1623_0_appE_FieldAccess(i171:0, java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(i171:0, java.lang.Object(o213sub:0)) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (15) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f1623_0_appE_FieldAccess(x1, x2) -> f1623_0_appE_FieldAccess(x2) ---------------------------------------- (16) Obligation: Rules: f1623_0_appE_FieldAccess(java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(java.lang.Object(o213sub:0)) :|: TRUE ---------------------------------------- (17) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1623_0_appE_FieldAccess(VARIABLE) java.lang.Object(VARIABLE) AppE(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (18) Obligation: Rules: f1623_0_appE_FieldAccess(java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(java.lang.Object(o213sub:0)) ---------------------------------------- (19) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: f1623_0_appE_FieldAccess(java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(java.lang.Object(o213sub:0)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) 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: *f1623_0_appE_FieldAccess(java.lang.Object(AppE(java.lang.Object(o213sub:0)))) -> f1623_0_appE_FieldAccess(java.lang.Object(o213sub:0)) The graph contains the following edges 1 > 1 ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: Termination digraph: Nodes: (1) f1623_0_appE_FieldAccess(x, java.lang.Object(AppE(NULL))) -> f1623_0_appE_FieldAccess(arith, java.lang.Object(AppE(NULL))) :|: x1 > 1 && x - 1 < x && x > 0 && arith = x - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (24) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (25) Obligation: Rules: f1623_0_appE_FieldAccess(x:0, java.lang.Object(AppE(NULL))) -> f1623_0_appE_FieldAccess(x:0 - 1, java.lang.Object(AppE(NULL))) :|: x1:0 > 1 && x:0 - 1 < x:0 && x:0 > 0 ---------------------------------------- (26) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f1623_0_appE_FieldAccess(x1, x2) -> f1623_0_appE_FieldAccess(x1) ---------------------------------------- (27) Obligation: Rules: f1623_0_appE_FieldAccess(x:0) -> f1623_0_appE_FieldAccess(x:0 - 1) :|: x1:0 > 1 && x:0 - 1 < x:0 && x:0 > 0 ---------------------------------------- (28) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1623_0_appE_FieldAccess(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (29) Obligation: Rules: f1623_0_appE_FieldAccess(x:0) -> f1623_0_appE_FieldAccess(c) :|: c = x:0 - 1 && (x1:0 > 1 && x:0 - 1 < x:0 && x:0 > 0) ---------------------------------------- (30) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1623_0_appE_FieldAccess(x)] = x The following rules are decreasing: f1623_0_appE_FieldAccess(x:0) -> f1623_0_appE_FieldAccess(c) :|: c = x:0 - 1 && (x1:0 > 1 && x:0 - 1 < x:0 && x:0 > 0) The following rules are bounded: f1623_0_appE_FieldAccess(x:0) -> f1623_0_appE_FieldAccess(c) :|: c = x:0 - 1 && (x1:0 > 1 && x:0 - 1 < x:0 && x:0 > 0) ---------------------------------------- (31) YES ---------------------------------------- (32) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: AppE.createList()LAppE; 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: ---------------------------------------- (33) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 17 IRulesP rules: f1300_0_createList_LE(EOS(STATIC_1300), i144, i144) -> f1306_0_createList_LE(EOS(STATIC_1306), i144, i144) :|: TRUE f1306_0_createList_LE(EOS(STATIC_1306), i144, i144) -> f1314_0_createList_New(EOS(STATIC_1314), i144) :|: i144 > 0 f1314_0_createList_New(EOS(STATIC_1314), i144) -> f1323_0_createList_Duplicate(EOS(STATIC_1323), i144) :|: TRUE f1323_0_createList_Duplicate(EOS(STATIC_1323), i144) -> f1328_0_createList_Load(EOS(STATIC_1328), i144) :|: TRUE f1328_0_createList_Load(EOS(STATIC_1328), i144) -> f1344_0_createList_InvokeMethod(EOS(STATIC_1344), i144) :|: TRUE f1344_0_createList_InvokeMethod(EOS(STATIC_1344), i144) -> f1379_0__init__Load(EOS(STATIC_1379), i144) :|: TRUE f1379_0__init__Load(EOS(STATIC_1379), i144) -> f1386_0__init__InvokeMethod(EOS(STATIC_1386), i144) :|: TRUE f1386_0__init__InvokeMethod(EOS(STATIC_1386), i144) -> f1390_0__init__Load(EOS(STATIC_1390), i144) :|: TRUE f1390_0__init__Load(EOS(STATIC_1390), i144) -> f1393_0__init__Load(EOS(STATIC_1393), i144) :|: TRUE f1393_0__init__Load(EOS(STATIC_1393), i144) -> f1395_0__init__FieldAccess(EOS(STATIC_1395), i144) :|: TRUE f1395_0__init__FieldAccess(EOS(STATIC_1395), i144) -> f1402_0__init__Return(EOS(STATIC_1402), i144) :|: TRUE f1402_0__init__Return(EOS(STATIC_1402), i144) -> f1406_0_createList_Store(EOS(STATIC_1406), i144) :|: TRUE f1406_0_createList_Store(EOS(STATIC_1406), i144) -> f1412_0_createList_Inc(EOS(STATIC_1412), i144) :|: TRUE f1412_0_createList_Inc(EOS(STATIC_1412), i144) -> f1419_0_createList_JMP(EOS(STATIC_1419), i144 + -1) :|: TRUE f1419_0_createList_JMP(EOS(STATIC_1419), i163) -> f1434_0_createList_Load(EOS(STATIC_1434), i163) :|: TRUE f1434_0_createList_Load(EOS(STATIC_1434), i163) -> f1293_0_createList_Load(EOS(STATIC_1293), i163) :|: TRUE f1293_0_createList_Load(EOS(STATIC_1293), i138) -> f1300_0_createList_LE(EOS(STATIC_1300), i138, i138) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f1300_0_createList_LE(EOS(STATIC_1300), i144:0, i144:0) -> f1300_0_createList_LE(EOS(STATIC_1300), i144:0 - 1, i144:0 - 1) :|: i144:0 > 0 Filtered constant ground arguments: f1300_0_createList_LE(x1, x2, x3) -> f1300_0_createList_LE(x2, x3) EOS(x1) -> EOS Filtered duplicate arguments: f1300_0_createList_LE(x1, x2) -> f1300_0_createList_LE(x2) Finished conversion. Obtained 1 rules.P rules: f1300_0_createList_LE(i144:0) -> f1300_0_createList_LE(i144:0 - 1) :|: i144:0 > 0 ---------------------------------------- (34) Obligation: Rules: f1300_0_createList_LE(i144:0) -> f1300_0_createList_LE(i144:0 - 1) :|: i144:0 > 0 ---------------------------------------- (35) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (36) Obligation: Rules: f1300_0_createList_LE(i144:0) -> f1300_0_createList_LE(arith) :|: i144:0 > 0 && arith = i144:0 - 1 ---------------------------------------- (37) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1300_0_createList_LE(i144:0) -> f1300_0_createList_LE(arith) :|: i144:0 > 0 && arith = i144:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (38) Obligation: Termination digraph: Nodes: (1) f1300_0_createList_LE(i144:0) -> f1300_0_createList_LE(arith) :|: i144:0 > 0 && arith = i144:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (39) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (40) Obligation: Rules: f1300_0_createList_LE(i144:0:0) -> f1300_0_createList_LE(i144:0:0 - 1) :|: i144:0:0 > 0 ---------------------------------------- (41) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1300_0_createList_LE(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (42) Obligation: Rules: f1300_0_createList_LE(i144:0:0) -> f1300_0_createList_LE(c) :|: c = i144:0:0 - 1 && i144:0:0 > 0 ---------------------------------------- (43) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f1300_0_createList_LE ] = f1300_0_createList_LE_1 The following rules are decreasing: f1300_0_createList_LE(i144:0:0) -> f1300_0_createList_LE(c) :|: c = i144:0:0 - 1 && i144:0:0 > 0 The following rules are bounded: f1300_0_createList_LE(i144:0:0) -> f1300_0_createList_LE(c) :|: c = i144:0:0 - 1 && i144:0:0 > 0 ---------------------------------------- (44) YES