/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, 1362 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 16 ms] (6) AND (7) JBCTerminationSCC (8) SCCToIRSProof [SOUND, 113 ms] (9) IRSwT (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (11) IRSwT (12) IRSwTTerminationDigraphProof [EQUIVALENT, 7 ms] (13) IRSwT (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] (15) IRSwT (16) TempFilterProof [SOUND, 1 ms] (17) IRSwT (18) IRSwTToQDPProof [SOUND, 0 ms] (19) QDP (20) QDPSizeChangeProof [EQUIVALENT, 0 ms] (21) YES (22) JBCTerminationSCC (23) SCCToQDPProof [SOUND, 110 ms] (24) QDP (25) QDPSizeChangeProof [EQUIVALENT, 0 ms] (26) YES (27) JBCTerminationSCC (28) SCCToIRSProof [SOUND, 164 ms] (29) IRSwT (30) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (31) IRSwT (32) IRSwTTerminationDigraphProof [EQUIVALENT, 116 ms] (33) IRSwT (34) IntTRSCompressionProof [EQUIVALENT, 0 ms] (35) IRSwT (36) TempFilterProof [SOUND, 30 ms] (37) IntTRS (38) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (39) IntTRS (40) RankingReductionPairProof [EQUIVALENT, 0 ms] (41) YES (42) JBCTerminationSCC (43) SCCToIRSProof [SOUND, 58 ms] (44) IRSwT (45) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (46) IRSwT (47) IRSwTTerminationDigraphProof [EQUIVALENT, 11 ms] (48) IRSwT (49) IntTRSCompressionProof [EQUIVALENT, 0 ms] (50) IRSwT (51) TempFilterProof [SOUND, 6 ms] (52) IntTRS (53) RankingReductionPairProof [EQUIVALENT, 0 ms] (54) YES (55) JBCTerminationSCC (56) SCCToIRSProof [SOUND, 29 ms] (57) IRSwT (58) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (59) IRSwT (60) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (61) IRSwT (62) IntTRSCompressionProof [EQUIVALENT, 0 ms] (63) IRSwT (64) TempFilterProof [SOUND, 6 ms] (65) IntTRS (66) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (67) YES (68) JBCTerminationSCC (69) SCCToIRSProof [SOUND, 49 ms] (70) IRSwT (71) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (72) IRSwT (73) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (74) IRSwT (75) IntTRSCompressionProof [EQUIVALENT, 0 ms] (76) IRSwT (77) TempFilterProof [SOUND, 33 ms] (78) IntTRS (79) RankingReductionPairProof [EQUIVALENT, 0 ms] (80) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class Test8 { public static void main(String[] args) { List[] ls = { List.mk(args.length), List.mk(args.length), List.mk(args.length) }; test(ls, ls.length - 1); } private static void test(List[] ls, int start) { if (start >= 0) { int len = length(ls[start]); for (int i = 0; i < len; i++) bubble(ls[start]); test(ls, start - 1); } } private static void bubble(List l) { if (l == null || l.getTail() == null) return; if (l.head > l.getTail().head) { int temp = l.head; l.head = l.getTail().head; l.getTail().head = temp; } bubble(l.getTail()); } private static int length(List list) { if (list == null) return 0; else return 1 + length(list.getTail()); } } public class List { public int head; private List tail; public List(int head, List tail) { this.head = head; this.tail = tail; } public List getTail() { return tail; } public static List mk(int len) { List result = null; while (len-- > 0) result = new List(len, result); return result; } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class Test8 { public static void main(String[] args) { List[] ls = { List.mk(args.length), List.mk(args.length), List.mk(args.length) }; test(ls, ls.length - 1); } private static void test(List[] ls, int start) { if (start >= 0) { int len = length(ls[start]); for (int i = 0; i < len; i++) bubble(ls[start]); test(ls, start - 1); } } private static void bubble(List l) { if (l == null || l.getTail() == null) return; if (l.head > l.getTail().head) { int temp = l.head; l.head = l.getTail().head; l.getTail().head = temp; } bubble(l.getTail()); } private static int length(List list) { if (list == null) return 0; else return 1 + length(list.getTail()); } } public class List { public int head; private List tail; public List(int head, List tail) { this.head = head; this.tail = tail; } public List getTail() { return tail; } public static List mk(int len) { List result = null; while (len-- > 0) result = new List(len, result); return result; } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: Test8.main([Ljava/lang/String;)V: Graph of 266 nodes with 3 SCCs. Test8.test([LList;I)V: Graph of 87 nodes with 1 SCC. Test8.length(LList;)I: Graph of 31 nodes with 0 SCCs. Test8.bubble(LList;)V: Graph of 67 nodes with 0 SCCs. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 6 SCCss. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Test8.bubble(LList;)V SCC calls the following helper methods: Test8.bubble(LList;)V Performed SCC analyses: *Used field analysis yielded the following read fields: *List: [tail, head] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (8) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 57 IRulesP rules: f4616_0_bubble_NULL(EOS(STATIC_4616), java.lang.Object(o2233sub), java.lang.Object(o2233sub)) -> f4619_0_bubble_NULL(EOS(STATIC_4619), java.lang.Object(o2233sub), java.lang.Object(o2233sub)) :|: TRUE f4619_0_bubble_NULL(EOS(STATIC_4619), java.lang.Object(o2233sub), java.lang.Object(o2233sub)) -> f4623_0_bubble_Load(EOS(STATIC_4623), java.lang.Object(o2233sub)) :|: TRUE f4623_0_bubble_Load(EOS(STATIC_4623), java.lang.Object(o2233sub)) -> f4626_0_bubble_InvokeMethod(EOS(STATIC_4626), java.lang.Object(o2233sub), java.lang.Object(o2233sub)) :|: TRUE f4626_0_bubble_InvokeMethod(EOS(STATIC_4626), java.lang.Object(o2233sub), java.lang.Object(o2233sub)) -> f4628_0_getTail_Load(EOS(STATIC_4628), java.lang.Object(o2233sub), java.lang.Object(o2233sub)) :|: TRUE f4628_0_getTail_Load(EOS(STATIC_4628), java.lang.Object(o2233sub), java.lang.Object(o2233sub)) -> f4635_0_getTail_FieldAccess(EOS(STATIC_4635), java.lang.Object(o2233sub), java.lang.Object(o2233sub)) :|: TRUE f4635_0_getTail_FieldAccess(EOS(STATIC_4635), java.lang.Object(List(EOC, o2251, i1618)), java.lang.Object(List(EOC, o2251, i1618))) -> f4637_0_getTail_FieldAccess(EOS(STATIC_4637), java.lang.Object(List(EOC, o2251, i1618)), java.lang.Object(List(EOC, o2251, i1618))) :|: TRUE f4637_0_getTail_FieldAccess(EOS(STATIC_4637), java.lang.Object(List(EOC, o2251, i1618)), java.lang.Object(List(EOC, o2251, i1618))) -> f4639_0_getTail_Return(EOS(STATIC_4639), java.lang.Object(List(EOC, o2251, i1618)), o2251) :|: TRUE f4639_0_getTail_Return(EOS(STATIC_4639), java.lang.Object(List(EOC, o2251, i1618)), o2251) -> f4642_0_bubble_NONNULL(EOS(STATIC_4642), java.lang.Object(List(EOC, o2251, i1618)), o2251) :|: TRUE f4642_0_bubble_NONNULL(EOS(STATIC_4642), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), java.lang.Object(o2264sub)) -> f4644_0_bubble_NONNULL(EOS(STATIC_4644), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), java.lang.Object(o2264sub)) :|: TRUE f4644_0_bubble_NONNULL(EOS(STATIC_4644), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), java.lang.Object(o2264sub)) -> f4647_0_bubble_Load(EOS(STATIC_4647), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) :|: TRUE f4647_0_bubble_Load(EOS(STATIC_4647), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) -> f4651_0_bubble_FieldAccess(EOS(STATIC_4651), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) :|: TRUE f4651_0_bubble_FieldAccess(EOS(STATIC_4651), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) -> f4654_0_bubble_Load(EOS(STATIC_4654), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618) :|: TRUE f4654_0_bubble_Load(EOS(STATIC_4654), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618) -> f4657_0_bubble_InvokeMethod(EOS(STATIC_4657), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) :|: TRUE f4657_0_bubble_InvokeMethod(EOS(STATIC_4657), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) -> f4660_0_getTail_Load(EOS(STATIC_4660), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) :|: TRUE f4660_0_getTail_Load(EOS(STATIC_4660), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) -> f4665_0_getTail_FieldAccess(EOS(STATIC_4665), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) :|: TRUE f4665_0_getTail_FieldAccess(EOS(STATIC_4665), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618))) -> f4668_0_getTail_Return(EOS(STATIC_4668), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(o2264sub)) :|: TRUE f4668_0_getTail_Return(EOS(STATIC_4668), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(o2264sub)) -> f4671_0_bubble_FieldAccess(EOS(STATIC_4671), java.lang.Object(List(EOC, java.lang.Object(o2264sub), i1618)), i1618, java.lang.Object(o2264sub)) :|: TRUE f4671_0_bubble_FieldAccess(EOS(STATIC_4671), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, o2278, i1626))) -> f4672_0_bubble_FieldAccess(EOS(STATIC_4672), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, o2278, i1626))) :|: TRUE f4672_0_bubble_FieldAccess(EOS(STATIC_4672), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, o2278, i1626))) -> f4673_0_bubble_LE(EOS(STATIC_4673), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, i1626) :|: TRUE f4673_0_bubble_LE(EOS(STATIC_4673), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, i1626) -> f4676_0_bubble_LE(EOS(STATIC_4676), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, i1626) :|: i1618 <= i1626 f4673_0_bubble_LE(EOS(STATIC_4673), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, i1626) -> f4677_0_bubble_LE(EOS(STATIC_4677), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, i1626) :|: i1618 > i1626 f4676_0_bubble_LE(EOS(STATIC_4676), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, i1626) -> f4681_0_bubble_Load(EOS(STATIC_4681), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: i1618 <= i1626 f4681_0_bubble_Load(EOS(STATIC_4681), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4686_0_bubble_InvokeMethod(EOS(STATIC_4686), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: TRUE f4686_0_bubble_InvokeMethod(EOS(STATIC_4686), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4691_0_getTail_Load(EOS(STATIC_4691), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: TRUE f4691_0_getTail_Load(EOS(STATIC_4691), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4696_0_getTail_FieldAccess(EOS(STATIC_4696), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: TRUE f4696_0_getTail_FieldAccess(EOS(STATIC_4696), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4700_0_getTail_Return(EOS(STATIC_4700), java.lang.Object(List(EOC, o2278, i1626))) :|: TRUE f4700_0_getTail_Return(EOS(STATIC_4700), java.lang.Object(List(EOC, o2278, i1626))) -> f4766_0_getTail_Return(EOS(STATIC_4766), java.lang.Object(List(EOC, o2278, i1626))) :|: TRUE f4766_0_getTail_Return(EOS(STATIC_4766), java.lang.Object(List(EOC, o2278, i1618))) -> f4769_0_bubble_InvokeMethod(EOS(STATIC_4769), java.lang.Object(List(EOC, o2278, i1618))) :|: TRUE f4769_0_bubble_InvokeMethod(EOS(STATIC_4769), java.lang.Object(List(EOC, o2278, i1618))) -> f4772_0_bubble_Load(EOS(STATIC_4772), java.lang.Object(List(EOC, o2278, i1618))) :|: TRUE f4769_0_bubble_InvokeMethod(EOS(STATIC_4769), java.lang.Object(List(EOC, o2278, i1618))) -> f4772_1_bubble_Load(EOS(STATIC_4772), java.lang.Object(List(EOC, o2278, i1618))) :|: TRUE f4772_0_bubble_Load(EOS(STATIC_4772), java.lang.Object(List(EOC, o2278, i1618))) -> f4775_0_bubble_Load(EOS(STATIC_4775), java.lang.Object(List(EOC, o2278, i1618))) :|: TRUE f4775_0_bubble_Load(EOS(STATIC_4775), java.lang.Object(List(EOC, o2278, i1618))) -> f4781_0_bubble_Load(EOS(STATIC_4781), java.lang.Object(List(EOC, o2278, i1618))) :|: TRUE f4781_0_bubble_Load(EOS(STATIC_4781), java.lang.Object(List(EOC, o2278, i1618))) -> f4614_0_bubble_Load(EOS(STATIC_4614), java.lang.Object(List(EOC, o2278, i1618))) :|: TRUE f4614_0_bubble_Load(EOS(STATIC_4614), o2222) -> f4616_0_bubble_NULL(EOS(STATIC_4616), o2222, o2222) :|: TRUE f4677_0_bubble_LE(EOS(STATIC_4677), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, i1626) -> f4682_0_bubble_Load(EOS(STATIC_4682), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: i1618 > i1626 f4682_0_bubble_Load(EOS(STATIC_4682), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4687_0_bubble_FieldAccess(EOS(STATIC_4687), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: TRUE f4687_0_bubble_FieldAccess(EOS(STATIC_4687), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4692_0_bubble_Store(EOS(STATIC_4692), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618) :|: TRUE f4692_0_bubble_Store(EOS(STATIC_4692), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618) -> f4694_0_bubble_Load(EOS(STATIC_4694), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618) :|: TRUE f4694_0_bubble_Load(EOS(STATIC_4694), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618) -> f4697_0_bubble_Load(EOS(STATIC_4697), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: TRUE f4697_0_bubble_Load(EOS(STATIC_4697), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4701_0_bubble_InvokeMethod(EOS(STATIC_4701), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: TRUE f4701_0_bubble_InvokeMethod(EOS(STATIC_4701), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4705_0_getTail_Load(EOS(STATIC_4705), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: TRUE f4705_0_getTail_Load(EOS(STATIC_4705), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4712_0_getTail_FieldAccess(EOS(STATIC_4712), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) :|: TRUE f4712_0_getTail_FieldAccess(EOS(STATIC_4712), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618))) -> f4715_0_getTail_Return(EOS(STATIC_4715), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, o2278, i1626))) :|: TRUE f4715_0_getTail_Return(EOS(STATIC_4715), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, o2278, i1626))) -> f4718_0_bubble_FieldAccess(EOS(STATIC_4718), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, o2278, i1626))) :|: TRUE f4718_0_bubble_FieldAccess(EOS(STATIC_4718), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), java.lang.Object(List(EOC, o2278, i1626))) -> f4721_0_bubble_FieldAccess(EOS(STATIC_4721), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1626) :|: TRUE f4721_0_bubble_FieldAccess(EOS(STATIC_4721), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1618)), i1626) -> f4726_0_bubble_Load(EOS(STATIC_4726), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618) :|: TRUE f4726_0_bubble_Load(EOS(STATIC_4726), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618) -> f4728_0_bubble_InvokeMethod(EOS(STATIC_4728), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626))) :|: TRUE f4728_0_bubble_InvokeMethod(EOS(STATIC_4728), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626))) -> f4730_0_getTail_Load(EOS(STATIC_4730), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626))) :|: TRUE f4730_0_getTail_Load(EOS(STATIC_4730), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626))) -> f4738_0_getTail_FieldAccess(EOS(STATIC_4738), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626))) :|: TRUE f4738_0_getTail_FieldAccess(EOS(STATIC_4738), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626))) -> f4744_0_getTail_Return(EOS(STATIC_4744), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, o2278, i1626))) :|: TRUE f4744_0_getTail_Return(EOS(STATIC_4744), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, o2278, i1626))) -> f4748_0_bubble_Load(EOS(STATIC_4748), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, o2278, i1626))) :|: TRUE f4748_0_bubble_Load(EOS(STATIC_4748), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), i1618, java.lang.Object(List(EOC, o2278, i1626))) -> f4750_0_bubble_FieldAccess(EOS(STATIC_4750), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), java.lang.Object(List(EOC, o2278, i1626)), i1618) :|: TRUE f4750_0_bubble_FieldAccess(EOS(STATIC_4750), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1626)), i1626)), java.lang.Object(List(EOC, o2278, i1626)), i1618) -> f4752_0_bubble_Load(EOS(STATIC_4752), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1618)), i1626))) :|: TRUE f4752_0_bubble_Load(EOS(STATIC_4752), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1618)), i1626))) -> f4755_0_bubble_InvokeMethod(EOS(STATIC_4755), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1618)), i1626))) :|: TRUE f4755_0_bubble_InvokeMethod(EOS(STATIC_4755), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1618)), i1626))) -> f4758_0_getTail_Load(EOS(STATIC_4758), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1618)), i1626))) :|: TRUE f4758_0_getTail_Load(EOS(STATIC_4758), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1618)), i1626))) -> f4763_0_getTail_FieldAccess(EOS(STATIC_4763), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1618)), i1626))) :|: TRUE f4763_0_getTail_FieldAccess(EOS(STATIC_4763), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278, i1618)), i1626))) -> f4766_0_getTail_Return(EOS(STATIC_4766), java.lang.Object(List(EOC, o2278, i1618))) :|: TRUE Combined rules. Obtained 3 IRulesP rules: f4769_0_bubble_InvokeMethod(EOS(STATIC_4769), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278:0, i1626:0)), i1618:0))) -> f4769_0_bubble_InvokeMethod(EOS(STATIC_4769), java.lang.Object(List(EOC, o2278:0, i1618:0))) :|: i1626:0 < i1618:0 f4769_0_bubble_InvokeMethod(EOS(STATIC_4769), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2278:0, i1626:0)), i1618:0))) -> f4769_0_bubble_InvokeMethod(EOS(STATIC_4769), java.lang.Object(List(EOC, o2278:0, i1626:0))) :|: i1626:0 >= i1618:0 Removed following non-SCC rules: f4769_0_bubble_InvokeMethod(EOS(STATIC_4769), java.lang.Object(List(EOC, o2278:0, i1618:0))) -> f4772_1_bubble_Load(EOS(STATIC_4772), java.lang.Object(List(EOC, o2278:0, i1618:0))) :|: TRUE Filtered constant ground arguments: f4769_0_bubble_InvokeMethod(x1, x2) -> f4769_0_bubble_InvokeMethod(x2) EOS(x1) -> EOS List(x1, x2, x3) -> List(x2, x3) Finished conversion. Obtained 2 rules.P rules: f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0, i1626:0)), i1618:0)), i1618:0) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0, i1618:0)), i1618:0) :|: i1626:0 < i1618:0 f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0, i1626:0)), i1618:0)), i1618:0) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0, i1626:0)), i1626:0) :|: i1626:0 >= i1618:0 ---------------------------------------- (9) Obligation: Rules: f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0, i1626:0)), i1618:0)), i1618:0) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0, i1618:0)), i1618:0) :|: i1626:0 < i1618:0 f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(x, x1)), x2)), x2) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(x, x1)), x1) :|: x1 >= x2 ---------------------------------------- (10) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (11) Obligation: Rules: f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0, i1626:0)), i1618:0)), i1618:0) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0, i1618:0)), i1618:0) :|: i1626:0 < i1618:0 f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(x, x1)), x2)), x2) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(x, x1)), x1) :|: x1 >= x2 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0, i1626:0)), i1618:0)), i1618:0) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0, i1618:0)), i1618:0) :|: i1626:0 < i1618:0 (2) f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(x, x1)), x2)), x2) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(x, x1)), x1) :|: x1 >= x2 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (13) Obligation: Termination digraph: Nodes: (1) f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0, i1626:0)), i1618:0)), i1618:0) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0, i1618:0)), i1618:0) :|: i1626:0 < i1618:0 (2) f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(x, x1)), x2)), x2) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(x, x1)), x1) :|: x1 >= x2 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (14) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (15) Obligation: Rules: f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0:0, i1626:0:0)), i1618:0:0)), i1618:0:0) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0:0, i1618:0:0)), i1618:0:0) :|: i1626:0:0 < i1618:0:0 f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(x:0, x1:0)), x2:0)), x2:0) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(x:0, x1:0)), x1:0) :|: x2:0 <= x1:0 ---------------------------------------- (16) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f4769_0_bubble_InvokeMethod(VARIABLE, INTEGER) java.lang.Object(VARIABLE) List(VARIABLE, INTEGER) Removed predefined arithmetic. ---------------------------------------- (17) Obligation: Rules: f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0:0))))) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0:0))) ---------------------------------------- (18) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0:0))))) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0:0))) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (20) 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: *f4769_0_bubble_InvokeMethod(java.lang.Object(List(java.lang.Object(List(o2278:0:0))))) -> f4769_0_bubble_InvokeMethod(java.lang.Object(List(o2278:0:0))) The graph contains the following edges 1 > 1 ---------------------------------------- (21) YES ---------------------------------------- (22) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Test8.length(LList;)I SCC calls the following helper methods: Test8.length(LList;)I Performed SCC analyses: *Used field analysis yielded the following read fields: *List: [tail] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (23) SCCToQDPProof (SOUND) Transformed TerminationGraph SCC to QDP. Log: Generated 15 rules for P and 29 rules for R.P rules: f4497_0_length_NONNULL(EOS(STATIC_4497), java.lang.Object(o1921sub), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4500_0_length_NONNULL(EOS(STATIC_4500), java.lang.Object(o1921sub), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4500_0_length_NONNULL(EOS(STATIC_4500), java.lang.Object(o1921sub), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4504_0_length_ConstantStackPush(EOS(STATIC_4504), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4504_0_length_ConstantStackPush(EOS(STATIC_4504), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4508_0_length_Load(EOS(STATIC_4508), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4508_0_length_Load(EOS(STATIC_4508), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4512_0_length_InvokeMethod(EOS(STATIC_4512), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4512_0_length_InvokeMethod(EOS(STATIC_4512), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4515_0_getTail_Load(EOS(STATIC_4515), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4515_0_getTail_Load(EOS(STATIC_4515), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4518_0_getTail_FieldAccess(EOS(STATIC_4518), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4518_0_getTail_FieldAccess(EOS(STATIC_4518), java.lang.Object(List(EOC, o1972)), java.lang.Object(List(EOC, o1972))) -> f4526_0_getTail_FieldAccess(EOS(STATIC_4526), java.lang.Object(List(EOC, o1972)), java.lang.Object(List(EOC, o1972))) :|: TRUE f4526_0_getTail_FieldAccess(EOS(STATIC_4526), java.lang.Object(List(EOC, o1972)), java.lang.Object(List(EOC, o1972))) -> f4531_0_getTail_Return(EOS(STATIC_4531), java.lang.Object(List(EOC, o1972)), o1972) :|: TRUE f4531_0_getTail_Return(EOS(STATIC_4531), java.lang.Object(List(EOC, o1972)), o1972) -> f4534_0_length_InvokeMethod(EOS(STATIC_4534), java.lang.Object(List(EOC, o1972)), o1972) :|: TRUE f4534_0_length_InvokeMethod(EOS(STATIC_4534), java.lang.Object(List(EOC, o1972)), o1972) -> f4535_1_length_InvokeMethod(f4535_0_length_Load(EOS(STATIC_4535), o1972, java.lang.Object(List(EOC, o1972)), o1972), java.lang.Object(List(EOC, o1972))) :|: TRUE f4535_0_length_Load(EOS(STATIC_4535), o1972, java.lang.Object(List(EOC, o1972)), o1972) -> f4540_0_length_Load(EOS(STATIC_4540), o1972, java.lang.Object(List(EOC, o1972)), o1972) :|: TRUE f4540_0_length_Load(EOS(STATIC_4540), o1972, java.lang.Object(List(EOC, o1972)), o1972) -> f4543_0_length_Load(EOS(STATIC_4543), o1972, java.lang.Object(List(EOC, o1972)), o1972) :|: TRUE f4543_0_length_Load(EOS(STATIC_4543), o1984, o1987, o1984) -> f4544_0_length_Load(EOS(STATIC_4544), o1984, o1984) :|: TRUE f4544_0_length_Load(EOS(STATIC_4544), o1984, o1984) -> f4494_0_length_Load(EOS(STATIC_4494), o1984, o1984) :|: TRUE f4494_0_length_Load(EOS(STATIC_4494), o1915, o1915) -> f4497_0_length_NONNULL(EOS(STATIC_4497), o1915, o1915, o1915) :|: TRUE R rules: f4494_0_length_Load(EOS(STATIC_4494), o1915, o1915) -> f4497_0_length_NONNULL(EOS(STATIC_4497), o1915, o1915, o1915) :|: TRUE f4497_0_length_NONNULL(EOS(STATIC_4497), java.lang.Object(o1921sub), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4500_0_length_NONNULL(EOS(STATIC_4500), java.lang.Object(o1921sub), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4497_0_length_NONNULL(EOS(STATIC_4497), NULL, NULL, NULL) -> f4501_0_length_NONNULL(EOS(STATIC_4501), NULL, NULL, NULL) :|: TRUE f4500_0_length_NONNULL(EOS(STATIC_4500), java.lang.Object(o1921sub), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4504_0_length_ConstantStackPush(EOS(STATIC_4504), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4501_0_length_NONNULL(EOS(STATIC_4501), NULL, NULL, NULL) -> f4505_0_length_ConstantStackPush(EOS(STATIC_4505), NULL) :|: TRUE f4504_0_length_ConstantStackPush(EOS(STATIC_4504), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4508_0_length_Load(EOS(STATIC_4508), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4505_0_length_ConstantStackPush(EOS(STATIC_4505), NULL) -> f4509_0_length_Return(EOS(STATIC_4509), NULL) :|: TRUE f4508_0_length_Load(EOS(STATIC_4508), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4512_0_length_InvokeMethod(EOS(STATIC_4512), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4512_0_length_InvokeMethod(EOS(STATIC_4512), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4515_0_getTail_Load(EOS(STATIC_4515), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4515_0_getTail_Load(EOS(STATIC_4515), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) -> f4518_0_getTail_FieldAccess(EOS(STATIC_4518), java.lang.Object(o1921sub), java.lang.Object(o1921sub)) :|: TRUE f4518_0_getTail_FieldAccess(EOS(STATIC_4518), java.lang.Object(List(EOC, o1972)), java.lang.Object(List(EOC, o1972))) -> f4526_0_getTail_FieldAccess(EOS(STATIC_4526), java.lang.Object(List(EOC, o1972)), java.lang.Object(List(EOC, o1972))) :|: TRUE f4526_0_getTail_FieldAccess(EOS(STATIC_4526), java.lang.Object(List(EOC, o1972)), java.lang.Object(List(EOC, o1972))) -> f4531_0_getTail_Return(EOS(STATIC_4531), java.lang.Object(List(EOC, o1972)), o1972) :|: TRUE f4531_0_getTail_Return(EOS(STATIC_4531), java.lang.Object(List(EOC, o1972)), o1972) -> f4534_0_length_InvokeMethod(EOS(STATIC_4534), java.lang.Object(List(EOC, o1972)), o1972) :|: TRUE f4534_0_length_InvokeMethod(EOS(STATIC_4534), java.lang.Object(List(EOC, o1972)), o1972) -> f4535_1_length_InvokeMethod(f4535_0_length_Load(EOS(STATIC_4535), o1972, java.lang.Object(List(EOC, o1972)), o1972), java.lang.Object(List(EOC, o1972))) :|: TRUE f4535_0_length_Load(EOS(STATIC_4535), o1972, java.lang.Object(List(EOC, o1972)), o1972) -> f4540_0_length_Load(EOS(STATIC_4540), o1972, java.lang.Object(List(EOC, o1972)), o1972) :|: TRUE f4540_0_length_Load(EOS(STATIC_4540), o1972, java.lang.Object(List(EOC, o1972)), o1972) -> f4543_0_length_Load(EOS(STATIC_4543), o1972, java.lang.Object(List(EOC, o1972)), o1972) :|: TRUE f4543_0_length_Load(EOS(STATIC_4543), o1984, o1987, o1984) -> f4544_0_length_Load(EOS(STATIC_4544), o1984, o1984) :|: TRUE f4545_0_length_Return(EOS(STATIC_4545), java.lang.Object(List(EOC, NULL))) -> f4546_0_length_IntArithmetic(EOS(STATIC_4546), java.lang.Object(List(EOC, NULL))) :|: TRUE f4546_0_length_IntArithmetic(EOS(STATIC_4546), java.lang.Object(List(EOC, NULL))) -> f4547_0_length_Return(EOS(STATIC_4547), java.lang.Object(List(EOC, NULL))) :|: TRUE f4550_0_length_Return(EOS(STATIC_4550), java.lang.Object(List(EOC, java.lang.Object(List(EOC, NULL))))) -> f4562_0_length_Return(EOS(STATIC_4562), java.lang.Object(List(EOC, java.lang.Object(List(EOC, NULL))))) :|: TRUE f4562_0_length_Return(EOS(STATIC_4562), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2052))))) -> f4574_0_length_Return(EOS(STATIC_4574), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2052))))) :|: TRUE f4574_0_length_Return(EOS(STATIC_4574), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2102))))) -> f4586_0_length_Return(EOS(STATIC_4586), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2102))))) :|: TRUE f4586_0_length_Return(EOS(STATIC_4586), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2160))))) -> f4588_0_length_IntArithmetic(EOS(STATIC_4588), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2160))))) :|: TRUE f4588_0_length_IntArithmetic(EOS(STATIC_4588), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2160))))) -> f4590_0_length_Return(EOS(STATIC_4590), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2160))))) :|: TRUE f4596_0_length_Return(EOS(STATIC_4596), java.lang.Object(List(EOC, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2192))))))) -> f4586_0_length_Return(EOS(STATIC_4586), java.lang.Object(List(EOC, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2192))))))) :|: TRUE f4544_0_length_Load(EOS(STATIC_4544), o1984, o1984) -> f4494_0_length_Load(EOS(STATIC_4494), o1984, o1984) :|: TRUE f4535_1_length_InvokeMethod(f4509_0_length_Return(EOS(STATIC_4509), NULL), java.lang.Object(List(EOC, NULL))) -> f4545_0_length_Return(EOS(STATIC_4545), java.lang.Object(List(EOC, NULL))) :|: TRUE f4535_1_length_InvokeMethod(f4547_0_length_Return(EOS(STATIC_4547), java.lang.Object(List(EOC, NULL))), java.lang.Object(List(EOC, java.lang.Object(List(EOC, NULL))))) -> f4550_0_length_Return(EOS(STATIC_4550), java.lang.Object(List(EOC, java.lang.Object(List(EOC, NULL))))) :|: TRUE f4535_1_length_InvokeMethod(f4590_0_length_Return(EOS(STATIC_4590), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2192))))), java.lang.Object(List(EOC, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2192))))))) -> f4596_0_length_Return(EOS(STATIC_4596), java.lang.Object(List(EOC, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2192))))))) :|: TRUE Combined rules. Obtained 1 conditional rules for P and 5 conditional rules for R.P rules: f4497_0_length_NONNULL(EOS(STATIC_4497), java.lang.Object(List(EOC, o1972:0)), java.lang.Object(List(EOC, o1972:0)), java.lang.Object(List(EOC, o1972:0))) -> f4535_1_length_InvokeMethod(f4497_0_length_NONNULL(EOS(STATIC_4497), o1972:0, o1972:0, o1972:0), java.lang.Object(List(EOC, o1972:0))) :|: TRUE R rules: f4535_1_length_InvokeMethod(f4547_0_length_Return(EOS(STATIC_4547), java.lang.Object(List(EOC, NULL))), java.lang.Object(List(EOC, java.lang.Object(List(EOC, NULL))))) -> f4590_0_length_Return(EOS(STATIC_4590), java.lang.Object(List(EOC, java.lang.Object(List(EOC, NULL))))) :|: TRUE f4535_1_length_InvokeMethod(f4590_0_length_Return(EOS(STATIC_4590), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2192:0))))), java.lang.Object(List(EOC, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2192:0))))))) -> f4590_0_length_Return(EOS(STATIC_4590), java.lang.Object(List(EOC, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o2192:0))))))) :|: TRUE f4497_0_length_NONNULL(EOS(STATIC_4497), NULL, NULL, NULL) -> f4509_0_length_Return(EOS(STATIC_4509), NULL) :|: TRUE f4497_0_length_NONNULL(EOS(STATIC_4497), java.lang.Object(List(EOC, o1972:0)), java.lang.Object(List(EOC, o1972:0)), java.lang.Object(List(EOC, o1972:0))) -> f4535_1_length_InvokeMethod(f4497_0_length_NONNULL(EOS(STATIC_4497), o1972:0, o1972:0, o1972:0), java.lang.Object(List(EOC, o1972:0))) :|: TRUE f4535_1_length_InvokeMethod(f4509_0_length_Return(EOS(STATIC_4509), NULL), java.lang.Object(List(EOC, NULL))) -> f4547_0_length_Return(EOS(STATIC_4547), java.lang.Object(List(EOC, NULL))) :|: TRUE Filtered ground terms: f4497_0_length_NONNULL(x1, x2, x3, x4) -> f4497_0_length_NONNULL(x2, x3, x4) List(x1, x2) -> List(x2) f4590_0_length_Return(x1, x2) -> f4590_0_length_Return(x2) f4509_0_length_Return(x1, x2) -> f4509_0_length_Return f4547_0_length_Return(x1, x2) -> f4547_0_length_Return Filtered duplicate args: f4497_0_length_NONNULL(x1, x2, x3) -> f4497_0_length_NONNULL(x3) Combined rules. Obtained 1 conditional rules for P and 0 conditional rules for R.P rules: F4497_0_LENGTH_NONNULL(java.lang.Object(List(o1972:0:0))) -> F4497_0_LENGTH_NONNULL(o1972:0:0) :|: TRUE R rules: ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: F4497_0_LENGTH_NONNULL(java.lang.Object(List(o1972:0:0))) -> F4497_0_LENGTH_NONNULL(o1972:0:0) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) 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: *F4497_0_LENGTH_NONNULL(java.lang.Object(List(o1972:0:0))) -> F4497_0_LENGTH_NONNULL(o1972:0:0) The graph contains the following edges 1 > 1 ---------------------------------------- (26) YES ---------------------------------------- (27) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Test8.test([LList;I)V SCC calls the following helper methods: Test8.length(LList;)I, Test8.test([LList;I)V, Test8.bubble(LList;)V Performed SCC analyses: *Used field analysis yielded the following read fields: *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (28) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 57 IRulesP rules: f4364_0_test_LT(EOS(STATIC_4364), i1282, java.lang.Object(ARRAY(matching1)), i1299, i1299) -> f4369_0_test_LT(EOS(STATIC_4369), i1282, java.lang.Object(ARRAY(3)), i1299, i1299) :|: TRUE && matching1 = 3 f4369_0_test_LT(EOS(STATIC_4369), i1282, java.lang.Object(ARRAY(matching1)), i1299, i1299) -> f4374_0_test_Load(EOS(STATIC_4374), i1282, java.lang.Object(ARRAY(3)), i1299) :|: i1299 >= 0 && matching1 = 3 f4374_0_test_Load(EOS(STATIC_4374), i1282, java.lang.Object(ARRAY(matching1)), i1299) -> f4380_0_test_Load(EOS(STATIC_4380), i1282, java.lang.Object(ARRAY(3)), i1299, java.lang.Object(ARRAY(3))) :|: TRUE && matching1 = 3 f4380_0_test_Load(EOS(STATIC_4380), i1282, java.lang.Object(ARRAY(matching1)), i1299, java.lang.Object(ARRAY(matching2))) -> f4384_0_test_ArrayAccess(EOS(STATIC_4384), i1282, java.lang.Object(ARRAY(3)), i1299, java.lang.Object(ARRAY(3)), i1299) :|: TRUE && matching1 = 3 && matching2 = 3 f4384_0_test_ArrayAccess(EOS(STATIC_4384), i1282, java.lang.Object(ARRAY(matching1)), i1376, java.lang.Object(ARRAY(matching2)), i1376) -> f4389_0_test_ArrayAccess(EOS(STATIC_4389), i1282, java.lang.Object(ARRAY(3)), i1376, java.lang.Object(ARRAY(3)), i1376) :|: TRUE && matching1 = 3 && matching2 = 3 f4389_0_test_ArrayAccess(EOS(STATIC_4389), i1282, java.lang.Object(ARRAY(matching1)), i1376, java.lang.Object(ARRAY(matching2)), i1376) -> f4394_0_test_InvokeMethod(EOS(STATIC_4394), i1282, java.lang.Object(ARRAY(3)), i1376, o1640) :|: i1376 < 3 && matching1 = 3 && matching2 = 3 f4394_0_test_InvokeMethod(EOS(STATIC_4394), i1282, java.lang.Object(ARRAY(matching1)), i1376, o1640) -> f4400_0_length_Load(EOS(STATIC_4400), java.lang.Object(ARRAY(3)), o1640) :|: TRUE && matching1 = 3 f4394_0_test_InvokeMethod(EOS(STATIC_4394), i1282, java.lang.Object(ARRAY(matching1)), i1376, o1640) -> f4400_1_length_Load(EOS(STATIC_4400), i1282, java.lang.Object(ARRAY(3)), i1376, o1640) :|: TRUE && matching1 = 3 f4400_0_length_Load(EOS(STATIC_4400), java.lang.Object(ARRAY(matching1)), o1640) -> f5041_0_length_Load(EOS(STATIC_5041), java.lang.Object(ARRAY(3)), o1640) :|: TRUE && matching1 = 3 f4517_0_length_Return(EOS(STATIC_4517), i1282, java.lang.Object(ARRAY(matching1)), i1376, matching2) -> f4459_0_length_Return(EOS(STATIC_4459), i1282, java.lang.Object(ARRAY(3)), i1376, 0) :|: TRUE && matching1 = 3 && matching2 = 0 f4459_0_length_Return(EOS(STATIC_4459), i1282, java.lang.Object(ARRAY(matching1)), i1376, matching2) -> f4464_0_test_Store(EOS(STATIC_4464), i1282, java.lang.Object(ARRAY(3)), i1376, 0) :|: TRUE && matching1 = 3 && matching2 = 0 f4464_0_test_Store(EOS(STATIC_4464), i1282, java.lang.Object(ARRAY(matching1)), i1376, matching2) -> f4587_0_test_Store(EOS(STATIC_4587), i1282, java.lang.Object(ARRAY(3)), i1376, 0) :|: TRUE && matching1 = 3 && matching2 = 0 f4587_0_test_Store(EOS(STATIC_4587), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1582) -> f4589_0_test_ConstantStackPush(EOS(STATIC_4589), i1282, java.lang.Object(ARRAY(3)), i1376, i1582) :|: TRUE && matching1 = 3 f4589_0_test_ConstantStackPush(EOS(STATIC_4589), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1582) -> f4591_0_test_Store(EOS(STATIC_4591), i1282, java.lang.Object(ARRAY(3)), i1376, i1582, 0) :|: TRUE && matching1 = 3 f4591_0_test_Store(EOS(STATIC_4591), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1582, matching2) -> f4593_0_test_Load(EOS(STATIC_4593), i1282, java.lang.Object(ARRAY(3)), i1376, i1582, 0) :|: TRUE && matching1 = 3 && matching2 = 0 f4593_0_test_Load(EOS(STATIC_4593), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1582, matching2) -> f4641_0_test_Load(EOS(STATIC_4641), i1282, java.lang.Object(ARRAY(3)), i1376, i1582, 0) :|: TRUE && matching1 = 3 && matching2 = 0 f4641_0_test_Load(EOS(STATIC_4641), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1620, i1621) -> f4690_0_test_Load(EOS(STATIC_4690), i1282, java.lang.Object(ARRAY(3)), i1376, i1620, i1621) :|: TRUE && matching1 = 3 f4690_0_test_Load(EOS(STATIC_4690), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1639, i1640) -> f4747_0_test_Load(EOS(STATIC_4747), i1282, java.lang.Object(ARRAY(3)), i1376, i1639, i1640) :|: TRUE && matching1 = 3 f4747_0_test_Load(EOS(STATIC_4747), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661) -> f4749_0_test_Load(EOS(STATIC_4749), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661, i1661) :|: TRUE && matching1 = 3 f4749_0_test_Load(EOS(STATIC_4749), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, i1661) -> f4751_0_test_GE(EOS(STATIC_4751), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661, i1661, i1660) :|: TRUE && matching1 = 3 f4751_0_test_GE(EOS(STATIC_4751), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, i1661, i1660) -> f4753_0_test_GE(EOS(STATIC_4753), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661, i1661, i1660) :|: i1661 >= i1660 && matching1 = 3 f4751_0_test_GE(EOS(STATIC_4751), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, i1661, i1660) -> f4754_0_test_GE(EOS(STATIC_4754), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661, i1661, i1660) :|: i1661 < i1660 && matching1 = 3 f4753_0_test_GE(EOS(STATIC_4753), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, i1661, i1660) -> f4756_0_test_Load(EOS(STATIC_4756), i1282, java.lang.Object(ARRAY(3)), i1376) :|: i1661 >= i1660 && matching1 = 3 f4756_0_test_Load(EOS(STATIC_4756), i1282, java.lang.Object(ARRAY(matching1)), i1376) -> f4759_0_test_Load(EOS(STATIC_4759), i1282, i1376, java.lang.Object(ARRAY(3))) :|: TRUE && matching1 = 3 f4759_0_test_Load(EOS(STATIC_4759), i1282, i1376, java.lang.Object(ARRAY(matching1))) -> f4761_0_test_ConstantStackPush(EOS(STATIC_4761), i1282, java.lang.Object(ARRAY(3)), i1376) :|: TRUE && matching1 = 3 f4761_0_test_ConstantStackPush(EOS(STATIC_4761), i1282, java.lang.Object(ARRAY(matching1)), i1376) -> f4764_0_test_IntArithmetic(EOS(STATIC_4764), i1282, java.lang.Object(ARRAY(3)), i1376, 1) :|: TRUE && matching1 = 3 f4764_0_test_IntArithmetic(EOS(STATIC_4764), i1282, java.lang.Object(ARRAY(matching1)), i1376, matching2) -> f4767_0_test_InvokeMethod(EOS(STATIC_4767), i1282, java.lang.Object(ARRAY(3)), i1376 - 1) :|: i1376 >= 0 && matching1 = 3 && matching2 = 1 f4767_0_test_InvokeMethod(EOS(STATIC_4767), i1282, java.lang.Object(ARRAY(matching1)), i1678) -> f4770_0_test_Load(EOS(STATIC_4770), i1678, java.lang.Object(ARRAY(3)), i1678) :|: i1678 <= 1 && matching1 = 3 f4767_0_test_InvokeMethod(EOS(STATIC_4767), i1282, java.lang.Object(ARRAY(matching1)), i1678) -> f4770_1_test_Load(EOS(STATIC_4770), i1282, java.lang.Object(ARRAY(3)), i1678) :|: i1678 <= 1 && matching1 = 3 f4770_0_test_Load(EOS(STATIC_4770), i1678, java.lang.Object(ARRAY(matching1)), i1678) -> f4773_0_test_Load(EOS(STATIC_4773), i1678, java.lang.Object(ARRAY(3)), i1678) :|: TRUE && matching1 = 3 f4773_0_test_Load(EOS(STATIC_4773), i1678, java.lang.Object(ARRAY(matching1)), i1678) -> f4359_0_test_Load(EOS(STATIC_4359), i1678, java.lang.Object(ARRAY(3)), i1678) :|: TRUE && matching1 = 3 f4359_0_test_Load(EOS(STATIC_4359), i1282, java.lang.Object(ARRAY(matching1)), i1283) -> f4364_0_test_LT(EOS(STATIC_4364), i1282, java.lang.Object(ARRAY(3)), i1283, i1283) :|: TRUE && matching1 = 3 f4754_0_test_GE(EOS(STATIC_4754), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, i1661, i1660) -> f4757_0_test_Load(EOS(STATIC_4757), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661) :|: i1661 < i1660 && matching1 = 3 f4757_0_test_Load(EOS(STATIC_4757), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661) -> f4760_0_test_Load(EOS(STATIC_4760), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661, java.lang.Object(ARRAY(3))) :|: TRUE && matching1 = 3 f4760_0_test_Load(EOS(STATIC_4760), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, java.lang.Object(ARRAY(matching2))) -> f4762_0_test_ArrayAccess(EOS(STATIC_4762), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661, java.lang.Object(ARRAY(3)), i1376) :|: TRUE && matching1 = 3 && matching2 = 3 f4762_0_test_ArrayAccess(EOS(STATIC_4762), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, java.lang.Object(ARRAY(matching2)), i1376) -> f4765_0_test_InvokeMethod(EOS(STATIC_4765), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661, o2424) :|: i1376 < 3 && matching1 = 3 && matching2 = 3 f4765_0_test_InvokeMethod(EOS(STATIC_4765), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, o2424) -> f4768_0_bubble_Load(EOS(STATIC_4768), java.lang.Object(ARRAY(3)), o2424) :|: i1660 >= 1 && i1661 < i1660 && matching1 = 3 f4765_0_test_InvokeMethod(EOS(STATIC_4765), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, o2424) -> f4768_1_bubble_Load(EOS(STATIC_4768), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661, o2424) :|: i1660 >= 1 && i1661 < i1660 && matching1 = 3 f4768_0_bubble_Load(EOS(STATIC_4768), java.lang.Object(ARRAY(matching1)), o2424) -> f5119_0_bubble_Load(EOS(STATIC_5119), java.lang.Object(ARRAY(3)), o2424) :|: TRUE && matching1 = 3 f4777_0_bubble_Return(EOS(STATIC_4777), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661) -> f4780_0_test_Inc(EOS(STATIC_4780), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661) :|: TRUE && matching1 = 3 f4780_0_test_Inc(EOS(STATIC_4780), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661) -> f4785_0_test_JMP(EOS(STATIC_4785), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661 + 1) :|: TRUE && matching1 = 3 f4785_0_test_JMP(EOS(STATIC_4785), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1689) -> f4788_0_test_Load(EOS(STATIC_4788), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1689) :|: TRUE && matching1 = 3 f4788_0_test_Load(EOS(STATIC_4788), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1689) -> f4747_0_test_Load(EOS(STATIC_4747), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1689) :|: TRUE && matching1 = 3 f4794_0_bubble_Return(EOS(STATIC_4794), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661) -> f4797_0_test_Inc(EOS(STATIC_4797), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661) :|: TRUE && matching1 = 3 f4797_0_test_Inc(EOS(STATIC_4797), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661) -> f4780_0_test_Inc(EOS(STATIC_4780), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661) :|: TRUE && matching1 = 3 f4800_0_bubble_Return(EOS(STATIC_4800), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661) -> f4794_0_bubble_Return(EOS(STATIC_4794), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661) :|: TRUE && matching1 = 3 f4549_0_length_Return(EOS(STATIC_4549), i1282, java.lang.Object(ARRAY(matching1)), i1376, matching2) -> f4560_0_length_Return(EOS(STATIC_4560), i1282, java.lang.Object(ARRAY(3)), i1376, 1) :|: TRUE && matching1 = 3 && matching2 = 1 f4560_0_length_Return(EOS(STATIC_4560), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1559) -> f4572_0_length_Return(EOS(STATIC_4572), i1282, java.lang.Object(ARRAY(3)), i1376, i1559) :|: TRUE && matching1 = 3 f4572_0_length_Return(EOS(STATIC_4572), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1569) -> f4584_0_length_Return(EOS(STATIC_4584), i1282, java.lang.Object(ARRAY(3)), i1376, i1569) :|: TRUE && matching1 = 3 f4584_0_length_Return(EOS(STATIC_4584), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1582) -> f4587_0_test_Store(EOS(STATIC_4587), i1282, java.lang.Object(ARRAY(3)), i1376, i1582) :|: TRUE && matching1 = 3 f4595_0_length_Return(EOS(STATIC_4595), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1590) -> f4584_0_length_Return(EOS(STATIC_4584), i1282, java.lang.Object(ARRAY(3)), i1376, i1590) :|: TRUE && matching1 = 3 f4400_1_length_Load(EOS(STATIC_4400), i1282, java.lang.Object(ARRAY(matching1)), i1376, o1640) -> f4517_0_length_Return(EOS(STATIC_4517), i1282, java.lang.Object(ARRAY(3)), i1376, 0) :|: TRUE && matching1 = 3 f4400_1_length_Load(EOS(STATIC_4400), i1282, java.lang.Object(ARRAY(matching1)), i1376, o1640) -> f4549_0_length_Return(EOS(STATIC_4549), i1282, java.lang.Object(ARRAY(3)), i1376, 1) :|: TRUE && matching1 = 3 f4400_1_length_Load(EOS(STATIC_4400), i1282, java.lang.Object(ARRAY(matching1)), i1376, o1640) -> f4595_0_length_Return(EOS(STATIC_4595), i1282, java.lang.Object(ARRAY(3)), i1376, i1590) :|: TRUE && matching1 = 3 f4768_1_bubble_Load(EOS(STATIC_4768), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, o2424) -> f4777_0_bubble_Return(EOS(STATIC_4777), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661) :|: TRUE && matching1 = 3 f4768_1_bubble_Load(EOS(STATIC_4768), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, o2424) -> f4794_0_bubble_Return(EOS(STATIC_4794), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661) :|: TRUE && matching1 = 3 f4768_1_bubble_Load(EOS(STATIC_4768), i1282, java.lang.Object(ARRAY(matching1)), i1376, i1660, i1661, o2424) -> f4800_0_bubble_Return(EOS(STATIC_4800), i1282, java.lang.Object(ARRAY(3)), i1376, i1660, i1661) :|: TRUE && matching1 = 3 Combined rules. Obtained 7 IRulesP rules: f4751_0_test_GE(EOS(STATIC_4751), i1282:0, java.lang.Object(ARRAY(3)), i1376:0, i1660:0, i1661:0, i1661:0, i1660:0) -> f4751_0_test_GE(EOS(STATIC_4751), i1282:0, java.lang.Object(ARRAY(3)), i1376:0, i1660:0, i1661:0 + 1, i1661:0 + 1, i1660:0) :|: i1661:0 < i1660:0 && i1376:0 < 3 && i1660:0 > 0 f4751_0_test_GE(EOS(STATIC_4751), i1282:0, java.lang.Object(ARRAY(3)), i1376:0, i1660:0, i1661:0, i1661:0, i1660:0) -> f4751_0_test_GE(EOS(STATIC_4751), i1376:0 - 1, java.lang.Object(ARRAY(3)), i1376:0 - 1, 1, 0, 0, 1) :|: i1376:0 > 0 && i1661:0 >= i1660:0 && i1376:0 < 3 && i1376:0 < 4 f4751_0_test_GE(EOS(STATIC_4751), i1282:0, java.lang.Object(ARRAY(3)), i1376:0, i1660:0, i1661:0, i1661:0, i1660:0) -> f4751_0_test_GE(EOS(STATIC_4751), i1376:0 - 1, java.lang.Object(ARRAY(3)), i1376:0 - 1, i1590:0, 0, 0, i1590:0) :|: i1376:0 > 0 && i1661:0 >= i1660:0 && i1376:0 < 3 && i1376:0 < 4 f4751_0_test_GE(EOS(STATIC_4751), i1282:0, java.lang.Object(ARRAY(3)), i1376:0, i1660:0, i1661:0, i1661:0, i1660:0) -> f4751_0_test_GE(EOS(STATIC_4751), i1376:0 - 1, java.lang.Object(ARRAY(3)), i1376:0 - 1, 0, 0, 0, 0) :|: i1376:0 > 0 && i1661:0 >= i1660:0 && i1376:0 < 3 && i1376:0 < 4 Removed following non-SCC rules: f4751_0_test_GE(EOS(STATIC_4751), i1282:0, java.lang.Object(ARRAY(3)), i1376:0, i1660:0, i1661:0, i1661:0, i1660:0) -> f4770_1_test_Load(EOS(STATIC_4770), i1282:0, java.lang.Object(ARRAY(3)), i1376:0 - 1) :|: i1661:0 >= i1660:0 && i1376:0 < 3 && i1376:0 > -1 f4751_0_test_GE(EOS(STATIC_4751), i1282:0, java.lang.Object(ARRAY(3)), i1376:0, i1660:0, i1661:0, i1661:0, i1660:0) -> f5119_0_bubble_Load(EOS(STATIC_5119), java.lang.Object(ARRAY(3)), o2424:0) :|: i1661:0 < i1660:0 && i1376:0 < 3 && i1660:0 > 0 f4751_0_test_GE(EOS(STATIC_4751), i1282:0, java.lang.Object(ARRAY(3)), i1376:0, i1660:0, i1661:0, i1661:0, i1660:0) -> f5041_0_length_Load(EOS(STATIC_5041), java.lang.Object(ARRAY(3)), o1640:0) :|: i1376:0 > 0 && i1661:0 >= i1660:0 && i1376:0 < 3 && i1376:0 < 4 Filtered constant ground arguments: f4751_0_test_GE(x1, x2, x3, x4, x5, x6, x7, x8) -> f4751_0_test_GE(x2, x4, x5, x6, x7, x8) EOS(x1) -> EOS java.lang.Object(x1) -> java.lang.Object ARRAY(x1) -> ARRAY Filtered duplicate arguments: f4751_0_test_GE(x1, x2, x3, x4, x5, x6) -> f4751_0_test_GE(x1, x2, x5, x6) Filtered unneeded arguments: f4751_0_test_GE(x1, x2, x3, x4) -> f4751_0_test_GE(x2, x3, x4) Finished conversion. Obtained 4 rules.P rules: f4751_0_test_GE(i1376:0, i1661:0, i1660:0) -> f4751_0_test_GE(i1376:0, i1661:0 + 1, i1660:0) :|: i1376:0 < 3 && i1660:0 > 0 && i1661:0 < i1660:0 f4751_0_test_GE(i1376:0, i1661:0, i1660:0) -> f4751_0_test_GE(i1376:0 - 1, 0, 1) :|: i1661:0 >= i1660:0 && i1376:0 > 0 && i1376:0 < 4 && i1376:0 < 3 f4751_0_test_GE(i1376:0, i1661:0, i1660:0) -> f4751_0_test_GE(i1376:0 - 1, 0, i1590:0) :|: i1661:0 >= i1660:0 && i1376:0 > 0 && i1376:0 < 4 && i1376:0 < 3 f4751_0_test_GE(i1376:0, i1661:0, i1660:0) -> f4751_0_test_GE(i1376:0 - 1, 0, 0) :|: i1661:0 >= i1660:0 && i1376:0 > 0 && i1376:0 < 4 && i1376:0 < 3 ---------------------------------------- (29) Obligation: Rules: f4751_0_test_GE(i1376:0, i1661:0, i1660:0) -> f4751_0_test_GE(i1376:0, i1661:0 + 1, i1660:0) :|: i1376:0 < 3 && i1660:0 > 0 && i1661:0 < i1660:0 f4751_0_test_GE(x, x1, x2) -> f4751_0_test_GE(x - 1, 0, 1) :|: x1 >= x2 && x > 0 && x < 4 && x < 3 f4751_0_test_GE(x3, x4, x5) -> f4751_0_test_GE(x3 - 1, 0, x6) :|: x4 >= x5 && x3 > 0 && x3 < 4 && x3 < 3 f4751_0_test_GE(x7, x8, x9) -> f4751_0_test_GE(x7 - 1, 0, 0) :|: x8 >= x9 && x7 > 0 && x7 < 4 && x7 < 3 ---------------------------------------- (30) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (31) Obligation: Rules: f4751_0_test_GE(i1376:0, i1661:0, i1660:0) -> f4751_0_test_GE(i1376:0, arith, i1660:0) :|: i1376:0 < 3 && i1660:0 > 0 && i1661:0 < i1660:0 && arith = i1661:0 + 1 f4751_0_test_GE(x10, x11, x12) -> f4751_0_test_GE(x13, 0, 1) :|: x11 >= x12 && x10 > 0 && x10 < 4 && x10 < 3 && x13 = x10 - 1 f4751_0_test_GE(x14, x15, x16) -> f4751_0_test_GE(x17, 0, x18) :|: x15 >= x16 && x14 > 0 && x14 < 4 && x14 < 3 && x17 = x14 - 1 f4751_0_test_GE(x19, x20, x21) -> f4751_0_test_GE(x22, 0, 0) :|: x20 >= x21 && x19 > 0 && x19 < 4 && x19 < 3 && x22 = x19 - 1 ---------------------------------------- (32) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f4751_0_test_GE(i1376:0, i1661:0, i1660:0) -> f4751_0_test_GE(i1376:0, arith, i1660:0) :|: i1376:0 < 3 && i1660:0 > 0 && i1661:0 < i1660:0 && arith = i1661:0 + 1 (2) f4751_0_test_GE(x10, x11, x12) -> f4751_0_test_GE(x13, 0, 1) :|: x11 >= x12 && x10 > 0 && x10 < 4 && x10 < 3 && x13 = x10 - 1 (3) f4751_0_test_GE(x14, x15, x16) -> f4751_0_test_GE(x17, 0, x18) :|: x15 >= x16 && x14 > 0 && x14 < 4 && x14 < 3 && x17 = x14 - 1 (4) f4751_0_test_GE(x19, x20, x21) -> f4751_0_test_GE(x22, 0, 0) :|: x20 >= x21 && x19 > 0 && x19 < 4 && x19 < 3 && x22 = x19 - 1 Arcs: (1) -> (1), (2), (3), (4) (2) -> (1) (3) -> (1), (2), (3), (4) (4) -> (2), (3), (4) This digraph is fully evaluated! ---------------------------------------- (33) Obligation: Termination digraph: Nodes: (1) f4751_0_test_GE(i1376:0, i1661:0, i1660:0) -> f4751_0_test_GE(i1376:0, arith, i1660:0) :|: i1376:0 < 3 && i1660:0 > 0 && i1661:0 < i1660:0 && arith = i1661:0 + 1 (2) f4751_0_test_GE(x10, x11, x12) -> f4751_0_test_GE(x13, 0, 1) :|: x11 >= x12 && x10 > 0 && x10 < 4 && x10 < 3 && x13 = x10 - 1 (3) f4751_0_test_GE(x14, x15, x16) -> f4751_0_test_GE(x17, 0, x18) :|: x15 >= x16 && x14 > 0 && x14 < 4 && x14 < 3 && x17 = x14 - 1 (4) f4751_0_test_GE(x19, x20, x21) -> f4751_0_test_GE(x22, 0, 0) :|: x20 >= x21 && x19 > 0 && x19 < 4 && x19 < 3 && x22 = x19 - 1 Arcs: (1) -> (1), (2), (3), (4) (2) -> (1) (3) -> (1), (2), (3), (4) (4) -> (2), (3), (4) This digraph is fully evaluated! ---------------------------------------- (34) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (35) Obligation: Rules: f4751_0_test_GE(i1376:0:0, i1661:0:0, i1660:0:0) -> f4751_0_test_GE(i1376:0:0, i1661:0:0 + 1, i1660:0:0) :|: i1376:0:0 < 3 && i1660:0:0 > 0 && i1661:0:0 < i1660:0:0 f4751_0_test_GE(x14:0, x15:0, x16:0) -> f4751_0_test_GE(x14:0 - 1, 0, x18:0) :|: x14:0 < 4 && x14:0 < 3 && x14:0 > 0 && x16:0 <= x15:0 f4751_0_test_GE(x19:0, x20:0, x21:0) -> f4751_0_test_GE(x19:0 - 1, 0, 0) :|: x19:0 < 4 && x19:0 < 3 && x19:0 > 0 && x21:0 <= x20:0 f4751_0_test_GE(x10:0, x11:0, x12:0) -> f4751_0_test_GE(x10:0 - 1, 0, 1) :|: x10:0 < 4 && x10:0 < 3 && x10:0 > 0 && x12:0 <= x11:0 ---------------------------------------- (36) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f4751_0_test_GE(INTEGER, VARIABLE, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (37) Obligation: Rules: f4751_0_test_GE(i1376:0:0, i1661:0:0, i1660:0:0) -> f4751_0_test_GE(i1376:0:0, c, i1660:0:0) :|: c = i1661:0:0 + 1 && (i1376:0:0 < 3 && i1660:0:0 > 0 && i1661:0:0 < i1660:0:0) f4751_0_test_GE(x14:0, x15:0, x16:0) -> f4751_0_test_GE(c1, c2, x18:0) :|: c2 = 0 && c1 = x14:0 - 1 && (x14:0 < 4 && x14:0 < 3 && x14:0 > 0 && x16:0 <= x15:0) f4751_0_test_GE(x19:0, x20:0, x21:0) -> f4751_0_test_GE(c3, c4, c5) :|: c5 = 0 && (c4 = 0 && c3 = x19:0 - 1) && (x19:0 < 4 && x19:0 < 3 && x19:0 > 0 && x21:0 <= x20:0) f4751_0_test_GE(x10:0, x11:0, x12:0) -> f4751_0_test_GE(c6, c7, c8) :|: c8 = 1 && (c7 = 0 && c6 = x10:0 - 1) && (x10:0 < 4 && x10:0 < 3 && x10:0 > 0 && x12:0 <= x11:0) ---------------------------------------- (38) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f4751_0_test_GE(x, x1, x2)] = -1 + x The following rules are decreasing: f4751_0_test_GE(x14:0, x15:0, x16:0) -> f4751_0_test_GE(c1, c2, x18:0) :|: c2 = 0 && c1 = x14:0 - 1 && (x14:0 < 4 && x14:0 < 3 && x14:0 > 0 && x16:0 <= x15:0) f4751_0_test_GE(x19:0, x20:0, x21:0) -> f4751_0_test_GE(c3, c4, c5) :|: c5 = 0 && (c4 = 0 && c3 = x19:0 - 1) && (x19:0 < 4 && x19:0 < 3 && x19:0 > 0 && x21:0 <= x20:0) f4751_0_test_GE(x10:0, x11:0, x12:0) -> f4751_0_test_GE(c6, c7, c8) :|: c8 = 1 && (c7 = 0 && c6 = x10:0 - 1) && (x10:0 < 4 && x10:0 < 3 && x10:0 > 0 && x12:0 <= x11:0) The following rules are bounded: f4751_0_test_GE(x14:0, x15:0, x16:0) -> f4751_0_test_GE(c1, c2, x18:0) :|: c2 = 0 && c1 = x14:0 - 1 && (x14:0 < 4 && x14:0 < 3 && x14:0 > 0 && x16:0 <= x15:0) f4751_0_test_GE(x19:0, x20:0, x21:0) -> f4751_0_test_GE(c3, c4, c5) :|: c5 = 0 && (c4 = 0 && c3 = x19:0 - 1) && (x19:0 < 4 && x19:0 < 3 && x19:0 > 0 && x21:0 <= x20:0) f4751_0_test_GE(x10:0, x11:0, x12:0) -> f4751_0_test_GE(c6, c7, c8) :|: c8 = 1 && (c7 = 0 && c6 = x10:0 - 1) && (x10:0 < 4 && x10:0 < 3 && x10:0 > 0 && x12:0 <= x11:0) ---------------------------------------- (39) Obligation: Rules: f4751_0_test_GE(i1376:0:0, i1661:0:0, i1660:0:0) -> f4751_0_test_GE(i1376:0:0, c, i1660:0:0) :|: c = i1661:0:0 + 1 && (i1376:0:0 < 3 && i1660:0:0 > 0 && i1661:0:0 < i1660:0:0) ---------------------------------------- (40) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f4751_0_test_GE ] = f4751_0_test_GE_3 + -1*f4751_0_test_GE_2 The following rules are decreasing: f4751_0_test_GE(i1376:0:0, i1661:0:0, i1660:0:0) -> f4751_0_test_GE(i1376:0:0, c, i1660:0:0) :|: c = i1661:0:0 + 1 && (i1376:0:0 < 3 && i1660:0:0 > 0 && i1661:0:0 < i1660:0:0) The following rules are bounded: f4751_0_test_GE(i1376:0:0, i1661:0:0, i1660:0:0) -> f4751_0_test_GE(i1376:0:0, c, i1660:0:0) :|: c = i1661:0:0 + 1 && (i1376:0:0 < 3 && i1660:0:0 > 0 && i1661:0:0 < i1660:0:0) ---------------------------------------- (41) YES ---------------------------------------- (42) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Test8.main([Ljava/lang/String;)V 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: ---------------------------------------- (43) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 21 IRulesP rules: f4381_0_mk_Inc(EOS(STATIC_4381), i1314, java.lang.Object(List(EOC)), i1314) -> f4385_0_mk_LE(EOS(STATIC_4385), i1314 + -1, java.lang.Object(List(EOC)), i1314) :|: TRUE f4385_0_mk_LE(EOS(STATIC_4385), i1349, java.lang.Object(List(EOC)), i1380) -> f4392_0_mk_LE(EOS(STATIC_4392), i1349, java.lang.Object(List(EOC)), i1380) :|: TRUE f4392_0_mk_LE(EOS(STATIC_4392), i1349, java.lang.Object(List(EOC)), i1380) -> f4397_0_mk_New(EOS(STATIC_4397), i1349, java.lang.Object(List(EOC))) :|: i1380 > 0 f4397_0_mk_New(EOS(STATIC_4397), i1349, java.lang.Object(List(EOC))) -> f4402_0_mk_Duplicate(EOS(STATIC_4402), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f4402_0_mk_Duplicate(EOS(STATIC_4402), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f4409_0_mk_Load(EOS(STATIC_4409), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f4409_0_mk_Load(EOS(STATIC_4409), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f4416_0_mk_Load(EOS(STATIC_4416), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349) :|: TRUE f4416_0_mk_Load(EOS(STATIC_4416), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349) -> f4421_0_mk_InvokeMethod(EOS(STATIC_4421), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC))) :|: TRUE f4421_0_mk_InvokeMethod(EOS(STATIC_4421), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC))) -> f4428_0__init__Load(EOS(STATIC_4428), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC))) :|: TRUE f4428_0__init__Load(EOS(STATIC_4428), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC))) -> f4436_0__init__InvokeMethod(EOS(STATIC_4436), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f4436_0__init__InvokeMethod(EOS(STATIC_4436), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f4441_0__init__Load(EOS(STATIC_4441), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC))) :|: TRUE f4441_0__init__Load(EOS(STATIC_4441), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC))) -> f4448_0__init__Load(EOS(STATIC_4448), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f4448_0__init__Load(EOS(STATIC_4448), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f4453_0__init__FieldAccess(EOS(STATIC_4453), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349) :|: TRUE f4453_0__init__FieldAccess(EOS(STATIC_4453), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i1349) -> f4458_0__init__Load(EOS(STATIC_4458), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f4458_0__init__Load(EOS(STATIC_4458), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f4461_0__init__Load(EOS(STATIC_4461), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f4461_0__init__Load(EOS(STATIC_4461), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f4465_0__init__FieldAccess(EOS(STATIC_4465), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f4465_0__init__FieldAccess(EOS(STATIC_4465), i1349, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f4470_0__init__Return(EOS(STATIC_4470), i1349, java.lang.Object(List(EOC))) :|: TRUE f4470_0__init__Return(EOS(STATIC_4470), i1349, java.lang.Object(List(EOC))) -> f4475_0_mk_Store(EOS(STATIC_4475), i1349, java.lang.Object(List(EOC))) :|: TRUE f4475_0_mk_Store(EOS(STATIC_4475), i1349, java.lang.Object(List(EOC))) -> f4480_0_mk_JMP(EOS(STATIC_4480), i1349, java.lang.Object(List(EOC))) :|: TRUE f4480_0_mk_JMP(EOS(STATIC_4480), i1349, java.lang.Object(List(EOC))) -> f4485_0_mk_Load(EOS(STATIC_4485), i1349, java.lang.Object(List(EOC))) :|: TRUE f4485_0_mk_Load(EOS(STATIC_4485), i1349, java.lang.Object(List(EOC))) -> f4376_0_mk_Load(EOS(STATIC_4376), i1349, java.lang.Object(List(EOC))) :|: TRUE f4376_0_mk_Load(EOS(STATIC_4376), i1314, java.lang.Object(List(EOC))) -> f4381_0_mk_Inc(EOS(STATIC_4381), i1314, java.lang.Object(List(EOC)), i1314) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f4381_0_mk_Inc(EOS(STATIC_4381), i1314:0, java.lang.Object(List(EOC)), i1314:0) -> f4381_0_mk_Inc(EOS(STATIC_4381), i1314:0 - 1, java.lang.Object(List(EOC)), i1314:0 - 1) :|: i1314:0 > 0 Filtered constant ground arguments: f4381_0_mk_Inc(x1, x2, x3, x4) -> f4381_0_mk_Inc(x2, x4) EOS(x1) -> EOS java.lang.Object(x1) -> java.lang.Object List(x1) -> List Filtered duplicate arguments: f4381_0_mk_Inc(x1, x2) -> f4381_0_mk_Inc(x2) Finished conversion. Obtained 1 rules.P rules: f4381_0_mk_Inc(i1314:0) -> f4381_0_mk_Inc(i1314:0 - 1) :|: i1314:0 > 0 ---------------------------------------- (44) Obligation: Rules: f4381_0_mk_Inc(i1314:0) -> f4381_0_mk_Inc(i1314:0 - 1) :|: i1314:0 > 0 ---------------------------------------- (45) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (46) Obligation: Rules: f4381_0_mk_Inc(i1314:0) -> f4381_0_mk_Inc(arith) :|: i1314:0 > 0 && arith = i1314:0 - 1 ---------------------------------------- (47) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f4381_0_mk_Inc(i1314:0) -> f4381_0_mk_Inc(arith) :|: i1314:0 > 0 && arith = i1314:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (48) Obligation: Termination digraph: Nodes: (1) f4381_0_mk_Inc(i1314:0) -> f4381_0_mk_Inc(arith) :|: i1314:0 > 0 && arith = i1314:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (49) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (50) Obligation: Rules: f4381_0_mk_Inc(i1314:0:0) -> f4381_0_mk_Inc(i1314:0:0 - 1) :|: i1314:0:0 > 0 ---------------------------------------- (51) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f4381_0_mk_Inc(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (52) Obligation: Rules: f4381_0_mk_Inc(i1314:0:0) -> f4381_0_mk_Inc(c) :|: c = i1314:0:0 - 1 && i1314:0:0 > 0 ---------------------------------------- (53) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f4381_0_mk_Inc ] = f4381_0_mk_Inc_1 The following rules are decreasing: f4381_0_mk_Inc(i1314:0:0) -> f4381_0_mk_Inc(c) :|: c = i1314:0:0 - 1 && i1314:0:0 > 0 The following rules are bounded: f4381_0_mk_Inc(i1314:0:0) -> f4381_0_mk_Inc(c) :|: c = i1314:0:0 - 1 && i1314:0:0 > 0 ---------------------------------------- (54) YES ---------------------------------------- (55) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Test8.main([Ljava/lang/String;)V 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: ---------------------------------------- (56) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 21 IRulesP rules: f2824_0_mk_Inc(EOS(STATIC_2824), i741, java.lang.Object(List(EOC)), i741) -> f2848_0_mk_LE(EOS(STATIC_2848), i741 + -1, java.lang.Object(List(EOC)), i741) :|: TRUE f2848_0_mk_LE(EOS(STATIC_2848), i762, java.lang.Object(List(EOC)), i786) -> f2856_0_mk_LE(EOS(STATIC_2856), i762, java.lang.Object(List(EOC)), i786) :|: TRUE f2856_0_mk_LE(EOS(STATIC_2856), i762, java.lang.Object(List(EOC)), i786) -> f2923_0_mk_New(EOS(STATIC_2923), i762, java.lang.Object(List(EOC))) :|: i786 > 0 f2923_0_mk_New(EOS(STATIC_2923), i762, java.lang.Object(List(EOC))) -> f3329_0_mk_Duplicate(EOS(STATIC_3329), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3329_0_mk_Duplicate(EOS(STATIC_3329), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3355_0_mk_Load(EOS(STATIC_3355), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3355_0_mk_Load(EOS(STATIC_3355), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3435_0_mk_Load(EOS(STATIC_3435), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762) :|: TRUE f3435_0_mk_Load(EOS(STATIC_3435), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762) -> f3520_0_mk_InvokeMethod(EOS(STATIC_3520), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC))) :|: TRUE f3520_0_mk_InvokeMethod(EOS(STATIC_3520), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC))) -> f3537_0__init__Load(EOS(STATIC_3537), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC))) :|: TRUE f3537_0__init__Load(EOS(STATIC_3537), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC))) -> f3611_0__init__InvokeMethod(EOS(STATIC_3611), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3611_0__init__InvokeMethod(EOS(STATIC_3611), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3628_0__init__Load(EOS(STATIC_3628), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC))) :|: TRUE f3628_0__init__Load(EOS(STATIC_3628), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC))) -> f3717_0__init__Load(EOS(STATIC_3717), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3717_0__init__Load(EOS(STATIC_3717), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3724_0__init__FieldAccess(EOS(STATIC_3724), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762) :|: TRUE f3724_0__init__FieldAccess(EOS(STATIC_3724), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i762) -> f3730_0__init__Load(EOS(STATIC_3730), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3730_0__init__Load(EOS(STATIC_3730), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3734_0__init__Load(EOS(STATIC_3734), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3734_0__init__Load(EOS(STATIC_3734), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3737_0__init__FieldAccess(EOS(STATIC_3737), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3737_0__init__FieldAccess(EOS(STATIC_3737), i762, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3772_0__init__Return(EOS(STATIC_3772), i762, java.lang.Object(List(EOC))) :|: TRUE f3772_0__init__Return(EOS(STATIC_3772), i762, java.lang.Object(List(EOC))) -> f3776_0_mk_Store(EOS(STATIC_3776), i762, java.lang.Object(List(EOC))) :|: TRUE f3776_0_mk_Store(EOS(STATIC_3776), i762, java.lang.Object(List(EOC))) -> f3780_0_mk_JMP(EOS(STATIC_3780), i762, java.lang.Object(List(EOC))) :|: TRUE f3780_0_mk_JMP(EOS(STATIC_3780), i762, java.lang.Object(List(EOC))) -> f3794_0_mk_Load(EOS(STATIC_3794), i762, java.lang.Object(List(EOC))) :|: TRUE f3794_0_mk_Load(EOS(STATIC_3794), i762, java.lang.Object(List(EOC))) -> f2815_0_mk_Load(EOS(STATIC_2815), i762, java.lang.Object(List(EOC))) :|: TRUE f2815_0_mk_Load(EOS(STATIC_2815), i741, java.lang.Object(List(EOC))) -> f2824_0_mk_Inc(EOS(STATIC_2824), i741, java.lang.Object(List(EOC)), i741) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f2824_0_mk_Inc(EOS(STATIC_2824), i741:0, java.lang.Object(List(EOC)), i741:0) -> f2824_0_mk_Inc(EOS(STATIC_2824), i741:0 - 1, java.lang.Object(List(EOC)), i741:0 - 1) :|: i741:0 > 0 Filtered constant ground arguments: f2824_0_mk_Inc(x1, x2, x3, x4) -> f2824_0_mk_Inc(x2, x4) EOS(x1) -> EOS java.lang.Object(x1) -> java.lang.Object List(x1) -> List Filtered duplicate arguments: f2824_0_mk_Inc(x1, x2) -> f2824_0_mk_Inc(x2) Finished conversion. Obtained 1 rules.P rules: f2824_0_mk_Inc(i741:0) -> f2824_0_mk_Inc(i741:0 - 1) :|: i741:0 > 0 ---------------------------------------- (57) Obligation: Rules: f2824_0_mk_Inc(i741:0) -> f2824_0_mk_Inc(i741:0 - 1) :|: i741:0 > 0 ---------------------------------------- (58) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (59) Obligation: Rules: f2824_0_mk_Inc(i741:0) -> f2824_0_mk_Inc(arith) :|: i741:0 > 0 && arith = i741:0 - 1 ---------------------------------------- (60) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f2824_0_mk_Inc(i741:0) -> f2824_0_mk_Inc(arith) :|: i741:0 > 0 && arith = i741:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (61) Obligation: Termination digraph: Nodes: (1) f2824_0_mk_Inc(i741:0) -> f2824_0_mk_Inc(arith) :|: i741:0 > 0 && arith = i741:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (62) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (63) Obligation: Rules: f2824_0_mk_Inc(i741:0:0) -> f2824_0_mk_Inc(i741:0:0 - 1) :|: i741:0:0 > 0 ---------------------------------------- (64) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f2824_0_mk_Inc(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (65) Obligation: Rules: f2824_0_mk_Inc(i741:0:0) -> f2824_0_mk_Inc(c) :|: c = i741:0:0 - 1 && i741:0:0 > 0 ---------------------------------------- (66) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f2824_0_mk_Inc(x)] = x The following rules are decreasing: f2824_0_mk_Inc(i741:0:0) -> f2824_0_mk_Inc(c) :|: c = i741:0:0 - 1 && i741:0:0 > 0 The following rules are bounded: f2824_0_mk_Inc(i741:0:0) -> f2824_0_mk_Inc(c) :|: c = i741:0:0 - 1 && i741:0:0 > 0 ---------------------------------------- (67) YES ---------------------------------------- (68) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Test8.main([Ljava/lang/String;)V 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: ---------------------------------------- (69) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 21 IRulesP rules: f888_0_mk_Inc(EOS(STATIC_888), i185, java.lang.Object(List(EOC)), i185) -> f891_0_mk_LE(EOS(STATIC_891), i185 + -1, java.lang.Object(List(EOC)), i185) :|: TRUE f891_0_mk_LE(EOS(STATIC_891), i206, java.lang.Object(List(EOC)), i223) -> f897_0_mk_LE(EOS(STATIC_897), i206, java.lang.Object(List(EOC)), i223) :|: TRUE f897_0_mk_LE(EOS(STATIC_897), i206, java.lang.Object(List(EOC)), i223) -> f926_0_mk_New(EOS(STATIC_926), i206, java.lang.Object(List(EOC))) :|: i223 > 0 f926_0_mk_New(EOS(STATIC_926), i206, java.lang.Object(List(EOC))) -> f1197_0_mk_Duplicate(EOS(STATIC_1197), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f1197_0_mk_Duplicate(EOS(STATIC_1197), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f1206_0_mk_Load(EOS(STATIC_1206), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f1206_0_mk_Load(EOS(STATIC_1206), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f1216_0_mk_Load(EOS(STATIC_1216), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206) :|: TRUE f1216_0_mk_Load(EOS(STATIC_1216), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206) -> f1223_0_mk_InvokeMethod(EOS(STATIC_1223), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC))) :|: TRUE f1223_0_mk_InvokeMethod(EOS(STATIC_1223), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC))) -> f1229_0__init__Load(EOS(STATIC_1229), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC))) :|: TRUE f1229_0__init__Load(EOS(STATIC_1229), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC))) -> f1236_0__init__InvokeMethod(EOS(STATIC_1236), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f1236_0__init__InvokeMethod(EOS(STATIC_1236), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f1282_0__init__Load(EOS(STATIC_1282), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC))) :|: TRUE f1282_0__init__Load(EOS(STATIC_1282), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC))) -> f1288_0__init__Load(EOS(STATIC_1288), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f1288_0__init__Load(EOS(STATIC_1288), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f1294_0__init__FieldAccess(EOS(STATIC_1294), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206) :|: TRUE f1294_0__init__FieldAccess(EOS(STATIC_1294), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i206) -> f1304_0__init__Load(EOS(STATIC_1304), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f1304_0__init__Load(EOS(STATIC_1304), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f1314_0__init__Load(EOS(STATIC_1314), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f1314_0__init__Load(EOS(STATIC_1314), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f1346_0__init__FieldAccess(EOS(STATIC_1346), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f1346_0__init__FieldAccess(EOS(STATIC_1346), i206, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f1377_0__init__Return(EOS(STATIC_1377), i206, java.lang.Object(List(EOC))) :|: TRUE f1377_0__init__Return(EOS(STATIC_1377), i206, java.lang.Object(List(EOC))) -> f1388_0_mk_Store(EOS(STATIC_1388), i206, java.lang.Object(List(EOC))) :|: TRUE f1388_0_mk_Store(EOS(STATIC_1388), i206, java.lang.Object(List(EOC))) -> f1401_0_mk_JMP(EOS(STATIC_1401), i206, java.lang.Object(List(EOC))) :|: TRUE f1401_0_mk_JMP(EOS(STATIC_1401), i206, java.lang.Object(List(EOC))) -> f1549_0_mk_Load(EOS(STATIC_1549), i206, java.lang.Object(List(EOC))) :|: TRUE f1549_0_mk_Load(EOS(STATIC_1549), i206, java.lang.Object(List(EOC))) -> f884_0_mk_Load(EOS(STATIC_884), i206, java.lang.Object(List(EOC))) :|: TRUE f884_0_mk_Load(EOS(STATIC_884), i185, java.lang.Object(List(EOC))) -> f888_0_mk_Inc(EOS(STATIC_888), i185, java.lang.Object(List(EOC)), i185) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f888_0_mk_Inc(EOS(STATIC_888), i185:0, java.lang.Object(List(EOC)), i185:0) -> f888_0_mk_Inc(EOS(STATIC_888), i185:0 - 1, java.lang.Object(List(EOC)), i185:0 - 1) :|: i185:0 > 0 Filtered constant ground arguments: f888_0_mk_Inc(x1, x2, x3, x4) -> f888_0_mk_Inc(x2, x4) EOS(x1) -> EOS java.lang.Object(x1) -> java.lang.Object List(x1) -> List Filtered duplicate arguments: f888_0_mk_Inc(x1, x2) -> f888_0_mk_Inc(x2) Finished conversion. Obtained 1 rules.P rules: f888_0_mk_Inc(i185:0) -> f888_0_mk_Inc(i185:0 - 1) :|: i185:0 > 0 ---------------------------------------- (70) Obligation: Rules: f888_0_mk_Inc(i185:0) -> f888_0_mk_Inc(i185:0 - 1) :|: i185:0 > 0 ---------------------------------------- (71) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (72) Obligation: Rules: f888_0_mk_Inc(i185:0) -> f888_0_mk_Inc(arith) :|: i185:0 > 0 && arith = i185:0 - 1 ---------------------------------------- (73) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f888_0_mk_Inc(i185:0) -> f888_0_mk_Inc(arith) :|: i185:0 > 0 && arith = i185:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (74) Obligation: Termination digraph: Nodes: (1) f888_0_mk_Inc(i185:0) -> f888_0_mk_Inc(arith) :|: i185:0 > 0 && arith = i185:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (75) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (76) Obligation: Rules: f888_0_mk_Inc(i185:0:0) -> f888_0_mk_Inc(i185:0:0 - 1) :|: i185:0:0 > 0 ---------------------------------------- (77) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f888_0_mk_Inc(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (78) Obligation: Rules: f888_0_mk_Inc(i185:0:0) -> f888_0_mk_Inc(c) :|: c = i185:0:0 - 1 && i185:0:0 > 0 ---------------------------------------- (79) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f888_0_mk_Inc ] = f888_0_mk_Inc_1 The following rules are decreasing: f888_0_mk_Inc(i185:0:0) -> f888_0_mk_Inc(c) :|: c = i185:0:0 - 1 && i185:0:0 > 0 The following rules are bounded: f888_0_mk_Inc(i185:0:0) -> f888_0_mk_Inc(c) :|: c = i185:0:0 - 1 && i185:0:0 > 0 ---------------------------------------- (80) YES