(0) Obligation:

Clauses:

mergesort([], []).
mergesort(.(X, []), .(X, [])).
mergesort(.(X, .(Y, Xs)), Ys) :- ','(split(.(X, .(Y, Xs)), X1s, X2s), ','(mergesort(X1s, Y1s), ','(mergesort(X2s, Y2s), merge(Y1s, Y2s, Ys)))).
split([], [], []).
split(.(X, Xs), .(X, Ys), Zs) :- split(Xs, Zs, Ys).
merge([], Xs, Xs).
merge(Xs, [], Xs).
merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(=(X, Y), merge(.(X, Xs), Ys, Zs)).

Queries:

mergesort(a,g).

(1) PredefinedPredicateTransformerProof (SOUND transformation)

Added definitions of predefined predicates [PROLOG].

(2) Obligation:

Clauses:

mergesort([], []).
mergesort(.(X, []), .(X, [])).
mergesort(.(X, .(Y, Xs)), Ys) :- ','(split(.(X, .(Y, Xs)), X1s, X2s), ','(mergesort(X1s, Y1s), ','(mergesort(X2s, Y2s), merge(Y1s, Y2s, Ys)))).
split([], [], []).
split(.(X, Xs), .(X, Ys), Zs) :- split(Xs, Zs, Ys).
merge([], Xs, Xs).
merge(Xs, [], Xs).
merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(=(X, Y), merge(.(X, Xs), Ys, Zs)).
=(X, X).

Queries:

mergesort(a,g).

(3) BuiltinConflictTransformerProof (SOUND transformation)

Renamed defined predicates conflicting with built-in predicates [PROLOG].

(4) Obligation:

Clauses:

mergesort([], []).
mergesort(.(X, []), .(X, [])).
mergesort(.(X, .(Y, Xs)), Ys) :- ','(split(.(X, .(Y, Xs)), X1s, X2s), ','(mergesort(X1s, Y1s), ','(mergesort(X2s, Y2s), merge(Y1s, Y2s, Ys)))).
split([], [], []).
split(.(X, Xs), .(X, Ys), Zs) :- split(Xs, Zs, Ys).
merge([], Xs, Xs).
merge(Xs, [], Xs).
merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(user_defined_=(X, Y), merge(.(X, Xs), Ys, Zs)).
user_defined_=(X, X).

Queries:

mergesort(a,g).

(5) PrologToDTProblemTransformerProof (SOUND transformation)

Built DT problem from termination graph.

(6) Obligation:

Triples:

split16(.(T49, T51), .(T49, X88), X89) :- split16(T51, X89, X88).
split12(T42, T44, .(T42, X70), X71) :- split16(T44, X71, X70).
p34(T72, T73, T74, X122, X123, X124, X125, X126) :- split12(T72, .(T73, T74), X122, X123).
p34(T72, T73, T74, T78, T79, X124, X125, X126) :- ','(splitc12(T72, .(T73, T74), T78, T79), mergesort38(T78, X124)).
p34(T72, T73, T74, T78, T84, T83, X125, X126) :- ','(splitc12(T72, .(T73, T74), T78, T84), ','(mergesortc38(T78, T83), mergesort38(T84, X125))).
p34(T72, T73, T74, T78, T84, T106, T105, X126) :- ','(splitc12(T72, .(T73, T74), T78, T84), ','(mergesortc38(T78, T106), ','(mergesortc38(T84, T105), merge54(T106, T105, X126)))).
mergesort38(.(T99, .(T100, T101)), X171) :- p34(T99, T100, T101, X167, X168, X169, X170, X171).
merge54(.(T143, T144), .(T143, T142), .(T143, X213)) :- merge54(.(T143, T144), T142, X213).
mergesort25(T72, .(T73, T74), X126) :- p34(T72, T73, T74, X122, X123, X124, X125, X126).
merge152(T439, T441, .(T439, T440), .(T439, T429)) :- merge152(T439, T441, T440, T429).
mergesort1(.(T29, .(T27, T28)), []) :- split12(T27, T28, X41, X40).
mergesort1(.(T34, .(T27, T28)), []) :- ','(splitc12(T27, T28, T32, T33), mergesort25(T34, T33, X12)).
mergesort1(.(T34, .(T27, T28)), []) :- ','(splitc12(T27, T28, T55, T33), ','(mergesortc25(T34, T33, T54), mergesort38(T55, X13))).
mergesort1(.(T34, .(T27, T28)), []) :- ','(splitc12(T27, T28, T55, T33), ','(mergesortc25(T34, T33, T150), ','(mergesortc38(T55, T149), merge72(T150, T149)))).
mergesort1(.(T196, .(T194, T195)), .(T176, [])) :- split12(T194, T195, X292, X291).
mergesort1(.(T201, .(T194, T195)), .(T176, [])) :- ','(splitc12(T194, T195, T199, T200), mergesort25(T201, T200, X263)).
mergesort1(.(T201, .(T194, T195)), .(T176, [])) :- ','(splitc12(T194, T195, T207, T200), ','(mergesortc25(T201, T200, T206), mergesort38(T207, X264))).
mergesort1(.(T201, .(T194, T195)), .(T261, [])) :- ','(splitc12(T194, T195, T207, T200), ','(mergesortc25(T201, T200, .(T261, T263)), ','(mergesortc38(T207, .(T261, T262)), merge72(.(T261, T263), T262)))).
mergesort1(.(T299, .(T297, T298)), T279) :- split12(T297, T298, X404, X403).
mergesort1(.(T304, .(T297, T298)), T279) :- ','(splitc12(T297, T298, T302, T303), mergesort25(T304, T303, X375)).
mergesort1(.(T304, .(T297, T298)), T279) :- ','(splitc12(T297, T298, T312, T303), ','(mergesortc25(T304, T303, T311), mergesort38(T312, X376))).
mergesort1(.(T304, .(T297, T298)), .(T398, .(T398, T388))) :- ','(splitc12(T297, T298, T312, T303), ','(mergesortc25(T304, T303, .(T398, T400)), ','(mergesortc38(T312, .(T398, .(T398, T399))), merge152(T398, T400, T399, T388)))).

Clauses:

splitc16([], [], []).
splitc16(.(T49, T51), .(T49, X88), X89) :- splitc16(T51, X89, X88).
splitc12(T42, T44, .(T42, X70), X71) :- splitc16(T44, X71, X70).
qc34(T72, T73, T74, T78, T84, T106, T105, X126) :- ','(splitc12(T72, .(T73, T74), T78, T84), ','(mergesortc38(T78, T106), ','(mergesortc38(T84, T105), mergec54(T106, T105, X126)))).
mergesortc38([], []).
mergesortc38(.(T89, []), .(T89, [])).
mergesortc38(.(T99, .(T100, T101)), X171) :- qc34(T99, T100, T101, X167, X168, X169, X170, X171).
mergec54([], T113, T113).
mergec54(T118, [], T118).
mergec54(.(T143, T144), .(T143, T142), .(T143, X213)) :- mergec54(.(T143, T144), T142, X213).
mergesortc25(T62, [], .(T62, [])).
mergesortc25(T72, .(T73, T74), X126) :- qc34(T72, T73, T74, X122, X123, X124, X125, X126).
mergec72([], []).
mergec72([], []).
mergec152(T413, T414, [], .(T413, T414)).
mergec152(T439, T441, .(T439, T440), .(T439, T429)) :- mergec152(T439, T441, T440, T429).

Afs:

mergesort1(x1, x2)  =  mergesort1(x2)

(7) UndefinedPredicateInTriplesTransformerProof (SOUND transformation)

Deleted triples and predicates having undefined goals [UNKNOWN].

(8) Obligation:

Triples:

split16(.(T49, T51), .(T49, X88), X89) :- split16(T51, X89, X88).
split12(T42, T44, .(T42, X70), X71) :- split16(T44, X71, X70).
p34(T72, T73, T74, X122, X123, X124, X125, X126) :- split12(T72, .(T73, T74), X122, X123).
p34(T72, T73, T74, T78, T79, X124, X125, X126) :- ','(splitc12(T72, .(T73, T74), T78, T79), mergesort38(T78, X124)).
p34(T72, T73, T74, T78, T84, T83, X125, X126) :- ','(splitc12(T72, .(T73, T74), T78, T84), ','(mergesortc38(T78, T83), mergesort38(T84, X125))).
p34(T72, T73, T74, T78, T84, T106, T105, X126) :- ','(splitc12(T72, .(T73, T74), T78, T84), ','(mergesortc38(T78, T106), ','(mergesortc38(T84, T105), merge54(T106, T105, X126)))).
mergesort38(.(T99, .(T100, T101)), X171) :- p34(T99, T100, T101, X167, X168, X169, X170, X171).
merge54(.(T143, T144), .(T143, T142), .(T143, X213)) :- merge54(.(T143, T144), T142, X213).
mergesort25(T72, .(T73, T74), X126) :- p34(T72, T73, T74, X122, X123, X124, X125, X126).
merge152(T439, T441, .(T439, T440), .(T439, T429)) :- merge152(T439, T441, T440, T429).
mergesort1(.(T29, .(T27, T28)), []) :- split12(T27, T28, X41, X40).
mergesort1(.(T34, .(T27, T28)), []) :- ','(splitc12(T27, T28, T32, T33), mergesort25(T34, T33, X12)).
mergesort1(.(T34, .(T27, T28)), []) :- ','(splitc12(T27, T28, T55, T33), ','(mergesortc25(T34, T33, T54), mergesort38(T55, X13))).
mergesort1(.(T196, .(T194, T195)), .(T176, [])) :- split12(T194, T195, X292, X291).
mergesort1(.(T201, .(T194, T195)), .(T176, [])) :- ','(splitc12(T194, T195, T199, T200), mergesort25(T201, T200, X263)).
mergesort1(.(T201, .(T194, T195)), .(T176, [])) :- ','(splitc12(T194, T195, T207, T200), ','(mergesortc25(T201, T200, T206), mergesort38(T207, X264))).
mergesort1(.(T299, .(T297, T298)), T279) :- split12(T297, T298, X404, X403).
mergesort1(.(T304, .(T297, T298)), T279) :- ','(splitc12(T297, T298, T302, T303), mergesort25(T304, T303, X375)).
mergesort1(.(T304, .(T297, T298)), T279) :- ','(splitc12(T297, T298, T312, T303), ','(mergesortc25(T304, T303, T311), mergesort38(T312, X376))).
mergesort1(.(T304, .(T297, T298)), .(T398, .(T398, T388))) :- ','(splitc12(T297, T298, T312, T303), ','(mergesortc25(T304, T303, .(T398, T400)), ','(mergesortc38(T312, .(T398, .(T398, T399))), merge152(T398, T400, T399, T388)))).

Clauses:

splitc16([], [], []).
splitc16(.(T49, T51), .(T49, X88), X89) :- splitc16(T51, X89, X88).
splitc12(T42, T44, .(T42, X70), X71) :- splitc16(T44, X71, X70).
qc34(T72, T73, T74, T78, T84, T106, T105, X126) :- ','(splitc12(T72, .(T73, T74), T78, T84), ','(mergesortc38(T78, T106), ','(mergesortc38(T84, T105), mergec54(T106, T105, X126)))).
mergesortc38([], []).
mergesortc38(.(T89, []), .(T89, [])).
mergesortc38(.(T99, .(T100, T101)), X171) :- qc34(T99, T100, T101, X167, X168, X169, X170, X171).
mergec54([], T113, T113).
mergec54(T118, [], T118).
mergec54(.(T143, T144), .(T143, T142), .(T143, X213)) :- mergec54(.(T143, T144), T142, X213).
mergesortc25(T62, [], .(T62, [])).
mergesortc25(T72, .(T73, T74), X126) :- qc34(T72, T73, T74, X122, X123, X124, X125, X126).
mergec72([], []).
mergec72([], []).
mergec152(T413, T414, [], .(T413, T414)).
mergec152(T439, T441, .(T439, T440), .(T439, T429)) :- mergec152(T439, T441, T440, T429).

Afs:

mergesort1(x1, x2)  =  mergesort1(x2)

(9) TriplesToPiDPProof (SOUND transformation)

We use the technique of [LOPSTR]. With regard to the inferred argument filtering the predicates were used in the following modes:
mergesort1_in: (f,b)
split12_in: (f,f,f,f) (f,b,f,f)
split16_in: (f,f,f) (b,f,f)
splitc12_in: (f,f,f,f) (f,b,f,f)
splitc16_in: (f,f,f) (b,f,f)
mergesort25_in: (f,b,f)
p34_in: (f,f,b,f,f,f,f,f)
mergesort38_in: (b,f)
mergesortc38_in: (b,f)
qc34_in: (f,f,b,f,f,f,f,f)
mergec54_in: (b,b,f)
merge54_in: (b,b,f)
mergesortc25_in: (f,b,f)
merge152_in: (f,b,b,b)
Transforming TRIPLES into the following Term Rewriting System:
Pi DP problem:
The TRS P consists of the following rules:

MERGESORT1_IN_AG(.(T29, .(T27, T28)), []) → U17_AG(T29, T27, T28, split12_in_aaaa(T27, T28, X41, X40))
MERGESORT1_IN_AG(.(T29, .(T27, T28)), []) → SPLIT12_IN_AAAA(T27, T28, X41, X40)
SPLIT12_IN_AAAA(T42, T44, .(T42, X70), X71) → U2_AAAA(T42, T44, X70, X71, split16_in_aaa(T44, X71, X70))
SPLIT12_IN_AAAA(T42, T44, .(T42, X70), X71) → SPLIT16_IN_AAA(T44, X71, X70)
SPLIT16_IN_AAA(.(T49, T51), .(T49, X88), X89) → U1_AAA(T49, T51, X88, X89, split16_in_aaa(T51, X89, X88))
SPLIT16_IN_AAA(.(T49, T51), .(T49, X88), X89) → SPLIT16_IN_AAA(T51, X89, X88)
MERGESORT1_IN_AG(.(T34, .(T27, T28)), []) → U18_AG(T34, T27, T28, splitc12_in_aaaa(T27, T28, T32, T33))
U18_AG(T34, T27, T28, splitc12_out_aaaa(T27, T28, T32, T33)) → U19_AG(T34, T27, T28, mergesort25_in_aga(T34, T33, X12))
U18_AG(T34, T27, T28, splitc12_out_aaaa(T27, T28, T32, T33)) → MERGESORT25_IN_AGA(T34, T33, X12)
MERGESORT25_IN_AGA(T72, .(T73, T74), X126) → U15_AGA(T72, T73, T74, X126, p34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
MERGESORT25_IN_AGA(T72, .(T73, T74), X126) → P34_IN_AAGAAAAA(T72, T73, T74, X122, X123, X124, X125, X126)
P34_IN_AAGAAAAA(T72, T73, T74, X122, X123, X124, X125, X126) → U3_AAGAAAAA(T72, T73, T74, X122, X123, X124, X125, X126, split12_in_agaa(T72, .(T73, T74), X122, X123))
P34_IN_AAGAAAAA(T72, T73, T74, X122, X123, X124, X125, X126) → SPLIT12_IN_AGAA(T72, .(T73, T74), X122, X123)
SPLIT12_IN_AGAA(T42, T44, .(T42, X70), X71) → U2_AGAA(T42, T44, X70, X71, split16_in_gaa(T44, X71, X70))
SPLIT12_IN_AGAA(T42, T44, .(T42, X70), X71) → SPLIT16_IN_GAA(T44, X71, X70)
SPLIT16_IN_GAA(.(T49, T51), .(T49, X88), X89) → U1_GAA(T49, T51, X88, X89, split16_in_gaa(T51, X89, X88))
SPLIT16_IN_GAA(.(T49, T51), .(T49, X88), X89) → SPLIT16_IN_GAA(T51, X89, X88)
P34_IN_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126) → U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T79))
U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T79)) → U5_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, mergesort38_in_ga(T78, X124))
U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T79)) → MERGESORT38_IN_GA(T78, X124)
MERGESORT38_IN_GA(.(T99, .(T100, T101)), X171) → U13_GA(T99, T100, T101, X171, p34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
MERGESORT38_IN_GA(.(T99, .(T100, T101)), X171) → P34_IN_AAGAAAAA(T99, T100, T101, X167, X168, X169, X170, X171)
P34_IN_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126) → U6_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U6_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_in_ga(T78, T83))
U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_out_ga(T78, T83)) → U8_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesort38_in_ga(T84, X125))
U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84, X125)
P34_IN_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126) → U9_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U9_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U10_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U10_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U11_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U11_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U12_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, merge54_in_gga(T106, T105, X126))
U11_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → MERGE54_IN_GGA(T106, T105, X126)
MERGE54_IN_GGA(.(T143, T144), .(T143, T142), .(T143, X213)) → U14_GGA(T143, T144, T142, X213, merge54_in_gga(.(T143, T144), T142, X213))
MERGE54_IN_GGA(.(T143, T144), .(T143, T142), .(T143, X213)) → MERGE54_IN_GGA(.(T143, T144), T142, X213)
MERGESORT1_IN_AG(.(T34, .(T27, T28)), []) → U20_AG(T34, T27, T28, splitc12_in_aaaa(T27, T28, T55, T33))
U20_AG(T34, T27, T28, splitc12_out_aaaa(T27, T28, T55, T33)) → U21_AG(T34, T27, T28, T55, mergesortc25_in_aga(T34, T33, T54))
U21_AG(T34, T27, T28, T55, mergesortc25_out_aga(T34, T33, T54)) → U22_AG(T34, T27, T28, mergesort38_in_ga(T55, X13))
U21_AG(T34, T27, T28, T55, mergesortc25_out_aga(T34, T33, T54)) → MERGESORT38_IN_GA(T55, X13)
MERGESORT1_IN_AG(.(T196, .(T194, T195)), .(T176, [])) → U23_AG(T196, T194, T195, T176, split12_in_aaaa(T194, T195, X292, X291))
MERGESORT1_IN_AG(.(T196, .(T194, T195)), .(T176, [])) → SPLIT12_IN_AAAA(T194, T195, X292, X291)
MERGESORT1_IN_AG(.(T201, .(T194, T195)), .(T176, [])) → U24_AG(T201, T194, T195, T176, splitc12_in_aaaa(T194, T195, T199, T200))
U24_AG(T201, T194, T195, T176, splitc12_out_aaaa(T194, T195, T199, T200)) → U25_AG(T201, T194, T195, T176, mergesort25_in_aga(T201, T200, X263))
U24_AG(T201, T194, T195, T176, splitc12_out_aaaa(T194, T195, T199, T200)) → MERGESORT25_IN_AGA(T201, T200, X263)
MERGESORT1_IN_AG(.(T201, .(T194, T195)), .(T176, [])) → U26_AG(T201, T194, T195, T176, splitc12_in_aaaa(T194, T195, T207, T200))
U26_AG(T201, T194, T195, T176, splitc12_out_aaaa(T194, T195, T207, T200)) → U27_AG(T201, T194, T195, T176, T207, mergesortc25_in_aga(T201, T200, T206))
U27_AG(T201, T194, T195, T176, T207, mergesortc25_out_aga(T201, T200, T206)) → U28_AG(T201, T194, T195, T176, mergesort38_in_ga(T207, X264))
U27_AG(T201, T194, T195, T176, T207, mergesortc25_out_aga(T201, T200, T206)) → MERGESORT38_IN_GA(T207, X264)
MERGESORT1_IN_AG(.(T299, .(T297, T298)), T279) → U29_AG(T299, T297, T298, T279, split12_in_aaaa(T297, T298, X404, X403))
MERGESORT1_IN_AG(.(T299, .(T297, T298)), T279) → SPLIT12_IN_AAAA(T297, T298, X404, X403)
MERGESORT1_IN_AG(.(T304, .(T297, T298)), T279) → U30_AG(T304, T297, T298, T279, splitc12_in_aaaa(T297, T298, T302, T303))
U30_AG(T304, T297, T298, T279, splitc12_out_aaaa(T297, T298, T302, T303)) → U31_AG(T304, T297, T298, T279, mergesort25_in_aga(T304, T303, X375))
U30_AG(T304, T297, T298, T279, splitc12_out_aaaa(T297, T298, T302, T303)) → MERGESORT25_IN_AGA(T304, T303, X375)
MERGESORT1_IN_AG(.(T304, .(T297, T298)), T279) → U32_AG(T304, T297, T298, T279, splitc12_in_aaaa(T297, T298, T312, T303))
U32_AG(T304, T297, T298, T279, splitc12_out_aaaa(T297, T298, T312, T303)) → U33_AG(T304, T297, T298, T279, T312, mergesortc25_in_aga(T304, T303, T311))
U33_AG(T304, T297, T298, T279, T312, mergesortc25_out_aga(T304, T303, T311)) → U34_AG(T304, T297, T298, T279, mergesort38_in_ga(T312, X376))
U33_AG(T304, T297, T298, T279, T312, mergesortc25_out_aga(T304, T303, T311)) → MERGESORT38_IN_GA(T312, X376)
MERGESORT1_IN_AG(.(T304, .(T297, T298)), .(T398, .(T398, T388))) → U35_AG(T304, T297, T298, T398, T388, splitc12_in_aaaa(T297, T298, T312, T303))
U35_AG(T304, T297, T298, T398, T388, splitc12_out_aaaa(T297, T298, T312, T303)) → U36_AG(T304, T297, T298, T398, T388, T312, mergesortc25_in_aga(T304, T303, .(T398, T400)))
U36_AG(T304, T297, T298, T398, T388, T312, mergesortc25_out_aga(T304, T303, .(T398, T400))) → U37_AG(T304, T297, T298, T398, T388, T400, mergesortc38_in_ga(T312, .(T398, .(T398, T399))))
U37_AG(T304, T297, T298, T398, T388, T400, mergesortc38_out_ga(T312, .(T398, .(T398, T399)))) → U38_AG(T304, T297, T298, T398, T388, merge152_in_aggg(T398, T400, T399, T388))
U37_AG(T304, T297, T298, T398, T388, T400, mergesortc38_out_ga(T312, .(T398, .(T398, T399)))) → MERGE152_IN_AGGG(T398, T400, T399, T388)
MERGE152_IN_AGGG(T439, T441, .(T439, T440), .(T439, T429)) → U16_AGGG(T439, T441, T440, T429, merge152_in_aggg(T439, T441, T440, T429))
MERGE152_IN_AGGG(T439, T441, .(T439, T440), .(T439, T429)) → MERGE152_IN_AGGG(T439, T441, T440, T429)

The TRS R consists of the following rules:

splitc12_in_aaaa(T42, T44, .(T42, X70), X71) → U41_aaaa(T42, T44, X70, X71, splitc16_in_aaa(T44, X71, X70))
splitc16_in_aaa([], [], []) → splitc16_out_aaa([], [], [])
splitc16_in_aaa(.(T49, T51), .(T49, X88), X89) → U40_aaa(T49, T51, X88, X89, splitc16_in_aaa(T51, X89, X88))
U40_aaa(T49, T51, X88, X89, splitc16_out_aaa(T51, X89, X88)) → splitc16_out_aaa(.(T49, T51), .(T49, X88), X89)
U41_aaaa(T42, T44, X70, X71, splitc16_out_aaa(T44, X71, X70)) → splitc12_out_aaaa(T42, T44, .(T42, X70), X71)
splitc12_in_agaa(T42, T44, .(T42, X70), X71) → U41_agaa(T42, T44, X70, X71, splitc16_in_gaa(T44, X71, X70))
splitc16_in_gaa([], [], []) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T49, T51), .(T49, X88), X89) → U40_gaa(T49, T51, X88, X89, splitc16_in_gaa(T51, X89, X88))
U40_gaa(T49, T51, X88, X89, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T49, T51), .(T49, X88), X89)
U41_agaa(T42, T44, X70, X71, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T42, T44, .(T42, X70), X71)
mergesortc38_in_ga([], []) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.(T89, []), .(T89, [])) → mergesortc38_out_ga(.(T89, []), .(T89, []))
mergesortc38_in_ga(.(T99, .(T100, T101)), X171) → U46_ga(T99, T100, T101, X171, qc34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
qc34_in_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126) → U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_in_gga(T106, T105, X126))
mergec54_in_gga([], T113, T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, [], T118) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T143, T144), .(T143, T142), .(T143, X213)) → U47_gga(T143, T144, T142, X213, mergec54_in_gga(.(T143, T144), T142, X213))
U47_gga(T143, T144, T142, X213, mergec54_out_gga(.(T143, T144), T142, X213)) → mergec54_out_gga(.(T143, T144), .(T143, T142), .(T143, X213))
U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126)
U46_ga(T99, T100, T101, X171, qc34_out_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(T99, .(T100, T101)), X171)
mergesortc25_in_aga(T62, [], .(T62, [])) → mergesortc25_out_aga(T62, [], .(T62, []))
mergesortc25_in_aga(T72, .(T73, T74), X126) → U48_aga(T72, T73, T74, X126, qc34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
U48_aga(T72, T73, T74, X126, qc34_out_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126)) → mergesortc25_out_aga(T72, .(T73, T74), X126)

The argument filtering Pi contains the following mapping:
[]  =  []
split12_in_aaaa(x1, x2, x3, x4)  =  split12_in_aaaa
split16_in_aaa(x1, x2, x3)  =  split16_in_aaa
.(x1, x2)  =  .(x2)
splitc12_in_aaaa(x1, x2, x3, x4)  =  splitc12_in_aaaa
U41_aaaa(x1, x2, x3, x4, x5)  =  U41_aaaa(x5)
splitc16_in_aaa(x1, x2, x3)  =  splitc16_in_aaa
splitc16_out_aaa(x1, x2, x3)  =  splitc16_out_aaa(x1, x2, x3)
U40_aaa(x1, x2, x3, x4, x5)  =  U40_aaa(x5)
splitc12_out_aaaa(x1, x2, x3, x4)  =  splitc12_out_aaaa(x2, x3, x4)
mergesort25_in_aga(x1, x2, x3)  =  mergesort25_in_aga(x2)
p34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  p34_in_aagaaaaa(x3)
split12_in_agaa(x1, x2, x3, x4)  =  split12_in_agaa(x2)
split16_in_gaa(x1, x2, x3)  =  split16_in_gaa(x1)
splitc12_in_agaa(x1, x2, x3, x4)  =  splitc12_in_agaa(x2)
U41_agaa(x1, x2, x3, x4, x5)  =  U41_agaa(x2, x5)
splitc16_in_gaa(x1, x2, x3)  =  splitc16_in_gaa(x1)
splitc16_out_gaa(x1, x2, x3)  =  splitc16_out_gaa(x1, x2, x3)
U40_gaa(x1, x2, x3, x4, x5)  =  U40_gaa(x2, x5)
splitc12_out_agaa(x1, x2, x3, x4)  =  splitc12_out_agaa(x2, x3, x4)
mergesort38_in_ga(x1, x2)  =  mergesort38_in_ga(x1)
mergesortc38_in_ga(x1, x2)  =  mergesortc38_in_ga(x1)
mergesortc38_out_ga(x1, x2)  =  mergesortc38_out_ga(x1, x2)
U46_ga(x1, x2, x3, x4, x5)  =  U46_ga(x3, x5)
qc34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_in_aagaaaaa(x3)
U42_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U42_aagaaaaa(x3, x9)
U43_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U43_aagaaaaa(x3, x4, x5, x9)
U44_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U44_aagaaaaa(x3, x4, x5, x6, x9)
U45_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U45_aagaaaaa(x3, x4, x5, x6, x7, x9)
mergec54_in_gga(x1, x2, x3)  =  mergec54_in_gga(x1, x2)
mergec54_out_gga(x1, x2, x3)  =  mergec54_out_gga(x1, x2, x3)
U47_gga(x1, x2, x3, x4, x5)  =  U47_gga(x2, x3, x5)
qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_out_aagaaaaa(x3, x4, x5, x6, x7, x8)
merge54_in_gga(x1, x2, x3)  =  merge54_in_gga(x1, x2)
mergesortc25_in_aga(x1, x2, x3)  =  mergesortc25_in_aga(x2)
mergesortc25_out_aga(x1, x2, x3)  =  mergesortc25_out_aga(x2, x3)
U48_aga(x1, x2, x3, x4, x5)  =  U48_aga(x3, x5)
merge152_in_aggg(x1, x2, x3, x4)  =  merge152_in_aggg(x2, x3, x4)
MERGESORT1_IN_AG(x1, x2)  =  MERGESORT1_IN_AG(x2)
U17_AG(x1, x2, x3, x4)  =  U17_AG(x4)
SPLIT12_IN_AAAA(x1, x2, x3, x4)  =  SPLIT12_IN_AAAA
U2_AAAA(x1, x2, x3, x4, x5)  =  U2_AAAA(x5)
SPLIT16_IN_AAA(x1, x2, x3)  =  SPLIT16_IN_AAA
U1_AAA(x1, x2, x3, x4, x5)  =  U1_AAA(x5)
U18_AG(x1, x2, x3, x4)  =  U18_AG(x4)
U19_AG(x1, x2, x3, x4)  =  U19_AG(x3, x4)
MERGESORT25_IN_AGA(x1, x2, x3)  =  MERGESORT25_IN_AGA(x2)
U15_AGA(x1, x2, x3, x4, x5)  =  U15_AGA(x3, x5)
P34_IN_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8)  =  P34_IN_AAGAAAAA(x3)
U3_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U3_AAGAAAAA(x3, x9)
SPLIT12_IN_AGAA(x1, x2, x3, x4)  =  SPLIT12_IN_AGAA(x2)
U2_AGAA(x1, x2, x3, x4, x5)  =  U2_AGAA(x2, x5)
SPLIT16_IN_GAA(x1, x2, x3)  =  SPLIT16_IN_GAA(x1)
U1_GAA(x1, x2, x3, x4, x5)  =  U1_GAA(x2, x5)
U4_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U4_AAGAAAAA(x3, x9)
U5_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U5_AAGAAAAA(x3, x4, x5, x9)
MERGESORT38_IN_GA(x1, x2)  =  MERGESORT38_IN_GA(x1)
U13_GA(x1, x2, x3, x4, x5)  =  U13_GA(x3, x5)
U6_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U6_AAGAAAAA(x3, x9)
U7_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U7_AAGAAAAA(x3, x4, x5, x9)
U8_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U8_AAGAAAAA(x3, x4, x5, x9)
U9_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U9_AAGAAAAA(x3, x9)
U10_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U10_AAGAAAAA(x3, x4, x5, x9)
U11_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U11_AAGAAAAA(x3, x4, x5, x6, x9)
U12_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U12_AAGAAAAA(x3, x4, x5, x9)
MERGE54_IN_GGA(x1, x2, x3)  =  MERGE54_IN_GGA(x1, x2)
U14_GGA(x1, x2, x3, x4, x5)  =  U14_GGA(x2, x3, x5)
U20_AG(x1, x2, x3, x4)  =  U20_AG(x4)
U21_AG(x1, x2, x3, x4, x5)  =  U21_AG(x3, x4, x5)
U22_AG(x1, x2, x3, x4)  =  U22_AG(x3, x4)
U23_AG(x1, x2, x3, x4, x5)  =  U23_AG(x5)
U24_AG(x1, x2, x3, x4, x5)  =  U24_AG(x5)
U25_AG(x1, x2, x3, x4, x5)  =  U25_AG(x3, x5)
U26_AG(x1, x2, x3, x4, x5)  =  U26_AG(x5)
U27_AG(x1, x2, x3, x4, x5, x6)  =  U27_AG(x3, x5, x6)
U28_AG(x1, x2, x3, x4, x5)  =  U28_AG(x3, x5)
U29_AG(x1, x2, x3, x4, x5)  =  U29_AG(x4, x5)
U30_AG(x1, x2, x3, x4, x5)  =  U30_AG(x4, x5)
U31_AG(x1, x2, x3, x4, x5)  =  U31_AG(x3, x4, x5)
U32_AG(x1, x2, x3, x4, x5)  =  U32_AG(x4, x5)
U33_AG(x1, x2, x3, x4, x5, x6)  =  U33_AG(x3, x4, x5, x6)
U34_AG(x1, x2, x3, x4, x5)  =  U34_AG(x3, x4, x5)
U35_AG(x1, x2, x3, x4, x5, x6)  =  U35_AG(x5, x6)
U36_AG(x1, x2, x3, x4, x5, x6, x7)  =  U36_AG(x3, x5, x6, x7)
U37_AG(x1, x2, x3, x4, x5, x6, x7)  =  U37_AG(x3, x5, x6, x7)
U38_AG(x1, x2, x3, x4, x5, x6)  =  U38_AG(x3, x5, x6)
MERGE152_IN_AGGG(x1, x2, x3, x4)  =  MERGE152_IN_AGGG(x2, x3, x4)
U16_AGGG(x1, x2, x3, x4, x5)  =  U16_AGGG(x2, x3, x4, x5)

We have to consider all (P,R,Pi)-chains

Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES

(10) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

MERGESORT1_IN_AG(.(T29, .(T27, T28)), []) → U17_AG(T29, T27, T28, split12_in_aaaa(T27, T28, X41, X40))
MERGESORT1_IN_AG(.(T29, .(T27, T28)), []) → SPLIT12_IN_AAAA(T27, T28, X41, X40)
SPLIT12_IN_AAAA(T42, T44, .(T42, X70), X71) → U2_AAAA(T42, T44, X70, X71, split16_in_aaa(T44, X71, X70))
SPLIT12_IN_AAAA(T42, T44, .(T42, X70), X71) → SPLIT16_IN_AAA(T44, X71, X70)
SPLIT16_IN_AAA(.(T49, T51), .(T49, X88), X89) → U1_AAA(T49, T51, X88, X89, split16_in_aaa(T51, X89, X88))
SPLIT16_IN_AAA(.(T49, T51), .(T49, X88), X89) → SPLIT16_IN_AAA(T51, X89, X88)
MERGESORT1_IN_AG(.(T34, .(T27, T28)), []) → U18_AG(T34, T27, T28, splitc12_in_aaaa(T27, T28, T32, T33))
U18_AG(T34, T27, T28, splitc12_out_aaaa(T27, T28, T32, T33)) → U19_AG(T34, T27, T28, mergesort25_in_aga(T34, T33, X12))
U18_AG(T34, T27, T28, splitc12_out_aaaa(T27, T28, T32, T33)) → MERGESORT25_IN_AGA(T34, T33, X12)
MERGESORT25_IN_AGA(T72, .(T73, T74), X126) → U15_AGA(T72, T73, T74, X126, p34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
MERGESORT25_IN_AGA(T72, .(T73, T74), X126) → P34_IN_AAGAAAAA(T72, T73, T74, X122, X123, X124, X125, X126)
P34_IN_AAGAAAAA(T72, T73, T74, X122, X123, X124, X125, X126) → U3_AAGAAAAA(T72, T73, T74, X122, X123, X124, X125, X126, split12_in_agaa(T72, .(T73, T74), X122, X123))
P34_IN_AAGAAAAA(T72, T73, T74, X122, X123, X124, X125, X126) → SPLIT12_IN_AGAA(T72, .(T73, T74), X122, X123)
SPLIT12_IN_AGAA(T42, T44, .(T42, X70), X71) → U2_AGAA(T42, T44, X70, X71, split16_in_gaa(T44, X71, X70))
SPLIT12_IN_AGAA(T42, T44, .(T42, X70), X71) → SPLIT16_IN_GAA(T44, X71, X70)
SPLIT16_IN_GAA(.(T49, T51), .(T49, X88), X89) → U1_GAA(T49, T51, X88, X89, split16_in_gaa(T51, X89, X88))
SPLIT16_IN_GAA(.(T49, T51), .(T49, X88), X89) → SPLIT16_IN_GAA(T51, X89, X88)
P34_IN_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126) → U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T79))
U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T79)) → U5_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, mergesort38_in_ga(T78, X124))
U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T79)) → MERGESORT38_IN_GA(T78, X124)
MERGESORT38_IN_GA(.(T99, .(T100, T101)), X171) → U13_GA(T99, T100, T101, X171, p34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
MERGESORT38_IN_GA(.(T99, .(T100, T101)), X171) → P34_IN_AAGAAAAA(T99, T100, T101, X167, X168, X169, X170, X171)
P34_IN_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126) → U6_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U6_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_in_ga(T78, T83))
U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_out_ga(T78, T83)) → U8_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesort38_in_ga(T84, X125))
U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84, X125)
P34_IN_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126) → U9_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U9_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U10_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U10_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U11_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U11_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U12_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, merge54_in_gga(T106, T105, X126))
U11_AAGAAAAA(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → MERGE54_IN_GGA(T106, T105, X126)
MERGE54_IN_GGA(.(T143, T144), .(T143, T142), .(T143, X213)) → U14_GGA(T143, T144, T142, X213, merge54_in_gga(.(T143, T144), T142, X213))
MERGE54_IN_GGA(.(T143, T144), .(T143, T142), .(T143, X213)) → MERGE54_IN_GGA(.(T143, T144), T142, X213)
MERGESORT1_IN_AG(.(T34, .(T27, T28)), []) → U20_AG(T34, T27, T28, splitc12_in_aaaa(T27, T28, T55, T33))
U20_AG(T34, T27, T28, splitc12_out_aaaa(T27, T28, T55, T33)) → U21_AG(T34, T27, T28, T55, mergesortc25_in_aga(T34, T33, T54))
U21_AG(T34, T27, T28, T55, mergesortc25_out_aga(T34, T33, T54)) → U22_AG(T34, T27, T28, mergesort38_in_ga(T55, X13))
U21_AG(T34, T27, T28, T55, mergesortc25_out_aga(T34, T33, T54)) → MERGESORT38_IN_GA(T55, X13)
MERGESORT1_IN_AG(.(T196, .(T194, T195)), .(T176, [])) → U23_AG(T196, T194, T195, T176, split12_in_aaaa(T194, T195, X292, X291))
MERGESORT1_IN_AG(.(T196, .(T194, T195)), .(T176, [])) → SPLIT12_IN_AAAA(T194, T195, X292, X291)
MERGESORT1_IN_AG(.(T201, .(T194, T195)), .(T176, [])) → U24_AG(T201, T194, T195, T176, splitc12_in_aaaa(T194, T195, T199, T200))
U24_AG(T201, T194, T195, T176, splitc12_out_aaaa(T194, T195, T199, T200)) → U25_AG(T201, T194, T195, T176, mergesort25_in_aga(T201, T200, X263))
U24_AG(T201, T194, T195, T176, splitc12_out_aaaa(T194, T195, T199, T200)) → MERGESORT25_IN_AGA(T201, T200, X263)
MERGESORT1_IN_AG(.(T201, .(T194, T195)), .(T176, [])) → U26_AG(T201, T194, T195, T176, splitc12_in_aaaa(T194, T195, T207, T200))
U26_AG(T201, T194, T195, T176, splitc12_out_aaaa(T194, T195, T207, T200)) → U27_AG(T201, T194, T195, T176, T207, mergesortc25_in_aga(T201, T200, T206))
U27_AG(T201, T194, T195, T176, T207, mergesortc25_out_aga(T201, T200, T206)) → U28_AG(T201, T194, T195, T176, mergesort38_in_ga(T207, X264))
U27_AG(T201, T194, T195, T176, T207, mergesortc25_out_aga(T201, T200, T206)) → MERGESORT38_IN_GA(T207, X264)
MERGESORT1_IN_AG(.(T299, .(T297, T298)), T279) → U29_AG(T299, T297, T298, T279, split12_in_aaaa(T297, T298, X404, X403))
MERGESORT1_IN_AG(.(T299, .(T297, T298)), T279) → SPLIT12_IN_AAAA(T297, T298, X404, X403)
MERGESORT1_IN_AG(.(T304, .(T297, T298)), T279) → U30_AG(T304, T297, T298, T279, splitc12_in_aaaa(T297, T298, T302, T303))
U30_AG(T304, T297, T298, T279, splitc12_out_aaaa(T297, T298, T302, T303)) → U31_AG(T304, T297, T298, T279, mergesort25_in_aga(T304, T303, X375))
U30_AG(T304, T297, T298, T279, splitc12_out_aaaa(T297, T298, T302, T303)) → MERGESORT25_IN_AGA(T304, T303, X375)
MERGESORT1_IN_AG(.(T304, .(T297, T298)), T279) → U32_AG(T304, T297, T298, T279, splitc12_in_aaaa(T297, T298, T312, T303))
U32_AG(T304, T297, T298, T279, splitc12_out_aaaa(T297, T298, T312, T303)) → U33_AG(T304, T297, T298, T279, T312, mergesortc25_in_aga(T304, T303, T311))
U33_AG(T304, T297, T298, T279, T312, mergesortc25_out_aga(T304, T303, T311)) → U34_AG(T304, T297, T298, T279, mergesort38_in_ga(T312, X376))
U33_AG(T304, T297, T298, T279, T312, mergesortc25_out_aga(T304, T303, T311)) → MERGESORT38_IN_GA(T312, X376)
MERGESORT1_IN_AG(.(T304, .(T297, T298)), .(T398, .(T398, T388))) → U35_AG(T304, T297, T298, T398, T388, splitc12_in_aaaa(T297, T298, T312, T303))
U35_AG(T304, T297, T298, T398, T388, splitc12_out_aaaa(T297, T298, T312, T303)) → U36_AG(T304, T297, T298, T398, T388, T312, mergesortc25_in_aga(T304, T303, .(T398, T400)))
U36_AG(T304, T297, T298, T398, T388, T312, mergesortc25_out_aga(T304, T303, .(T398, T400))) → U37_AG(T304, T297, T298, T398, T388, T400, mergesortc38_in_ga(T312, .(T398, .(T398, T399))))
U37_AG(T304, T297, T298, T398, T388, T400, mergesortc38_out_ga(T312, .(T398, .(T398, T399)))) → U38_AG(T304, T297, T298, T398, T388, merge152_in_aggg(T398, T400, T399, T388))
U37_AG(T304, T297, T298, T398, T388, T400, mergesortc38_out_ga(T312, .(T398, .(T398, T399)))) → MERGE152_IN_AGGG(T398, T400, T399, T388)
MERGE152_IN_AGGG(T439, T441, .(T439, T440), .(T439, T429)) → U16_AGGG(T439, T441, T440, T429, merge152_in_aggg(T439, T441, T440, T429))
MERGE152_IN_AGGG(T439, T441, .(T439, T440), .(T439, T429)) → MERGE152_IN_AGGG(T439, T441, T440, T429)

The TRS R consists of the following rules:

splitc12_in_aaaa(T42, T44, .(T42, X70), X71) → U41_aaaa(T42, T44, X70, X71, splitc16_in_aaa(T44, X71, X70))
splitc16_in_aaa([], [], []) → splitc16_out_aaa([], [], [])
splitc16_in_aaa(.(T49, T51), .(T49, X88), X89) → U40_aaa(T49, T51, X88, X89, splitc16_in_aaa(T51, X89, X88))
U40_aaa(T49, T51, X88, X89, splitc16_out_aaa(T51, X89, X88)) → splitc16_out_aaa(.(T49, T51), .(T49, X88), X89)
U41_aaaa(T42, T44, X70, X71, splitc16_out_aaa(T44, X71, X70)) → splitc12_out_aaaa(T42, T44, .(T42, X70), X71)
splitc12_in_agaa(T42, T44, .(T42, X70), X71) → U41_agaa(T42, T44, X70, X71, splitc16_in_gaa(T44, X71, X70))
splitc16_in_gaa([], [], []) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T49, T51), .(T49, X88), X89) → U40_gaa(T49, T51, X88, X89, splitc16_in_gaa(T51, X89, X88))
U40_gaa(T49, T51, X88, X89, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T49, T51), .(T49, X88), X89)
U41_agaa(T42, T44, X70, X71, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T42, T44, .(T42, X70), X71)
mergesortc38_in_ga([], []) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.(T89, []), .(T89, [])) → mergesortc38_out_ga(.(T89, []), .(T89, []))
mergesortc38_in_ga(.(T99, .(T100, T101)), X171) → U46_ga(T99, T100, T101, X171, qc34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
qc34_in_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126) → U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_in_gga(T106, T105, X126))
mergec54_in_gga([], T113, T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, [], T118) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T143, T144), .(T143, T142), .(T143, X213)) → U47_gga(T143, T144, T142, X213, mergec54_in_gga(.(T143, T144), T142, X213))
U47_gga(T143, T144, T142, X213, mergec54_out_gga(.(T143, T144), T142, X213)) → mergec54_out_gga(.(T143, T144), .(T143, T142), .(T143, X213))
U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126)
U46_ga(T99, T100, T101, X171, qc34_out_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(T99, .(T100, T101)), X171)
mergesortc25_in_aga(T62, [], .(T62, [])) → mergesortc25_out_aga(T62, [], .(T62, []))
mergesortc25_in_aga(T72, .(T73, T74), X126) → U48_aga(T72, T73, T74, X126, qc34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
U48_aga(T72, T73, T74, X126, qc34_out_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126)) → mergesortc25_out_aga(T72, .(T73, T74), X126)

The argument filtering Pi contains the following mapping:
[]  =  []
split12_in_aaaa(x1, x2, x3, x4)  =  split12_in_aaaa
split16_in_aaa(x1, x2, x3)  =  split16_in_aaa
.(x1, x2)  =  .(x2)
splitc12_in_aaaa(x1, x2, x3, x4)  =  splitc12_in_aaaa
U41_aaaa(x1, x2, x3, x4, x5)  =  U41_aaaa(x5)
splitc16_in_aaa(x1, x2, x3)  =  splitc16_in_aaa
splitc16_out_aaa(x1, x2, x3)  =  splitc16_out_aaa(x1, x2, x3)
U40_aaa(x1, x2, x3, x4, x5)  =  U40_aaa(x5)
splitc12_out_aaaa(x1, x2, x3, x4)  =  splitc12_out_aaaa(x2, x3, x4)
mergesort25_in_aga(x1, x2, x3)  =  mergesort25_in_aga(x2)
p34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  p34_in_aagaaaaa(x3)
split12_in_agaa(x1, x2, x3, x4)  =  split12_in_agaa(x2)
split16_in_gaa(x1, x2, x3)  =  split16_in_gaa(x1)
splitc12_in_agaa(x1, x2, x3, x4)  =  splitc12_in_agaa(x2)
U41_agaa(x1, x2, x3, x4, x5)  =  U41_agaa(x2, x5)
splitc16_in_gaa(x1, x2, x3)  =  splitc16_in_gaa(x1)
splitc16_out_gaa(x1, x2, x3)  =  splitc16_out_gaa(x1, x2, x3)
U40_gaa(x1, x2, x3, x4, x5)  =  U40_gaa(x2, x5)
splitc12_out_agaa(x1, x2, x3, x4)  =  splitc12_out_agaa(x2, x3, x4)
mergesort38_in_ga(x1, x2)  =  mergesort38_in_ga(x1)
mergesortc38_in_ga(x1, x2)  =  mergesortc38_in_ga(x1)
mergesortc38_out_ga(x1, x2)  =  mergesortc38_out_ga(x1, x2)
U46_ga(x1, x2, x3, x4, x5)  =  U46_ga(x3, x5)
qc34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_in_aagaaaaa(x3)
U42_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U42_aagaaaaa(x3, x9)
U43_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U43_aagaaaaa(x3, x4, x5, x9)
U44_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U44_aagaaaaa(x3, x4, x5, x6, x9)
U45_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U45_aagaaaaa(x3, x4, x5, x6, x7, x9)
mergec54_in_gga(x1, x2, x3)  =  mergec54_in_gga(x1, x2)
mergec54_out_gga(x1, x2, x3)  =  mergec54_out_gga(x1, x2, x3)
U47_gga(x1, x2, x3, x4, x5)  =  U47_gga(x2, x3, x5)
qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_out_aagaaaaa(x3, x4, x5, x6, x7, x8)
merge54_in_gga(x1, x2, x3)  =  merge54_in_gga(x1, x2)
mergesortc25_in_aga(x1, x2, x3)  =  mergesortc25_in_aga(x2)
mergesortc25_out_aga(x1, x2, x3)  =  mergesortc25_out_aga(x2, x3)
U48_aga(x1, x2, x3, x4, x5)  =  U48_aga(x3, x5)
merge152_in_aggg(x1, x2, x3, x4)  =  merge152_in_aggg(x2, x3, x4)
MERGESORT1_IN_AG(x1, x2)  =  MERGESORT1_IN_AG(x2)
U17_AG(x1, x2, x3, x4)  =  U17_AG(x4)
SPLIT12_IN_AAAA(x1, x2, x3, x4)  =  SPLIT12_IN_AAAA
U2_AAAA(x1, x2, x3, x4, x5)  =  U2_AAAA(x5)
SPLIT16_IN_AAA(x1, x2, x3)  =  SPLIT16_IN_AAA
U1_AAA(x1, x2, x3, x4, x5)  =  U1_AAA(x5)
U18_AG(x1, x2, x3, x4)  =  U18_AG(x4)
U19_AG(x1, x2, x3, x4)  =  U19_AG(x3, x4)
MERGESORT25_IN_AGA(x1, x2, x3)  =  MERGESORT25_IN_AGA(x2)
U15_AGA(x1, x2, x3, x4, x5)  =  U15_AGA(x3, x5)
P34_IN_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8)  =  P34_IN_AAGAAAAA(x3)
U3_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U3_AAGAAAAA(x3, x9)
SPLIT12_IN_AGAA(x1, x2, x3, x4)  =  SPLIT12_IN_AGAA(x2)
U2_AGAA(x1, x2, x3, x4, x5)  =  U2_AGAA(x2, x5)
SPLIT16_IN_GAA(x1, x2, x3)  =  SPLIT16_IN_GAA(x1)
U1_GAA(x1, x2, x3, x4, x5)  =  U1_GAA(x2, x5)
U4_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U4_AAGAAAAA(x3, x9)
U5_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U5_AAGAAAAA(x3, x4, x5, x9)
MERGESORT38_IN_GA(x1, x2)  =  MERGESORT38_IN_GA(x1)
U13_GA(x1, x2, x3, x4, x5)  =  U13_GA(x3, x5)
U6_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U6_AAGAAAAA(x3, x9)
U7_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U7_AAGAAAAA(x3, x4, x5, x9)
U8_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U8_AAGAAAAA(x3, x4, x5, x9)
U9_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U9_AAGAAAAA(x3, x9)
U10_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U10_AAGAAAAA(x3, x4, x5, x9)
U11_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U11_AAGAAAAA(x3, x4, x5, x6, x9)
U12_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U12_AAGAAAAA(x3, x4, x5, x9)
MERGE54_IN_GGA(x1, x2, x3)  =  MERGE54_IN_GGA(x1, x2)
U14_GGA(x1, x2, x3, x4, x5)  =  U14_GGA(x2, x3, x5)
U20_AG(x1, x2, x3, x4)  =  U20_AG(x4)
U21_AG(x1, x2, x3, x4, x5)  =  U21_AG(x3, x4, x5)
U22_AG(x1, x2, x3, x4)  =  U22_AG(x3, x4)
U23_AG(x1, x2, x3, x4, x5)  =  U23_AG(x5)
U24_AG(x1, x2, x3, x4, x5)  =  U24_AG(x5)
U25_AG(x1, x2, x3, x4, x5)  =  U25_AG(x3, x5)
U26_AG(x1, x2, x3, x4, x5)  =  U26_AG(x5)
U27_AG(x1, x2, x3, x4, x5, x6)  =  U27_AG(x3, x5, x6)
U28_AG(x1, x2, x3, x4, x5)  =  U28_AG(x3, x5)
U29_AG(x1, x2, x3, x4, x5)  =  U29_AG(x4, x5)
U30_AG(x1, x2, x3, x4, x5)  =  U30_AG(x4, x5)
U31_AG(x1, x2, x3, x4, x5)  =  U31_AG(x3, x4, x5)
U32_AG(x1, x2, x3, x4, x5)  =  U32_AG(x4, x5)
U33_AG(x1, x2, x3, x4, x5, x6)  =  U33_AG(x3, x4, x5, x6)
U34_AG(x1, x2, x3, x4, x5)  =  U34_AG(x3, x4, x5)
U35_AG(x1, x2, x3, x4, x5, x6)  =  U35_AG(x5, x6)
U36_AG(x1, x2, x3, x4, x5, x6, x7)  =  U36_AG(x3, x5, x6, x7)
U37_AG(x1, x2, x3, x4, x5, x6, x7)  =  U37_AG(x3, x5, x6, x7)
U38_AG(x1, x2, x3, x4, x5, x6)  =  U38_AG(x3, x5, x6)
MERGE152_IN_AGGG(x1, x2, x3, x4)  =  MERGE152_IN_AGGG(x2, x3, x4)
U16_AGGG(x1, x2, x3, x4, x5)  =  U16_AGGG(x2, x3, x4, x5)

We have to consider all (P,R,Pi)-chains

(11) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 52 less nodes.

(12) Complex Obligation (AND)

(13) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

MERGE152_IN_AGGG(T439, T441, .(T439, T440), .(T439, T429)) → MERGE152_IN_AGGG(T439, T441, T440, T429)

The TRS R consists of the following rules:

splitc12_in_aaaa(T42, T44, .(T42, X70), X71) → U41_aaaa(T42, T44, X70, X71, splitc16_in_aaa(T44, X71, X70))
splitc16_in_aaa([], [], []) → splitc16_out_aaa([], [], [])
splitc16_in_aaa(.(T49, T51), .(T49, X88), X89) → U40_aaa(T49, T51, X88, X89, splitc16_in_aaa(T51, X89, X88))
U40_aaa(T49, T51, X88, X89, splitc16_out_aaa(T51, X89, X88)) → splitc16_out_aaa(.(T49, T51), .(T49, X88), X89)
U41_aaaa(T42, T44, X70, X71, splitc16_out_aaa(T44, X71, X70)) → splitc12_out_aaaa(T42, T44, .(T42, X70), X71)
splitc12_in_agaa(T42, T44, .(T42, X70), X71) → U41_agaa(T42, T44, X70, X71, splitc16_in_gaa(T44, X71, X70))
splitc16_in_gaa([], [], []) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T49, T51), .(T49, X88), X89) → U40_gaa(T49, T51, X88, X89, splitc16_in_gaa(T51, X89, X88))
U40_gaa(T49, T51, X88, X89, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T49, T51), .(T49, X88), X89)
U41_agaa(T42, T44, X70, X71, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T42, T44, .(T42, X70), X71)
mergesortc38_in_ga([], []) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.(T89, []), .(T89, [])) → mergesortc38_out_ga(.(T89, []), .(T89, []))
mergesortc38_in_ga(.(T99, .(T100, T101)), X171) → U46_ga(T99, T100, T101, X171, qc34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
qc34_in_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126) → U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_in_gga(T106, T105, X126))
mergec54_in_gga([], T113, T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, [], T118) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T143, T144), .(T143, T142), .(T143, X213)) → U47_gga(T143, T144, T142, X213, mergec54_in_gga(.(T143, T144), T142, X213))
U47_gga(T143, T144, T142, X213, mergec54_out_gga(.(T143, T144), T142, X213)) → mergec54_out_gga(.(T143, T144), .(T143, T142), .(T143, X213))
U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126)
U46_ga(T99, T100, T101, X171, qc34_out_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(T99, .(T100, T101)), X171)
mergesortc25_in_aga(T62, [], .(T62, [])) → mergesortc25_out_aga(T62, [], .(T62, []))
mergesortc25_in_aga(T72, .(T73, T74), X126) → U48_aga(T72, T73, T74, X126, qc34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
U48_aga(T72, T73, T74, X126, qc34_out_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126)) → mergesortc25_out_aga(T72, .(T73, T74), X126)

The argument filtering Pi contains the following mapping:
[]  =  []
.(x1, x2)  =  .(x2)
splitc12_in_aaaa(x1, x2, x3, x4)  =  splitc12_in_aaaa
U41_aaaa(x1, x2, x3, x4, x5)  =  U41_aaaa(x5)
splitc16_in_aaa(x1, x2, x3)  =  splitc16_in_aaa
splitc16_out_aaa(x1, x2, x3)  =  splitc16_out_aaa(x1, x2, x3)
U40_aaa(x1, x2, x3, x4, x5)  =  U40_aaa(x5)
splitc12_out_aaaa(x1, x2, x3, x4)  =  splitc12_out_aaaa(x2, x3, x4)
splitc12_in_agaa(x1, x2, x3, x4)  =  splitc12_in_agaa(x2)
U41_agaa(x1, x2, x3, x4, x5)  =  U41_agaa(x2, x5)
splitc16_in_gaa(x1, x2, x3)  =  splitc16_in_gaa(x1)
splitc16_out_gaa(x1, x2, x3)  =  splitc16_out_gaa(x1, x2, x3)
U40_gaa(x1, x2, x3, x4, x5)  =  U40_gaa(x2, x5)
splitc12_out_agaa(x1, x2, x3, x4)  =  splitc12_out_agaa(x2, x3, x4)
mergesortc38_in_ga(x1, x2)  =  mergesortc38_in_ga(x1)
mergesortc38_out_ga(x1, x2)  =  mergesortc38_out_ga(x1, x2)
U46_ga(x1, x2, x3, x4, x5)  =  U46_ga(x3, x5)
qc34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_in_aagaaaaa(x3)
U42_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U42_aagaaaaa(x3, x9)
U43_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U43_aagaaaaa(x3, x4, x5, x9)
U44_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U44_aagaaaaa(x3, x4, x5, x6, x9)
U45_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U45_aagaaaaa(x3, x4, x5, x6, x7, x9)
mergec54_in_gga(x1, x2, x3)  =  mergec54_in_gga(x1, x2)
mergec54_out_gga(x1, x2, x3)  =  mergec54_out_gga(x1, x2, x3)
U47_gga(x1, x2, x3, x4, x5)  =  U47_gga(x2, x3, x5)
qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_out_aagaaaaa(x3, x4, x5, x6, x7, x8)
mergesortc25_in_aga(x1, x2, x3)  =  mergesortc25_in_aga(x2)
mergesortc25_out_aga(x1, x2, x3)  =  mergesortc25_out_aga(x2, x3)
U48_aga(x1, x2, x3, x4, x5)  =  U48_aga(x3, x5)
MERGE152_IN_AGGG(x1, x2, x3, x4)  =  MERGE152_IN_AGGG(x2, x3, x4)

We have to consider all (P,R,Pi)-chains

(14) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(15) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

MERGE152_IN_AGGG(T439, T441, .(T439, T440), .(T439, T429)) → MERGE152_IN_AGGG(T439, T441, T440, T429)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)
MERGE152_IN_AGGG(x1, x2, x3, x4)  =  MERGE152_IN_AGGG(x2, x3, x4)

We have to consider all (P,R,Pi)-chains

(16) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(17) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MERGE152_IN_AGGG(T441, .(T440), .(T429)) → MERGE152_IN_AGGG(T441, T440, T429)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(18) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • MERGE152_IN_AGGG(T441, .(T440), .(T429)) → MERGE152_IN_AGGG(T441, T440, T429)
    The graph contains the following edges 1 >= 1, 2 > 2, 3 > 3

(19) YES

(20) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

MERGE54_IN_GGA(.(T143, T144), .(T143, T142), .(T143, X213)) → MERGE54_IN_GGA(.(T143, T144), T142, X213)

The TRS R consists of the following rules:

splitc12_in_aaaa(T42, T44, .(T42, X70), X71) → U41_aaaa(T42, T44, X70, X71, splitc16_in_aaa(T44, X71, X70))
splitc16_in_aaa([], [], []) → splitc16_out_aaa([], [], [])
splitc16_in_aaa(.(T49, T51), .(T49, X88), X89) → U40_aaa(T49, T51, X88, X89, splitc16_in_aaa(T51, X89, X88))
U40_aaa(T49, T51, X88, X89, splitc16_out_aaa(T51, X89, X88)) → splitc16_out_aaa(.(T49, T51), .(T49, X88), X89)
U41_aaaa(T42, T44, X70, X71, splitc16_out_aaa(T44, X71, X70)) → splitc12_out_aaaa(T42, T44, .(T42, X70), X71)
splitc12_in_agaa(T42, T44, .(T42, X70), X71) → U41_agaa(T42, T44, X70, X71, splitc16_in_gaa(T44, X71, X70))
splitc16_in_gaa([], [], []) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T49, T51), .(T49, X88), X89) → U40_gaa(T49, T51, X88, X89, splitc16_in_gaa(T51, X89, X88))
U40_gaa(T49, T51, X88, X89, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T49, T51), .(T49, X88), X89)
U41_agaa(T42, T44, X70, X71, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T42, T44, .(T42, X70), X71)
mergesortc38_in_ga([], []) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.(T89, []), .(T89, [])) → mergesortc38_out_ga(.(T89, []), .(T89, []))
mergesortc38_in_ga(.(T99, .(T100, T101)), X171) → U46_ga(T99, T100, T101, X171, qc34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
qc34_in_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126) → U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_in_gga(T106, T105, X126))
mergec54_in_gga([], T113, T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, [], T118) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T143, T144), .(T143, T142), .(T143, X213)) → U47_gga(T143, T144, T142, X213, mergec54_in_gga(.(T143, T144), T142, X213))
U47_gga(T143, T144, T142, X213, mergec54_out_gga(.(T143, T144), T142, X213)) → mergec54_out_gga(.(T143, T144), .(T143, T142), .(T143, X213))
U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126)
U46_ga(T99, T100, T101, X171, qc34_out_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(T99, .(T100, T101)), X171)
mergesortc25_in_aga(T62, [], .(T62, [])) → mergesortc25_out_aga(T62, [], .(T62, []))
mergesortc25_in_aga(T72, .(T73, T74), X126) → U48_aga(T72, T73, T74, X126, qc34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
U48_aga(T72, T73, T74, X126, qc34_out_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126)) → mergesortc25_out_aga(T72, .(T73, T74), X126)

The argument filtering Pi contains the following mapping:
[]  =  []
.(x1, x2)  =  .(x2)
splitc12_in_aaaa(x1, x2, x3, x4)  =  splitc12_in_aaaa
U41_aaaa(x1, x2, x3, x4, x5)  =  U41_aaaa(x5)
splitc16_in_aaa(x1, x2, x3)  =  splitc16_in_aaa
splitc16_out_aaa(x1, x2, x3)  =  splitc16_out_aaa(x1, x2, x3)
U40_aaa(x1, x2, x3, x4, x5)  =  U40_aaa(x5)
splitc12_out_aaaa(x1, x2, x3, x4)  =  splitc12_out_aaaa(x2, x3, x4)
splitc12_in_agaa(x1, x2, x3, x4)  =  splitc12_in_agaa(x2)
U41_agaa(x1, x2, x3, x4, x5)  =  U41_agaa(x2, x5)
splitc16_in_gaa(x1, x2, x3)  =  splitc16_in_gaa(x1)
splitc16_out_gaa(x1, x2, x3)  =  splitc16_out_gaa(x1, x2, x3)
U40_gaa(x1, x2, x3, x4, x5)  =  U40_gaa(x2, x5)
splitc12_out_agaa(x1, x2, x3, x4)  =  splitc12_out_agaa(x2, x3, x4)
mergesortc38_in_ga(x1, x2)  =  mergesortc38_in_ga(x1)
mergesortc38_out_ga(x1, x2)  =  mergesortc38_out_ga(x1, x2)
U46_ga(x1, x2, x3, x4, x5)  =  U46_ga(x3, x5)
qc34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_in_aagaaaaa(x3)
U42_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U42_aagaaaaa(x3, x9)
U43_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U43_aagaaaaa(x3, x4, x5, x9)
U44_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U44_aagaaaaa(x3, x4, x5, x6, x9)
U45_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U45_aagaaaaa(x3, x4, x5, x6, x7, x9)
mergec54_in_gga(x1, x2, x3)  =  mergec54_in_gga(x1, x2)
mergec54_out_gga(x1, x2, x3)  =  mergec54_out_gga(x1, x2, x3)
U47_gga(x1, x2, x3, x4, x5)  =  U47_gga(x2, x3, x5)
qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_out_aagaaaaa(x3, x4, x5, x6, x7, x8)
mergesortc25_in_aga(x1, x2, x3)  =  mergesortc25_in_aga(x2)
mergesortc25_out_aga(x1, x2, x3)  =  mergesortc25_out_aga(x2, x3)
U48_aga(x1, x2, x3, x4, x5)  =  U48_aga(x3, x5)
MERGE54_IN_GGA(x1, x2, x3)  =  MERGE54_IN_GGA(x1, x2)

We have to consider all (P,R,Pi)-chains

(21) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(22) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

MERGE54_IN_GGA(.(T143, T144), .(T143, T142), .(T143, X213)) → MERGE54_IN_GGA(.(T143, T144), T142, X213)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)
MERGE54_IN_GGA(x1, x2, x3)  =  MERGE54_IN_GGA(x1, x2)

We have to consider all (P,R,Pi)-chains

(23) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(24) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MERGE54_IN_GGA(.(T144), .(T142)) → MERGE54_IN_GGA(.(T144), T142)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(25) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • MERGE54_IN_GGA(.(T144), .(T142)) → MERGE54_IN_GGA(.(T144), T142)
    The graph contains the following edges 1 >= 1, 2 > 2

(26) YES

(27) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

SPLIT16_IN_GAA(.(T49, T51), .(T49, X88), X89) → SPLIT16_IN_GAA(T51, X89, X88)

The TRS R consists of the following rules:

splitc12_in_aaaa(T42, T44, .(T42, X70), X71) → U41_aaaa(T42, T44, X70, X71, splitc16_in_aaa(T44, X71, X70))
splitc16_in_aaa([], [], []) → splitc16_out_aaa([], [], [])
splitc16_in_aaa(.(T49, T51), .(T49, X88), X89) → U40_aaa(T49, T51, X88, X89, splitc16_in_aaa(T51, X89, X88))
U40_aaa(T49, T51, X88, X89, splitc16_out_aaa(T51, X89, X88)) → splitc16_out_aaa(.(T49, T51), .(T49, X88), X89)
U41_aaaa(T42, T44, X70, X71, splitc16_out_aaa(T44, X71, X70)) → splitc12_out_aaaa(T42, T44, .(T42, X70), X71)
splitc12_in_agaa(T42, T44, .(T42, X70), X71) → U41_agaa(T42, T44, X70, X71, splitc16_in_gaa(T44, X71, X70))
splitc16_in_gaa([], [], []) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T49, T51), .(T49, X88), X89) → U40_gaa(T49, T51, X88, X89, splitc16_in_gaa(T51, X89, X88))
U40_gaa(T49, T51, X88, X89, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T49, T51), .(T49, X88), X89)
U41_agaa(T42, T44, X70, X71, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T42, T44, .(T42, X70), X71)
mergesortc38_in_ga([], []) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.(T89, []), .(T89, [])) → mergesortc38_out_ga(.(T89, []), .(T89, []))
mergesortc38_in_ga(.(T99, .(T100, T101)), X171) → U46_ga(T99, T100, T101, X171, qc34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
qc34_in_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126) → U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_in_gga(T106, T105, X126))
mergec54_in_gga([], T113, T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, [], T118) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T143, T144), .(T143, T142), .(T143, X213)) → U47_gga(T143, T144, T142, X213, mergec54_in_gga(.(T143, T144), T142, X213))
U47_gga(T143, T144, T142, X213, mergec54_out_gga(.(T143, T144), T142, X213)) → mergec54_out_gga(.(T143, T144), .(T143, T142), .(T143, X213))
U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126)
U46_ga(T99, T100, T101, X171, qc34_out_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(T99, .(T100, T101)), X171)
mergesortc25_in_aga(T62, [], .(T62, [])) → mergesortc25_out_aga(T62, [], .(T62, []))
mergesortc25_in_aga(T72, .(T73, T74), X126) → U48_aga(T72, T73, T74, X126, qc34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
U48_aga(T72, T73, T74, X126, qc34_out_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126)) → mergesortc25_out_aga(T72, .(T73, T74), X126)

The argument filtering Pi contains the following mapping:
[]  =  []
.(x1, x2)  =  .(x2)
splitc12_in_aaaa(x1, x2, x3, x4)  =  splitc12_in_aaaa
U41_aaaa(x1, x2, x3, x4, x5)  =  U41_aaaa(x5)
splitc16_in_aaa(x1, x2, x3)  =  splitc16_in_aaa
splitc16_out_aaa(x1, x2, x3)  =  splitc16_out_aaa(x1, x2, x3)
U40_aaa(x1, x2, x3, x4, x5)  =  U40_aaa(x5)
splitc12_out_aaaa(x1, x2, x3, x4)  =  splitc12_out_aaaa(x2, x3, x4)
splitc12_in_agaa(x1, x2, x3, x4)  =  splitc12_in_agaa(x2)
U41_agaa(x1, x2, x3, x4, x5)  =  U41_agaa(x2, x5)
splitc16_in_gaa(x1, x2, x3)  =  splitc16_in_gaa(x1)
splitc16_out_gaa(x1, x2, x3)  =  splitc16_out_gaa(x1, x2, x3)
U40_gaa(x1, x2, x3, x4, x5)  =  U40_gaa(x2, x5)
splitc12_out_agaa(x1, x2, x3, x4)  =  splitc12_out_agaa(x2, x3, x4)
mergesortc38_in_ga(x1, x2)  =  mergesortc38_in_ga(x1)
mergesortc38_out_ga(x1, x2)  =  mergesortc38_out_ga(x1, x2)
U46_ga(x1, x2, x3, x4, x5)  =  U46_ga(x3, x5)
qc34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_in_aagaaaaa(x3)
U42_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U42_aagaaaaa(x3, x9)
U43_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U43_aagaaaaa(x3, x4, x5, x9)
U44_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U44_aagaaaaa(x3, x4, x5, x6, x9)
U45_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U45_aagaaaaa(x3, x4, x5, x6, x7, x9)
mergec54_in_gga(x1, x2, x3)  =  mergec54_in_gga(x1, x2)
mergec54_out_gga(x1, x2, x3)  =  mergec54_out_gga(x1, x2, x3)
U47_gga(x1, x2, x3, x4, x5)  =  U47_gga(x2, x3, x5)
qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_out_aagaaaaa(x3, x4, x5, x6, x7, x8)
mergesortc25_in_aga(x1, x2, x3)  =  mergesortc25_in_aga(x2)
mergesortc25_out_aga(x1, x2, x3)  =  mergesortc25_out_aga(x2, x3)
U48_aga(x1, x2, x3, x4, x5)  =  U48_aga(x3, x5)
SPLIT16_IN_GAA(x1, x2, x3)  =  SPLIT16_IN_GAA(x1)

We have to consider all (P,R,Pi)-chains

(28) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(29) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

SPLIT16_IN_GAA(.(T49, T51), .(T49, X88), X89) → SPLIT16_IN_GAA(T51, X89, X88)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)
SPLIT16_IN_GAA(x1, x2, x3)  =  SPLIT16_IN_GAA(x1)

We have to consider all (P,R,Pi)-chains

(30) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(31) Obligation:

Q DP problem:
The TRS P consists of the following rules:

SPLIT16_IN_GAA(.(T51)) → SPLIT16_IN_GAA(T51)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(32) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • SPLIT16_IN_GAA(.(T51)) → SPLIT16_IN_GAA(T51)
    The graph contains the following edges 1 > 1

(33) YES

(34) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

P34_IN_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126) → U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T79))
U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T79)) → MERGESORT38_IN_GA(T78, X124)
MERGESORT38_IN_GA(.(T99, .(T100, T101)), X171) → P34_IN_AAGAAAAA(T99, T100, T101, X167, X168, X169, X170, X171)
P34_IN_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126) → U6_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U6_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_in_ga(T78, T83))
U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84, X125)

The TRS R consists of the following rules:

splitc12_in_aaaa(T42, T44, .(T42, X70), X71) → U41_aaaa(T42, T44, X70, X71, splitc16_in_aaa(T44, X71, X70))
splitc16_in_aaa([], [], []) → splitc16_out_aaa([], [], [])
splitc16_in_aaa(.(T49, T51), .(T49, X88), X89) → U40_aaa(T49, T51, X88, X89, splitc16_in_aaa(T51, X89, X88))
U40_aaa(T49, T51, X88, X89, splitc16_out_aaa(T51, X89, X88)) → splitc16_out_aaa(.(T49, T51), .(T49, X88), X89)
U41_aaaa(T42, T44, X70, X71, splitc16_out_aaa(T44, X71, X70)) → splitc12_out_aaaa(T42, T44, .(T42, X70), X71)
splitc12_in_agaa(T42, T44, .(T42, X70), X71) → U41_agaa(T42, T44, X70, X71, splitc16_in_gaa(T44, X71, X70))
splitc16_in_gaa([], [], []) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T49, T51), .(T49, X88), X89) → U40_gaa(T49, T51, X88, X89, splitc16_in_gaa(T51, X89, X88))
U40_gaa(T49, T51, X88, X89, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T49, T51), .(T49, X88), X89)
U41_agaa(T42, T44, X70, X71, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T42, T44, .(T42, X70), X71)
mergesortc38_in_ga([], []) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.(T89, []), .(T89, [])) → mergesortc38_out_ga(.(T89, []), .(T89, []))
mergesortc38_in_ga(.(T99, .(T100, T101)), X171) → U46_ga(T99, T100, T101, X171, qc34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
qc34_in_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126) → U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_in_gga(T106, T105, X126))
mergec54_in_gga([], T113, T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, [], T118) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T143, T144), .(T143, T142), .(T143, X213)) → U47_gga(T143, T144, T142, X213, mergec54_in_gga(.(T143, T144), T142, X213))
U47_gga(T143, T144, T142, X213, mergec54_out_gga(.(T143, T144), T142, X213)) → mergec54_out_gga(.(T143, T144), .(T143, T142), .(T143, X213))
U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126)
U46_ga(T99, T100, T101, X171, qc34_out_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(T99, .(T100, T101)), X171)
mergesortc25_in_aga(T62, [], .(T62, [])) → mergesortc25_out_aga(T62, [], .(T62, []))
mergesortc25_in_aga(T72, .(T73, T74), X126) → U48_aga(T72, T73, T74, X126, qc34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
U48_aga(T72, T73, T74, X126, qc34_out_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126)) → mergesortc25_out_aga(T72, .(T73, T74), X126)

The argument filtering Pi contains the following mapping:
[]  =  []
.(x1, x2)  =  .(x2)
splitc12_in_aaaa(x1, x2, x3, x4)  =  splitc12_in_aaaa
U41_aaaa(x1, x2, x3, x4, x5)  =  U41_aaaa(x5)
splitc16_in_aaa(x1, x2, x3)  =  splitc16_in_aaa
splitc16_out_aaa(x1, x2, x3)  =  splitc16_out_aaa(x1, x2, x3)
U40_aaa(x1, x2, x3, x4, x5)  =  U40_aaa(x5)
splitc12_out_aaaa(x1, x2, x3, x4)  =  splitc12_out_aaaa(x2, x3, x4)
splitc12_in_agaa(x1, x2, x3, x4)  =  splitc12_in_agaa(x2)
U41_agaa(x1, x2, x3, x4, x5)  =  U41_agaa(x2, x5)
splitc16_in_gaa(x1, x2, x3)  =  splitc16_in_gaa(x1)
splitc16_out_gaa(x1, x2, x3)  =  splitc16_out_gaa(x1, x2, x3)
U40_gaa(x1, x2, x3, x4, x5)  =  U40_gaa(x2, x5)
splitc12_out_agaa(x1, x2, x3, x4)  =  splitc12_out_agaa(x2, x3, x4)
mergesortc38_in_ga(x1, x2)  =  mergesortc38_in_ga(x1)
mergesortc38_out_ga(x1, x2)  =  mergesortc38_out_ga(x1, x2)
U46_ga(x1, x2, x3, x4, x5)  =  U46_ga(x3, x5)
qc34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_in_aagaaaaa(x3)
U42_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U42_aagaaaaa(x3, x9)
U43_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U43_aagaaaaa(x3, x4, x5, x9)
U44_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U44_aagaaaaa(x3, x4, x5, x6, x9)
U45_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U45_aagaaaaa(x3, x4, x5, x6, x7, x9)
mergec54_in_gga(x1, x2, x3)  =  mergec54_in_gga(x1, x2)
mergec54_out_gga(x1, x2, x3)  =  mergec54_out_gga(x1, x2, x3)
U47_gga(x1, x2, x3, x4, x5)  =  U47_gga(x2, x3, x5)
qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_out_aagaaaaa(x3, x4, x5, x6, x7, x8)
mergesortc25_in_aga(x1, x2, x3)  =  mergesortc25_in_aga(x2)
mergesortc25_out_aga(x1, x2, x3)  =  mergesortc25_out_aga(x2, x3)
U48_aga(x1, x2, x3, x4, x5)  =  U48_aga(x3, x5)
P34_IN_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8)  =  P34_IN_AAGAAAAA(x3)
U4_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U4_AAGAAAAA(x3, x9)
MERGESORT38_IN_GA(x1, x2)  =  MERGESORT38_IN_GA(x1)
U6_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U6_AAGAAAAA(x3, x9)
U7_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U7_AAGAAAAA(x3, x4, x5, x9)

We have to consider all (P,R,Pi)-chains

(35) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(36) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

P34_IN_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126) → U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T79))
U4_AAGAAAAA(T72, T73, T74, T78, T79, X124, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T79)) → MERGESORT38_IN_GA(T78, X124)
MERGESORT38_IN_GA(.(T99, .(T100, T101)), X171) → P34_IN_AAGAAAAA(T99, T100, T101, X167, X168, X169, X170, X171)
P34_IN_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126) → U6_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U6_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_in_ga(T78, T83))
U7_AAGAAAAA(T72, T73, T74, T78, T84, T83, X125, X126, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84, X125)

The TRS R consists of the following rules:

splitc12_in_agaa(T42, T44, .(T42, X70), X71) → U41_agaa(T42, T44, X70, X71, splitc16_in_gaa(T44, X71, X70))
mergesortc38_in_ga([], []) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.(T89, []), .(T89, [])) → mergesortc38_out_ga(.(T89, []), .(T89, []))
mergesortc38_in_ga(.(T99, .(T100, T101)), X171) → U46_ga(T99, T100, T101, X171, qc34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
U41_agaa(T42, T44, X70, X71, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T42, T44, .(T42, X70), X71)
U46_ga(T99, T100, T101, X171, qc34_out_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(T99, .(T100, T101)), X171)
splitc16_in_gaa([], [], []) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T49, T51), .(T49, X88), X89) → U40_gaa(T49, T51, X88, X89, splitc16_in_gaa(T51, X89, X88))
qc34_in_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126) → U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U40_gaa(T49, T51, X88, X89, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T49, T51), .(T49, X88), X89)
U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_in_gga(T106, T105, X126))
U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126)
mergec54_in_gga([], T113, T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, [], T118) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T143, T144), .(T143, T142), .(T143, X213)) → U47_gga(T143, T144, T142, X213, mergec54_in_gga(.(T143, T144), T142, X213))
U47_gga(T143, T144, T142, X213, mergec54_out_gga(.(T143, T144), T142, X213)) → mergec54_out_gga(.(T143, T144), .(T143, T142), .(T143, X213))

The argument filtering Pi contains the following mapping:
[]  =  []
.(x1, x2)  =  .(x2)
splitc12_in_agaa(x1, x2, x3, x4)  =  splitc12_in_agaa(x2)
U41_agaa(x1, x2, x3, x4, x5)  =  U41_agaa(x2, x5)
splitc16_in_gaa(x1, x2, x3)  =  splitc16_in_gaa(x1)
splitc16_out_gaa(x1, x2, x3)  =  splitc16_out_gaa(x1, x2, x3)
U40_gaa(x1, x2, x3, x4, x5)  =  U40_gaa(x2, x5)
splitc12_out_agaa(x1, x2, x3, x4)  =  splitc12_out_agaa(x2, x3, x4)
mergesortc38_in_ga(x1, x2)  =  mergesortc38_in_ga(x1)
mergesortc38_out_ga(x1, x2)  =  mergesortc38_out_ga(x1, x2)
U46_ga(x1, x2, x3, x4, x5)  =  U46_ga(x3, x5)
qc34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_in_aagaaaaa(x3)
U42_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U42_aagaaaaa(x3, x9)
U43_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U43_aagaaaaa(x3, x4, x5, x9)
U44_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U44_aagaaaaa(x3, x4, x5, x6, x9)
U45_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U45_aagaaaaa(x3, x4, x5, x6, x7, x9)
mergec54_in_gga(x1, x2, x3)  =  mergec54_in_gga(x1, x2)
mergec54_out_gga(x1, x2, x3)  =  mergec54_out_gga(x1, x2, x3)
U47_gga(x1, x2, x3, x4, x5)  =  U47_gga(x2, x3, x5)
qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_out_aagaaaaa(x3, x4, x5, x6, x7, x8)
P34_IN_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8)  =  P34_IN_AAGAAAAA(x3)
U4_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U4_AAGAAAAA(x3, x9)
MERGESORT38_IN_GA(x1, x2)  =  MERGESORT38_IN_GA(x1)
U6_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U6_AAGAAAAA(x3, x9)
U7_AAGAAAAA(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U7_AAGAAAAA(x3, x4, x5, x9)

We have to consider all (P,R,Pi)-chains

(37) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(38) Obligation:

Q DP problem:
The TRS P consists of the following rules:

P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, splitc12_in_agaa(.(T74)))
U4_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T79)) → MERGESORT38_IN_GA(T78)
MERGESORT38_IN_GA(.(.(T101))) → P34_IN_AAGAAAAA(T101)
P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, splitc12_in_agaa(.(T74)))
U6_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T84)) → U7_AAGAAAAA(T74, T78, T84, mergesortc38_in_ga(T78))
U7_AAGAAAAA(T74, T78, T84, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84)

The TRS R consists of the following rules:

splitc12_in_agaa(T44) → U41_agaa(T44, splitc16_in_gaa(T44))
mergesortc38_in_ga([]) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.([])) → mergesortc38_out_ga(.([]), .([]))
mergesortc38_in_ga(.(.(T101))) → U46_ga(T101, qc34_in_aagaaaaa(T101))
U41_agaa(T44, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T44, .(X70), X71)
U46_ga(T101, qc34_out_aagaaaaa(T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(.(T101)), X171)
splitc16_in_gaa([]) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T51)) → U40_gaa(T51, splitc16_in_gaa(T51))
qc34_in_aagaaaaa(T74) → U42_aagaaaaa(T74, splitc12_in_agaa(.(T74)))
U40_gaa(T51, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T51), .(X88), X89)
U42_aagaaaaa(T74, splitc12_out_agaa(.(T74), T78, T84)) → U43_aagaaaaa(T74, T78, T84, mergesortc38_in_ga(T78))
U43_aagaaaaa(T74, T78, T84, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_in_ga(T84))
U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_in_gga(T106, T105))
U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T74, T78, T84, T106, T105, X126)
mergec54_in_gga([], T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, []) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T144), .(T142)) → U47_gga(T144, T142, mergec54_in_gga(.(T144), T142))
U47_gga(T144, T142, mergec54_out_gga(.(T144), T142, X213)) → mergec54_out_gga(.(T144), .(T142), .(X213))

The set Q consists of the following terms:

splitc12_in_agaa(x0)
mergesortc38_in_ga(x0)
U41_agaa(x0, x1)
U46_ga(x0, x1)
splitc16_in_gaa(x0)
qc34_in_aagaaaaa(x0)
U40_gaa(x0, x1)
U42_aagaaaaa(x0, x1)
U43_aagaaaaa(x0, x1, x2, x3)
U44_aagaaaaa(x0, x1, x2, x3, x4)
U45_aagaaaaa(x0, x1, x2, x3, x4, x5)
mergec54_in_gga(x0, x1)
U47_gga(x0, x1, x2)

We have to consider all (P,Q,R)-chains.

(39) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, splitc12_in_agaa(.(T74))) at position [1] we obtained the following new rules [LPAR04]:

P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, U41_agaa(.(T74), splitc16_in_gaa(.(T74))))

(40) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U4_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T79)) → MERGESORT38_IN_GA(T78)
MERGESORT38_IN_GA(.(.(T101))) → P34_IN_AAGAAAAA(T101)
P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, splitc12_in_agaa(.(T74)))
U6_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T84)) → U7_AAGAAAAA(T74, T78, T84, mergesortc38_in_ga(T78))
U7_AAGAAAAA(T74, T78, T84, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84)
P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, U41_agaa(.(T74), splitc16_in_gaa(.(T74))))

The TRS R consists of the following rules:

splitc12_in_agaa(T44) → U41_agaa(T44, splitc16_in_gaa(T44))
mergesortc38_in_ga([]) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.([])) → mergesortc38_out_ga(.([]), .([]))
mergesortc38_in_ga(.(.(T101))) → U46_ga(T101, qc34_in_aagaaaaa(T101))
U41_agaa(T44, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T44, .(X70), X71)
U46_ga(T101, qc34_out_aagaaaaa(T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(.(T101)), X171)
splitc16_in_gaa([]) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T51)) → U40_gaa(T51, splitc16_in_gaa(T51))
qc34_in_aagaaaaa(T74) → U42_aagaaaaa(T74, splitc12_in_agaa(.(T74)))
U40_gaa(T51, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T51), .(X88), X89)
U42_aagaaaaa(T74, splitc12_out_agaa(.(T74), T78, T84)) → U43_aagaaaaa(T74, T78, T84, mergesortc38_in_ga(T78))
U43_aagaaaaa(T74, T78, T84, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_in_ga(T84))
U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_in_gga(T106, T105))
U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T74, T78, T84, T106, T105, X126)
mergec54_in_gga([], T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, []) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T144), .(T142)) → U47_gga(T144, T142, mergec54_in_gga(.(T144), T142))
U47_gga(T144, T142, mergec54_out_gga(.(T144), T142, X213)) → mergec54_out_gga(.(T144), .(T142), .(X213))

The set Q consists of the following terms:

splitc12_in_agaa(x0)
mergesortc38_in_ga(x0)
U41_agaa(x0, x1)
U46_ga(x0, x1)
splitc16_in_gaa(x0)
qc34_in_aagaaaaa(x0)
U40_gaa(x0, x1)
U42_aagaaaaa(x0, x1)
U43_aagaaaaa(x0, x1, x2, x3)
U44_aagaaaaa(x0, x1, x2, x3, x4)
U45_aagaaaaa(x0, x1, x2, x3, x4, x5)
mergec54_in_gga(x0, x1)
U47_gga(x0, x1, x2)

We have to consider all (P,Q,R)-chains.

(41) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, splitc12_in_agaa(.(T74))) at position [1] we obtained the following new rules [LPAR04]:

P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, U41_agaa(.(T74), splitc16_in_gaa(.(T74))))

(42) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U4_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T79)) → MERGESORT38_IN_GA(T78)
MERGESORT38_IN_GA(.(.(T101))) → P34_IN_AAGAAAAA(T101)
U6_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T84)) → U7_AAGAAAAA(T74, T78, T84, mergesortc38_in_ga(T78))
U7_AAGAAAAA(T74, T78, T84, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84)
P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, U41_agaa(.(T74), splitc16_in_gaa(.(T74))))
P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, U41_agaa(.(T74), splitc16_in_gaa(.(T74))))

The TRS R consists of the following rules:

splitc12_in_agaa(T44) → U41_agaa(T44, splitc16_in_gaa(T44))
mergesortc38_in_ga([]) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.([])) → mergesortc38_out_ga(.([]), .([]))
mergesortc38_in_ga(.(.(T101))) → U46_ga(T101, qc34_in_aagaaaaa(T101))
U41_agaa(T44, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T44, .(X70), X71)
U46_ga(T101, qc34_out_aagaaaaa(T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(.(T101)), X171)
splitc16_in_gaa([]) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T51)) → U40_gaa(T51, splitc16_in_gaa(T51))
qc34_in_aagaaaaa(T74) → U42_aagaaaaa(T74, splitc12_in_agaa(.(T74)))
U40_gaa(T51, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T51), .(X88), X89)
U42_aagaaaaa(T74, splitc12_out_agaa(.(T74), T78, T84)) → U43_aagaaaaa(T74, T78, T84, mergesortc38_in_ga(T78))
U43_aagaaaaa(T74, T78, T84, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_in_ga(T84))
U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_in_gga(T106, T105))
U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T74, T78, T84, T106, T105, X126)
mergec54_in_gga([], T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, []) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T144), .(T142)) → U47_gga(T144, T142, mergec54_in_gga(.(T144), T142))
U47_gga(T144, T142, mergec54_out_gga(.(T144), T142, X213)) → mergec54_out_gga(.(T144), .(T142), .(X213))

The set Q consists of the following terms:

splitc12_in_agaa(x0)
mergesortc38_in_ga(x0)
U41_agaa(x0, x1)
U46_ga(x0, x1)
splitc16_in_gaa(x0)
qc34_in_aagaaaaa(x0)
U40_gaa(x0, x1)
U42_aagaaaaa(x0, x1)
U43_aagaaaaa(x0, x1, x2, x3)
U44_aagaaaaa(x0, x1, x2, x3, x4)
U45_aagaaaaa(x0, x1, x2, x3, x4, x5)
mergec54_in_gga(x0, x1)
U47_gga(x0, x1, x2)

We have to consider all (P,Q,R)-chains.

(43) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, U41_agaa(.(T74), splitc16_in_gaa(.(T74)))) at position [1,1] we obtained the following new rules [LPAR04]:

P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, U41_agaa(.(T74), U40_gaa(T74, splitc16_in_gaa(T74))))

(44) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U4_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T79)) → MERGESORT38_IN_GA(T78)
MERGESORT38_IN_GA(.(.(T101))) → P34_IN_AAGAAAAA(T101)
U6_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T84)) → U7_AAGAAAAA(T74, T78, T84, mergesortc38_in_ga(T78))
U7_AAGAAAAA(T74, T78, T84, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84)
P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, U41_agaa(.(T74), splitc16_in_gaa(.(T74))))
P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, U41_agaa(.(T74), U40_gaa(T74, splitc16_in_gaa(T74))))

The TRS R consists of the following rules:

splitc12_in_agaa(T44) → U41_agaa(T44, splitc16_in_gaa(T44))
mergesortc38_in_ga([]) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.([])) → mergesortc38_out_ga(.([]), .([]))
mergesortc38_in_ga(.(.(T101))) → U46_ga(T101, qc34_in_aagaaaaa(T101))
U41_agaa(T44, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T44, .(X70), X71)
U46_ga(T101, qc34_out_aagaaaaa(T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(.(T101)), X171)
splitc16_in_gaa([]) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T51)) → U40_gaa(T51, splitc16_in_gaa(T51))
qc34_in_aagaaaaa(T74) → U42_aagaaaaa(T74, splitc12_in_agaa(.(T74)))
U40_gaa(T51, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T51), .(X88), X89)
U42_aagaaaaa(T74, splitc12_out_agaa(.(T74), T78, T84)) → U43_aagaaaaa(T74, T78, T84, mergesortc38_in_ga(T78))
U43_aagaaaaa(T74, T78, T84, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_in_ga(T84))
U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_in_gga(T106, T105))
U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T74, T78, T84, T106, T105, X126)
mergec54_in_gga([], T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, []) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T144), .(T142)) → U47_gga(T144, T142, mergec54_in_gga(.(T144), T142))
U47_gga(T144, T142, mergec54_out_gga(.(T144), T142, X213)) → mergec54_out_gga(.(T144), .(T142), .(X213))

The set Q consists of the following terms:

splitc12_in_agaa(x0)
mergesortc38_in_ga(x0)
U41_agaa(x0, x1)
U46_ga(x0, x1)
splitc16_in_gaa(x0)
qc34_in_aagaaaaa(x0)
U40_gaa(x0, x1)
U42_aagaaaaa(x0, x1)
U43_aagaaaaa(x0, x1, x2, x3)
U44_aagaaaaa(x0, x1, x2, x3, x4)
U45_aagaaaaa(x0, x1, x2, x3, x4, x5)
mergec54_in_gga(x0, x1)
U47_gga(x0, x1, x2)

We have to consider all (P,Q,R)-chains.

(45) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, U41_agaa(.(T74), splitc16_in_gaa(.(T74)))) at position [1,1] we obtained the following new rules [LPAR04]:

P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, U41_agaa(.(T74), U40_gaa(T74, splitc16_in_gaa(T74))))

(46) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U4_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T79)) → MERGESORT38_IN_GA(T78)
MERGESORT38_IN_GA(.(.(T101))) → P34_IN_AAGAAAAA(T101)
U6_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T84)) → U7_AAGAAAAA(T74, T78, T84, mergesortc38_in_ga(T78))
U7_AAGAAAAA(T74, T78, T84, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84)
P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, U41_agaa(.(T74), U40_gaa(T74, splitc16_in_gaa(T74))))
P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, U41_agaa(.(T74), U40_gaa(T74, splitc16_in_gaa(T74))))

The TRS R consists of the following rules:

splitc12_in_agaa(T44) → U41_agaa(T44, splitc16_in_gaa(T44))
mergesortc38_in_ga([]) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.([])) → mergesortc38_out_ga(.([]), .([]))
mergesortc38_in_ga(.(.(T101))) → U46_ga(T101, qc34_in_aagaaaaa(T101))
U41_agaa(T44, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T44, .(X70), X71)
U46_ga(T101, qc34_out_aagaaaaa(T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(.(T101)), X171)
splitc16_in_gaa([]) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T51)) → U40_gaa(T51, splitc16_in_gaa(T51))
qc34_in_aagaaaaa(T74) → U42_aagaaaaa(T74, splitc12_in_agaa(.(T74)))
U40_gaa(T51, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T51), .(X88), X89)
U42_aagaaaaa(T74, splitc12_out_agaa(.(T74), T78, T84)) → U43_aagaaaaa(T74, T78, T84, mergesortc38_in_ga(T78))
U43_aagaaaaa(T74, T78, T84, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_in_ga(T84))
U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_in_gga(T106, T105))
U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T74, T78, T84, T106, T105, X126)
mergec54_in_gga([], T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, []) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T144), .(T142)) → U47_gga(T144, T142, mergec54_in_gga(.(T144), T142))
U47_gga(T144, T142, mergec54_out_gga(.(T144), T142, X213)) → mergec54_out_gga(.(T144), .(T142), .(X213))

The set Q consists of the following terms:

splitc12_in_agaa(x0)
mergesortc38_in_ga(x0)
U41_agaa(x0, x1)
U46_ga(x0, x1)
splitc16_in_gaa(x0)
qc34_in_aagaaaaa(x0)
U40_gaa(x0, x1)
U42_aagaaaaa(x0, x1)
U43_aagaaaaa(x0, x1, x2, x3)
U44_aagaaaaa(x0, x1, x2, x3, x4)
U45_aagaaaaa(x0, x1, x2, x3, x4, x5)
mergec54_in_gga(x0, x1)
U47_gga(x0, x1, x2)

We have to consider all (P,Q,R)-chains.

(47) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


P34_IN_AAGAAAAA(T74) → U4_AAGAAAAA(T74, U41_agaa(.(T74), U40_gaa(T74, splitc16_in_gaa(T74))))
P34_IN_AAGAAAAA(T74) → U6_AAGAAAAA(T74, U41_agaa(.(T74), U40_gaa(T74, splitc16_in_gaa(T74))))
The remaining pairs can at least be oriented weakly.
Used ordering: Matrix interpretation [MATRO]:

POL(U4_AAGAAAAA(x1, x2)) = 0 +
[0,0]
·x1 +
[1,0]
·x2

POL(splitc12_out_agaa(x1, x2, x3)) =
/0\
\0/
+
/00\
\00/
·x1 +
/10\
\00/
·x2 +
/10\
\00/
·x3

POL(.(x1)) =
/0\
\1/
+
/11\
\11/
·x1

POL(MERGESORT38_IN_GA(x1)) = 0 +
[1,0]
·x1

POL(P34_IN_AAGAAAAA(x1)) = 1 +
[1,1]
·x1

POL(U6_AAGAAAAA(x1, x2)) = 0 +
[0,0]
·x1 +
[1,0]
·x2

POL(U7_AAGAAAAA(x1, x2, x3, x4)) = 0 +
[0,0]
·x1 +
[0,0]
·x2 +
[1,0]
·x3 +
[0,0]
·x4

POL(mergesortc38_in_ga(x1)) =
/0\
\0/
+
/00\
\00/
·x1

POL(mergesortc38_out_ga(x1, x2)) =
/0\
\0/
+
/00\
\01/
·x1 +
/01\
\01/
·x2

POL(U41_agaa(x1, x2)) =
/0\
\0/
+
/00\
\00/
·x1 +
/10\
\00/
·x2

POL(U40_gaa(x1, x2)) =
/0\
\1/
+
/00\
\00/
·x1 +
/11\
\10/
·x2

POL(splitc16_in_gaa(x1)) =
/0\
\0/
+
/10\
\01/
·x1

POL([]) =
/0\
\0/

POL(U46_ga(x1, x2)) =
/1\
\1/
+
/01\
\11/
·x1 +
/00\
\00/
·x2

POL(qc34_in_aagaaaaa(x1)) =
/0\
\0/
+
/00\
\00/
·x1

POL(splitc16_out_gaa(x1, x2, x3)) =
/0\
\0/
+
/00\
\00/
·x1 +
/10\
\01/
·x2 +
/11\
\00/
·x3

POL(U42_aagaaaaa(x1, x2)) =
/0\
\0/
+
/10\
\00/
·x1 +
/00\
\00/
·x2

POL(U43_aagaaaaa(x1, x2, x3, x4)) =
/1\
\1/
+
/11\
\11/
·x1 +
/11\
\01/
·x2 +
/10\
\10/
·x3 +
/00\
\00/
·x4

POL(qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6)) =
/1\
\1/
+
/11\
\10/
·x1 +
/01\
\11/
·x2 +
/01\
\11/
·x3 +
/11\
\11/
·x4 +
/11\
\11/
·x5 +
/01\
\11/
·x6

POL(splitc12_in_agaa(x1)) =
/1\
\1/
+
/01\
\00/
·x1

POL(U44_aagaaaaa(x1, x2, x3, x4, x5)) =
/0\
\0/
+
/01\
\00/
·x1 +
/01\
\10/
·x2 +
/10\
\01/
·x3 +
/00\
\00/
·x4 +
/00\
\00/
·x5

POL(U45_aagaaaaa(x1, x2, x3, x4, x5, x6)) =
/0\
\0/
+
/00\
\01/
·x1 +
/00\
\00/
·x2 +
/01\
\10/
·x3 +
/00\
\01/
·x4 +
/00\
\00/
·x5 +
/00\
\00/
·x6

POL(mergec54_in_gga(x1, x2)) =
/0\
\0/
+
/11\
\00/
·x1 +
/10\
\00/
·x2

POL(mergec54_out_gga(x1, x2, x3)) =
/1\
\0/
+
/11\
\00/
·x1 +
/10\
\00/
·x2 +
/00\
\00/
·x3

POL(U47_gga(x1, x2, x3)) =
/0\
\0/
+
/10\
\01/
·x1 +
/00\
\10/
·x2 +
/00\
\10/
·x3

The following usable rules [FROCOS05] were oriented:

splitc16_in_gaa([]) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T51)) → U40_gaa(T51, splitc16_in_gaa(T51))
U40_gaa(T51, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T51), .(X88), X89)
U41_agaa(T44, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T44, .(X70), X71)

(48) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U4_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T79)) → MERGESORT38_IN_GA(T78)
MERGESORT38_IN_GA(.(.(T101))) → P34_IN_AAGAAAAA(T101)
U6_AAGAAAAA(T74, splitc12_out_agaa(.(T74), T78, T84)) → U7_AAGAAAAA(T74, T78, T84, mergesortc38_in_ga(T78))
U7_AAGAAAAA(T74, T78, T84, mergesortc38_out_ga(T78, T83)) → MERGESORT38_IN_GA(T84)

The TRS R consists of the following rules:

splitc12_in_agaa(T44) → U41_agaa(T44, splitc16_in_gaa(T44))
mergesortc38_in_ga([]) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.([])) → mergesortc38_out_ga(.([]), .([]))
mergesortc38_in_ga(.(.(T101))) → U46_ga(T101, qc34_in_aagaaaaa(T101))
U41_agaa(T44, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T44, .(X70), X71)
U46_ga(T101, qc34_out_aagaaaaa(T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(.(T101)), X171)
splitc16_in_gaa([]) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T51)) → U40_gaa(T51, splitc16_in_gaa(T51))
qc34_in_aagaaaaa(T74) → U42_aagaaaaa(T74, splitc12_in_agaa(.(T74)))
U40_gaa(T51, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T51), .(X88), X89)
U42_aagaaaaa(T74, splitc12_out_agaa(.(T74), T78, T84)) → U43_aagaaaaa(T74, T78, T84, mergesortc38_in_ga(T78))
U43_aagaaaaa(T74, T78, T84, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_in_ga(T84))
U44_aagaaaaa(T74, T78, T84, T106, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_in_gga(T106, T105))
U45_aagaaaaa(T74, T78, T84, T106, T105, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T74, T78, T84, T106, T105, X126)
mergec54_in_gga([], T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, []) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T144), .(T142)) → U47_gga(T144, T142, mergec54_in_gga(.(T144), T142))
U47_gga(T144, T142, mergec54_out_gga(.(T144), T142, X213)) → mergec54_out_gga(.(T144), .(T142), .(X213))

The set Q consists of the following terms:

splitc12_in_agaa(x0)
mergesortc38_in_ga(x0)
U41_agaa(x0, x1)
U46_ga(x0, x1)
splitc16_in_gaa(x0)
qc34_in_aagaaaaa(x0)
U40_gaa(x0, x1)
U42_aagaaaaa(x0, x1)
U43_aagaaaaa(x0, x1, x2, x3)
U44_aagaaaaa(x0, x1, x2, x3, x4)
U45_aagaaaaa(x0, x1, x2, x3, x4, x5)
mergec54_in_gga(x0, x1)
U47_gga(x0, x1, x2)

We have to consider all (P,Q,R)-chains.

(49) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes.

(50) TRUE

(51) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

SPLIT16_IN_AAA(.(T49, T51), .(T49, X88), X89) → SPLIT16_IN_AAA(T51, X89, X88)

The TRS R consists of the following rules:

splitc12_in_aaaa(T42, T44, .(T42, X70), X71) → U41_aaaa(T42, T44, X70, X71, splitc16_in_aaa(T44, X71, X70))
splitc16_in_aaa([], [], []) → splitc16_out_aaa([], [], [])
splitc16_in_aaa(.(T49, T51), .(T49, X88), X89) → U40_aaa(T49, T51, X88, X89, splitc16_in_aaa(T51, X89, X88))
U40_aaa(T49, T51, X88, X89, splitc16_out_aaa(T51, X89, X88)) → splitc16_out_aaa(.(T49, T51), .(T49, X88), X89)
U41_aaaa(T42, T44, X70, X71, splitc16_out_aaa(T44, X71, X70)) → splitc12_out_aaaa(T42, T44, .(T42, X70), X71)
splitc12_in_agaa(T42, T44, .(T42, X70), X71) → U41_agaa(T42, T44, X70, X71, splitc16_in_gaa(T44, X71, X70))
splitc16_in_gaa([], [], []) → splitc16_out_gaa([], [], [])
splitc16_in_gaa(.(T49, T51), .(T49, X88), X89) → U40_gaa(T49, T51, X88, X89, splitc16_in_gaa(T51, X89, X88))
U40_gaa(T49, T51, X88, X89, splitc16_out_gaa(T51, X89, X88)) → splitc16_out_gaa(.(T49, T51), .(T49, X88), X89)
U41_agaa(T42, T44, X70, X71, splitc16_out_gaa(T44, X71, X70)) → splitc12_out_agaa(T42, T44, .(T42, X70), X71)
mergesortc38_in_ga([], []) → mergesortc38_out_ga([], [])
mergesortc38_in_ga(.(T89, []), .(T89, [])) → mergesortc38_out_ga(.(T89, []), .(T89, []))
mergesortc38_in_ga(.(T99, .(T100, T101)), X171) → U46_ga(T99, T100, T101, X171, qc34_in_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171))
qc34_in_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126) → U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_in_agaa(T72, .(T73, T74), T78, T84))
U42_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, splitc12_out_agaa(T72, .(T73, T74), T78, T84)) → U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T78, T106))
U43_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T78, T106)) → U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_in_ga(T84, T105))
U44_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergesortc38_out_ga(T84, T105)) → U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_in_gga(T106, T105, X126))
mergec54_in_gga([], T113, T113) → mergec54_out_gga([], T113, T113)
mergec54_in_gga(T118, [], T118) → mergec54_out_gga(T118, [], T118)
mergec54_in_gga(.(T143, T144), .(T143, T142), .(T143, X213)) → U47_gga(T143, T144, T142, X213, mergec54_in_gga(.(T143, T144), T142, X213))
U47_gga(T143, T144, T142, X213, mergec54_out_gga(.(T143, T144), T142, X213)) → mergec54_out_gga(.(T143, T144), .(T143, T142), .(T143, X213))
U45_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126, mergec54_out_gga(T106, T105, X126)) → qc34_out_aagaaaaa(T72, T73, T74, T78, T84, T106, T105, X126)
U46_ga(T99, T100, T101, X171, qc34_out_aagaaaaa(T99, T100, T101, X167, X168, X169, X170, X171)) → mergesortc38_out_ga(.(T99, .(T100, T101)), X171)
mergesortc25_in_aga(T62, [], .(T62, [])) → mergesortc25_out_aga(T62, [], .(T62, []))
mergesortc25_in_aga(T72, .(T73, T74), X126) → U48_aga(T72, T73, T74, X126, qc34_in_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126))
U48_aga(T72, T73, T74, X126, qc34_out_aagaaaaa(T72, T73, T74, X122, X123, X124, X125, X126)) → mergesortc25_out_aga(T72, .(T73, T74), X126)

The argument filtering Pi contains the following mapping:
[]  =  []
.(x1, x2)  =  .(x2)
splitc12_in_aaaa(x1, x2, x3, x4)  =  splitc12_in_aaaa
U41_aaaa(x1, x2, x3, x4, x5)  =  U41_aaaa(x5)
splitc16_in_aaa(x1, x2, x3)  =  splitc16_in_aaa
splitc16_out_aaa(x1, x2, x3)  =  splitc16_out_aaa(x1, x2, x3)
U40_aaa(x1, x2, x3, x4, x5)  =  U40_aaa(x5)
splitc12_out_aaaa(x1, x2, x3, x4)  =  splitc12_out_aaaa(x2, x3, x4)
splitc12_in_agaa(x1, x2, x3, x4)  =  splitc12_in_agaa(x2)
U41_agaa(x1, x2, x3, x4, x5)  =  U41_agaa(x2, x5)
splitc16_in_gaa(x1, x2, x3)  =  splitc16_in_gaa(x1)
splitc16_out_gaa(x1, x2, x3)  =  splitc16_out_gaa(x1, x2, x3)
U40_gaa(x1, x2, x3, x4, x5)  =  U40_gaa(x2, x5)
splitc12_out_agaa(x1, x2, x3, x4)  =  splitc12_out_agaa(x2, x3, x4)
mergesortc38_in_ga(x1, x2)  =  mergesortc38_in_ga(x1)
mergesortc38_out_ga(x1, x2)  =  mergesortc38_out_ga(x1, x2)
U46_ga(x1, x2, x3, x4, x5)  =  U46_ga(x3, x5)
qc34_in_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_in_aagaaaaa(x3)
U42_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U42_aagaaaaa(x3, x9)
U43_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U43_aagaaaaa(x3, x4, x5, x9)
U44_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U44_aagaaaaa(x3, x4, x5, x6, x9)
U45_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8, x9)  =  U45_aagaaaaa(x3, x4, x5, x6, x7, x9)
mergec54_in_gga(x1, x2, x3)  =  mergec54_in_gga(x1, x2)
mergec54_out_gga(x1, x2, x3)  =  mergec54_out_gga(x1, x2, x3)
U47_gga(x1, x2, x3, x4, x5)  =  U47_gga(x2, x3, x5)
qc34_out_aagaaaaa(x1, x2, x3, x4, x5, x6, x7, x8)  =  qc34_out_aagaaaaa(x3, x4, x5, x6, x7, x8)
mergesortc25_in_aga(x1, x2, x3)  =  mergesortc25_in_aga(x2)
mergesortc25_out_aga(x1, x2, x3)  =  mergesortc25_out_aga(x2, x3)
U48_aga(x1, x2, x3, x4, x5)  =  U48_aga(x3, x5)
SPLIT16_IN_AAA(x1, x2, x3)  =  SPLIT16_IN_AAA

We have to consider all (P,R,Pi)-chains

(52) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(53) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

SPLIT16_IN_AAA(.(T49, T51), .(T49, X88), X89) → SPLIT16_IN_AAA(T51, X89, X88)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)
SPLIT16_IN_AAA(x1, x2, x3)  =  SPLIT16_IN_AAA

We have to consider all (P,R,Pi)-chains

(54) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(55) Obligation:

Q DP problem:
The TRS P consists of the following rules:

SPLIT16_IN_AAASPLIT16_IN_AAA

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(56) NonTerminationProof (EQUIVALENT transformation)

We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = SPLIT16_IN_AAA evaluates to t =SPLIT16_IN_AAA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
  • Semiunifier: [ ]
  • Matcher: [ ]




Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from SPLIT16_IN_AAA to SPLIT16_IN_AAA.



(57) NO