/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, 96 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 489 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 9 ms] (6) AND (7) JBCTerminationSCC (8) SCCToIRSProof [SOUND, 85 ms] (9) IRSwT (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (11) IRSwT (12) IRSwTTerminationDigraphProof [EQUIVALENT, 8 ms] (13) IRSwT (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] (15) IRSwT (16) TempFilterProof [SOUND, 2 ms] (17) IRSwT (18) IRSwTToQDPProof [SOUND, 0 ms] (19) QDP (20) QDPSizeChangeProof [EQUIVALENT, 0 ms] (21) YES (22) JBCTerminationSCC (23) SCCToQDPProof [SOUND, 80 ms] (24) QDP (25) QDPSizeChangeProof [EQUIVALENT, 0 ms] (26) YES (27) JBCTerminationSCC (28) SCCToIRSProof [SOUND, 43 ms] (29) IRSwT (30) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (31) IRSwT (32) IRSwTTerminationDigraphProof [EQUIVALENT, 1 ms] (33) IRSwT (34) IntTRSCompressionProof [EQUIVALENT, 0 ms] (35) IRSwT (36) TempFilterProof [SOUND, 35 ms] (37) IntTRS (38) RankingReductionPairProof [EQUIVALENT, 15 ms] (39) YES (40) JBCTerminationSCC (41) SCCToIRSProof [SOUND, 74 ms] (42) IRSwT (43) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (44) IRSwT (45) IRSwTTerminationDigraphProof [EQUIVALENT, 33 ms] (46) IRSwT (47) IntTRSCompressionProof [EQUIVALENT, 0 ms] (48) IRSwT (49) TempFilterProof [SOUND, 21 ms] (50) IntTRS (51) RankingReductionPairProof [EQUIVALENT, 0 ms] (52) IntTRS (53) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (54) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class Test7 { public static void main(String[] args) { List[] ls = { List.mk(args.length), List.mk(args.length), List.mk(args.length) }; for (int k = 0; k < ls.length; k++) { int len = length(ls[0]); for (int i = 0; i < len; i++) bubble(ls[0]); } } private static void bubble(List l) { for (List cursor = l; cursor != null && cursor.getTail() != null; cursor = cursor.getTail()) if (cursor.head > cursor.getTail().head) { int temp = cursor.head; cursor.head = cursor.getTail().head; cursor.getTail().head = temp; } } private static int length(List list) { int len = 0; while (list != null) { list = list.getTail(); len++; } return len; } } 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 Test7 { public static void main(String[] args) { List[] ls = { List.mk(args.length), List.mk(args.length), List.mk(args.length) }; for (int k = 0; k < ls.length; k++) { int len = length(ls[0]); for (int i = 0; i < len; i++) bubble(ls[0]); } } private static void bubble(List l) { for (List cursor = l; cursor != null && cursor.getTail() != null; cursor = cursor.getTail()) if (cursor.head > cursor.getTail().head) { int temp = cursor.head; cursor.head = cursor.getTail().head; cursor.getTail().head = temp; } } private static int length(List list) { int len = 0; while (list != null) { list = list.getTail(); len++; } return len; } } 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: Test7.main([Ljava/lang/String;)V: Graph of 83 nodes with 1 SCC. List.mk(I)LList;: Graph of 54 nodes with 1 SCC. Test7.length(LList;)I: Graph of 22 nodes with 1 SCC. Test7.bubble(LList;)V: Graph of 63 nodes with 1 SCC. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 4 SCCss. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Test7.bubble(LList;)V SCC calls the following helper methods: 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 55 IRulesP rules: f3697_0_bubble_NULL(EOS(STATIC_3697), java.lang.Object(o485sub), java.lang.Object(o485sub)) -> f3698_0_bubble_NULL(EOS(STATIC_3698), java.lang.Object(o485sub), java.lang.Object(o485sub)) :|: TRUE f3698_0_bubble_NULL(EOS(STATIC_3698), java.lang.Object(o485sub), java.lang.Object(o485sub)) -> f3700_0_bubble_Load(EOS(STATIC_3700), java.lang.Object(o485sub)) :|: TRUE f3700_0_bubble_Load(EOS(STATIC_3700), java.lang.Object(o485sub)) -> f3702_0_bubble_InvokeMethod(EOS(STATIC_3702), java.lang.Object(o485sub), java.lang.Object(o485sub)) :|: TRUE f3702_0_bubble_InvokeMethod(EOS(STATIC_3702), java.lang.Object(o485sub), java.lang.Object(o485sub)) -> f3704_0_getTail_Load(EOS(STATIC_3704), java.lang.Object(o485sub), java.lang.Object(o485sub)) :|: TRUE f3704_0_getTail_Load(EOS(STATIC_3704), java.lang.Object(o485sub), java.lang.Object(o485sub)) -> f3706_0_getTail_FieldAccess(EOS(STATIC_3706), java.lang.Object(o485sub), java.lang.Object(o485sub)) :|: TRUE f3706_0_getTail_FieldAccess(EOS(STATIC_3706), java.lang.Object(List(EOC, o491, i561)), java.lang.Object(List(EOC, o491, i561))) -> f3707_0_getTail_FieldAccess(EOS(STATIC_3707), java.lang.Object(List(EOC, o491, i561)), java.lang.Object(List(EOC, o491, i561))) :|: TRUE f3707_0_getTail_FieldAccess(EOS(STATIC_3707), java.lang.Object(List(EOC, o491, i561)), java.lang.Object(List(EOC, o491, i561))) -> f3708_0_getTail_Return(EOS(STATIC_3708), java.lang.Object(List(EOC, o491, i561)), o491) :|: TRUE f3708_0_getTail_Return(EOS(STATIC_3708), java.lang.Object(List(EOC, o491, i561)), o491) -> f3709_0_bubble_NULL(EOS(STATIC_3709), java.lang.Object(List(EOC, o491, i561)), o491) :|: TRUE f3709_0_bubble_NULL(EOS(STATIC_3709), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), java.lang.Object(o492sub)) -> f3710_0_bubble_NULL(EOS(STATIC_3710), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), java.lang.Object(o492sub)) :|: TRUE f3710_0_bubble_NULL(EOS(STATIC_3710), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), java.lang.Object(o492sub)) -> f3712_0_bubble_Load(EOS(STATIC_3712), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) :|: TRUE f3712_0_bubble_Load(EOS(STATIC_3712), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) -> f3714_0_bubble_FieldAccess(EOS(STATIC_3714), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) :|: TRUE f3714_0_bubble_FieldAccess(EOS(STATIC_3714), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) -> f3715_0_bubble_Load(EOS(STATIC_3715), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561) :|: TRUE f3715_0_bubble_Load(EOS(STATIC_3715), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561) -> f3716_0_bubble_InvokeMethod(EOS(STATIC_3716), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) :|: TRUE f3716_0_bubble_InvokeMethod(EOS(STATIC_3716), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) -> f3717_0_getTail_Load(EOS(STATIC_3717), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) :|: TRUE f3717_0_getTail_Load(EOS(STATIC_3717), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) -> f3718_0_getTail_FieldAccess(EOS(STATIC_3718), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) :|: TRUE f3718_0_getTail_FieldAccess(EOS(STATIC_3718), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(o492sub), i561))) -> f3719_0_getTail_Return(EOS(STATIC_3719), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(o492sub)) :|: TRUE f3719_0_getTail_Return(EOS(STATIC_3719), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(o492sub)) -> f3720_0_bubble_FieldAccess(EOS(STATIC_3720), java.lang.Object(List(EOC, java.lang.Object(o492sub), i561)), i561, java.lang.Object(o492sub)) :|: TRUE f3720_0_bubble_FieldAccess(EOS(STATIC_3720), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, o496, i562))) -> f3721_0_bubble_FieldAccess(EOS(STATIC_3721), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3721_0_bubble_FieldAccess(EOS(STATIC_3721), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, o496, i562))) -> f3722_0_bubble_LE(EOS(STATIC_3722), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, i562) :|: TRUE f3722_0_bubble_LE(EOS(STATIC_3722), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, i562) -> f3723_0_bubble_LE(EOS(STATIC_3723), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, i562) :|: i561 <= i562 f3722_0_bubble_LE(EOS(STATIC_3722), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, i562) -> f3724_0_bubble_LE(EOS(STATIC_3724), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, i562) :|: i561 > i562 f3723_0_bubble_LE(EOS(STATIC_3723), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, i562) -> f3725_0_bubble_Load(EOS(STATIC_3725), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: i561 <= i562 f3725_0_bubble_Load(EOS(STATIC_3725), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3727_0_bubble_InvokeMethod(EOS(STATIC_3727), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: TRUE f3727_0_bubble_InvokeMethod(EOS(STATIC_3727), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3729_0_getTail_Load(EOS(STATIC_3729), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: TRUE f3729_0_getTail_Load(EOS(STATIC_3729), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3732_0_getTail_FieldAccess(EOS(STATIC_3732), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: TRUE f3732_0_getTail_FieldAccess(EOS(STATIC_3732), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3734_0_getTail_Return(EOS(STATIC_3734), java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3734_0_getTail_Return(EOS(STATIC_3734), java.lang.Object(List(EOC, o496, i562))) -> f3736_0_bubble_Store(EOS(STATIC_3736), java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3736_0_bubble_Store(EOS(STATIC_3736), java.lang.Object(List(EOC, o496, i562))) -> f3738_0_bubble_JMP(EOS(STATIC_3738), java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3738_0_bubble_JMP(EOS(STATIC_3738), java.lang.Object(List(EOC, o496, i562))) -> f3739_0_bubble_Load(EOS(STATIC_3739), java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3739_0_bubble_Load(EOS(STATIC_3739), java.lang.Object(List(EOC, o496, i562))) -> f3696_0_bubble_Load(EOS(STATIC_3696), java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3696_0_bubble_Load(EOS(STATIC_3696), o482) -> f3697_0_bubble_NULL(EOS(STATIC_3697), o482, o482) :|: TRUE f3724_0_bubble_LE(EOS(STATIC_3724), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, i562) -> f3726_0_bubble_Load(EOS(STATIC_3726), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: i561 > i562 f3726_0_bubble_Load(EOS(STATIC_3726), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3728_0_bubble_FieldAccess(EOS(STATIC_3728), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: TRUE f3728_0_bubble_FieldAccess(EOS(STATIC_3728), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3730_0_bubble_Store(EOS(STATIC_3730), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561) :|: TRUE f3730_0_bubble_Store(EOS(STATIC_3730), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561) -> f3731_0_bubble_Load(EOS(STATIC_3731), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561) :|: TRUE f3731_0_bubble_Load(EOS(STATIC_3731), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561) -> f3733_0_bubble_Load(EOS(STATIC_3733), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: TRUE f3733_0_bubble_Load(EOS(STATIC_3733), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3735_0_bubble_InvokeMethod(EOS(STATIC_3735), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: TRUE f3735_0_bubble_InvokeMethod(EOS(STATIC_3735), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3737_0_getTail_Load(EOS(STATIC_3737), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: TRUE f3737_0_getTail_Load(EOS(STATIC_3737), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3740_0_getTail_FieldAccess(EOS(STATIC_3740), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) :|: TRUE f3740_0_getTail_FieldAccess(EOS(STATIC_3740), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561))) -> f3741_0_getTail_Return(EOS(STATIC_3741), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3741_0_getTail_Return(EOS(STATIC_3741), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, o496, i562))) -> f3742_0_bubble_FieldAccess(EOS(STATIC_3742), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3742_0_bubble_FieldAccess(EOS(STATIC_3742), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), java.lang.Object(List(EOC, o496, i562))) -> f3743_0_bubble_FieldAccess(EOS(STATIC_3743), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i562) :|: TRUE f3743_0_bubble_FieldAccess(EOS(STATIC_3743), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i561)), i562) -> f3744_0_bubble_Load(EOS(STATIC_3744), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561) :|: TRUE f3744_0_bubble_Load(EOS(STATIC_3744), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561) -> f3745_0_bubble_InvokeMethod(EOS(STATIC_3745), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562))) :|: TRUE f3745_0_bubble_InvokeMethod(EOS(STATIC_3745), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562))) -> f3746_0_getTail_Load(EOS(STATIC_3746), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562))) :|: TRUE f3746_0_getTail_Load(EOS(STATIC_3746), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562))) -> f3747_0_getTail_FieldAccess(EOS(STATIC_3747), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562))) :|: TRUE f3747_0_getTail_FieldAccess(EOS(STATIC_3747), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562))) -> f3748_0_getTail_Return(EOS(STATIC_3748), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3748_0_getTail_Return(EOS(STATIC_3748), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, o496, i562))) -> f3749_0_bubble_Load(EOS(STATIC_3749), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, o496, i562))) :|: TRUE f3749_0_bubble_Load(EOS(STATIC_3749), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), i561, java.lang.Object(List(EOC, o496, i562))) -> f3750_0_bubble_FieldAccess(EOS(STATIC_3750), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), java.lang.Object(List(EOC, o496, i562)), i561) :|: TRUE f3750_0_bubble_FieldAccess(EOS(STATIC_3750), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i562)), i562)), java.lang.Object(List(EOC, o496, i562)), i561) -> f3751_0_bubble_Load(EOS(STATIC_3751), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i561)), i562))) :|: TRUE f3751_0_bubble_Load(EOS(STATIC_3751), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i561)), i562))) -> f3752_0_bubble_InvokeMethod(EOS(STATIC_3752), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i561)), i562))) :|: TRUE f3752_0_bubble_InvokeMethod(EOS(STATIC_3752), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i561)), i562))) -> f3753_0_getTail_Load(EOS(STATIC_3753), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i561)), i562))) :|: TRUE f3753_0_getTail_Load(EOS(STATIC_3753), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i561)), i562))) -> f3754_0_getTail_FieldAccess(EOS(STATIC_3754), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i561)), i562))) :|: TRUE f3754_0_getTail_FieldAccess(EOS(STATIC_3754), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496, i561)), i562))) -> f3755_0_getTail_Return(EOS(STATIC_3755), java.lang.Object(List(EOC, o496, i561))) :|: TRUE f3755_0_getTail_Return(EOS(STATIC_3755), java.lang.Object(List(EOC, o496, i561))) -> f3734_0_getTail_Return(EOS(STATIC_3734), java.lang.Object(List(EOC, o496, i561))) :|: TRUE Combined rules. Obtained 2 IRulesP rules: f3697_0_bubble_NULL(EOS(STATIC_3697), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496:0, i562:0)), i561:0)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496:0, i562:0)), i561:0))) -> f3697_0_bubble_NULL(EOS(STATIC_3697), java.lang.Object(List(EOC, o496:0, i561:0)), java.lang.Object(List(EOC, o496:0, i561:0))) :|: i562:0 < i561:0 f3697_0_bubble_NULL(EOS(STATIC_3697), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496:0, i562:0)), i561:0)), java.lang.Object(List(EOC, java.lang.Object(List(EOC, o496:0, i562:0)), i561:0))) -> f3697_0_bubble_NULL(EOS(STATIC_3697), java.lang.Object(List(EOC, o496:0, i562:0)), java.lang.Object(List(EOC, o496:0, i562:0))) :|: i562:0 >= i561:0 Filtered constant ground arguments: f3697_0_bubble_NULL(x1, x2, x3) -> f3697_0_bubble_NULL(x2, x3) EOS(x1) -> EOS List(x1, x2, x3) -> List(x2, x3) Filtered duplicate arguments: f3697_0_bubble_NULL(x1, x2) -> f3697_0_bubble_NULL(x2) Finished conversion. Obtained 2 rules.P rules: f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0, i562:0)), i561:0)), i561:0) -> f3697_0_bubble_NULL(java.lang.Object(List(o496:0, i561:0)), i561:0) :|: i562:0 < i561:0 f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0, i562:0)), i561:0)), i561:0) -> f3697_0_bubble_NULL(java.lang.Object(List(o496:0, i562:0)), i562:0) :|: i562:0 >= i561:0 ---------------------------------------- (9) Obligation: Rules: f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0, i562:0)), i561:0)), i561:0) -> f3697_0_bubble_NULL(java.lang.Object(List(o496:0, i561:0)), i561:0) :|: i562:0 < i561:0 f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(x, x1)), x2)), x2) -> f3697_0_bubble_NULL(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: f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0, i562:0)), i561:0)), i561:0) -> f3697_0_bubble_NULL(java.lang.Object(List(o496:0, i561:0)), i561:0) :|: i562:0 < i561:0 f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(x, x1)), x2)), x2) -> f3697_0_bubble_NULL(java.lang.Object(List(x, x1)), x1) :|: x1 >= x2 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0, i562:0)), i561:0)), i561:0) -> f3697_0_bubble_NULL(java.lang.Object(List(o496:0, i561:0)), i561:0) :|: i562:0 < i561:0 (2) f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(x, x1)), x2)), x2) -> f3697_0_bubble_NULL(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) f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0, i562:0)), i561:0)), i561:0) -> f3697_0_bubble_NULL(java.lang.Object(List(o496:0, i561:0)), i561:0) :|: i562:0 < i561:0 (2) f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(x, x1)), x2)), x2) -> f3697_0_bubble_NULL(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: f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0:0, i562:0:0)), i561:0:0)), i561:0:0) -> f3697_0_bubble_NULL(java.lang.Object(List(o496:0:0, i561:0:0)), i561:0:0) :|: i562:0:0 < i561:0:0 f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(x:0, x1:0)), x2:0)), x2:0) -> f3697_0_bubble_NULL(java.lang.Object(List(x:0, x1:0)), x1:0) :|: x2:0 <= x1:0 ---------------------------------------- (16) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f3697_0_bubble_NULL(VARIABLE, INTEGER) java.lang.Object(VARIABLE) List(VARIABLE, INTEGER) Removed predefined arithmetic. ---------------------------------------- (17) Obligation: Rules: f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0:0))))) -> f3697_0_bubble_NULL(java.lang.Object(List(o496: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: f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0:0))))) -> f3697_0_bubble_NULL(java.lang.Object(List(o496: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: *f3697_0_bubble_NULL(java.lang.Object(List(java.lang.Object(List(o496:0:0))))) -> f3697_0_bubble_NULL(java.lang.Object(List(o496: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: Test7.length(LList;)I SCC calls the following helper methods: 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 13 rules for P and 0 rules for R.P rules: f3449_0_length_NULL(EOS(STATIC_3449), java.lang.Object(o295sub), java.lang.Object(o295sub)) -> f3452_0_length_NULL(EOS(STATIC_3452), java.lang.Object(o295sub), java.lang.Object(o295sub)) :|: TRUE f3452_0_length_NULL(EOS(STATIC_3452), java.lang.Object(o295sub), java.lang.Object(o295sub)) -> f3456_0_length_Load(EOS(STATIC_3456), java.lang.Object(o295sub)) :|: TRUE f3456_0_length_Load(EOS(STATIC_3456), java.lang.Object(o295sub)) -> f3460_0_length_InvokeMethod(EOS(STATIC_3460), java.lang.Object(o295sub)) :|: TRUE f3460_0_length_InvokeMethod(EOS(STATIC_3460), java.lang.Object(o295sub)) -> f3464_0_getTail_Load(EOS(STATIC_3464), java.lang.Object(o295sub)) :|: TRUE f3464_0_getTail_Load(EOS(STATIC_3464), java.lang.Object(o295sub)) -> f3468_0_getTail_FieldAccess(EOS(STATIC_3468), java.lang.Object(o295sub)) :|: TRUE f3468_0_getTail_FieldAccess(EOS(STATIC_3468), java.lang.Object(List(EOC, o309))) -> f3470_0_getTail_FieldAccess(EOS(STATIC_3470), java.lang.Object(List(EOC, o309))) :|: TRUE f3470_0_getTail_FieldAccess(EOS(STATIC_3470), java.lang.Object(List(EOC, o309))) -> f3472_0_getTail_Return(EOS(STATIC_3472), o309) :|: TRUE f3472_0_getTail_Return(EOS(STATIC_3472), o309) -> f3474_0_length_Store(EOS(STATIC_3474), o309) :|: TRUE f3474_0_length_Store(EOS(STATIC_3474), o309) -> f3476_0_length_Inc(EOS(STATIC_3476), o309) :|: TRUE f3476_0_length_Inc(EOS(STATIC_3476), o309) -> f3478_0_length_JMP(EOS(STATIC_3478), o309) :|: TRUE f3478_0_length_JMP(EOS(STATIC_3478), o309) -> f3480_0_length_Load(EOS(STATIC_3480), o309) :|: TRUE f3480_0_length_Load(EOS(STATIC_3480), o309) -> f3447_0_length_Load(EOS(STATIC_3447), o309) :|: TRUE f3447_0_length_Load(EOS(STATIC_3447), o290) -> f3449_0_length_NULL(EOS(STATIC_3449), o290, o290) :|: TRUE R rules: Combined rules. Obtained 1 conditional rules for P and 0 conditional rules for R.P rules: f3449_0_length_NULL(EOS(STATIC_3449), java.lang.Object(List(EOC, o309:0)), java.lang.Object(List(EOC, o309:0))) -> f3449_0_length_NULL(EOS(STATIC_3449), o309:0, o309:0) :|: TRUE R rules: Filtered ground terms: f3449_0_length_NULL(x1, x2, x3) -> f3449_0_length_NULL(x2, x3) EOS(x1) -> EOS List(x1, x2) -> List(x2) Filtered duplicate args: f3449_0_length_NULL(x1, x2) -> f3449_0_length_NULL(x2) Combined rules. Obtained 1 conditional rules for P and 0 conditional rules for R.P rules: F3449_0_LENGTH_NULL(java.lang.Object(List(o309:0:0))) -> F3449_0_LENGTH_NULL(o309:0:0) :|: TRUE R rules: ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: F3449_0_LENGTH_NULL(java.lang.Object(List(o309:0:0))) -> F3449_0_LENGTH_NULL(o309: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: *F3449_0_LENGTH_NULL(java.lang.Object(List(o309:0:0))) -> F3449_0_LENGTH_NULL(o309: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: List.mk(I)LList; 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: ---------------------------------------- (28) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 21 IRulesP rules: f3338_0_mk_Inc(EOS(STATIC_3338), i435, java.lang.Object(List(EOC)), i435) -> f3340_0_mk_LE(EOS(STATIC_3340), i435 + -1, java.lang.Object(List(EOC)), i435) :|: TRUE f3340_0_mk_LE(EOS(STATIC_3340), i444, java.lang.Object(List(EOC)), i455) -> f3343_0_mk_LE(EOS(STATIC_3343), i444, java.lang.Object(List(EOC)), i455) :|: TRUE f3343_0_mk_LE(EOS(STATIC_3343), i444, java.lang.Object(List(EOC)), i455) -> f3346_0_mk_New(EOS(STATIC_3346), i444, java.lang.Object(List(EOC))) :|: i455 > 0 f3346_0_mk_New(EOS(STATIC_3346), i444, java.lang.Object(List(EOC))) -> f3348_0_mk_Duplicate(EOS(STATIC_3348), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3348_0_mk_Duplicate(EOS(STATIC_3348), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3350_0_mk_Load(EOS(STATIC_3350), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3350_0_mk_Load(EOS(STATIC_3350), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3352_0_mk_Load(EOS(STATIC_3352), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444) :|: TRUE f3352_0_mk_Load(EOS(STATIC_3352), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444) -> f3357_0_mk_InvokeMethod(EOS(STATIC_3357), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC))) :|: TRUE f3357_0_mk_InvokeMethod(EOS(STATIC_3357), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC))) -> f3359_0__init__Load(EOS(STATIC_3359), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC))) :|: TRUE f3359_0__init__Load(EOS(STATIC_3359), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC))) -> f3363_0__init__InvokeMethod(EOS(STATIC_3363), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3363_0__init__InvokeMethod(EOS(STATIC_3363), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3366_0__init__Load(EOS(STATIC_3366), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC))) :|: TRUE f3366_0__init__Load(EOS(STATIC_3366), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC))) -> f3369_0__init__Load(EOS(STATIC_3369), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3369_0__init__Load(EOS(STATIC_3369), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3372_0__init__FieldAccess(EOS(STATIC_3372), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444) :|: TRUE f3372_0__init__FieldAccess(EOS(STATIC_3372), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), i444) -> f3373_0__init__Load(EOS(STATIC_3373), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3373_0__init__Load(EOS(STATIC_3373), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3376_0__init__Load(EOS(STATIC_3376), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3376_0__init__Load(EOS(STATIC_3376), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3379_0__init__FieldAccess(EOS(STATIC_3379), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) :|: TRUE f3379_0__init__FieldAccess(EOS(STATIC_3379), i444, java.lang.Object(List(EOC)), java.lang.Object(List(EOC)), java.lang.Object(List(EOC))) -> f3382_0__init__Return(EOS(STATIC_3382), i444, java.lang.Object(List(EOC))) :|: TRUE f3382_0__init__Return(EOS(STATIC_3382), i444, java.lang.Object(List(EOC))) -> f3385_0_mk_Store(EOS(STATIC_3385), i444, java.lang.Object(List(EOC))) :|: TRUE f3385_0_mk_Store(EOS(STATIC_3385), i444, java.lang.Object(List(EOC))) -> f3388_0_mk_JMP(EOS(STATIC_3388), i444, java.lang.Object(List(EOC))) :|: TRUE f3388_0_mk_JMP(EOS(STATIC_3388), i444, java.lang.Object(List(EOC))) -> f3391_0_mk_Load(EOS(STATIC_3391), i444, java.lang.Object(List(EOC))) :|: TRUE f3391_0_mk_Load(EOS(STATIC_3391), i444, java.lang.Object(List(EOC))) -> f3336_0_mk_Load(EOS(STATIC_3336), i444, java.lang.Object(List(EOC))) :|: TRUE f3336_0_mk_Load(EOS(STATIC_3336), i435, java.lang.Object(List(EOC))) -> f3338_0_mk_Inc(EOS(STATIC_3338), i435, java.lang.Object(List(EOC)), i435) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f3338_0_mk_Inc(EOS(STATIC_3338), i435:0, java.lang.Object(List(EOC)), i435:0) -> f3338_0_mk_Inc(EOS(STATIC_3338), i435:0 - 1, java.lang.Object(List(EOC)), i435:0 - 1) :|: i435:0 > 0 Filtered constant ground arguments: f3338_0_mk_Inc(x1, x2, x3, x4) -> f3338_0_mk_Inc(x2, x4) EOS(x1) -> EOS java.lang.Object(x1) -> java.lang.Object List(x1) -> List Filtered duplicate arguments: f3338_0_mk_Inc(x1, x2) -> f3338_0_mk_Inc(x2) Finished conversion. Obtained 1 rules.P rules: f3338_0_mk_Inc(i435:0) -> f3338_0_mk_Inc(i435:0 - 1) :|: i435:0 > 0 ---------------------------------------- (29) Obligation: Rules: f3338_0_mk_Inc(i435:0) -> f3338_0_mk_Inc(i435:0 - 1) :|: i435:0 > 0 ---------------------------------------- (30) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (31) Obligation: Rules: f3338_0_mk_Inc(i435:0) -> f3338_0_mk_Inc(arith) :|: i435:0 > 0 && arith = i435:0 - 1 ---------------------------------------- (32) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f3338_0_mk_Inc(i435:0) -> f3338_0_mk_Inc(arith) :|: i435:0 > 0 && arith = i435:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (33) Obligation: Termination digraph: Nodes: (1) f3338_0_mk_Inc(i435:0) -> f3338_0_mk_Inc(arith) :|: i435:0 > 0 && arith = i435:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (34) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (35) Obligation: Rules: f3338_0_mk_Inc(i435:0:0) -> f3338_0_mk_Inc(i435:0:0 - 1) :|: i435:0:0 > 0 ---------------------------------------- (36) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f3338_0_mk_Inc(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (37) Obligation: Rules: f3338_0_mk_Inc(i435:0:0) -> f3338_0_mk_Inc(c) :|: c = i435:0:0 - 1 && i435:0:0 > 0 ---------------------------------------- (38) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f3338_0_mk_Inc ] = f3338_0_mk_Inc_1 The following rules are decreasing: f3338_0_mk_Inc(i435:0:0) -> f3338_0_mk_Inc(c) :|: c = i435:0:0 - 1 && i435:0:0 > 0 The following rules are bounded: f3338_0_mk_Inc(i435:0:0) -> f3338_0_mk_Inc(c) :|: c = i435:0:0 - 1 && i435:0:0 > 0 ---------------------------------------- (39) YES ---------------------------------------- (40) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: Test7.main([Ljava/lang/String;)V SCC calls the following helper methods: Test7.length(LList;)I, Test7.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: ---------------------------------------- (41) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 40 IRulesP rules: f3497_0_main_Load(EOS(STATIC_3497), java.lang.Object(ARRAY(matching1)), i504, i504) -> f3498_0_main_ArrayLength(EOS(STATIC_3498), java.lang.Object(ARRAY(3)), i504, i504, java.lang.Object(ARRAY(3))) :|: TRUE && matching1 = 3 f3498_0_main_ArrayLength(EOS(STATIC_3498), java.lang.Object(ARRAY(matching1)), i504, i504, java.lang.Object(ARRAY(matching2))) -> f3499_0_main_GE(EOS(STATIC_3499), java.lang.Object(ARRAY(3)), i504, i504, 3) :|: 3 >= 0 && matching1 = 3 && matching2 = 3 f3499_0_main_GE(EOS(STATIC_3499), java.lang.Object(ARRAY(matching1)), i506, i506, matching2) -> f3500_0_main_GE(EOS(STATIC_3500), java.lang.Object(ARRAY(3)), i506, i506, 3) :|: TRUE && matching1 = 3 && matching2 = 3 f3500_0_main_GE(EOS(STATIC_3500), java.lang.Object(ARRAY(matching1)), i506, i506, matching2) -> f3502_0_main_Load(EOS(STATIC_3502), java.lang.Object(ARRAY(3)), i506) :|: i506 < 3 && matching1 = 3 && matching2 = 3 f3502_0_main_Load(EOS(STATIC_3502), java.lang.Object(ARRAY(matching1)), i506) -> f3504_0_main_ConstantStackPush(EOS(STATIC_3504), java.lang.Object(ARRAY(3)), i506, java.lang.Object(ARRAY(3))) :|: TRUE && matching1 = 3 f3504_0_main_ConstantStackPush(EOS(STATIC_3504), java.lang.Object(ARRAY(matching1)), i506, java.lang.Object(ARRAY(matching2))) -> f3506_0_main_ArrayAccess(EOS(STATIC_3506), java.lang.Object(ARRAY(3)), i506, java.lang.Object(ARRAY(3)), 0) :|: TRUE && matching1 = 3 && matching2 = 3 f3506_0_main_ArrayAccess(EOS(STATIC_3506), java.lang.Object(ARRAY(matching1)), i506, java.lang.Object(ARRAY(matching2)), matching3) -> f3507_0_main_InvokeMethod(EOS(STATIC_3507), java.lang.Object(ARRAY(3)), i506, o320) :|: 0 < 3 && matching1 = 3 && matching2 = 3 && matching3 = 0 f3507_0_main_InvokeMethod(EOS(STATIC_3507), java.lang.Object(ARRAY(matching1)), i506, o320) -> f3508_0_length_ConstantStackPush(EOS(STATIC_3508), o320, o320) :|: TRUE && matching1 = 3 f3507_0_main_InvokeMethod(EOS(STATIC_3507), java.lang.Object(ARRAY(matching1)), i506, o320) -> f3508_1_length_ConstantStackPush(EOS(STATIC_3508), java.lang.Object(ARRAY(3)), i506, o320) :|: TRUE && matching1 = 3 f3508_0_length_ConstantStackPush(EOS(STATIC_3508), o320, o320) -> f3951_0_length_ConstantStackPush(EOS(STATIC_3951), o320, o320) :|: TRUE f3510_0_length_Return(EOS(STATIC_3510), java.lang.Object(ARRAY(matching1)), i506, i508) -> f3511_0_main_Store(EOS(STATIC_3511), java.lang.Object(ARRAY(3)), i506, i508) :|: TRUE && matching1 = 3 f3511_0_main_Store(EOS(STATIC_3511), java.lang.Object(ARRAY(matching1)), i506, i508) -> f3512_0_main_ConstantStackPush(EOS(STATIC_3512), java.lang.Object(ARRAY(3)), i506, i508) :|: TRUE && matching1 = 3 f3512_0_main_ConstantStackPush(EOS(STATIC_3512), java.lang.Object(ARRAY(matching1)), i506, i508) -> f3513_0_main_Store(EOS(STATIC_3513), java.lang.Object(ARRAY(3)), i506, i508, 0) :|: TRUE && matching1 = 3 f3513_0_main_Store(EOS(STATIC_3513), java.lang.Object(ARRAY(matching1)), i506, i508, matching2) -> f3514_0_main_Load(EOS(STATIC_3514), java.lang.Object(ARRAY(3)), i506, i508, 0) :|: TRUE && matching1 = 3 && matching2 = 0 f3514_0_main_Load(EOS(STATIC_3514), java.lang.Object(ARRAY(matching1)), i506, i508, matching2) -> f3546_0_main_Load(EOS(STATIC_3546), java.lang.Object(ARRAY(3)), i506, i508, 0) :|: TRUE && matching1 = 3 && matching2 = 0 f3546_0_main_Load(EOS(STATIC_3546), java.lang.Object(ARRAY(matching1)), i506, i514, i515) -> f3587_0_main_Load(EOS(STATIC_3587), java.lang.Object(ARRAY(3)), i506, i514, i515) :|: TRUE && matching1 = 3 f3587_0_main_Load(EOS(STATIC_3587), java.lang.Object(ARRAY(matching1)), i506, i524, i525) -> f3628_0_main_Load(EOS(STATIC_3628), java.lang.Object(ARRAY(3)), i506, i524, i525) :|: TRUE && matching1 = 3 f3628_0_main_Load(EOS(STATIC_3628), java.lang.Object(ARRAY(matching1)), i506, i534, i535) -> f3630_0_main_Load(EOS(STATIC_3630), java.lang.Object(ARRAY(3)), i506, i534, i535, i535) :|: TRUE && matching1 = 3 f3630_0_main_Load(EOS(STATIC_3630), java.lang.Object(ARRAY(matching1)), i506, i534, i535, i535) -> f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(3)), i506, i534, i535, i535, i534) :|: TRUE && matching1 = 3 f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(matching1)), i506, i534, i535, i535, i534) -> f3636_0_main_GE(EOS(STATIC_3636), java.lang.Object(ARRAY(3)), i506, i534, i535, i535, i534) :|: i535 >= i534 && matching1 = 3 f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(matching1)), i506, i534, i535, i535, i534) -> f3637_0_main_GE(EOS(STATIC_3637), java.lang.Object(ARRAY(3)), i506, i534, i535, i535, i534) :|: i535 < i534 && matching1 = 3 f3636_0_main_GE(EOS(STATIC_3636), java.lang.Object(ARRAY(matching1)), i506, i534, i535, i535, i534) -> f3639_0_main_Inc(EOS(STATIC_3639), java.lang.Object(ARRAY(3)), i506) :|: i535 >= i534 && matching1 = 3 f3639_0_main_Inc(EOS(STATIC_3639), java.lang.Object(ARRAY(matching1)), i506) -> f3642_0_main_JMP(EOS(STATIC_3642), java.lang.Object(ARRAY(3)), i506 + 1) :|: TRUE && matching1 = 3 f3642_0_main_JMP(EOS(STATIC_3642), java.lang.Object(ARRAY(matching1)), i539) -> f3645_0_main_Load(EOS(STATIC_3645), java.lang.Object(ARRAY(3)), i539) :|: TRUE && matching1 = 3 f3645_0_main_Load(EOS(STATIC_3645), java.lang.Object(ARRAY(matching1)), i539) -> f3496_0_main_Load(EOS(STATIC_3496), java.lang.Object(ARRAY(3)), i539) :|: TRUE && matching1 = 3 f3496_0_main_Load(EOS(STATIC_3496), java.lang.Object(ARRAY(matching1)), i504) -> f3497_0_main_Load(EOS(STATIC_3497), java.lang.Object(ARRAY(3)), i504, i504) :|: TRUE && matching1 = 3 f3637_0_main_GE(EOS(STATIC_3637), java.lang.Object(ARRAY(matching1)), i506, i534, i535, i535, i534) -> f3640_0_main_Load(EOS(STATIC_3640), java.lang.Object(ARRAY(3)), i506, i534, i535) :|: i535 < i534 && matching1 = 3 f3640_0_main_Load(EOS(STATIC_3640), java.lang.Object(ARRAY(matching1)), i506, i534, i535) -> f3643_0_main_ConstantStackPush(EOS(STATIC_3643), java.lang.Object(ARRAY(3)), i506, i534, i535, java.lang.Object(ARRAY(3))) :|: TRUE && matching1 = 3 f3643_0_main_ConstantStackPush(EOS(STATIC_3643), java.lang.Object(ARRAY(matching1)), i506, i534, i535, java.lang.Object(ARRAY(matching2))) -> f3646_0_main_ArrayAccess(EOS(STATIC_3646), java.lang.Object(ARRAY(3)), i506, i534, i535, java.lang.Object(ARRAY(3)), 0) :|: TRUE && matching1 = 3 && matching2 = 3 f3646_0_main_ArrayAccess(EOS(STATIC_3646), java.lang.Object(ARRAY(matching1)), i506, i534, i535, java.lang.Object(ARRAY(matching2)), matching3) -> f3648_0_main_InvokeMethod(EOS(STATIC_3648), java.lang.Object(ARRAY(3)), i506, i534, i535, o406) :|: 0 < 3 && matching1 = 3 && matching2 = 3 && matching3 = 0 f3648_0_main_InvokeMethod(EOS(STATIC_3648), java.lang.Object(ARRAY(matching1)), i506, i534, i535, o406) -> f3649_0_bubble_Load(EOS(STATIC_3649), o406, o406) :|: i534 >= 1 && i535 < i534 && matching1 = 3 f3648_0_main_InvokeMethod(EOS(STATIC_3648), java.lang.Object(ARRAY(matching1)), i506, i534, i535, o406) -> f3649_1_bubble_Load(EOS(STATIC_3649), java.lang.Object(ARRAY(3)), i506, i534, i535, o406) :|: i534 >= 1 && i535 < i534 && matching1 = 3 f3649_0_bubble_Load(EOS(STATIC_3649), o406, o406) -> f4003_0_bubble_Load(EOS(STATIC_4003), o406, o406) :|: TRUE f3705_0_bubble_Return(EOS(STATIC_3705), java.lang.Object(ARRAY(matching1)), i506, i534, i535) -> f3656_0_bubble_Return(EOS(STATIC_3656), java.lang.Object(ARRAY(3)), i506, i534, i535) :|: TRUE && matching1 = 3 f3656_0_bubble_Return(EOS(STATIC_3656), java.lang.Object(ARRAY(matching1)), i506, i534, i535) -> f3659_0_main_Inc(EOS(STATIC_3659), java.lang.Object(ARRAY(3)), i506, i534, i535) :|: TRUE && matching1 = 3 f3659_0_main_Inc(EOS(STATIC_3659), java.lang.Object(ARRAY(matching1)), i506, i534, i535) -> f3662_0_main_JMP(EOS(STATIC_3662), java.lang.Object(ARRAY(3)), i506, i534, i535 + 1) :|: TRUE && matching1 = 3 f3662_0_main_JMP(EOS(STATIC_3662), java.lang.Object(ARRAY(matching1)), i506, i534, i542) -> f3665_0_main_Load(EOS(STATIC_3665), java.lang.Object(ARRAY(3)), i506, i534, i542) :|: TRUE && matching1 = 3 f3665_0_main_Load(EOS(STATIC_3665), java.lang.Object(ARRAY(matching1)), i506, i534, i542) -> f3628_0_main_Load(EOS(STATIC_3628), java.lang.Object(ARRAY(3)), i506, i534, i542) :|: TRUE && matching1 = 3 f3508_1_length_ConstantStackPush(EOS(STATIC_3508), java.lang.Object(ARRAY(matching1)), i506, o333) -> f3510_0_length_Return(EOS(STATIC_3510), java.lang.Object(ARRAY(3)), i506, i508) :|: TRUE && matching1 = 3 f3649_1_bubble_Load(EOS(STATIC_3649), java.lang.Object(ARRAY(matching1)), i506, i534, i535, o406) -> f3705_0_bubble_Return(EOS(STATIC_3705), java.lang.Object(ARRAY(3)), i506, i534, i535) :|: TRUE && matching1 = 3 Combined rules. Obtained 4 IRulesP rules: f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(3)), i506:0, i534:0, i535:0, i535:0, i534:0) -> f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(3)), i506:0 + 1, i508:0, 0, 0, i508:0) :|: i506:0 < 2 && i535:0 >= i534:0 f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(3)), i506:0, i534:0, i535:0, i535:0, i534:0) -> f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(3)), i506:0, i534:0, i535:0 + 1, i535:0 + 1, i534:0) :|: i535:0 < i534:0 && i534:0 > 0 Removed following non-SCC rules: f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(3)), i506:0, i534:0, i535:0, i535:0, i534:0) -> f4003_0_bubble_Load(EOS(STATIC_4003), o406:0, o406:0) :|: i535:0 < i534:0 && i534:0 > 0 f3633_0_main_GE(EOS(STATIC_3633), java.lang.Object(ARRAY(3)), i506:0, i534:0, i535:0, i535:0, i534:0) -> f3951_0_length_ConstantStackPush(EOS(STATIC_3951), o320:0, o320:0) :|: i506:0 < 2 && i535:0 >= i534:0 Filtered constant ground arguments: f3633_0_main_GE(x1, x2, x3, x4, x5, x6, x7) -> f3633_0_main_GE(x3, x4, x5, x6, x7) EOS(x1) -> EOS java.lang.Object(x1) -> java.lang.Object ARRAY(x1) -> ARRAY Filtered duplicate arguments: f3633_0_main_GE(x1, x2, x3, x4, x5) -> f3633_0_main_GE(x1, x4, x5) Finished conversion. Obtained 2 rules.P rules: f3633_0_main_GE(i506:0, i535:0, i534:0) -> f3633_0_main_GE(i506:0 + 1, 0, i508:0) :|: i506:0 < 2 && i535:0 >= i534:0 f3633_0_main_GE(i506:0, i535:0, i534:0) -> f3633_0_main_GE(i506:0, i535:0 + 1, i534:0) :|: i535:0 < i534:0 && i534:0 > 0 ---------------------------------------- (42) Obligation: Rules: f3633_0_main_GE(i506:0, i535:0, i534:0) -> f3633_0_main_GE(i506:0 + 1, 0, i508:0) :|: i506:0 < 2 && i535:0 >= i534:0 f3633_0_main_GE(x, x1, x2) -> f3633_0_main_GE(x, x1 + 1, x2) :|: x1 < x2 && x2 > 0 ---------------------------------------- (43) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (44) Obligation: Rules: f3633_0_main_GE(i506:0, i535:0, i534:0) -> f3633_0_main_GE(arith, 0, i508:0) :|: i506:0 < 2 && i535:0 >= i534:0 && arith = i506:0 + 1 f3633_0_main_GE(x3, x4, x5) -> f3633_0_main_GE(x3, x6, x5) :|: x4 < x5 && x5 > 0 && x6 = x4 + 1 ---------------------------------------- (45) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f3633_0_main_GE(i506:0, i535:0, i534:0) -> f3633_0_main_GE(arith, 0, i508:0) :|: i506:0 < 2 && i535:0 >= i534:0 && arith = i506:0 + 1 (2) f3633_0_main_GE(x3, x4, x5) -> f3633_0_main_GE(x3, x6, x5) :|: x4 < x5 && x5 > 0 && x6 = x4 + 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (46) Obligation: Termination digraph: Nodes: (1) f3633_0_main_GE(i506:0, i535:0, i534:0) -> f3633_0_main_GE(arith, 0, i508:0) :|: i506:0 < 2 && i535:0 >= i534:0 && arith = i506:0 + 1 (2) f3633_0_main_GE(x3, x4, x5) -> f3633_0_main_GE(x3, x6, x5) :|: x4 < x5 && x5 > 0 && x6 = x4 + 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (47) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (48) Obligation: Rules: f3633_0_main_GE(i506:0:0, i535:0:0, i534:0:0) -> f3633_0_main_GE(i506:0:0 + 1, 0, i508:0:0) :|: i506:0:0 < 2 && i535:0:0 >= i534:0:0 f3633_0_main_GE(x3:0, x4:0, x5:0) -> f3633_0_main_GE(x3:0, x4:0 + 1, x5:0) :|: x5:0 > x4:0 && x5:0 > 0 ---------------------------------------- (49) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f3633_0_main_GE(VARIABLE, VARIABLE, VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (50) Obligation: Rules: f3633_0_main_GE(i506:0:0, i535:0:0, i534:0:0) -> f3633_0_main_GE(c, c1, i508:0:0) :|: c1 = 0 && c = i506:0:0 + 1 && (i506:0:0 < 2 && i535:0:0 >= i534:0:0) f3633_0_main_GE(x3:0, x4:0, x5:0) -> f3633_0_main_GE(x3:0, c2, x5:0) :|: c2 = x4:0 + 1 && (x5:0 > x4:0 && x5:0 > 0) ---------------------------------------- (51) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f3633_0_main_GE ] = -2*f3633_0_main_GE_1 The following rules are decreasing: f3633_0_main_GE(i506:0:0, i535:0:0, i534:0:0) -> f3633_0_main_GE(c, c1, i508:0:0) :|: c1 = 0 && c = i506:0:0 + 1 && (i506:0:0 < 2 && i535:0:0 >= i534:0:0) The following rules are bounded: f3633_0_main_GE(i506:0:0, i535:0:0, i534:0:0) -> f3633_0_main_GE(c, c1, i508:0:0) :|: c1 = 0 && c = i506:0:0 + 1 && (i506:0:0 < 2 && i535:0:0 >= i534:0:0) ---------------------------------------- (52) Obligation: Rules: f3633_0_main_GE(x3:0, x4:0, x5:0) -> f3633_0_main_GE(x3:0, c2, x5:0) :|: c2 = x4:0 + 1 && (x5:0 > x4:0 && x5:0 > 0) ---------------------------------------- (53) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f3633_0_main_GE(x, x1, x2)] = -x1 + x2 The following rules are decreasing: f3633_0_main_GE(x3:0, x4:0, x5:0) -> f3633_0_main_GE(x3:0, c2, x5:0) :|: c2 = x4:0 + 1 && (x5:0 > x4:0 && x5:0 > 0) The following rules are bounded: f3633_0_main_GE(x3:0, x4:0, x5:0) -> f3633_0_main_GE(x3:0, c2, x5:0) :|: c2 = x4:0 + 1 && (x5:0 > x4:0 && x5:0 > 0) ---------------------------------------- (54) YES