/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.jar /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty termination of the given Bare JBC problem could be proven: (0) Bare JBC problem (1) BareJBCToJBCProof [EQUIVALENT, 97 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 1831 ms] (4) JBCTerminationGraph (5) TerminationGraphToSCCProof [SOUND, 18 ms] (6) AND (7) JBCTerminationSCC (8) SCCToIRSProof [SOUND, 130 ms] (9) IRSwT (10) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (11) IRSwT (12) IRSwTTerminationDigraphProof [EQUIVALENT, 39 ms] (13) IRSwT (14) IntTRSCompressionProof [EQUIVALENT, 0 ms] (15) IRSwT (16) TempFilterProof [SOUND, 55 ms] (17) IntTRS (18) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (19) AND (20) IntTRS (21) RankingReductionPairProof [EQUIVALENT, 7 ms] (22) YES (23) IntTRS (24) RankingReductionPairProof [EQUIVALENT, 7 ms] (25) YES (26) JBCTerminationSCC (27) SCCToIRSProof [SOUND, 71 ms] (28) IRSwT (29) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (30) IRSwT (31) IRSwTTerminationDigraphProof [EQUIVALENT, 17 ms] (32) IRSwT (33) IntTRSCompressionProof [EQUIVALENT, 0 ms] (34) IRSwT (35) TempFilterProof [SOUND, 41 ms] (36) IntTRS (37) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (38) YES (39) JBCTerminationSCC (40) SCCToIRSProof [SOUND, 68 ms] (41) IRSwT (42) IRSFormatTransformerProof [EQUIVALENT, 1 ms] (43) IRSwT (44) IRSwTTerminationDigraphProof [EQUIVALENT, 11 ms] (45) IRSwT (46) IntTRSCompressionProof [EQUIVALENT, 0 ms] (47) IRSwT (48) TempFilterProof [SOUND, 11 ms] (49) IntTRS (50) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (51) YES (52) JBCTerminationSCC (53) SCCToIRSProof [SOUND, 397 ms] (54) IRSwT (55) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (56) IRSwT (57) IRSwTTerminationDigraphProof [EQUIVALENT, 78 ms] (58) IRSwT (59) IntTRSCompressionProof [EQUIVALENT, 0 ms] (60) IRSwT (61) TempFilterProof [SOUND, 28 ms] (62) IntTRS (63) RankingReductionPairProof [EQUIVALENT, 11 ms] (64) YES (65) JBCTerminationSCC (66) SCCToIRSProof [SOUND, 51 ms] (67) IRSwT (68) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (69) IRSwT (70) IRSwTTerminationDigraphProof [EQUIVALENT, 23 ms] (71) IRSwT (72) IntTRSCompressionProof [EQUIVALENT, 0 ms] (73) IRSwT (74) TempFilterProof [SOUND, 13 ms] (75) IntTRS (76) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (77) YES ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class MergeSort { static void merge(int g, int d, int m, int T[]) { int TT[] = new int[T.length]; int i, j; for (i = g; i <= m; i++) TT[i] = T[i]; for (i = m+1; i <= d; i++) TT[d+m+1-i] = T[i]; i = g; j = d; for (int k = g; k <= d; k++) if (TT[i] < TT[j]) { T[k] = TT[i]; i++; } else { T[k] = TT[j]; j--; } } static void sort(int g, int d, int T[]) { if (g < d) { int m = (g+d)/2; if (m-g < d-g) sort(g, m, T); if (d - (m+1) < d-g) sort(m+1, d, T); merge(g,d,m,T); } } public static void main(String args[]) { int n = args.length; int T[] = new int[n]; for (int i = 0; i < n; i++) T[i] = args[i].length(); /* for (int i = 0; i < n; i++) System.out.print(T[i] + " "); System.out.println(); */ sort(0, n-1, T); /* for (int i = 0; i < n; i++) System.out.print(T[i] + " "); System.out.println(); */ } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class MergeSort { static void merge(int g, int d, int m, int T[]) { int TT[] = new int[T.length]; int i, j; for (i = g; i <= m; i++) TT[i] = T[i]; for (i = m+1; i <= d; i++) TT[d+m+1-i] = T[i]; i = g; j = d; for (int k = g; k <= d; k++) if (TT[i] < TT[j]) { T[k] = TT[i]; i++; } else { T[k] = TT[j]; j--; } } static void sort(int g, int d, int T[]) { if (g < d) { int m = (g+d)/2; if (m-g < d-g) sort(g, m, T); if (d - (m+1) < d-g) sort(m+1, d, T); merge(g,d,m,T); } } public static void main(String args[]) { int n = args.length; int T[] = new int[n]; for (int i = 0; i < n; i++) T[i] = args[i].length(); /* for (int i = 0; i < n; i++) System.out.print(T[i] + " "); System.out.println(); */ sort(0, n-1, T); /* for (int i = 0; i < n; i++) System.out.print(T[i] + " "); System.out.println(); */ } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: MergeSort.main([Ljava/lang/String;)V: Graph of 135 nodes with 1 SCC. MergeSort.sort(II[I)V: Graph of 275 nodes with 0 SCCs. MergeSort.merge(III[I)V: Graph of 497 nodes with 3 SCCs. ---------------------------------------- (5) TerminationGraphToSCCProof (SOUND) Splitted TerminationGraph to 5 SCCss. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: MergeSort.merge(III[I)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: ---------------------------------------- (8) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 45 IRulesP rules: f5648_0_merge_Load(EOS(STATIC_5648), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, i1923) -> f5649_0_merge_GT(EOS(STATIC_5649), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, i1923, i557) :|: TRUE f5649_0_merge_GT(EOS(STATIC_5649), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, i1923, i557) -> f5651_0_merge_GT(EOS(STATIC_5651), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, i1923, i557) :|: i1923 <= i557 f5651_0_merge_GT(EOS(STATIC_5651), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, i1923, i557) -> f5653_0_merge_Load(EOS(STATIC_5653), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923) :|: i1923 <= i557 f5653_0_merge_Load(EOS(STATIC_5653), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923) -> f5655_0_merge_Load(EOS(STATIC_5655), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, java.lang.Object(ARRAY(i109))) :|: TRUE f5655_0_merge_Load(EOS(STATIC_5655), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, java.lang.Object(ARRAY(i109))) -> f5656_0_merge_ArrayAccess(EOS(STATIC_5656), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, java.lang.Object(ARRAY(i109)), i1921) :|: TRUE f5656_0_merge_ArrayAccess(EOS(STATIC_5656), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, java.lang.Object(ARRAY(i109)), i1964) -> f5661_0_merge_ArrayAccess(EOS(STATIC_5661), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, java.lang.Object(ARRAY(i109)), i1964) :|: TRUE f5661_0_merge_ArrayAccess(EOS(STATIC_5661), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, java.lang.Object(ARRAY(i109)), i1964) -> f5663_0_merge_ArrayAccess(EOS(STATIC_5663), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, java.lang.Object(ARRAY(i109)), i1964) :|: TRUE f5663_0_merge_ArrayAccess(EOS(STATIC_5663), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, java.lang.Object(ARRAY(i109)), i1964) -> f5665_0_merge_Load(EOS(STATIC_5665), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, i1965) :|: i1964 < i109 f5665_0_merge_Load(EOS(STATIC_5665), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, i1965) -> f5668_0_merge_Load(EOS(STATIC_5668), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, i1965, java.lang.Object(ARRAY(i109))) :|: TRUE f5668_0_merge_Load(EOS(STATIC_5668), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, i1965, java.lang.Object(ARRAY(i109))) -> f5670_0_merge_ArrayAccess(EOS(STATIC_5670), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1922, i1923, i1965, java.lang.Object(ARRAY(i109)), i1922) :|: TRUE f5670_0_merge_ArrayAccess(EOS(STATIC_5670), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, java.lang.Object(ARRAY(i109)), i1967) -> f5673_0_merge_ArrayAccess(EOS(STATIC_5673), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, java.lang.Object(ARRAY(i109)), i1967) :|: TRUE f5673_0_merge_ArrayAccess(EOS(STATIC_5673), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, java.lang.Object(ARRAY(i109)), i1967) -> f5677_0_merge_ArrayAccess(EOS(STATIC_5677), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, java.lang.Object(ARRAY(i109)), i1967) :|: TRUE f5677_0_merge_ArrayAccess(EOS(STATIC_5677), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, java.lang.Object(ARRAY(i109)), i1967) -> f5680_0_merge_GE(EOS(STATIC_5680), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, i1968) :|: i1967 < i109 f5680_0_merge_GE(EOS(STATIC_5680), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, i1968) -> f5684_0_merge_GE(EOS(STATIC_5684), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, i1968) :|: i1965 >= i1968 f5680_0_merge_GE(EOS(STATIC_5680), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, i1968) -> f5685_0_merge_GE(EOS(STATIC_5685), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, i1968) :|: i1965 < i1968 f5684_0_merge_GE(EOS(STATIC_5684), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, i1968) -> f5689_0_merge_Load(EOS(STATIC_5689), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923) :|: i1965 >= i1968 f5689_0_merge_Load(EOS(STATIC_5689), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923) -> f5693_0_merge_Load(EOS(STATIC_5693), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109))) :|: TRUE f5693_0_merge_Load(EOS(STATIC_5693), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109))) -> f5698_0_merge_Load(EOS(STATIC_5698), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923) :|: TRUE f5698_0_merge_Load(EOS(STATIC_5698), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923) -> f5703_0_merge_Load(EOS(STATIC_5703), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109))) :|: TRUE f5703_0_merge_Load(EOS(STATIC_5703), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109))) -> f5707_0_merge_ArrayAccess(EOS(STATIC_5707), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109)), i1967) :|: TRUE f5707_0_merge_ArrayAccess(EOS(STATIC_5707), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109)), i1967) -> f5712_0_merge_ArrayAccess(EOS(STATIC_5712), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109)), i1967) :|: TRUE f5712_0_merge_ArrayAccess(EOS(STATIC_5712), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109)), i1967) -> f5719_0_merge_ArrayAccess(EOS(STATIC_5719), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, i1969) :|: i1967 < i109 f5719_0_merge_ArrayAccess(EOS(STATIC_5719), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1972, java.lang.Object(ARRAY(i109)), i1972, i1969) -> f5726_0_merge_ArrayAccess(EOS(STATIC_5726), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1972, java.lang.Object(ARRAY(i109)), i1972, i1969) :|: TRUE f5726_0_merge_ArrayAccess(EOS(STATIC_5726), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1972, java.lang.Object(ARRAY(i109)), i1972, i1969) -> f5734_0_merge_ArrayAccess(EOS(STATIC_5734), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1972, java.lang.Object(ARRAY(i109)), i1972, i1969) :|: TRUE f5734_0_merge_ArrayAccess(EOS(STATIC_5734), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1972, java.lang.Object(ARRAY(i109)), i1972, i1969) -> f5744_0_merge_Inc(EOS(STATIC_5744), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1972) :|: i1972 < i109 f5744_0_merge_Inc(EOS(STATIC_5744), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1972) -> f5754_0_merge_Inc(EOS(STATIC_5754), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967 + -1, i1972) :|: TRUE f5754_0_merge_Inc(EOS(STATIC_5754), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1975, i1972) -> f5762_0_merge_JMP(EOS(STATIC_5762), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1975, i1972 + 1) :|: TRUE f5762_0_merge_JMP(EOS(STATIC_5762), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1975, i1977) -> f5772_0_merge_Load(EOS(STATIC_5772), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1975, i1977) :|: TRUE f5772_0_merge_Load(EOS(STATIC_5772), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1975, i1977) -> f5647_0_merge_Load(EOS(STATIC_5647), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1975, i1977) :|: TRUE f5647_0_merge_Load(EOS(STATIC_5647), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923) -> f5648_0_merge_Load(EOS(STATIC_5648), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1921, i1922, i1923, i1923) :|: TRUE f5685_0_merge_GE(EOS(STATIC_5685), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, i1965, i1968) -> f5690_0_merge_Load(EOS(STATIC_5690), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923) :|: i1965 < i1968 f5690_0_merge_Load(EOS(STATIC_5690), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923) -> f5694_0_merge_Load(EOS(STATIC_5694), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109))) :|: TRUE f5694_0_merge_Load(EOS(STATIC_5694), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109))) -> f5699_0_merge_Load(EOS(STATIC_5699), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923) :|: TRUE f5699_0_merge_Load(EOS(STATIC_5699), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923) -> f5704_0_merge_Load(EOS(STATIC_5704), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109))) :|: TRUE f5704_0_merge_Load(EOS(STATIC_5704), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109))) -> f5708_0_merge_ArrayAccess(EOS(STATIC_5708), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109)), i1964) :|: TRUE f5708_0_merge_ArrayAccess(EOS(STATIC_5708), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109)), i1964) -> f5714_0_merge_ArrayAccess(EOS(STATIC_5714), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109)), i1964) :|: TRUE f5714_0_merge_ArrayAccess(EOS(STATIC_5714), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, java.lang.Object(ARRAY(i109)), i1964) -> f5721_0_merge_ArrayAccess(EOS(STATIC_5721), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1923, java.lang.Object(ARRAY(i109)), i1923, i1970) :|: i1964 < i109 f5721_0_merge_ArrayAccess(EOS(STATIC_5721), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1974, java.lang.Object(ARRAY(i109)), i1974, i1970) -> f5728_0_merge_ArrayAccess(EOS(STATIC_5728), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1974, java.lang.Object(ARRAY(i109)), i1974, i1970) :|: TRUE f5728_0_merge_ArrayAccess(EOS(STATIC_5728), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1974, java.lang.Object(ARRAY(i109)), i1974, i1970) -> f5738_0_merge_ArrayAccess(EOS(STATIC_5738), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1974, java.lang.Object(ARRAY(i109)), i1974, i1970) :|: TRUE f5738_0_merge_ArrayAccess(EOS(STATIC_5738), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1974, java.lang.Object(ARRAY(i109)), i1974, i1970) -> f5747_0_merge_Inc(EOS(STATIC_5747), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1974) :|: i1974 < i109 f5747_0_merge_Inc(EOS(STATIC_5747), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964, i1967, i1974) -> f5756_0_merge_JMP(EOS(STATIC_5756), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1964 + 1, i1967, i1974) :|: TRUE f5756_0_merge_JMP(EOS(STATIC_5756), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1976, i1967, i1974) -> f5766_0_merge_Inc(EOS(STATIC_5766), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1976, i1967, i1974) :|: TRUE f5766_0_merge_Inc(EOS(STATIC_5766), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1976, i1967, i1974) -> f5775_0_merge_JMP(EOS(STATIC_5775), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1976, i1967, i1974 + 1) :|: TRUE f5775_0_merge_JMP(EOS(STATIC_5775), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1976, i1967, i1981) -> f5784_0_merge_Load(EOS(STATIC_5784), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1976, i1967, i1981) :|: TRUE f5784_0_merge_Load(EOS(STATIC_5784), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1976, i1967, i1981) -> f5647_0_merge_Load(EOS(STATIC_5647), i557, i557, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i1976, i1967, i1981) :|: TRUE Combined rules. Obtained 2 IRulesP rules: f5648_0_merge_Load(EOS(STATIC_5648), i557:0, i557:0, java.lang.Object(ARRAY(i109:0)), java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0, i1923:0, i1923:0) -> f5648_0_merge_Load(EOS(STATIC_5648), i557:0, i557:0, java.lang.Object(ARRAY(i109:0)), java.lang.Object(ARRAY(i109:0)), i1921:0 + 1, i1922:0, i1923:0 + 1, i1923:0 + 1) :|: i557:0 >= i1923:0 && i1921:0 < i109:0 && i1922:0 < i109:0 && i1968:0 > i1965:0 && i1923:0 < i109:0 f5648_0_merge_Load(EOS(STATIC_5648), i557:0, i557:0, java.lang.Object(ARRAY(i109:0)), java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0, i1923:0, i1923:0) -> f5648_0_merge_Load(EOS(STATIC_5648), i557:0, i557:0, java.lang.Object(ARRAY(i109:0)), java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0 - 1, i1923:0 + 1, i1923:0 + 1) :|: i557:0 >= i1923:0 && i1921:0 < i109:0 && i1922:0 < i109:0 && i1968:0 <= i1965:0 && i1923:0 < i109:0 Filtered constant ground arguments: f5648_0_merge_Load(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f5648_0_merge_Load(x2, x3, x4, x5, x6, x7, x8, x9) EOS(x1) -> EOS Filtered duplicate arguments: f5648_0_merge_Load(x1, x2, x3, x4, x5, x6, x7, x8) -> f5648_0_merge_Load(x2, x4, x5, x6, x8) Finished conversion. Obtained 2 rules.P rules: f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0, i1923:0, i109:0) -> f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0 + 1, i1922:0, i1923:0 + 1, i109:0) :|: i1921:0 < i109:0 && i557:0 >= i1923:0 && i1922:0 < i109:0 && i1923:0 < i109:0 && i1968:0 > i1965:0 f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0, i1923:0, i109:0) -> f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0 - 1, i1923:0 + 1, i109:0) :|: i1921:0 < i109:0 && i557:0 >= i1923:0 && i1922:0 < i109:0 && i1923:0 < i109:0 && i1968:0 <= i1965:0 ---------------------------------------- (9) Obligation: Rules: f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0, i1923:0, i109:0) -> f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0 + 1, i1922:0, i1923:0 + 1, i109:0) :|: i1921:0 < i109:0 && i557:0 >= i1923:0 && i1922:0 < i109:0 && i1923:0 < i109:0 && i1968:0 > i1965:0 f5648_0_merge_Load(x, java.lang.Object(ARRAY(x1)), x2, x3, x4, x1) -> f5648_0_merge_Load(x, java.lang.Object(ARRAY(x1)), x2, x3 - 1, x4 + 1, x1) :|: x2 < x1 && x >= x4 && x3 < x1 && x4 < x1 && x5 <= x6 ---------------------------------------- (10) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (11) Obligation: Rules: f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0, i1923:0, i109:0) -> f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), arith, i1922:0, arith1, i109:0) :|: i1921:0 < i109:0 && i557:0 >= i1923:0 && i1922:0 < i109:0 && i1923:0 < i109:0 && i1968:0 > i1965:0 && arith = i1921:0 + 1 && arith1 = i1923:0 + 1 f5648_0_merge_Load(x7, java.lang.Object(ARRAY(x8)), x9, x10, x11, x8) -> f5648_0_merge_Load(x7, java.lang.Object(ARRAY(x8)), x9, x12, x13, x8) :|: x9 < x8 && x7 >= x11 && x10 < x8 && x11 < x8 && x14 <= x15 && x12 = x10 - 1 && x13 = x11 + 1 ---------------------------------------- (12) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0, i1923:0, i109:0) -> f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), arith, i1922:0, arith1, i109:0) :|: i1921:0 < i109:0 && i557:0 >= i1923:0 && i1922:0 < i109:0 && i1923:0 < i109:0 && i1968:0 > i1965:0 && arith = i1921:0 + 1 && arith1 = i1923:0 + 1 (2) f5648_0_merge_Load(x7, java.lang.Object(ARRAY(x8)), x9, x10, x11, x8) -> f5648_0_merge_Load(x7, java.lang.Object(ARRAY(x8)), x9, x12, x13, x8) :|: x9 < x8 && x7 >= x11 && x10 < x8 && x11 < x8 && x14 <= x15 && x12 = x10 - 1 && x13 = x11 + 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (13) Obligation: Termination digraph: Nodes: (1) f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), i1921:0, i1922:0, i1923:0, i109:0) -> f5648_0_merge_Load(i557:0, java.lang.Object(ARRAY(i109:0)), arith, i1922:0, arith1, i109:0) :|: i1921:0 < i109:0 && i557:0 >= i1923:0 && i1922:0 < i109:0 && i1923:0 < i109:0 && i1968:0 > i1965:0 && arith = i1921:0 + 1 && arith1 = i1923:0 + 1 (2) f5648_0_merge_Load(x7, java.lang.Object(ARRAY(x8)), x9, x10, x11, x8) -> f5648_0_merge_Load(x7, java.lang.Object(ARRAY(x8)), x9, x12, x13, x8) :|: x9 < x8 && x7 >= x11 && x10 < x8 && x11 < x8 && x14 <= x15 && x12 = x10 - 1 && x13 = x11 + 1 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (14) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (15) Obligation: Rules: f5648_0_merge_Load(i557:0:0, java.lang.Object(ARRAY(i109:0:0)), i1921:0:0, i1922:0:0, i1923:0:0, i109:0:0) -> f5648_0_merge_Load(i557:0:0, java.lang.Object(ARRAY(i109:0:0)), i1921:0:0 + 1, i1922:0:0, i1923:0:0 + 1, i109:0:0) :|: i1923:0:0 < i109:0:0 && i1968:0:0 > i1965:0:0 && i1922:0:0 < i109:0:0 && i557:0:0 >= i1923:0:0 && i1921:0:0 < i109:0:0 f5648_0_merge_Load(x7:0, java.lang.Object(ARRAY(x8:0)), x9:0, x10:0, x11:0, x8:0) -> f5648_0_merge_Load(x7:0, java.lang.Object(ARRAY(x8:0)), x9:0, x10:0 - 1, x11:0 + 1, x8:0) :|: x8:0 > x11:0 && x15:0 >= x14:0 && x8:0 > x10:0 && x7:0 >= x11:0 && x9:0 < x8:0 ---------------------------------------- (16) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f5648_0_merge_Load(INTEGER, VARIABLE, INTEGER, INTEGER, INTEGER, INTEGER) java.lang.Object(VARIABLE) ARRAY(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (17) Obligation: Rules: f5648_0_merge_Load(i557:0:0, c, i1921:0:0, i1922:0:0, i1923:0:0, i109:0:0) -> f5648_0_merge_Load(i557:0:0, c1, c2, i1922:0:0, c3, i109:0:0) :|: c3 = i1923:0:0 + 1 && (c2 = i1921:0:0 + 1 && (c1 = 0 && c = 0)) && (i1923:0:0 < i109:0:0 && i1968:0:0 > i1965:0:0 && i1922:0:0 < i109:0:0 && i557:0:0 >= i1923:0:0 && i1921:0:0 < i109:0:0) f5648_0_merge_Load(x7:0, c4, x9:0, x10:0, x11:0, x8:0) -> f5648_0_merge_Load(x7:0, c5, x9:0, c6, c7, x8:0) :|: c7 = x11:0 + 1 && (c6 = x10:0 - 1 && (c5 = 0 && c4 = 0)) && (x8:0 > x11:0 && x15:0 >= x14:0 && x8:0 > x10:0 && x7:0 >= x11:0 && x9:0 < x8:0) ---------------------------------------- (18) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f5648_0_merge_Load(x, x1, x2, x3, x4, x5)] = x + c1*x1 - x3 - x4 + x5 The following rules are decreasing: f5648_0_merge_Load(i557:0:0, c, i1921:0:0, i1922:0:0, i1923:0:0, i109:0:0) -> f5648_0_merge_Load(i557:0:0, c1, c2, i1922:0:0, c3, i109:0:0) :|: c3 = i1923:0:0 + 1 && (c2 = i1921:0:0 + 1 && (c1 = 0 && c = 0)) && (i1923:0:0 < i109:0:0 && i1968:0:0 > i1965:0:0 && i1922:0:0 < i109:0:0 && i557:0:0 >= i1923:0:0 && i1921:0:0 < i109:0:0) The following rules are bounded: f5648_0_merge_Load(x7:0, c4, x9:0, x10:0, x11:0, x8:0) -> f5648_0_merge_Load(x7:0, c5, x9:0, c6, c7, x8:0) :|: c7 = x11:0 + 1 && (c6 = x10:0 - 1 && (c5 = 0 && c4 = 0)) && (x8:0 > x11:0 && x15:0 >= x14:0 && x8:0 > x10:0 && x7:0 >= x11:0 && x9:0 < x8:0) ---------------------------------------- (19) Complex Obligation (AND) ---------------------------------------- (20) Obligation: Rules: f5648_0_merge_Load(x7:0, c4, x9:0, x10:0, x11:0, x8:0) -> f5648_0_merge_Load(x7:0, c5, x9:0, c6, c7, x8:0) :|: c7 = x11:0 + 1 && (c6 = x10:0 - 1 && (c5 = 0 && c4 = 0)) && (x8:0 > x11:0 && x15:0 >= x14:0 && x8:0 > x10:0 && x7:0 >= x11:0 && x9:0 < x8:0) ---------------------------------------- (21) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f5648_0_merge_Load ] = f5648_0_merge_Load_6 + -1*f5648_0_merge_Load_5 The following rules are decreasing: f5648_0_merge_Load(x7:0, c4, x9:0, x10:0, x11:0, x8:0) -> f5648_0_merge_Load(x7:0, c5, x9:0, c6, c7, x8:0) :|: c7 = x11:0 + 1 && (c6 = x10:0 - 1 && (c5 = 0 && c4 = 0)) && (x8:0 > x11:0 && x15:0 >= x14:0 && x8:0 > x10:0 && x7:0 >= x11:0 && x9:0 < x8:0) The following rules are bounded: f5648_0_merge_Load(x7:0, c4, x9:0, x10:0, x11:0, x8:0) -> f5648_0_merge_Load(x7:0, c5, x9:0, c6, c7, x8:0) :|: c7 = x11:0 + 1 && (c6 = x10:0 - 1 && (c5 = 0 && c4 = 0)) && (x8:0 > x11:0 && x15:0 >= x14:0 && x8:0 > x10:0 && x7:0 >= x11:0 && x9:0 < x8:0) ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: Rules: f5648_0_merge_Load(i557:0:0, c, i1921:0:0, i1922:0:0, i1923:0:0, i109:0:0) -> f5648_0_merge_Load(i557:0:0, c1, c2, i1922:0:0, c3, i109:0:0) :|: c3 = i1923:0:0 + 1 && (c2 = i1921:0:0 + 1 && (c1 = 0 && c = 0)) && (i1923:0:0 < i109:0:0 && i1968:0:0 > i1965:0:0 && i1922:0:0 < i109:0:0 && i557:0:0 >= i1923:0:0 && i1921:0:0 < i109:0:0) ---------------------------------------- (24) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f5648_0_merge_Load ] = f5648_0_merge_Load_6 + -1*f5648_0_merge_Load_3 The following rules are decreasing: f5648_0_merge_Load(i557:0:0, c, i1921:0:0, i1922:0:0, i1923:0:0, i109:0:0) -> f5648_0_merge_Load(i557:0:0, c1, c2, i1922:0:0, c3, i109:0:0) :|: c3 = i1923:0:0 + 1 && (c2 = i1921:0:0 + 1 && (c1 = 0 && c = 0)) && (i1923:0:0 < i109:0:0 && i1968:0:0 > i1965:0:0 && i1922:0:0 < i109:0:0 && i557:0:0 >= i1923:0:0 && i1921:0:0 < i109:0:0) The following rules are bounded: f5648_0_merge_Load(i557:0:0, c, i1921:0:0, i1922:0:0, i1923:0:0, i109:0:0) -> f5648_0_merge_Load(i557:0:0, c1, c2, i1922:0:0, c3, i109:0:0) :|: c3 = i1923:0:0 + 1 && (c2 = i1921:0:0 + 1 && (c1 = 0 && c = 0)) && (i1923:0:0 < i109:0:0 && i1968:0:0 > i1965:0:0 && i1922:0:0 < i109:0:0 && i557:0:0 >= i1923:0:0 && i1921:0:0 < i109:0:0) ---------------------------------------- (25) YES ---------------------------------------- (26) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: MergeSort.merge(III[I)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: ---------------------------------------- (27) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 23 IRulesP rules: f4748_0_merge_Load(EOS(STATIC_4748), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, i379) -> f4751_0_merge_GT(EOS(STATIC_4751), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, i379, i336) :|: TRUE f4751_0_merge_GT(EOS(STATIC_4751), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, i379, i336) -> f4756_0_merge_GT(EOS(STATIC_4756), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, i379, i336) :|: i379 <= i336 f4756_0_merge_GT(EOS(STATIC_4756), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, i379, i336) -> f4760_0_merge_Load(EOS(STATIC_4760), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379) :|: i379 <= i336 f4760_0_merge_Load(EOS(STATIC_4760), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379) -> f4765_0_merge_Load(EOS(STATIC_4765), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109))) :|: TRUE f4765_0_merge_Load(EOS(STATIC_4765), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109))) -> f4771_0_merge_Load(EOS(STATIC_4771), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i336) :|: TRUE f4771_0_merge_Load(EOS(STATIC_4771), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i336) -> f4775_0_merge_IntArithmetic(EOS(STATIC_4775), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i336, i337) :|: TRUE f4775_0_merge_IntArithmetic(EOS(STATIC_4775), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i336, i337) -> f4780_0_merge_ConstantStackPush(EOS(STATIC_4780), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i336 + i337) :|: TRUE f4780_0_merge_ConstantStackPush(EOS(STATIC_4780), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i385) -> f4785_0_merge_IntArithmetic(EOS(STATIC_4785), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i385, 1) :|: TRUE f4785_0_merge_IntArithmetic(EOS(STATIC_4785), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i385, matching1) -> f4788_0_merge_Load(EOS(STATIC_4788), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i385 + 1) :|: TRUE && matching1 = 1 f4788_0_merge_Load(EOS(STATIC_4788), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i386) -> f4792_0_merge_IntArithmetic(EOS(STATIC_4792), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i386, i379) :|: TRUE f4792_0_merge_IntArithmetic(EOS(STATIC_4792), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i386, i379) -> f4797_0_merge_Load(EOS(STATIC_4797), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i386 - i379) :|: TRUE f4797_0_merge_Load(EOS(STATIC_4797), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i387) -> f4800_0_merge_Load(EOS(STATIC_4800), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i387, java.lang.Object(ARRAY(i109))) :|: TRUE f4800_0_merge_Load(EOS(STATIC_4800), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i387, java.lang.Object(ARRAY(i109))) -> f4804_0_merge_ArrayAccess(EOS(STATIC_4804), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, java.lang.Object(ARRAY(i109)), i387, java.lang.Object(ARRAY(i109)), i379) :|: TRUE f4804_0_merge_ArrayAccess(EOS(STATIC_4804), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i387, java.lang.Object(ARRAY(i109)), i389) -> f4810_0_merge_ArrayAccess(EOS(STATIC_4810), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i387, java.lang.Object(ARRAY(i109)), i389) :|: TRUE f4810_0_merge_ArrayAccess(EOS(STATIC_4810), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i387, java.lang.Object(ARRAY(i109)), i389) -> f4814_0_merge_ArrayAccess(EOS(STATIC_4814), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i387, java.lang.Object(ARRAY(i109)), i389) :|: TRUE f4814_0_merge_ArrayAccess(EOS(STATIC_4814), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i387, java.lang.Object(ARRAY(i109)), i389) -> f4820_0_merge_ArrayAccess(EOS(STATIC_4820), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i387, i392) :|: i389 < i109 f4820_0_merge_ArrayAccess(EOS(STATIC_4820), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i394, i392) -> f4830_0_merge_ArrayAccess(EOS(STATIC_4830), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i394, i392) :|: TRUE f4830_0_merge_ArrayAccess(EOS(STATIC_4830), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i394, i392) -> f4837_0_merge_ArrayAccess(EOS(STATIC_4837), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i394, i392) :|: TRUE f4837_0_merge_ArrayAccess(EOS(STATIC_4837), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389, java.lang.Object(ARRAY(i109)), i394, i392) -> f4845_0_merge_Inc(EOS(STATIC_4845), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389) :|: i394 < i109 f4845_0_merge_Inc(EOS(STATIC_4845), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389) -> f4856_0_merge_JMP(EOS(STATIC_4856), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i389 + 1) :|: TRUE f4856_0_merge_JMP(EOS(STATIC_4856), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i396) -> f4865_0_merge_Load(EOS(STATIC_4865), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i396) :|: TRUE f4865_0_merge_Load(EOS(STATIC_4865), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i396) -> f4746_0_merge_Load(EOS(STATIC_4746), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i396) :|: TRUE f4746_0_merge_Load(EOS(STATIC_4746), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379) -> f4748_0_merge_Load(EOS(STATIC_4748), i336, i337, i336, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i379, i379) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f4748_0_merge_Load(EOS(STATIC_4748), i336:0, i337:0, i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), java.lang.Object(ARRAY(i109:0)), i379:0, i379:0) -> f4748_0_merge_Load(EOS(STATIC_4748), i336:0, i337:0, i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), java.lang.Object(ARRAY(i109:0)), i379:0 + 1, i379:0 + 1) :|: i379:0 <= i336:0 && i336:0 + i337:0 + 1 - i379:0 < i109:0 && i379:0 < i109:0 Filtered constant ground arguments: f4748_0_merge_Load(x1, x2, x3, x4, x5, x6, x7, x8, x9) -> f4748_0_merge_Load(x2, x3, x4, x5, x6, x7, x8, x9) EOS(x1) -> EOS Filtered duplicate arguments: f4748_0_merge_Load(x1, x2, x3, x4, x5, x6, x7, x8) -> f4748_0_merge_Load(x3, x4, x6, x8) Finished conversion. Obtained 1 rules.P rules: f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), i379:0, i109:0) -> f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), i379:0 + 1, i109:0) :|: i336:0 + i337:0 + 1 - i379:0 < i109:0 && i379:0 < i109:0 && i379:0 <= i336:0 ---------------------------------------- (28) Obligation: Rules: f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), i379:0, i109:0) -> f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), i379:0 + 1, i109:0) :|: i336:0 + i337:0 + 1 - i379:0 < i109:0 && i379:0 < i109:0 && i379:0 <= i336:0 ---------------------------------------- (29) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (30) Obligation: Rules: f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), i379:0, i109:0) -> f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), arith, i109:0) :|: i336:0 + i337:0 + 1 - i379:0 < i109:0 && i379:0 < i109:0 && i379:0 <= i336:0 && arith = i379:0 + 1 ---------------------------------------- (31) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), i379:0, i109:0) -> f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), arith, i109:0) :|: i336:0 + i337:0 + 1 - i379:0 < i109:0 && i379:0 < i109:0 && i379:0 <= i336:0 && arith = i379:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (32) Obligation: Termination digraph: Nodes: (1) f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), i379:0, i109:0) -> f4748_0_merge_Load(i336:0, i337:0, java.lang.Object(ARRAY(i109:0)), arith, i109:0) :|: i336:0 + i337:0 + 1 - i379:0 < i109:0 && i379:0 < i109:0 && i379:0 <= i336:0 && arith = i379:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (33) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (34) Obligation: Rules: f4748_0_merge_Load(i336:0:0, i337:0:0, java.lang.Object(ARRAY(i109:0:0)), i379:0:0, i109:0:0) -> f4748_0_merge_Load(i336:0:0, i337:0:0, java.lang.Object(ARRAY(i109:0:0)), i379:0:0 + 1, i109:0:0) :|: i336:0:0 + i337:0:0 + 1 - i379:0:0 < i109:0:0 && i379:0:0 < i109:0:0 && i379:0:0 <= i336:0:0 ---------------------------------------- (35) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f4748_0_merge_Load(INTEGER, INTEGER, VARIABLE, INTEGER, INTEGER) java.lang.Object(VARIABLE) ARRAY(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (36) Obligation: Rules: f4748_0_merge_Load(i336:0:0, i337:0:0, c, i379:0:0, i109:0:0) -> f4748_0_merge_Load(i336:0:0, i337:0:0, c1, c2, i109:0:0) :|: c2 = i379:0:0 + 1 && (c1 = 0 && c = 0) && (i336:0:0 + i337:0:0 + 1 - i379:0:0 < i109:0:0 && i379:0:0 < i109:0:0 && i379:0:0 <= i336:0:0) ---------------------------------------- (37) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f4748_0_merge_Load(x, x1, x2, x3, x4)] = c2*x2 - x3 + x4 The following rules are decreasing: f4748_0_merge_Load(i336:0:0, i337:0:0, c, i379:0:0, i109:0:0) -> f4748_0_merge_Load(i336:0:0, i337:0:0, c1, c2, i109:0:0) :|: c2 = i379:0:0 + 1 && (c1 = 0 && c = 0) && (i336:0:0 + i337:0:0 + 1 - i379:0:0 < i109:0:0 && i379:0:0 < i109:0:0 && i379:0:0 <= i336:0:0) The following rules are bounded: f4748_0_merge_Load(i336:0:0, i337:0:0, c, i379:0:0, i109:0:0) -> f4748_0_merge_Load(i336:0:0, i337:0:0, c1, c2, i109:0:0) :|: c2 = i379:0:0 + 1 && (c1 = 0 && c = 0) && (i336:0:0 + i337:0:0 + 1 - i379:0:0 < i109:0:0 && i379:0:0 < i109:0:0 && i379:0:0 <= i336:0:0) ---------------------------------------- (38) YES ---------------------------------------- (39) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: MergeSort.merge(III[I)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: ---------------------------------------- (40) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 16 IRulesP rules: f4734_0_merge_Load(EOS(STATIC_4734), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, i376) -> f4735_0_merge_GT(EOS(STATIC_4735), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, i376, i337) :|: TRUE f4735_0_merge_GT(EOS(STATIC_4735), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, i376, i337) -> f4737_0_merge_GT(EOS(STATIC_4737), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, i376, i337) :|: i376 <= i337 f4737_0_merge_GT(EOS(STATIC_4737), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, i376, i337) -> f4739_0_merge_Load(EOS(STATIC_4739), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376) :|: i376 <= i337 f4739_0_merge_Load(EOS(STATIC_4739), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376) -> f4741_0_merge_Load(EOS(STATIC_4741), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109))) :|: TRUE f4741_0_merge_Load(EOS(STATIC_4741), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109))) -> f4743_0_merge_Load(EOS(STATIC_4743), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109)), i376) :|: TRUE f4743_0_merge_Load(EOS(STATIC_4743), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109)), i376) -> f4745_0_merge_Load(EOS(STATIC_4745), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109))) :|: TRUE f4745_0_merge_Load(EOS(STATIC_4745), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109))) -> f4747_0_merge_ArrayAccess(EOS(STATIC_4747), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109)), i376, java.lang.Object(ARRAY(i109)), i376) :|: TRUE f4747_0_merge_ArrayAccess(EOS(STATIC_4747), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381) -> f4750_0_merge_ArrayAccess(EOS(STATIC_4750), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381) :|: TRUE f4750_0_merge_ArrayAccess(EOS(STATIC_4750), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381) -> f4753_0_merge_ArrayAccess(EOS(STATIC_4753), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381) :|: TRUE f4753_0_merge_ArrayAccess(EOS(STATIC_4753), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381) -> f4757_0_merge_ArrayAccess(EOS(STATIC_4757), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, i382) :|: i381 < i109 f4757_0_merge_ArrayAccess(EOS(STATIC_4757), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, i382) -> f4762_0_merge_ArrayAccess(EOS(STATIC_4762), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, i382) :|: TRUE f4762_0_merge_ArrayAccess(EOS(STATIC_4762), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381, java.lang.Object(ARRAY(i109)), i381, i382) -> f4767_0_merge_Inc(EOS(STATIC_4767), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381) :|: i381 < i109 f4767_0_merge_Inc(EOS(STATIC_4767), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381) -> f4772_0_merge_JMP(EOS(STATIC_4772), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i381 + 1) :|: TRUE f4772_0_merge_JMP(EOS(STATIC_4772), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i383) -> f4777_0_merge_Load(EOS(STATIC_4777), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i383) :|: TRUE f4777_0_merge_Load(EOS(STATIC_4777), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i383) -> f4733_0_merge_Load(EOS(STATIC_4733), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i383) :|: TRUE f4733_0_merge_Load(EOS(STATIC_4733), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376) -> f4734_0_merge_Load(EOS(STATIC_4734), i337, i337, java.lang.Object(ARRAY(i109)), java.lang.Object(ARRAY(i109)), i376, i376) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f4734_0_merge_Load(EOS(STATIC_4734), i337:0, i337:0, java.lang.Object(ARRAY(i109:0)), java.lang.Object(ARRAY(i109:0)), i376:0, i376:0) -> f4734_0_merge_Load(EOS(STATIC_4734), i337:0, i337:0, java.lang.Object(ARRAY(i109:0)), java.lang.Object(ARRAY(i109:0)), i376:0 + 1, i376:0 + 1) :|: i376:0 <= i337:0 && i376:0 < i109:0 Filtered constant ground arguments: f4734_0_merge_Load(x1, x2, x3, x4, x5, x6, x7) -> f4734_0_merge_Load(x2, x3, x4, x5, x6, x7) EOS(x1) -> EOS Filtered duplicate arguments: f4734_0_merge_Load(x1, x2, x3, x4, x5, x6) -> f4734_0_merge_Load(x2, x4, x6) Finished conversion. Obtained 1 rules.P rules: f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), i376:0, i109:0) -> f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), i376:0 + 1, i109:0) :|: i376:0 <= i337:0 && i376:0 < i109:0 ---------------------------------------- (41) Obligation: Rules: f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), i376:0, i109:0) -> f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), i376:0 + 1, i109:0) :|: i376:0 <= i337:0 && i376:0 < i109:0 ---------------------------------------- (42) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (43) Obligation: Rules: f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), i376:0, i109:0) -> f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), arith, i109:0) :|: i376:0 <= i337:0 && i376:0 < i109:0 && arith = i376:0 + 1 ---------------------------------------- (44) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), i376:0, i109:0) -> f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), arith, i109:0) :|: i376:0 <= i337:0 && i376:0 < i109:0 && arith = i376:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (45) Obligation: Termination digraph: Nodes: (1) f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), i376:0, i109:0) -> f4734_0_merge_Load(i337:0, java.lang.Object(ARRAY(i109:0)), arith, i109:0) :|: i376:0 <= i337:0 && i376:0 < i109:0 && arith = i376:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (46) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (47) Obligation: Rules: f4734_0_merge_Load(i337:0:0, java.lang.Object(ARRAY(i109:0:0)), i376:0:0, i109:0:0) -> f4734_0_merge_Load(i337:0:0, java.lang.Object(ARRAY(i109:0:0)), i376:0:0 + 1, i109:0:0) :|: i376:0:0 <= i337:0:0 && i376:0:0 < i109:0:0 ---------------------------------------- (48) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f4734_0_merge_Load(INTEGER, VARIABLE, INTEGER, INTEGER) java.lang.Object(VARIABLE) ARRAY(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (49) Obligation: Rules: f4734_0_merge_Load(i337:0:0, c, i376:0:0, i109:0:0) -> f4734_0_merge_Load(i337:0:0, c1, c2, i109:0:0) :|: c2 = i376:0:0 + 1 && (c1 = 0 && c = 0) && (i376:0:0 <= i337:0:0 && i376:0:0 < i109:0:0) ---------------------------------------- (50) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f4734_0_merge_Load(x, x1, x2, x3)] = c1*x1 - x2 + x3 The following rules are decreasing: f4734_0_merge_Load(i337:0:0, c, i376:0:0, i109:0:0) -> f4734_0_merge_Load(i337:0:0, c1, c2, i109:0:0) :|: c2 = i376:0:0 + 1 && (c1 = 0 && c = 0) && (i376:0:0 <= i337:0:0 && i376:0:0 < i109:0:0) The following rules are bounded: f4734_0_merge_Load(i337:0:0, c, i376:0:0, i109:0:0) -> f4734_0_merge_Load(i337:0:0, c1, c2, i109:0:0) :|: c2 = i376:0:0 + 1 && (c1 = 0 && c = 0) && (i376:0:0 <= i337:0:0 && i376:0:0 < i109:0:0) ---------------------------------------- (51) YES ---------------------------------------- (52) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: MergeSort.sort(II[I)V SCC calls the following helper methods: MergeSort.sort(II[I)V, MergeSort.merge(III[I)V Performed SCC analyses: *Used field analysis yielded the following read fields: *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (53) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 77 IRulesP rules: f3676_0_sort_Load(EOS(STATIC_3676), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214) -> f3680_0_sort_GE(EOS(STATIC_3680), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214, i246) :|: TRUE f3680_0_sort_GE(EOS(STATIC_3680), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214, i246) -> f3696_0_sort_GE(EOS(STATIC_3696), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214, i246) :|: i214 < i246 f3696_0_sort_GE(EOS(STATIC_3696), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214, i246) -> f3934_0_sort_Load(EOS(STATIC_3934), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109))) :|: i214 < i246 f3934_0_sort_Load(EOS(STATIC_3934), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109))) -> f3940_0_sort_Load(EOS(STATIC_3940), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214) :|: TRUE f3940_0_sort_Load(EOS(STATIC_3940), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214) -> f3959_0_sort_IntArithmetic(EOS(STATIC_3959), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214, i246) :|: TRUE f3959_0_sort_IntArithmetic(EOS(STATIC_3959), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214, i246) -> f3983_0_sort_ConstantStackPush(EOS(STATIC_3983), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214 + i246) :|: TRUE f3983_0_sort_ConstantStackPush(EOS(STATIC_3983), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i266) -> f3998_0_sort_IntArithmetic(EOS(STATIC_3998), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i266, 2) :|: TRUE f3998_0_sort_IntArithmetic(EOS(STATIC_3998), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i266, matching1) -> f4005_0_sort_Store(EOS(STATIC_4005), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) :|: i267 = i266 / 2 && matching1 = 2 f4005_0_sort_Store(EOS(STATIC_4005), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) -> f4010_0_sort_Load(EOS(STATIC_4010), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) :|: TRUE f4010_0_sort_Load(EOS(STATIC_4010), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) -> f4016_0_sort_Load(EOS(STATIC_4016), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267) :|: TRUE f4016_0_sort_Load(EOS(STATIC_4016), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267) -> f4020_0_sort_IntArithmetic(EOS(STATIC_4020), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267, i214) :|: TRUE f4020_0_sort_IntArithmetic(EOS(STATIC_4020), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267, i214) -> f4025_0_sort_Load(EOS(STATIC_4025), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267 - i214) :|: TRUE f4025_0_sort_Load(EOS(STATIC_4025), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269) -> f4070_0_sort_Load(EOS(STATIC_4070), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i246) :|: TRUE f4070_0_sort_Load(EOS(STATIC_4070), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i246) -> f4092_0_sort_IntArithmetic(EOS(STATIC_4092), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i246, i214) :|: TRUE f4092_0_sort_IntArithmetic(EOS(STATIC_4092), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i246, i214) -> f4112_0_sort_GE(EOS(STATIC_4112), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i246 - i214) :|: TRUE f4112_0_sort_GE(EOS(STATIC_4112), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i273) -> f4128_0_sort_GE(EOS(STATIC_4128), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i273) :|: i269 >= i273 f4112_0_sort_GE(EOS(STATIC_4112), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i273) -> f4130_0_sort_GE(EOS(STATIC_4130), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i273) :|: i269 < i273 f4128_0_sort_GE(EOS(STATIC_4128), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i273) -> f4209_0_sort_Load(EOS(STATIC_4209), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) :|: i269 >= i273 f4209_0_sort_Load(EOS(STATIC_4209), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) -> f4217_0_sort_Load(EOS(STATIC_4217), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246) :|: TRUE f4217_0_sort_Load(EOS(STATIC_4217), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246) -> f4222_0_sort_ConstantStackPush(EOS(STATIC_4222), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246, i267) :|: TRUE f4222_0_sort_ConstantStackPush(EOS(STATIC_4222), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246, i267) -> f4230_0_sort_IntArithmetic(EOS(STATIC_4230), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246, i267, 1) :|: TRUE f4230_0_sort_IntArithmetic(EOS(STATIC_4230), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246, i267, matching1) -> f4236_0_sort_IntArithmetic(EOS(STATIC_4236), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246, i267 + 1) :|: TRUE && matching1 = 1 f4236_0_sort_IntArithmetic(EOS(STATIC_4236), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246, i277) -> f4240_0_sort_Load(EOS(STATIC_4240), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i246 - i277) :|: TRUE f4240_0_sort_Load(EOS(STATIC_4240), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278) -> f4252_0_sort_Load(EOS(STATIC_4252), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278, i246) :|: TRUE f4252_0_sort_Load(EOS(STATIC_4252), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278, i246) -> f4260_0_sort_IntArithmetic(EOS(STATIC_4260), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278, i246, i214) :|: TRUE f4260_0_sort_IntArithmetic(EOS(STATIC_4260), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278, i246, i214) -> f4268_0_sort_GE(EOS(STATIC_4268), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278, i246 - i214) :|: TRUE f4268_0_sort_GE(EOS(STATIC_4268), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278, i280) -> f4277_0_sort_GE(EOS(STATIC_4277), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278, i280) :|: i278 < i280 f4277_0_sort_GE(EOS(STATIC_4277), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i278, i280) -> f4579_0_sort_Load(EOS(STATIC_4579), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) :|: i278 < i280 f4579_0_sort_Load(EOS(STATIC_4579), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) -> f4585_0_sort_ConstantStackPush(EOS(STATIC_4585), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267) :|: TRUE f4585_0_sort_ConstantStackPush(EOS(STATIC_4585), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267) -> f4592_0_sort_IntArithmetic(EOS(STATIC_4592), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267, 1) :|: TRUE f4592_0_sort_IntArithmetic(EOS(STATIC_4592), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267, matching1) -> f4598_0_sort_Load(EOS(STATIC_4598), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i267 + 1) :|: TRUE && matching1 = 1 f4598_0_sort_Load(EOS(STATIC_4598), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i309) -> f4604_0_sort_Load(EOS(STATIC_4604), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i309, i246) :|: TRUE f4604_0_sort_Load(EOS(STATIC_4604), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i309, i246) -> f4610_0_sort_InvokeMethod(EOS(STATIC_4610), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i309, i246, java.lang.Object(ARRAY(i109))) :|: TRUE f4610_0_sort_InvokeMethod(EOS(STATIC_4610), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i309, i246, java.lang.Object(ARRAY(i109))) -> f4615_0_sort_Load(EOS(STATIC_4615), i309, i246, java.lang.Object(ARRAY(i109)), java.lang.Object(o196put), i309, i246, java.lang.Object(ARRAY(i109))) :|: i214 < i246 && i309 > i267 f4610_0_sort_InvokeMethod(EOS(STATIC_4610), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i309, i246, java.lang.Object(ARRAY(i109))) -> f4615_1_sort_Load(EOS(STATIC_4615), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i309, i246, java.lang.Object(ARRAY(i109))) :|: i214 < i246 && i309 > i267 f4615_0_sort_Load(EOS(STATIC_4615), i309, i246, java.lang.Object(ARRAY(i109)), java.lang.Object(o196put), i309, i246, java.lang.Object(ARRAY(i109))) -> f4619_0_sort_Load(EOS(STATIC_4619), i309, i246, java.lang.Object(ARRAY(i109)), java.lang.Object(o196put), i309, i246, java.lang.Object(ARRAY(i109))) :|: TRUE f4619_0_sort_Load(EOS(STATIC_4619), i309, i246, java.lang.Object(ARRAY(i109)), java.lang.Object(o196put), i309, i246, java.lang.Object(ARRAY(i109))) -> f4631_0_sort_Load(EOS(STATIC_4631), i309, i246, java.lang.Object(ARRAY(i109)), i309, i246, java.lang.Object(ARRAY(i109))) :|: TRUE f4631_0_sort_Load(EOS(STATIC_4631), i309, i246, java.lang.Object(ARRAY(i109)), i309, i246, java.lang.Object(ARRAY(i109))) -> f3671_0_sort_Load(EOS(STATIC_3671), i309, i246, java.lang.Object(ARRAY(i109)), i309, i246, java.lang.Object(ARRAY(i109))) :|: TRUE f3671_0_sort_Load(EOS(STATIC_3671), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109))) -> f3676_0_sort_Load(EOS(STATIC_3676), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i214) :|: TRUE f4130_0_sort_GE(EOS(STATIC_4130), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i269, i273) -> f4215_0_sort_Load(EOS(STATIC_4215), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) :|: i269 < i273 f4215_0_sort_Load(EOS(STATIC_4215), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267) -> f4218_0_sort_Load(EOS(STATIC_4218), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i214) :|: TRUE f4218_0_sort_Load(EOS(STATIC_4218), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i214) -> f4225_0_sort_Load(EOS(STATIC_4225), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i214, i267) :|: TRUE f4225_0_sort_Load(EOS(STATIC_4225), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i214, i267) -> f4231_0_sort_InvokeMethod(EOS(STATIC_4231), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i214, i267, java.lang.Object(ARRAY(i109))) :|: TRUE f4231_0_sort_InvokeMethod(EOS(STATIC_4231), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i214, i267, java.lang.Object(ARRAY(i109))) -> f4237_0_sort_Load(EOS(STATIC_4237), i214, i267, java.lang.Object(ARRAY(i109)), java.lang.Object(o196put), i214, i267, java.lang.Object(ARRAY(i109))) :|: i214 < i246 f4231_0_sort_InvokeMethod(EOS(STATIC_4231), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i214, i267, java.lang.Object(ARRAY(i109))) -> f4237_1_sort_Load(EOS(STATIC_4237), i214, i246, java.lang.Object(o196put), i214, i246, java.lang.Object(ARRAY(i109)), i267, i214, i267, java.lang.Object(ARRAY(i109))) :|: i214 < i246 f4237_0_sort_Load(EOS(STATIC_4237), i214, i267, java.lang.Object(ARRAY(i109)), java.lang.Object(o196put), i214, i267, java.lang.Object(ARRAY(i109))) -> f4244_0_sort_Load(EOS(STATIC_4244), i214, i267, java.lang.Object(ARRAY(i109)), java.lang.Object(o196put), i214, i267, java.lang.Object(ARRAY(i109))) :|: TRUE f4244_0_sort_Load(EOS(STATIC_4244), i214, i267, java.lang.Object(ARRAY(i109)), java.lang.Object(o196put), i214, i267, java.lang.Object(ARRAY(i109))) -> f4278_0_sort_Load(EOS(STATIC_4278), i214, i267, java.lang.Object(ARRAY(i109)), i214, i267, java.lang.Object(ARRAY(i109))) :|: TRUE f4278_0_sort_Load(EOS(STATIC_4278), i214, i267, java.lang.Object(ARRAY(i109)), i214, i267, java.lang.Object(ARRAY(i109))) -> f3671_0_sort_Load(EOS(STATIC_3671), i214, i267, java.lang.Object(ARRAY(i109)), i214, i267, java.lang.Object(ARRAY(i109))) :|: TRUE f4574_0_sort_Return(EOS(STATIC_4574), i291, i246, java.lang.Object(o196put), i291, i246, java.lang.Object(ARRAY(i109)), i293) -> f5252_0_sort_Return(EOS(STATIC_5252), i291, i246, java.lang.Object(o196put), i291, i246, java.lang.Object(ARRAY(i109)), i293) :|: TRUE f5252_0_sort_Return(EOS(STATIC_5252), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937) -> f5261_0_sort_Load(EOS(STATIC_5261), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937) :|: TRUE f5261_0_sort_Load(EOS(STATIC_5261), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937) -> f5266_0_sort_Load(EOS(STATIC_5266), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246) :|: TRUE f5266_0_sort_Load(EOS(STATIC_5266), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246) -> f5272_0_sort_ConstantStackPush(EOS(STATIC_5272), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246, i937) :|: TRUE f5272_0_sort_ConstantStackPush(EOS(STATIC_5272), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246, i937) -> f5278_0_sort_IntArithmetic(EOS(STATIC_5278), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246, i937, 1) :|: TRUE f5278_0_sort_IntArithmetic(EOS(STATIC_5278), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246, i937, matching1) -> f5284_0_sort_IntArithmetic(EOS(STATIC_5284), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246, i937 + 1) :|: TRUE && matching1 = 1 f5284_0_sort_IntArithmetic(EOS(STATIC_5284), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246, i960) -> f5291_0_sort_Load(EOS(STATIC_5291), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i246 - i960) :|: TRUE f5291_0_sort_Load(EOS(STATIC_5291), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965) -> f5298_0_sort_Load(EOS(STATIC_5298), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965, i246) :|: TRUE f5298_0_sort_Load(EOS(STATIC_5298), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965, i246) -> f5304_0_sort_IntArithmetic(EOS(STATIC_5304), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965, i246, i936) :|: TRUE f5304_0_sort_IntArithmetic(EOS(STATIC_5304), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965, i246, i936) -> f5310_0_sort_GE(EOS(STATIC_5310), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965, i246 - i936) :|: TRUE f5310_0_sort_GE(EOS(STATIC_5310), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965, i975) -> f5317_0_sort_GE(EOS(STATIC_5317), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965, i975) :|: i965 < i975 f5317_0_sort_GE(EOS(STATIC_5317), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i965, i975) -> f5325_0_sort_Load(EOS(STATIC_5325), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937) :|: i965 < i975 f5325_0_sort_Load(EOS(STATIC_5325), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937) -> f5344_0_sort_ConstantStackPush(EOS(STATIC_5344), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i937) :|: TRUE f5344_0_sort_ConstantStackPush(EOS(STATIC_5344), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i937) -> f5358_0_sort_IntArithmetic(EOS(STATIC_5358), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i937, 1) :|: TRUE f5358_0_sort_IntArithmetic(EOS(STATIC_5358), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i937, matching1) -> f5373_0_sort_Load(EOS(STATIC_5373), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i937 + 1) :|: TRUE && matching1 = 1 f5373_0_sort_Load(EOS(STATIC_5373), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i1148) -> f5385_0_sort_Load(EOS(STATIC_5385), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i1148, i246) :|: TRUE f5385_0_sort_Load(EOS(STATIC_5385), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i1148, i246) -> f5401_0_sort_InvokeMethod(EOS(STATIC_5401), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i1148, i246, java.lang.Object(ARRAY(i109))) :|: TRUE f5401_0_sort_InvokeMethod(EOS(STATIC_5401), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i1148, i246, java.lang.Object(ARRAY(i109))) -> f5415_0_sort_Load(EOS(STATIC_5415), i1148, i246, java.lang.Object(ARRAY(i109)), i1148, i246, java.lang.Object(ARRAY(i109))) :|: i246 > i936 && i1148 > i937 f5401_0_sort_InvokeMethod(EOS(STATIC_5401), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i1148, i246, java.lang.Object(ARRAY(i109))) -> f5415_1_sort_Load(EOS(STATIC_5415), i936, i246, java.lang.Object(o1629put), i936, i246, java.lang.Object(ARRAY(i109)), i937, i1148, i246, java.lang.Object(ARRAY(i109))) :|: i246 > i936 && i1148 > i937 f5415_0_sort_Load(EOS(STATIC_5415), i1148, i246, java.lang.Object(ARRAY(i109)), i1148, i246, java.lang.Object(ARRAY(i109))) -> f5427_0_sort_Load(EOS(STATIC_5427), i1148, i246, java.lang.Object(ARRAY(i109)), i1148, i246, java.lang.Object(ARRAY(i109))) :|: TRUE f5427_0_sort_Load(EOS(STATIC_5427), i1148, i246, java.lang.Object(ARRAY(i109)), i1148, i246, java.lang.Object(ARRAY(i109))) -> f5456_0_sort_Load(EOS(STATIC_5456), i1148, i246, java.lang.Object(ARRAY(i109)), i1148, i246, java.lang.Object(ARRAY(i109))) :|: TRUE f5456_0_sort_Load(EOS(STATIC_5456), i1148, i246, java.lang.Object(ARRAY(i109)), i1148, i246, java.lang.Object(ARRAY(i109))) -> f3671_0_sort_Load(EOS(STATIC_3671), i1148, i246, java.lang.Object(ARRAY(i109)), i1148, i246, java.lang.Object(ARRAY(i109))) :|: TRUE f5251_0_sort_Return(EOS(STATIC_5251), i910, i246, java.lang.Object(o196put), i910, i246, java.lang.Object(ARRAY(i109)), i912) -> f5252_0_sort_Return(EOS(STATIC_5252), i910, i246, java.lang.Object(o196put), i910, i246, java.lang.Object(ARRAY(i109)), i912) :|: TRUE f5391_0_sort_Return(EOS(STATIC_5391), i1175, i246, java.lang.Object(o196put), i1175, i246, java.lang.Object(ARRAY(i109)), i1177) -> f5252_0_sort_Return(EOS(STATIC_5252), i1175, i246, java.lang.Object(o196put), i1175, i246, java.lang.Object(ARRAY(i109)), i1177) :|: TRUE f5522_0_sort_Return(EOS(STATIC_5522), i1786, i246, java.lang.Object(o196put), i1786, i246, java.lang.Object(ARRAY(i109)), i1788) -> f5252_0_sort_Return(EOS(STATIC_5252), i1786, i246, java.lang.Object(o196put), i1786, i246, java.lang.Object(ARRAY(i109)), i1788) :|: TRUE f4237_1_sort_Load(EOS(STATIC_4237), i291, i246, java.lang.Object(o196put), i291, i246, java.lang.Object(ARRAY(i109)), i293, i291, i293, java.lang.Object(ARRAY(i109))) -> f4574_0_sort_Return(EOS(STATIC_4574), i291, i246, java.lang.Object(o196put), i291, i246, java.lang.Object(ARRAY(i109)), i293) :|: TRUE f4237_1_sort_Load(EOS(STATIC_4237), i910, i246, java.lang.Object(o196put), i910, i246, java.lang.Object(ARRAY(i109)), i912, i910, i912, java.lang.Object(ARRAY(i109))) -> f5251_0_sort_Return(EOS(STATIC_5251), i910, i246, java.lang.Object(o196put), i910, i246, java.lang.Object(ARRAY(i109)), i912) :|: TRUE f4237_1_sort_Load(EOS(STATIC_4237), i1175, i246, java.lang.Object(o196put), i1175, i246, java.lang.Object(ARRAY(i109)), i1177, i1175, i1177, java.lang.Object(ARRAY(i109))) -> f5391_0_sort_Return(EOS(STATIC_5391), i1175, i246, java.lang.Object(o196put), i1175, i246, java.lang.Object(ARRAY(i109)), i1177) :|: TRUE f4237_1_sort_Load(EOS(STATIC_4237), i1786, i246, java.lang.Object(o196put), i1786, i246, java.lang.Object(ARRAY(i109)), i1788, i1786, i1788, java.lang.Object(ARRAY(i109))) -> f5522_0_sort_Return(EOS(STATIC_5522), i1786, i246, java.lang.Object(o196put), i1786, i246, java.lang.Object(ARRAY(i109)), i1788) :|: TRUE Combined rules. Obtained 8 IRulesP rules: f3676_0_sort_Load(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) -> f3676_0_sort_Load'(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) :|: i246:0 > i214:0 && i246:0 - i214:0 <= div - i214:0 && i246:0 - i214:0 > i246:0 - (div + 1) && div + 1 > div f3676_0_sort_Load(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) -> f3676_0_sort_Load'(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) :|: i246:0 > i214:0 && i246:0 - i214:0 > i246:0 - (div + 1) && i246:0 - i214:0 > div - i214:0 && div + 1 > div f3676_0_sort_Load'(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) -> f3676_0_sort_Load(EOS(STATIC_3676), div + 1, i246:0, java.lang.Object(ARRAY(i109:0)), div + 1, i246:0, java.lang.Object(ARRAY(i109:0)), div + 1) :|: i246:0 > i214:0 && i246:0 - i214:0 <= div - i214:0 && i246:0 - i214:0 > i246:0 - (div + 1) && div + 1 > div && i214:0 + i246:0 - 2 * div < 2 && i214:0 + i246:0 - 2 * div > -2 f3676_0_sort_Load'(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) -> f3676_0_sort_Load(EOS(STATIC_3676), div + 1, i246:0, java.lang.Object(ARRAY(i109:0)), div + 1, i246:0, java.lang.Object(ARRAY(i109:0)), div + 1) :|: i246:0 > i214:0 && i246:0 - i214:0 > i246:0 - (div + 1) && i246:0 - i214:0 > div - i214:0 && div + 1 > div && i214:0 + i246:0 - 2 * div < 2 && i214:0 + i246:0 - 2 * div > -2 f3676_0_sort_Load(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) -> f3676_0_sort_Load'(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) :|: i246:0 > i214:0 && i246:0 - i214:0 > div - i214:0 f3676_0_sort_Load'(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) -> f3676_0_sort_Load(EOS(STATIC_3676), i214:0, div, java.lang.Object(ARRAY(i109:0)), i214:0, div, java.lang.Object(ARRAY(i109:0)), i214:0) :|: i246:0 > i214:0 && i246:0 - i214:0 > div - i214:0 && i214:0 + i246:0 - 2 * div < 2 && i214:0 + i246:0 - 2 * div > -2 Removed following non-SCC rules: f3676_0_sort_Load'(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) -> f4615_1_sort_Load(EOS(STATIC_4615), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), div, div + 1, i246:0, java.lang.Object(ARRAY(i109:0))) :|: i246:0 > i214:0 && i246:0 - i214:0 <= div - i214:0 && i246:0 - i214:0 > i246:0 - (div + 1) && div + 1 > div && i214:0 + i246:0 - 2 * div < 2 && i214:0 + i246:0 - 2 * div > -2 f3676_0_sort_Load'(EOS(STATIC_3676), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), i214:0) -> f5415_1_sort_Load(EOS(STATIC_5415), i214:0, i246:0, java.lang.Object(o196put:0), i214:0, i246:0, java.lang.Object(ARRAY(i109:0)), div, div + 1, i246:0, java.lang.Object(ARRAY(i109:0))) :|: i246:0 > i214:0 && i246:0 - i214:0 > i246:0 - (div + 1) && i246:0 - i214:0 > div - i214:0 && div + 1 > div && i214:0 + i246:0 - 2 * div < 2 && i214:0 + i246:0 - 2 * div > -2 Filtered constant ground arguments: f3676_0_sort_Load(x1, x2, x3, x4, x5, x6, x7, x8) -> f3676_0_sort_Load(x2, x3, x4, x5, x6, x7, x8) f3676_0_sort_Load'(x1, x2, x3, x4, x5, x6, x7, x8) -> f3676_0_sort_Load'(x2, x3, x4, x5, x6, x7, x8) EOS(x1) -> EOS Filtered duplicate arguments: f3676_0_sort_Load(x1, x2, x3, x4, x5, x6, x7) -> f3676_0_sort_Load(x3, x5, x6, x7) f3676_0_sort_Load'(x1, x2, x3, x4, x5, x6, x7) -> f3676_0_sort_Load'(x3, x5, x6, x7) Filtered unneeded arguments: f3676_0_sort_Load(x1, x2, x3, x4) -> f3676_0_sort_Load(x1, x2, x4) f3676_0_sort_Load'(x1, x2, x3, x4) -> f3676_0_sort_Load'(x2, x4) Finished conversion. Obtained 6 rules.P rules: f3676_0_sort_Load(java.lang.Object(o196put:0), i246:0, i214:0) -> f3676_0_sort_Load'(i246:0, i214:0) :|: i246:0 - i214:0 <= div - i214:0 && i246:0 > i214:0 && div + 1 > div && i246:0 - i214:0 > i246:0 - (div + 1) f3676_0_sort_Load(java.lang.Object(o196put:0), i246:0, i214:0) -> f3676_0_sort_Load'(i246:0, i214:0) :|: i246:0 - i214:0 > i246:0 - (div + 1) && i246:0 > i214:0 && div + 1 > div && i246:0 - i214:0 > div - i214:0 f3676_0_sort_Load'(i246:0, i214:0) -> f3676_0_sort_Load(java.lang.Object(ARRAY(i109:0)), i246:0, div + 1) :|: i246:0 - i214:0 <= div - i214:0 && i246:0 > i214:0 && i246:0 - i214:0 > i246:0 - (div + 1) && div + 1 > div && i214:0 + i246:0 - 2 * div > -2 && i214:0 + i246:0 - 2 * div < 2 f3676_0_sort_Load'(i246:0, i214:0) -> f3676_0_sort_Load(java.lang.Object(ARRAY(i109:0)), i246:0, div + 1) :|: i246:0 - i214:0 > i246:0 - (div + 1) && i246:0 > i214:0 && i246:0 - i214:0 > div - i214:0 && div + 1 > div && i214:0 + i246:0 - 2 * div > -2 && i214:0 + i246:0 - 2 * div < 2 f3676_0_sort_Load(java.lang.Object(o196put:0), i246:0, i214:0) -> f3676_0_sort_Load'(i246:0, i214:0) :|: i246:0 > i214:0 && i246:0 - i214:0 > div - i214:0 f3676_0_sort_Load'(i246:0, i214:0) -> f3676_0_sort_Load(java.lang.Object(ARRAY(i109:0)), div, i214:0) :|: i246:0 - i214:0 > div - i214:0 && i246:0 > i214:0 && i214:0 + i246:0 - 2 * div > -2 && i214:0 + i246:0 - 2 * div < 2 ---------------------------------------- (54) Obligation: Rules: f3676_0_sort_Load(java.lang.Object(x), x1, x2) -> f3676_0_sort_Load'(x1, x2) :|: x1 - x2 <= x3 - x2 && x1 > x2 && x3 + 1 > x3 && x1 - x2 > x1 - (x3 + 1) f3676_0_sort_Load(java.lang.Object(x4), x5, x6) -> f3676_0_sort_Load'(x5, x6) :|: x5 - x6 > x5 - (x7 + 1) && x5 > x6 && x7 + 1 > x7 && x5 - x6 > x7 - x6 f3676_0_sort_Load'(x8, x9) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x10)), x8, x11 + 1) :|: x8 - x9 <= x11 - x9 && x8 > x9 && x8 - x9 > x8 - (x11 + 1) && x11 + 1 > x11 && x9 + x8 - 2 * x11 > -2 && x9 + x8 - 2 * x11 < 2 f3676_0_sort_Load'(x12, x13) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x14)), x12, x15 + 1) :|: x12 - x13 > x12 - (x15 + 1) && x12 > x13 && x12 - x13 > x15 - x13 && x15 + 1 > x15 && x13 + x12 - 2 * x15 > -2 && x13 + x12 - 2 * x15 < 2 f3676_0_sort_Load(java.lang.Object(x16), x17, x18) -> f3676_0_sort_Load'(x17, x18) :|: x17 > x18 && x17 - x18 > x19 - x18 f3676_0_sort_Load'(x20, x21) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x22)), x23, x21) :|: x20 - x21 > x23 - x21 && x20 > x21 && x21 + x20 - 2 * x23 > -2 && x21 + x20 - 2 * x23 < 2 ---------------------------------------- (55) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (56) Obligation: Rules: f3676_0_sort_Load(java.lang.Object(x), x1, x2) -> f3676_0_sort_Load'(x1, x2) :|: x1 - x2 <= x3 - x2 && x1 > x2 && x3 + 1 > x3 && x1 - x2 > x1 - (x3 + 1) f3676_0_sort_Load(java.lang.Object(x4), x5, x6) -> f3676_0_sort_Load'(x5, x6) :|: x5 - x6 > x5 - (x7 + 1) && x5 > x6 && x7 + 1 > x7 && x5 - x6 > x7 - x6 f3676_0_sort_Load'(x8, x9) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x10)), x8, arith) :|: x8 - x9 <= x11 - x9 && x8 > x9 && x8 - x9 > x8 - (x11 + 1) && x11 + 1 > x11 && x9 + x8 - 2 * x11 > -2 && x9 + x8 - 2 * x11 < 2 && arith = x11 + 1 f3676_0_sort_Load'(x24, x25) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x26)), x24, x27) :|: x24 - x25 > x24 - (x28 + 1) && x24 > x25 && x24 - x25 > x28 - x25 && x28 + 1 > x28 && x25 + x24 - 2 * x28 > -2 && x25 + x24 - 2 * x28 < 2 && x27 = x28 + 1 f3676_0_sort_Load(java.lang.Object(x16), x17, x18) -> f3676_0_sort_Load'(x17, x18) :|: x17 > x18 && x17 - x18 > x19 - x18 f3676_0_sort_Load'(x20, x21) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x22)), x23, x21) :|: x20 - x21 > x23 - x21 && x20 > x21 && x21 + x20 - 2 * x23 > -2 && x21 + x20 - 2 * x23 < 2 ---------------------------------------- (57) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f3676_0_sort_Load(java.lang.Object(x), x1, x2) -> f3676_0_sort_Load'(x1, x2) :|: x1 - x2 <= x3 - x2 && x1 > x2 && x3 + 1 > x3 && x1 - x2 > x1 - (x3 + 1) (2) f3676_0_sort_Load(java.lang.Object(x4), x5, x6) -> f3676_0_sort_Load'(x5, x6) :|: x5 - x6 > x5 - (x7 + 1) && x5 > x6 && x7 + 1 > x7 && x5 - x6 > x7 - x6 (3) f3676_0_sort_Load'(x8, x9) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x10)), x8, arith) :|: x8 - x9 <= x11 - x9 && x8 > x9 && x8 - x9 > x8 - (x11 + 1) && x11 + 1 > x11 && x9 + x8 - 2 * x11 > -2 && x9 + x8 - 2 * x11 < 2 && arith = x11 + 1 (4) f3676_0_sort_Load'(x24, x25) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x26)), x24, x27) :|: x24 - x25 > x24 - (x28 + 1) && x24 > x25 && x24 - x25 > x28 - x25 && x28 + 1 > x28 && x25 + x24 - 2 * x28 > -2 && x25 + x24 - 2 * x28 < 2 && x27 = x28 + 1 (5) f3676_0_sort_Load(java.lang.Object(x16), x17, x18) -> f3676_0_sort_Load'(x17, x18) :|: x17 > x18 && x17 - x18 > x19 - x18 (6) f3676_0_sort_Load'(x20, x21) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x22)), x23, x21) :|: x20 - x21 > x23 - x21 && x20 > x21 && x21 + x20 - 2 * x23 > -2 && x21 + x20 - 2 * x23 < 2 Arcs: (1) -> (3), (4), (6) (2) -> (3), (4), (6) (4) -> (1), (2), (5) (5) -> (3), (4), (6) (6) -> (1), (2), (5) This digraph is fully evaluated! ---------------------------------------- (58) Obligation: Termination digraph: Nodes: (1) f3676_0_sort_Load(java.lang.Object(x), x1, x2) -> f3676_0_sort_Load'(x1, x2) :|: x1 - x2 <= x3 - x2 && x1 > x2 && x3 + 1 > x3 && x1 - x2 > x1 - (x3 + 1) (2) f3676_0_sort_Load'(x24, x25) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x26)), x24, x27) :|: x24 - x25 > x24 - (x28 + 1) && x24 > x25 && x24 - x25 > x28 - x25 && x28 + 1 > x28 && x25 + x24 - 2 * x28 > -2 && x25 + x24 - 2 * x28 < 2 && x27 = x28 + 1 (3) f3676_0_sort_Load(java.lang.Object(x4), x5, x6) -> f3676_0_sort_Load'(x5, x6) :|: x5 - x6 > x5 - (x7 + 1) && x5 > x6 && x7 + 1 > x7 && x5 - x6 > x7 - x6 (4) f3676_0_sort_Load'(x20, x21) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x22)), x23, x21) :|: x20 - x21 > x23 - x21 && x20 > x21 && x21 + x20 - 2 * x23 > -2 && x21 + x20 - 2 * x23 < 2 (5) f3676_0_sort_Load(java.lang.Object(x16), x17, x18) -> f3676_0_sort_Load'(x17, x18) :|: x17 > x18 && x17 - x18 > x19 - x18 Arcs: (1) -> (2), (4) (2) -> (1), (3), (5) (3) -> (2), (4) (4) -> (1), (3), (5) (5) -> (2), (4) This digraph is fully evaluated! ---------------------------------------- (59) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (60) Obligation: Rules: f3676_0_sort_Load(java.lang.Object(x:0), x1:0, x2:0) -> f3676_0_sort_Load'(x1:0, x2:0) :|: x3:0 + 1 > x3:0 && x1:0 - (x3:0 + 1) < x1:0 - x2:0 && x2:0 < x1:0 && x3:0 - x2:0 >= x1:0 - x2:0 f3676_0_sort_Load'(x24:0, x25:0) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x26:0)), x24:0, x28:0 + 1) :|: x25:0 + x24:0 - 2 * x28:0 > -2 && x25:0 + x24:0 - 2 * x28:0 < 2 && x28:0 + 1 > x28:0 && x28:0 - x25:0 < x24:0 - x25:0 && x25:0 < x24:0 && x24:0 - (x28:0 + 1) < x24:0 - x25:0 f3676_0_sort_Load'(x20:0, x21:0) -> f3676_0_sort_Load(java.lang.Object(ARRAY(x22:0)), x23:0, x21:0) :|: x21:0 + x20:0 - 2 * x23:0 > -2 && x21:0 + x20:0 - 2 * x23:0 < 2 && x21:0 < x20:0 && x23:0 - x21:0 < x20:0 - x21:0 f3676_0_sort_Load(java.lang.Object(x4:0), x5:0, x6:0) -> f3676_0_sort_Load'(x5:0, x6:0) :|: x7:0 + 1 > x7:0 && x7:0 - x6:0 < x5:0 - x6:0 && x6:0 < x5:0 && x5:0 - (x7:0 + 1) < x5:0 - x6:0 f3676_0_sort_Load(java.lang.Object(x16:0), x17:0, x18:0) -> f3676_0_sort_Load'(x17:0, x18:0) :|: x18:0 < x17:0 && x19:0 - x18:0 < x17:0 - x18:0 ---------------------------------------- (61) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f3676_0_sort_Load(VARIABLE, INTEGER, INTEGER) java.lang.Object(VARIABLE) f3676_0_sort_Load'(INTEGER, INTEGER) ARRAY(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (62) Obligation: Rules: f3676_0_sort_Load(c, x1:0, x2:0) -> f3676_0_sort_Load'(x1:0, x2:0) :|: c = 0 && (x3:0 + 1 > x3:0 && x1:0 - (x3:0 + 1) < x1:0 - x2:0 && x2:0 < x1:0 && x3:0 - x2:0 >= x1:0 - x2:0) f3676_0_sort_Load'(x24:0, x25:0) -> f3676_0_sort_Load(c1, x24:0, c2) :|: c2 = x28:0 + 1 && c1 = 0 && (x25:0 + x24:0 - 2 * x28:0 > -2 && x25:0 + x24:0 - 2 * x28:0 < 2 && x28:0 + 1 > x28:0 && x28:0 - x25:0 < x24:0 - x25:0 && x25:0 < x24:0 && x24:0 - (x28:0 + 1) < x24:0 - x25:0) f3676_0_sort_Load'(x20:0, x21:0) -> f3676_0_sort_Load(c3, x23:0, x21:0) :|: c3 = 0 && (x21:0 + x20:0 - 2 * x23:0 > -2 && x21:0 + x20:0 - 2 * x23:0 < 2 && x21:0 < x20:0 && x23:0 - x21:0 < x20:0 - x21:0) f3676_0_sort_Load(c4, x5:0, x6:0) -> f3676_0_sort_Load'(x5:0, x6:0) :|: c4 = 0 && (x7:0 + 1 > x7:0 && x7:0 - x6:0 < x5:0 - x6:0 && x6:0 < x5:0 && x5:0 - (x7:0 + 1) < x5:0 - x6:0) f3676_0_sort_Load(c5, x17:0, x18:0) -> f3676_0_sort_Load'(x17:0, x18:0) :|: c5 = 0 && (x18:0 < x17:0 && x19:0 - x18:0 < x17:0 - x18:0) ---------------------------------------- (63) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f3676_0_sort_Load ] = -2*f3676_0_sort_Load_3 + 2*f3676_0_sort_Load_2 + 1 [ f3676_0_sort_Load' ] = 2*f3676_0_sort_Load'_1 + -2*f3676_0_sort_Load'_2 The following rules are decreasing: f3676_0_sort_Load(c, x1:0, x2:0) -> f3676_0_sort_Load'(x1:0, x2:0) :|: c = 0 && (x3:0 + 1 > x3:0 && x1:0 - (x3:0 + 1) < x1:0 - x2:0 && x2:0 < x1:0 && x3:0 - x2:0 >= x1:0 - x2:0) f3676_0_sort_Load'(x24:0, x25:0) -> f3676_0_sort_Load(c1, x24:0, c2) :|: c2 = x28:0 + 1 && c1 = 0 && (x25:0 + x24:0 - 2 * x28:0 > -2 && x25:0 + x24:0 - 2 * x28:0 < 2 && x28:0 + 1 > x28:0 && x28:0 - x25:0 < x24:0 - x25:0 && x25:0 < x24:0 && x24:0 - (x28:0 + 1) < x24:0 - x25:0) f3676_0_sort_Load'(x20:0, x21:0) -> f3676_0_sort_Load(c3, x23:0, x21:0) :|: c3 = 0 && (x21:0 + x20:0 - 2 * x23:0 > -2 && x21:0 + x20:0 - 2 * x23:0 < 2 && x21:0 < x20:0 && x23:0 - x21:0 < x20:0 - x21:0) f3676_0_sort_Load(c4, x5:0, x6:0) -> f3676_0_sort_Load'(x5:0, x6:0) :|: c4 = 0 && (x7:0 + 1 > x7:0 && x7:0 - x6:0 < x5:0 - x6:0 && x6:0 < x5:0 && x5:0 - (x7:0 + 1) < x5:0 - x6:0) f3676_0_sort_Load(c5, x17:0, x18:0) -> f3676_0_sort_Load'(x17:0, x18:0) :|: c5 = 0 && (x18:0 < x17:0 && x19:0 - x18:0 < x17:0 - x18:0) The following rules are bounded: f3676_0_sort_Load(c, x1:0, x2:0) -> f3676_0_sort_Load'(x1:0, x2:0) :|: c = 0 && (x3:0 + 1 > x3:0 && x1:0 - (x3:0 + 1) < x1:0 - x2:0 && x2:0 < x1:0 && x3:0 - x2:0 >= x1:0 - x2:0) f3676_0_sort_Load'(x24:0, x25:0) -> f3676_0_sort_Load(c1, x24:0, c2) :|: c2 = x28:0 + 1 && c1 = 0 && (x25:0 + x24:0 - 2 * x28:0 > -2 && x25:0 + x24:0 - 2 * x28:0 < 2 && x28:0 + 1 > x28:0 && x28:0 - x25:0 < x24:0 - x25:0 && x25:0 < x24:0 && x24:0 - (x28:0 + 1) < x24:0 - x25:0) f3676_0_sort_Load'(x20:0, x21:0) -> f3676_0_sort_Load(c3, x23:0, x21:0) :|: c3 = 0 && (x21:0 + x20:0 - 2 * x23:0 > -2 && x21:0 + x20:0 - 2 * x23:0 < 2 && x21:0 < x20:0 && x23:0 - x21:0 < x20:0 - x21:0) f3676_0_sort_Load(c4, x5:0, x6:0) -> f3676_0_sort_Load'(x5:0, x6:0) :|: c4 = 0 && (x7:0 + 1 > x7:0 && x7:0 - x6:0 < x5:0 - x6:0 && x6:0 < x5:0 && x5:0 - (x7:0 + 1) < x5:0 - x6:0) f3676_0_sort_Load(c5, x17:0, x18:0) -> f3676_0_sort_Load'(x17:0, x18:0) :|: c5 = 0 && (x18:0 < x17:0 && x19:0 - x18:0 < x17:0 - x18:0) ---------------------------------------- (64) YES ---------------------------------------- (65) Obligation: SCC of termination graph based on JBC Program. SCC contains nodes from the following methods: MergeSort.main([Ljava/lang/String;)V SCC calls the following helper methods: Performed SCC analyses: *Used field analysis yielded the following read fields: *java.lang.String: [count] *Marker field analysis yielded the following relations that could be markers: ---------------------------------------- (66) SCCToIRSProof (SOUND) Transformed FIGraph SCCs to intTRSs. Log: Generated rules. Obtained 22 IRulesP rules: f1055_0_main_Load(EOS(STATIC_1055), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, i115) -> f1059_0_main_GE(EOS(STATIC_1059), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, i115, i114) :|: TRUE f1059_0_main_GE(EOS(STATIC_1059), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, i115, i114) -> f1075_0_main_GE(EOS(STATIC_1075), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, i115, i114) :|: i115 < i114 f1075_0_main_GE(EOS(STATIC_1075), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, i115, i114) -> f1080_0_main_Load(EOS(STATIC_1080), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115) :|: i115 < i114 f1080_0_main_Load(EOS(STATIC_1080), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115) -> f1087_0_main_Load(EOS(STATIC_1087), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114))) :|: TRUE f1087_0_main_Load(EOS(STATIC_1087), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114))) -> f1091_0_main_Load(EOS(STATIC_1091), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115) :|: TRUE f1091_0_main_Load(EOS(STATIC_1091), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115) -> f1095_0_main_Load(EOS(STATIC_1095), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114))) :|: TRUE f1095_0_main_Load(EOS(STATIC_1095), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114))) -> f1098_0_main_ArrayAccess(EOS(STATIC_1098), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115) :|: TRUE f1098_0_main_ArrayAccess(EOS(STATIC_1098), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115) -> f1103_0_main_ArrayAccess(EOS(STATIC_1103), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115) :|: TRUE f1103_0_main_ArrayAccess(EOS(STATIC_1103), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115) -> f1107_0_main_InvokeMethod(EOS(STATIC_1107), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, o81) :|: i115 < i114 f1107_0_main_InvokeMethod(EOS(STATIC_1107), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(o83sub)) -> f1111_0_main_InvokeMethod(EOS(STATIC_1111), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(o83sub)) :|: TRUE f1111_0_main_InvokeMethod(EOS(STATIC_1111), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(o84sub)) -> f1117_0_main_InvokeMethod(EOS(STATIC_1117), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(o84sub)) :|: TRUE f1117_0_main_InvokeMethod(EOS(STATIC_1117), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(o84sub)) -> f1132_0_length_Load(EOS(STATIC_1132), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(o84sub)) :|: TRUE f1132_0_length_Load(EOS(STATIC_1132), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(o84sub)) -> f1526_0_length_FieldAccess(EOS(STATIC_1526), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(o84sub)) :|: TRUE f1526_0_length_FieldAccess(EOS(STATIC_1526), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(java.lang.String(EOC, i146))) -> f1543_0_length_FieldAccess(EOS(STATIC_1543), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(java.lang.String(EOC, i146))) :|: i146 >= 0 f1543_0_length_FieldAccess(EOS(STATIC_1543), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(java.lang.String(EOC, i146))) -> f1550_0_length_Return(EOS(STATIC_1550), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, i146) :|: TRUE f1550_0_length_Return(EOS(STATIC_1550), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, i146) -> f1555_0_main_ArrayAccess(EOS(STATIC_1555), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, i146) :|: TRUE f1555_0_main_ArrayAccess(EOS(STATIC_1555), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, i146) -> f1569_0_main_ArrayAccess(EOS(STATIC_1569), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, i146) :|: TRUE f1569_0_main_ArrayAccess(EOS(STATIC_1569), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, java.lang.Object(ARRAY(i114)), i115, i146) -> f1576_0_main_Inc(EOS(STATIC_1576), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115) :|: i115 < i114 f1576_0_main_Inc(EOS(STATIC_1576), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115) -> f1580_0_main_JMP(EOS(STATIC_1580), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115 + 1) :|: TRUE f1580_0_main_JMP(EOS(STATIC_1580), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i155) -> f1648_0_main_Load(EOS(STATIC_1648), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i155) :|: TRUE f1648_0_main_Load(EOS(STATIC_1648), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i155) -> f1044_0_main_Load(EOS(STATIC_1044), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i155) :|: TRUE f1044_0_main_Load(EOS(STATIC_1044), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115) -> f1055_0_main_Load(EOS(STATIC_1055), java.lang.Object(ARRAY(i114)), java.lang.Object(ARRAY(i114)), i114, java.lang.Object(ARRAY(i114)), i115, i115) :|: TRUE Combined rules. Obtained 1 IRulesP rules: f1055_0_main_Load(EOS(STATIC_1055), java.lang.Object(ARRAY(i114:0)), java.lang.Object(ARRAY(i114:0)), i114:0, java.lang.Object(ARRAY(i114:0)), i115:0, i115:0) -> f1055_0_main_Load(EOS(STATIC_1055), java.lang.Object(ARRAY(i114:0)), java.lang.Object(ARRAY(i114:0)), i114:0, java.lang.Object(ARRAY(i114:0)), i115:0 + 1, i115:0 + 1) :|: i115:0 < i114:0 && i146:0 > -1 Filtered constant ground arguments: f1055_0_main_Load(x1, x2, x3, x4, x5, x6, x7) -> f1055_0_main_Load(x2, x3, x4, x5, x6, x7) EOS(x1) -> EOS Filtered duplicate arguments: f1055_0_main_Load(x1, x2, x3, x4, x5, x6) -> f1055_0_main_Load(x3, x4, x6) Finished conversion. Obtained 1 rules.P rules: f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), i115:0, i114:0) -> f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), i115:0 + 1, i114:0) :|: i115:0 < i114:0 && i146:0 > -1 ---------------------------------------- (67) Obligation: Rules: f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), i115:0, i114:0) -> f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), i115:0 + 1, i114:0) :|: i115:0 < i114:0 && i146:0 > -1 ---------------------------------------- (68) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (69) Obligation: Rules: f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), i115:0, i114:0) -> f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), arith, i114:0) :|: i115:0 < i114:0 && i146:0 > -1 && arith = i115:0 + 1 ---------------------------------------- (70) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), i115:0, i114:0) -> f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), arith, i114:0) :|: i115:0 < i114:0 && i146:0 > -1 && arith = i115:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (71) Obligation: Termination digraph: Nodes: (1) f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), i115:0, i114:0) -> f1055_0_main_Load(i114:0, java.lang.Object(ARRAY(i114:0)), arith, i114:0) :|: i115:0 < i114:0 && i146:0 > -1 && arith = i115:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (72) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (73) Obligation: Rules: f1055_0_main_Load(i114:0:0, java.lang.Object(ARRAY(i114:0:0)), i115:0:0, i114:0:0) -> f1055_0_main_Load(i114:0:0, java.lang.Object(ARRAY(i114:0:0)), i115:0:0 + 1, i114:0:0) :|: i115:0:0 < i114:0:0 && i146:0:0 > -1 ---------------------------------------- (74) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1055_0_main_Load(INTEGER, VARIABLE, INTEGER, INTEGER) java.lang.Object(VARIABLE) ARRAY(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (75) Obligation: Rules: f1055_0_main_Load(i114:0:0, c, i115:0:0, i114:0:0) -> f1055_0_main_Load(i114:0:0, c1, c2, i114:0:0) :|: c2 = i115:0:0 + 1 && (c1 = 0 && c = 0) && (i115:0:0 < i114:0:0 && i146:0:0 > -1) ---------------------------------------- (76) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1055_0_main_Load(x, x1, x2, x3)] = c1*x1 - x2 + x3 The following rules are decreasing: f1055_0_main_Load(i114:0:0, c, i115:0:0, i114:0:0) -> f1055_0_main_Load(i114:0:0, c1, c2, i114:0:0) :|: c2 = i115:0:0 + 1 && (c1 = 0 && c = 0) && (i115:0:0 < i114:0:0 && i146:0:0 > -1) The following rules are bounded: f1055_0_main_Load(i114:0:0, c, i115:0:0, i114:0:0) -> f1055_0_main_Load(i114:0:0, c1, c2, i114:0:0) :|: c2 = i115:0:0 + 1 && (c1 = 0 && c = 0) && (i115:0:0 < i114:0:0 && i146:0:0 > -1) ---------------------------------------- (77) YES