(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)) :- ','(le(X, Y), merge(Xs, .(Y, Ys), Zs)).
merge(.(X, Xs), .(Y, Ys), .(Y, Zs)) :- ','(gt(X, Y), merge(.(X, Xs), Ys, Zs)).
gt(s(X), s(Y)) :- gt(X, Y).
gt(s(X), 0).
le(s(X), s(Y)) :- le(X, Y).
le(0, s(Y)).
le(0, 0).

Queries:

mergesort(g,a).

(1) PrologToDTProblemTransformerProof (SOUND transformation)

Built DT problem from termination graph.

(2) Obligation:

Triples:

split21(.(T42, T43), .(T42, X99), X100) :- split21(T43, X100, X99).
split17(T36, T37, .(T36, X81), X82) :- split21(T37, X82, X81).
mergesort32(.(T61, .(T62, T63)), X137) :- split17(T61, .(T62, T63), X133, X134).
mergesort32(.(T61, .(T62, T63)), X137) :- ','(splitc17(T61, .(T62, T63), T67, T68), mergesort32(T67, X135)).
mergesort32(.(T61, .(T62, T63)), X137) :- ','(splitc17(T61, .(T62, T63), T67, T68), ','(mergesortc32(T67, T72), mergesort32(T68, X136))).
mergesort32(.(T61, .(T62, T63)), X137) :- ','(splitc17(T61, .(T62, T63), T67, T68), ','(mergesortc32(T67, T72), ','(mergesortc32(T68, T73), merge33(T72, T73, X137)))).
merge33(.(T108, T109), .(T110, T111), .(T108, T113)) :- le68(T108, T110).
merge33(.(T108, T109), .(T110, T111), .(T108, T113)) :- ','(lec68(T108, T110), merge33(T109, .(T110, T111), T113)).
merge33(.(T149, T150), .(T151, T152), .(T151, T154)) :- gt85(T149, T151).
merge33(.(T149, T150), .(T151, T152), .(T151, T154)) :- ','(gtc85(T149, T151), merge33(.(T149, T150), T152, T154)).
le68(s(T126), s(T127)) :- le68(T126, T127).
gt85(s(T167), s(T168)) :- gt85(T167, T168).
mergesort1(.(T23, .(T24, T25)), T14) :- split17(T24, T25, X52, X51).
mergesort1(.(T23, .(T24, T25)), T14) :- ','(splitc17(T24, T25, T28, T29), mergesort1(.(T23, T29), X23)).
mergesort1(.(T23, .(T24, T25)), T14) :- ','(splitc17(T24, T25, T28, T29), ','(mergesortc1(.(T23, T29), T46), mergesort32(T28, X24))).
mergesort1(.(T23, .(T24, T25)), T14) :- ','(splitc17(T24, T25, T28, T29), ','(mergesortc1(.(T23, T29), T46), ','(mergesortc32(T28, T49), merge33(T46, T49, T14)))).

Clauses:

splitc21([], [], []).
splitc21(.(T42, T43), .(T42, X99), X100) :- splitc21(T43, X100, X99).
mergesortc1([], []).
mergesortc1(.(T4, []), .(T4, [])).
mergesortc1(.(T23, .(T24, T25)), T14) :- ','(splitc17(T24, T25, T28, T29), ','(mergesortc1(.(T23, T29), T46), ','(mergesortc32(T28, T49), mergec33(T46, T49, T14)))).
splitc17(T36, T37, .(T36, X81), X82) :- splitc21(T37, X82, X81).
mergesortc32([], []).
mergesortc32(.(T54, []), .(T54, [])).
mergesortc32(.(T61, .(T62, T63)), X137) :- ','(splitc17(T61, .(T62, T63), T67, T68), ','(mergesortc32(T67, T72), ','(mergesortc32(T68, T73), mergec33(T72, T73, X137)))).
mergec33([], T82, T82).
mergec33(T87, [], T87).
mergec33(.(T108, T109), .(T110, T111), .(T108, T113)) :- ','(lec68(T108, T110), mergec33(T109, .(T110, T111), T113)).
mergec33(.(T149, T150), .(T151, T152), .(T151, T154)) :- ','(gtc85(T149, T151), mergec33(.(T149, T150), T152, T154)).
lec68(s(T126), s(T127)) :- lec68(T126, T127).
lec68(0, s(T134)).
lec68(0, 0).
gtc85(s(T167), s(T168)) :- gtc85(T167, T168).
gtc85(s(T173), 0).

Afs:

mergesort1(x1, x2)  =  mergesort1(x1)

(3) 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: (b,f)
split17_in: (b,b,f,f)
split21_in: (b,f,f)
splitc17_in: (b,b,f,f)
splitc21_in: (b,f,f)
mergesortc1_in: (b,f)
mergesortc32_in: (b,f)
mergec33_in: (b,b,f)
lec68_in: (b,b)
gtc85_in: (b,b)
mergesort32_in: (b,f)
merge33_in: (b,b,f)
le68_in: (b,b)
gt85_in: (b,b)
Transforming TRIPLES into the following Term Rewriting System:
Pi DP problem:
The TRS P consists of the following rules:

MERGESORT1_IN_GA(.(T23, .(T24, T25)), T14) → U18_GA(T23, T24, T25, T14, split17_in_ggaa(T24, T25, X52, X51))
MERGESORT1_IN_GA(.(T23, .(T24, T25)), T14) → SPLIT17_IN_GGAA(T24, T25, X52, X51)
SPLIT17_IN_GGAA(T36, T37, .(T36, X81), X82) → U2_GGAA(T36, T37, X81, X82, split21_in_gaa(T37, X82, X81))
SPLIT17_IN_GGAA(T36, T37, .(T36, X81), X82) → SPLIT21_IN_GAA(T37, X82, X81)
SPLIT21_IN_GAA(.(T42, T43), .(T42, X99), X100) → U1_GAA(T42, T43, X99, X100, split21_in_gaa(T43, X100, X99))
SPLIT21_IN_GAA(.(T42, T43), .(T42, X99), X100) → SPLIT21_IN_GAA(T43, X100, X99)
MERGESORT1_IN_GA(.(T23, .(T24, T25)), T14) → U19_GA(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U19_GA(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U20_GA(T23, T24, T25, T14, mergesort1_in_ga(.(T23, T29), X23))
U19_GA(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29), X23)
U19_GA(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U21_GA(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U21_GA(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U22_GA(T23, T24, T25, T14, mergesort32_in_ga(T28, X24))
U21_GA(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → MERGESORT32_IN_GA(T28, X24)
MERGESORT32_IN_GA(.(T61, .(T62, T63)), X137) → U3_GA(T61, T62, T63, X137, split17_in_ggaa(T61, .(T62, T63), X133, X134))
MERGESORT32_IN_GA(.(T61, .(T62, T63)), X137) → SPLIT17_IN_GGAA(T61, .(T62, T63), X133, X134)
MERGESORT32_IN_GA(.(T61, .(T62, T63)), X137) → U4_GA(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U5_GA(T61, T62, T63, X137, mergesort32_in_ga(T67, X135))
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → MERGESORT32_IN_GA(T67, X135)
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U6_GA(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U6_GA(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U7_GA(T61, T62, T63, X137, mergesort32_in_ga(T68, X136))
U6_GA(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → MERGESORT32_IN_GA(T68, X136)
U6_GA(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U8_GA(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U8_GA(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U9_GA(T61, T62, T63, X137, merge33_in_gga(T72, T73, X137))
U8_GA(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → MERGE33_IN_GGA(T72, T73, X137)
MERGE33_IN_GGA(.(T108, T109), .(T110, T111), .(T108, T113)) → U10_GGA(T108, T109, T110, T111, T113, le68_in_gg(T108, T110))
MERGE33_IN_GGA(.(T108, T109), .(T110, T111), .(T108, T113)) → LE68_IN_GG(T108, T110)
LE68_IN_GG(s(T126), s(T127)) → U16_GG(T126, T127, le68_in_gg(T126, T127))
LE68_IN_GG(s(T126), s(T127)) → LE68_IN_GG(T126, T127)
MERGE33_IN_GGA(.(T108, T109), .(T110, T111), .(T108, T113)) → U11_GGA(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
U11_GGA(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U12_GGA(T108, T109, T110, T111, T113, merge33_in_gga(T109, .(T110, T111), T113))
U11_GGA(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → MERGE33_IN_GGA(T109, .(T110, T111), T113)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152), .(T151, T154)) → U13_GGA(T149, T150, T151, T152, T154, gt85_in_gg(T149, T151))
MERGE33_IN_GGA(.(T149, T150), .(T151, T152), .(T151, T154)) → GT85_IN_GG(T149, T151)
GT85_IN_GG(s(T167), s(T168)) → U17_GG(T167, T168, gt85_in_gg(T167, T168))
GT85_IN_GG(s(T167), s(T168)) → GT85_IN_GG(T167, T168)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152), .(T151, T154)) → U14_GGA(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
U14_GGA(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U15_GGA(T149, T150, T151, T152, T154, merge33_in_gga(.(T149, T150), T152, T154))
U14_GGA(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152, T154)
U21_GA(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U23_GA(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
U23_GA(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U24_GA(T23, T24, T25, T14, merge33_in_gga(T46, T49, T14))
U23_GA(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → MERGE33_IN_GGA(T46, T49, T14)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
mergesortc1_in_ga([], []) → mergesortc1_out_ga([], [])
mergesortc1_in_ga(.(T4, []), .(T4, [])) → mergesortc1_out_ga(.(T4, []), .(T4, []))
mergesortc1_in_ga(.(T23, .(T24, T25)), T14) → U27_ga(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U27_ga(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U28_ga(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U28_ga(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U29_ga(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
U29_ga(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U30_ga(T23, T24, T25, T14, mergec33_in_gga(T46, T49, T14))
U30_ga(T23, T24, T25, T14, mergec33_out_gga(T46, T49, T14)) → mergesortc1_out_ga(.(T23, .(T24, T25)), T14)

The argument filtering Pi contains the following mapping:
mergesort1_in_ga(x1, x2)  =  mergesort1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
split17_in_ggaa(x1, x2, x3, x4)  =  split17_in_ggaa(x1, x2)
split21_in_gaa(x1, x2, x3)  =  split21_in_gaa(x1)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc1_in_ga(x1, x2)  =  mergesortc1_in_ga(x1)
mergesortc1_out_ga(x1, x2)  =  mergesortc1_out_ga(x1, x2)
U27_ga(x1, x2, x3, x4, x5)  =  U27_ga(x1, x2, x3, x5)
U28_ga(x1, x2, x3, x4, x5, x6)  =  U28_ga(x1, x2, x3, x5, x6)
U29_ga(x1, x2, x3, x4, x5, x6)  =  U29_ga(x1, x2, x3, x5, x6)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
U30_ga(x1, x2, x3, x4, x5)  =  U30_ga(x1, x2, x3, x5)
mergesort32_in_ga(x1, x2)  =  mergesort32_in_ga(x1)
merge33_in_gga(x1, x2, x3)  =  merge33_in_gga(x1, x2)
le68_in_gg(x1, x2)  =  le68_in_gg(x1, x2)
gt85_in_gg(x1, x2)  =  gt85_in_gg(x1, x2)
MERGESORT1_IN_GA(x1, x2)  =  MERGESORT1_IN_GA(x1)
U18_GA(x1, x2, x3, x4, x5)  =  U18_GA(x1, x2, x3, x5)
SPLIT17_IN_GGAA(x1, x2, x3, x4)  =  SPLIT17_IN_GGAA(x1, x2)
U2_GGAA(x1, x2, x3, x4, x5)  =  U2_GGAA(x1, x2, x5)
SPLIT21_IN_GAA(x1, x2, x3)  =  SPLIT21_IN_GAA(x1)
U1_GAA(x1, x2, x3, x4, x5)  =  U1_GAA(x1, x2, x5)
U19_GA(x1, x2, x3, x4, x5)  =  U19_GA(x1, x2, x3, x5)
U20_GA(x1, x2, x3, x4, x5)  =  U20_GA(x1, x2, x3, x5)
U21_GA(x1, x2, x3, x4, x5, x6)  =  U21_GA(x1, x2, x3, x5, x6)
U22_GA(x1, x2, x3, x4, x5)  =  U22_GA(x1, x2, x3, x5)
MERGESORT32_IN_GA(x1, x2)  =  MERGESORT32_IN_GA(x1)
U3_GA(x1, x2, x3, x4, x5)  =  U3_GA(x1, x2, x3, x5)
U4_GA(x1, x2, x3, x4, x5)  =  U4_GA(x1, x2, x3, x5)
U5_GA(x1, x2, x3, x4, x5)  =  U5_GA(x1, x2, x3, x5)
U6_GA(x1, x2, x3, x4, x5, x6)  =  U6_GA(x1, x2, x3, x5, x6)
U7_GA(x1, x2, x3, x4, x5)  =  U7_GA(x1, x2, x3, x5)
U8_GA(x1, x2, x3, x4, x5, x6)  =  U8_GA(x1, x2, x3, x5, x6)
U9_GA(x1, x2, x3, x4, x5)  =  U9_GA(x1, x2, x3, x5)
MERGE33_IN_GGA(x1, x2, x3)  =  MERGE33_IN_GGA(x1, x2)
U10_GGA(x1, x2, x3, x4, x5, x6)  =  U10_GGA(x1, x2, x3, x4, x6)
LE68_IN_GG(x1, x2)  =  LE68_IN_GG(x1, x2)
U16_GG(x1, x2, x3)  =  U16_GG(x1, x2, x3)
U11_GGA(x1, x2, x3, x4, x5, x6)  =  U11_GGA(x1, x2, x3, x4, x6)
U12_GGA(x1, x2, x3, x4, x5, x6)  =  U12_GGA(x1, x2, x3, x4, x6)
U13_GGA(x1, x2, x3, x4, x5, x6)  =  U13_GGA(x1, x2, x3, x4, x6)
GT85_IN_GG(x1, x2)  =  GT85_IN_GG(x1, x2)
U17_GG(x1, x2, x3)  =  U17_GG(x1, x2, x3)
U14_GGA(x1, x2, x3, x4, x5, x6)  =  U14_GGA(x1, x2, x3, x4, x6)
U15_GGA(x1, x2, x3, x4, x5, x6)  =  U15_GGA(x1, x2, x3, x4, x6)
U23_GA(x1, x2, x3, x4, x5, x6)  =  U23_GA(x1, x2, x3, x5, x6)
U24_GA(x1, x2, x3, x4, x5)  =  U24_GA(x1, x2, x3, x5)

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

Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES

(4) Obligation:

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

MERGESORT1_IN_GA(.(T23, .(T24, T25)), T14) → U18_GA(T23, T24, T25, T14, split17_in_ggaa(T24, T25, X52, X51))
MERGESORT1_IN_GA(.(T23, .(T24, T25)), T14) → SPLIT17_IN_GGAA(T24, T25, X52, X51)
SPLIT17_IN_GGAA(T36, T37, .(T36, X81), X82) → U2_GGAA(T36, T37, X81, X82, split21_in_gaa(T37, X82, X81))
SPLIT17_IN_GGAA(T36, T37, .(T36, X81), X82) → SPLIT21_IN_GAA(T37, X82, X81)
SPLIT21_IN_GAA(.(T42, T43), .(T42, X99), X100) → U1_GAA(T42, T43, X99, X100, split21_in_gaa(T43, X100, X99))
SPLIT21_IN_GAA(.(T42, T43), .(T42, X99), X100) → SPLIT21_IN_GAA(T43, X100, X99)
MERGESORT1_IN_GA(.(T23, .(T24, T25)), T14) → U19_GA(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U19_GA(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U20_GA(T23, T24, T25, T14, mergesort1_in_ga(.(T23, T29), X23))
U19_GA(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29), X23)
U19_GA(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U21_GA(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U21_GA(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U22_GA(T23, T24, T25, T14, mergesort32_in_ga(T28, X24))
U21_GA(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → MERGESORT32_IN_GA(T28, X24)
MERGESORT32_IN_GA(.(T61, .(T62, T63)), X137) → U3_GA(T61, T62, T63, X137, split17_in_ggaa(T61, .(T62, T63), X133, X134))
MERGESORT32_IN_GA(.(T61, .(T62, T63)), X137) → SPLIT17_IN_GGAA(T61, .(T62, T63), X133, X134)
MERGESORT32_IN_GA(.(T61, .(T62, T63)), X137) → U4_GA(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U5_GA(T61, T62, T63, X137, mergesort32_in_ga(T67, X135))
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → MERGESORT32_IN_GA(T67, X135)
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U6_GA(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U6_GA(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U7_GA(T61, T62, T63, X137, mergesort32_in_ga(T68, X136))
U6_GA(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → MERGESORT32_IN_GA(T68, X136)
U6_GA(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U8_GA(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U8_GA(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U9_GA(T61, T62, T63, X137, merge33_in_gga(T72, T73, X137))
U8_GA(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → MERGE33_IN_GGA(T72, T73, X137)
MERGE33_IN_GGA(.(T108, T109), .(T110, T111), .(T108, T113)) → U10_GGA(T108, T109, T110, T111, T113, le68_in_gg(T108, T110))
MERGE33_IN_GGA(.(T108, T109), .(T110, T111), .(T108, T113)) → LE68_IN_GG(T108, T110)
LE68_IN_GG(s(T126), s(T127)) → U16_GG(T126, T127, le68_in_gg(T126, T127))
LE68_IN_GG(s(T126), s(T127)) → LE68_IN_GG(T126, T127)
MERGE33_IN_GGA(.(T108, T109), .(T110, T111), .(T108, T113)) → U11_GGA(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
U11_GGA(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U12_GGA(T108, T109, T110, T111, T113, merge33_in_gga(T109, .(T110, T111), T113))
U11_GGA(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → MERGE33_IN_GGA(T109, .(T110, T111), T113)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152), .(T151, T154)) → U13_GGA(T149, T150, T151, T152, T154, gt85_in_gg(T149, T151))
MERGE33_IN_GGA(.(T149, T150), .(T151, T152), .(T151, T154)) → GT85_IN_GG(T149, T151)
GT85_IN_GG(s(T167), s(T168)) → U17_GG(T167, T168, gt85_in_gg(T167, T168))
GT85_IN_GG(s(T167), s(T168)) → GT85_IN_GG(T167, T168)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152), .(T151, T154)) → U14_GGA(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
U14_GGA(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U15_GGA(T149, T150, T151, T152, T154, merge33_in_gga(.(T149, T150), T152, T154))
U14_GGA(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152, T154)
U21_GA(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U23_GA(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
U23_GA(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U24_GA(T23, T24, T25, T14, merge33_in_gga(T46, T49, T14))
U23_GA(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → MERGE33_IN_GGA(T46, T49, T14)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
mergesortc1_in_ga([], []) → mergesortc1_out_ga([], [])
mergesortc1_in_ga(.(T4, []), .(T4, [])) → mergesortc1_out_ga(.(T4, []), .(T4, []))
mergesortc1_in_ga(.(T23, .(T24, T25)), T14) → U27_ga(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U27_ga(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U28_ga(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U28_ga(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U29_ga(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
U29_ga(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U30_ga(T23, T24, T25, T14, mergec33_in_gga(T46, T49, T14))
U30_ga(T23, T24, T25, T14, mergec33_out_gga(T46, T49, T14)) → mergesortc1_out_ga(.(T23, .(T24, T25)), T14)

The argument filtering Pi contains the following mapping:
mergesort1_in_ga(x1, x2)  =  mergesort1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
split17_in_ggaa(x1, x2, x3, x4)  =  split17_in_ggaa(x1, x2)
split21_in_gaa(x1, x2, x3)  =  split21_in_gaa(x1)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc1_in_ga(x1, x2)  =  mergesortc1_in_ga(x1)
mergesortc1_out_ga(x1, x2)  =  mergesortc1_out_ga(x1, x2)
U27_ga(x1, x2, x3, x4, x5)  =  U27_ga(x1, x2, x3, x5)
U28_ga(x1, x2, x3, x4, x5, x6)  =  U28_ga(x1, x2, x3, x5, x6)
U29_ga(x1, x2, x3, x4, x5, x6)  =  U29_ga(x1, x2, x3, x5, x6)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
U30_ga(x1, x2, x3, x4, x5)  =  U30_ga(x1, x2, x3, x5)
mergesort32_in_ga(x1, x2)  =  mergesort32_in_ga(x1)
merge33_in_gga(x1, x2, x3)  =  merge33_in_gga(x1, x2)
le68_in_gg(x1, x2)  =  le68_in_gg(x1, x2)
gt85_in_gg(x1, x2)  =  gt85_in_gg(x1, x2)
MERGESORT1_IN_GA(x1, x2)  =  MERGESORT1_IN_GA(x1)
U18_GA(x1, x2, x3, x4, x5)  =  U18_GA(x1, x2, x3, x5)
SPLIT17_IN_GGAA(x1, x2, x3, x4)  =  SPLIT17_IN_GGAA(x1, x2)
U2_GGAA(x1, x2, x3, x4, x5)  =  U2_GGAA(x1, x2, x5)
SPLIT21_IN_GAA(x1, x2, x3)  =  SPLIT21_IN_GAA(x1)
U1_GAA(x1, x2, x3, x4, x5)  =  U1_GAA(x1, x2, x5)
U19_GA(x1, x2, x3, x4, x5)  =  U19_GA(x1, x2, x3, x5)
U20_GA(x1, x2, x3, x4, x5)  =  U20_GA(x1, x2, x3, x5)
U21_GA(x1, x2, x3, x4, x5, x6)  =  U21_GA(x1, x2, x3, x5, x6)
U22_GA(x1, x2, x3, x4, x5)  =  U22_GA(x1, x2, x3, x5)
MERGESORT32_IN_GA(x1, x2)  =  MERGESORT32_IN_GA(x1)
U3_GA(x1, x2, x3, x4, x5)  =  U3_GA(x1, x2, x3, x5)
U4_GA(x1, x2, x3, x4, x5)  =  U4_GA(x1, x2, x3, x5)
U5_GA(x1, x2, x3, x4, x5)  =  U5_GA(x1, x2, x3, x5)
U6_GA(x1, x2, x3, x4, x5, x6)  =  U6_GA(x1, x2, x3, x5, x6)
U7_GA(x1, x2, x3, x4, x5)  =  U7_GA(x1, x2, x3, x5)
U8_GA(x1, x2, x3, x4, x5, x6)  =  U8_GA(x1, x2, x3, x5, x6)
U9_GA(x1, x2, x3, x4, x5)  =  U9_GA(x1, x2, x3, x5)
MERGE33_IN_GGA(x1, x2, x3)  =  MERGE33_IN_GGA(x1, x2)
U10_GGA(x1, x2, x3, x4, x5, x6)  =  U10_GGA(x1, x2, x3, x4, x6)
LE68_IN_GG(x1, x2)  =  LE68_IN_GG(x1, x2)
U16_GG(x1, x2, x3)  =  U16_GG(x1, x2, x3)
U11_GGA(x1, x2, x3, x4, x5, x6)  =  U11_GGA(x1, x2, x3, x4, x6)
U12_GGA(x1, x2, x3, x4, x5, x6)  =  U12_GGA(x1, x2, x3, x4, x6)
U13_GGA(x1, x2, x3, x4, x5, x6)  =  U13_GGA(x1, x2, x3, x4, x6)
GT85_IN_GG(x1, x2)  =  GT85_IN_GG(x1, x2)
U17_GG(x1, x2, x3)  =  U17_GG(x1, x2, x3)
U14_GGA(x1, x2, x3, x4, x5, x6)  =  U14_GGA(x1, x2, x3, x4, x6)
U15_GGA(x1, x2, x3, x4, x5, x6)  =  U15_GGA(x1, x2, x3, x4, x6)
U23_GA(x1, x2, x3, x4, x5, x6)  =  U23_GA(x1, x2, x3, x5, x6)
U24_GA(x1, x2, x3, x4, x5)  =  U24_GA(x1, x2, x3, x5)

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

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 6 SCCs with 27 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

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

GT85_IN_GG(s(T167), s(T168)) → GT85_IN_GG(T167, T168)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
mergesortc1_in_ga([], []) → mergesortc1_out_ga([], [])
mergesortc1_in_ga(.(T4, []), .(T4, [])) → mergesortc1_out_ga(.(T4, []), .(T4, []))
mergesortc1_in_ga(.(T23, .(T24, T25)), T14) → U27_ga(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U27_ga(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U28_ga(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U28_ga(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U29_ga(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
U29_ga(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U30_ga(T23, T24, T25, T14, mergec33_in_gga(T46, T49, T14))
U30_ga(T23, T24, T25, T14, mergec33_out_gga(T46, T49, T14)) → mergesortc1_out_ga(.(T23, .(T24, T25)), T14)

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc1_in_ga(x1, x2)  =  mergesortc1_in_ga(x1)
mergesortc1_out_ga(x1, x2)  =  mergesortc1_out_ga(x1, x2)
U27_ga(x1, x2, x3, x4, x5)  =  U27_ga(x1, x2, x3, x5)
U28_ga(x1, x2, x3, x4, x5, x6)  =  U28_ga(x1, x2, x3, x5, x6)
U29_ga(x1, x2, x3, x4, x5, x6)  =  U29_ga(x1, x2, x3, x5, x6)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
U30_ga(x1, x2, x3, x4, x5)  =  U30_ga(x1, x2, x3, x5)
GT85_IN_GG(x1, x2)  =  GT85_IN_GG(x1, x2)

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

(8) UsableRulesProof (EQUIVALENT transformation)

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

(9) Obligation:

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

GT85_IN_GG(s(T167), s(T168)) → GT85_IN_GG(T167, T168)

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

(10) PiDPToQDPProof (EQUIVALENT transformation)

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

(11) Obligation:

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

GT85_IN_GG(s(T167), s(T168)) → GT85_IN_GG(T167, T168)

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

(12) 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:

  • GT85_IN_GG(s(T167), s(T168)) → GT85_IN_GG(T167, T168)
    The graph contains the following edges 1 > 1, 2 > 2

(13) YES

(14) Obligation:

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

LE68_IN_GG(s(T126), s(T127)) → LE68_IN_GG(T126, T127)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
mergesortc1_in_ga([], []) → mergesortc1_out_ga([], [])
mergesortc1_in_ga(.(T4, []), .(T4, [])) → mergesortc1_out_ga(.(T4, []), .(T4, []))
mergesortc1_in_ga(.(T23, .(T24, T25)), T14) → U27_ga(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U27_ga(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U28_ga(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U28_ga(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U29_ga(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
U29_ga(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U30_ga(T23, T24, T25, T14, mergec33_in_gga(T46, T49, T14))
U30_ga(T23, T24, T25, T14, mergec33_out_gga(T46, T49, T14)) → mergesortc1_out_ga(.(T23, .(T24, T25)), T14)

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc1_in_ga(x1, x2)  =  mergesortc1_in_ga(x1)
mergesortc1_out_ga(x1, x2)  =  mergesortc1_out_ga(x1, x2)
U27_ga(x1, x2, x3, x4, x5)  =  U27_ga(x1, x2, x3, x5)
U28_ga(x1, x2, x3, x4, x5, x6)  =  U28_ga(x1, x2, x3, x5, x6)
U29_ga(x1, x2, x3, x4, x5, x6)  =  U29_ga(x1, x2, x3, x5, x6)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
U30_ga(x1, x2, x3, x4, x5)  =  U30_ga(x1, x2, x3, x5)
LE68_IN_GG(x1, x2)  =  LE68_IN_GG(x1, x2)

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

(15) UsableRulesProof (EQUIVALENT transformation)

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

(16) Obligation:

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

LE68_IN_GG(s(T126), s(T127)) → LE68_IN_GG(T126, T127)

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

(17) PiDPToQDPProof (EQUIVALENT transformation)

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

(18) Obligation:

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

LE68_IN_GG(s(T126), s(T127)) → LE68_IN_GG(T126, T127)

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

(19) 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:

  • LE68_IN_GG(s(T126), s(T127)) → LE68_IN_GG(T126, T127)
    The graph contains the following edges 1 > 1, 2 > 2

(20) YES

(21) Obligation:

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

MERGE33_IN_GGA(.(T108, T109), .(T110, T111), .(T108, T113)) → U11_GGA(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
U11_GGA(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → MERGE33_IN_GGA(T109, .(T110, T111), T113)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152), .(T151, T154)) → U14_GGA(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
U14_GGA(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152, T154)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
mergesortc1_in_ga([], []) → mergesortc1_out_ga([], [])
mergesortc1_in_ga(.(T4, []), .(T4, [])) → mergesortc1_out_ga(.(T4, []), .(T4, []))
mergesortc1_in_ga(.(T23, .(T24, T25)), T14) → U27_ga(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U27_ga(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U28_ga(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U28_ga(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U29_ga(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
U29_ga(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U30_ga(T23, T24, T25, T14, mergec33_in_gga(T46, T49, T14))
U30_ga(T23, T24, T25, T14, mergec33_out_gga(T46, T49, T14)) → mergesortc1_out_ga(.(T23, .(T24, T25)), T14)

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc1_in_ga(x1, x2)  =  mergesortc1_in_ga(x1)
mergesortc1_out_ga(x1, x2)  =  mergesortc1_out_ga(x1, x2)
U27_ga(x1, x2, x3, x4, x5)  =  U27_ga(x1, x2, x3, x5)
U28_ga(x1, x2, x3, x4, x5, x6)  =  U28_ga(x1, x2, x3, x5, x6)
U29_ga(x1, x2, x3, x4, x5, x6)  =  U29_ga(x1, x2, x3, x5, x6)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
U30_ga(x1, x2, x3, x4, x5)  =  U30_ga(x1, x2, x3, x5)
MERGE33_IN_GGA(x1, x2, x3)  =  MERGE33_IN_GGA(x1, x2)
U11_GGA(x1, x2, x3, x4, x5, x6)  =  U11_GGA(x1, x2, x3, x4, x6)
U14_GGA(x1, x2, x3, x4, x5, x6)  =  U14_GGA(x1, x2, x3, x4, x6)

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

(22) UsableRulesProof (EQUIVALENT transformation)

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

(23) Obligation:

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

MERGE33_IN_GGA(.(T108, T109), .(T110, T111), .(T108, T113)) → U11_GGA(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
U11_GGA(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → MERGE33_IN_GGA(T109, .(T110, T111), T113)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152), .(T151, T154)) → U14_GGA(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
U14_GGA(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152, T154)

The TRS R consists of the following rules:

lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
MERGE33_IN_GGA(x1, x2, x3)  =  MERGE33_IN_GGA(x1, x2)
U11_GGA(x1, x2, x3, x4, x5, x6)  =  U11_GGA(x1, x2, x3, x4, x6)
U14_GGA(x1, x2, x3, x4, x5, x6)  =  U14_GGA(x1, x2, x3, x4, x6)

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

(24) PiDPToQDPProof (SOUND transformation)

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

(25) Obligation:

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

MERGE33_IN_GGA(.(T108, T109), .(T110, T111)) → U11_GGA(T108, T109, T110, T111, lec68_in_gg(T108, T110))
U11_GGA(T108, T109, T110, T111, lec68_out_gg(T108, T110)) → MERGE33_IN_GGA(T109, .(T110, T111))
MERGE33_IN_GGA(.(T149, T150), .(T151, T152)) → U14_GGA(T149, T150, T151, T152, gtc85_in_gg(T149, T151))
U14_GGA(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152)

The TRS R consists of the following rules:

lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

lec68_in_gg(x0, x1)
gtc85_in_gg(x0, x1)
U40_gg(x0, x1, x2)
U41_gg(x0, x1, x2)

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

(26) MRRProof (EQUIVALENT transformation)

By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
Strictly oriented dependency pairs:

MERGE33_IN_GGA(.(T108, T109), .(T110, T111)) → U11_GGA(T108, T109, T110, T111, lec68_in_gg(T108, T110))

Strictly oriented rules of the TRS R:

gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)

Used ordering: Polynomial interpretation [POLO]:

POL(.(x1, x2)) = 1 + 2·x1 + x2   
POL(0) = 0   
POL(MERGE33_IN_GGA(x1, x2)) = 2·x1 + 2·x2   
POL(U11_GGA(x1, x2, x3, x4, x5)) = 2 + x1 + 2·x2 + 2·x3 + 2·x4 + x5   
POL(U14_GGA(x1, x2, x3, x4, x5)) = 2 + 2·x1 + 2·x2 + 2·x3 + 2·x4 + 2·x5   
POL(U40_gg(x1, x2, x3)) = 2·x1 + 2·x2 + x3   
POL(U41_gg(x1, x2, x3)) = x1 + x2 + x3   
POL(gtc85_in_gg(x1, x2)) = 1 + x1 + x2   
POL(gtc85_out_gg(x1, x2)) = x1 + x2   
POL(lec68_in_gg(x1, x2)) = 2·x1 + 2·x2   
POL(lec68_out_gg(x1, x2)) = 2·x1 + 2·x2   
POL(s(x1)) = 2·x1   

(27) Obligation:

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

U11_GGA(T108, T109, T110, T111, lec68_out_gg(T108, T110)) → MERGE33_IN_GGA(T109, .(T110, T111))
MERGE33_IN_GGA(.(T149, T150), .(T151, T152)) → U14_GGA(T149, T150, T151, T152, gtc85_in_gg(T149, T151))
U14_GGA(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152)

The TRS R consists of the following rules:

lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

lec68_in_gg(x0, x1)
gtc85_in_gg(x0, x1)
U40_gg(x0, x1, x2)
U41_gg(x0, x1, x2)

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

(28) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.

(29) Obligation:

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

U14_GGA(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152)) → U14_GGA(T149, T150, T151, T152, gtc85_in_gg(T149, T151))

The TRS R consists of the following rules:

lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

lec68_in_gg(x0, x1)
gtc85_in_gg(x0, x1)
U40_gg(x0, x1, x2)
U41_gg(x0, x1, x2)

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

(30) UsableRulesProof (EQUIVALENT transformation)

As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.

(31) Obligation:

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

U14_GGA(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152)) → U14_GGA(T149, T150, T151, T152, gtc85_in_gg(T149, T151))

The TRS R consists of the following rules:

gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

lec68_in_gg(x0, x1)
gtc85_in_gg(x0, x1)
U40_gg(x0, x1, x2)
U41_gg(x0, x1, x2)

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

(32) QReductionProof (EQUIVALENT transformation)

We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

lec68_in_gg(x0, x1)
U40_gg(x0, x1, x2)

(33) Obligation:

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

U14_GGA(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152)
MERGE33_IN_GGA(.(T149, T150), .(T151, T152)) → U14_GGA(T149, T150, T151, T152, gtc85_in_gg(T149, T151))

The TRS R consists of the following rules:

gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

gtc85_in_gg(x0, x1)
U41_gg(x0, x1, x2)

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

(34) 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:

  • MERGE33_IN_GGA(.(T149, T150), .(T151, T152)) → U14_GGA(T149, T150, T151, T152, gtc85_in_gg(T149, T151))
    The graph contains the following edges 1 > 1, 1 > 2, 2 > 3, 2 > 4

  • U14_GGA(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → MERGE33_IN_GGA(.(T149, T150), T152)
    The graph contains the following edges 4 >= 2

(35) YES

(36) Obligation:

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

SPLIT21_IN_GAA(.(T42, T43), .(T42, X99), X100) → SPLIT21_IN_GAA(T43, X100, X99)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
mergesortc1_in_ga([], []) → mergesortc1_out_ga([], [])
mergesortc1_in_ga(.(T4, []), .(T4, [])) → mergesortc1_out_ga(.(T4, []), .(T4, []))
mergesortc1_in_ga(.(T23, .(T24, T25)), T14) → U27_ga(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U27_ga(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U28_ga(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U28_ga(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U29_ga(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
U29_ga(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U30_ga(T23, T24, T25, T14, mergec33_in_gga(T46, T49, T14))
U30_ga(T23, T24, T25, T14, mergec33_out_gga(T46, T49, T14)) → mergesortc1_out_ga(.(T23, .(T24, T25)), T14)

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc1_in_ga(x1, x2)  =  mergesortc1_in_ga(x1)
mergesortc1_out_ga(x1, x2)  =  mergesortc1_out_ga(x1, x2)
U27_ga(x1, x2, x3, x4, x5)  =  U27_ga(x1, x2, x3, x5)
U28_ga(x1, x2, x3, x4, x5, x6)  =  U28_ga(x1, x2, x3, x5, x6)
U29_ga(x1, x2, x3, x4, x5, x6)  =  U29_ga(x1, x2, x3, x5, x6)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
U30_ga(x1, x2, x3, x4, x5)  =  U30_ga(x1, x2, x3, x5)
SPLIT21_IN_GAA(x1, x2, x3)  =  SPLIT21_IN_GAA(x1)

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

(37) UsableRulesProof (EQUIVALENT transformation)

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

(38) Obligation:

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

SPLIT21_IN_GAA(.(T42, T43), .(T42, X99), X100) → SPLIT21_IN_GAA(T43, X100, X99)

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

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

(39) PiDPToQDPProof (SOUND transformation)

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

(40) Obligation:

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

SPLIT21_IN_GAA(.(T42, T43)) → SPLIT21_IN_GAA(T43)

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

(41) 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:

  • SPLIT21_IN_GAA(.(T42, T43)) → SPLIT21_IN_GAA(T43)
    The graph contains the following edges 1 > 1

(42) YES

(43) Obligation:

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

MERGESORT32_IN_GA(.(T61, .(T62, T63)), X137) → U4_GA(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → MERGESORT32_IN_GA(T67, X135)
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U6_GA(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U6_GA(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → MERGESORT32_IN_GA(T68, X136)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
mergesortc1_in_ga([], []) → mergesortc1_out_ga([], [])
mergesortc1_in_ga(.(T4, []), .(T4, [])) → mergesortc1_out_ga(.(T4, []), .(T4, []))
mergesortc1_in_ga(.(T23, .(T24, T25)), T14) → U27_ga(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U27_ga(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U28_ga(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U28_ga(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U29_ga(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
U29_ga(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U30_ga(T23, T24, T25, T14, mergec33_in_gga(T46, T49, T14))
U30_ga(T23, T24, T25, T14, mergec33_out_gga(T46, T49, T14)) → mergesortc1_out_ga(.(T23, .(T24, T25)), T14)

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc1_in_ga(x1, x2)  =  mergesortc1_in_ga(x1)
mergesortc1_out_ga(x1, x2)  =  mergesortc1_out_ga(x1, x2)
U27_ga(x1, x2, x3, x4, x5)  =  U27_ga(x1, x2, x3, x5)
U28_ga(x1, x2, x3, x4, x5, x6)  =  U28_ga(x1, x2, x3, x5, x6)
U29_ga(x1, x2, x3, x4, x5, x6)  =  U29_ga(x1, x2, x3, x5, x6)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
U30_ga(x1, x2, x3, x4, x5)  =  U30_ga(x1, x2, x3, x5)
MERGESORT32_IN_GA(x1, x2)  =  MERGESORT32_IN_GA(x1)
U4_GA(x1, x2, x3, x4, x5)  =  U4_GA(x1, x2, x3, x5)
U6_GA(x1, x2, x3, x4, x5, x6)  =  U6_GA(x1, x2, x3, x5, x6)

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

(44) UsableRulesProof (EQUIVALENT transformation)

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

(45) Obligation:

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

MERGESORT32_IN_GA(.(T61, .(T62, T63)), X137) → U4_GA(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → MERGESORT32_IN_GA(T67, X135)
U4_GA(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U6_GA(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U6_GA(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → MERGESORT32_IN_GA(T68, X136)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
MERGESORT32_IN_GA(x1, x2)  =  MERGESORT32_IN_GA(x1)
U4_GA(x1, x2, x3, x4, x5)  =  U4_GA(x1, x2, x3, x5)
U6_GA(x1, x2, x3, x4, x5, x6)  =  U6_GA(x1, x2, x3, x5, x6)

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

(46) PiDPToQDPProof (SOUND transformation)

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

(47) Obligation:

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

MERGESORT32_IN_GA(.(T61, .(T62, T63))) → U4_GA(T61, T62, T63, splitc17_in_ggaa(T61, .(T62, T63)))
U4_GA(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → MERGESORT32_IN_GA(T67)
U4_GA(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U6_GA(T61, T62, T63, T68, mergesortc32_in_ga(T67))
U6_GA(T61, T62, T63, T68, mergesortc32_out_ga(T67, T72)) → MERGESORT32_IN_GA(T68)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37) → U31_ggaa(T36, T37, splitc21_in_gaa(T37))
mergesortc32_in_ga([]) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63))) → U32_ga(T61, T62, T63, splitc17_in_ggaa(T61, .(T62, T63)))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U32_ga(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, T68, mergesortc32_in_ga(T67))
splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U33_ga(T61, T62, T63, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, T72, mergesortc32_in_ga(T68))
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U34_ga(T61, T62, T63, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, mergec33_in_gga(T72, T73))
U35_ga(T61, T62, T63, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
mergec33_in_gga([], T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, []) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111)) → U36_gga(T108, T109, T110, T111, lec68_in_gg(T108, T110))
mergec33_in_gga(.(T149, T150), .(T151, T152)) → U38_gga(T149, T150, T151, T152, gtc85_in_gg(T149, T151))
U36_gga(T108, T109, T110, T111, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, mergec33_in_gga(T109, .(T110, T111)))
U38_gga(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, mergec33_in_gga(.(T149, T150), T152))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U37_gga(T108, T109, T110, T111, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U39_gga(T149, T150, T151, T152, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

splitc17_in_ggaa(x0, x1)
mergesortc32_in_ga(x0)
U31_ggaa(x0, x1, x2)
U32_ga(x0, x1, x2, x3)
splitc21_in_gaa(x0)
U33_ga(x0, x1, x2, x3, x4)
U26_gaa(x0, x1, x2)
U34_ga(x0, x1, x2, x3, x4)
U35_ga(x0, x1, x2, x3)
mergec33_in_gga(x0, x1)
U36_gga(x0, x1, x2, x3, x4)
U38_gga(x0, x1, x2, x3, x4)
lec68_in_gg(x0, x1)
U37_gga(x0, x1, x2, x3, x4)
gtc85_in_gg(x0, x1)
U39_gga(x0, x1, x2, x3, x4)
U40_gg(x0, x1, x2)
U41_gg(x0, x1, x2)

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

(48) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule MERGESORT32_IN_GA(.(T61, .(T62, T63))) → U4_GA(T61, T62, T63, splitc17_in_ggaa(T61, .(T62, T63))) at position [3] we obtained the following new rules [LPAR04]:

MERGESORT32_IN_GA(.(T61, .(T62, T63))) → U4_GA(T61, T62, T63, U31_ggaa(T61, .(T62, T63), splitc21_in_gaa(.(T62, T63))))

(49) Obligation:

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

U4_GA(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → MERGESORT32_IN_GA(T67)
U4_GA(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U6_GA(T61, T62, T63, T68, mergesortc32_in_ga(T67))
U6_GA(T61, T62, T63, T68, mergesortc32_out_ga(T67, T72)) → MERGESORT32_IN_GA(T68)
MERGESORT32_IN_GA(.(T61, .(T62, T63))) → U4_GA(T61, T62, T63, U31_ggaa(T61, .(T62, T63), splitc21_in_gaa(.(T62, T63))))

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37) → U31_ggaa(T36, T37, splitc21_in_gaa(T37))
mergesortc32_in_ga([]) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63))) → U32_ga(T61, T62, T63, splitc17_in_ggaa(T61, .(T62, T63)))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U32_ga(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, T68, mergesortc32_in_ga(T67))
splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U33_ga(T61, T62, T63, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, T72, mergesortc32_in_ga(T68))
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U34_ga(T61, T62, T63, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, mergec33_in_gga(T72, T73))
U35_ga(T61, T62, T63, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
mergec33_in_gga([], T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, []) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111)) → U36_gga(T108, T109, T110, T111, lec68_in_gg(T108, T110))
mergec33_in_gga(.(T149, T150), .(T151, T152)) → U38_gga(T149, T150, T151, T152, gtc85_in_gg(T149, T151))
U36_gga(T108, T109, T110, T111, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, mergec33_in_gga(T109, .(T110, T111)))
U38_gga(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, mergec33_in_gga(.(T149, T150), T152))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U37_gga(T108, T109, T110, T111, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U39_gga(T149, T150, T151, T152, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

splitc17_in_ggaa(x0, x1)
mergesortc32_in_ga(x0)
U31_ggaa(x0, x1, x2)
U32_ga(x0, x1, x2, x3)
splitc21_in_gaa(x0)
U33_ga(x0, x1, x2, x3, x4)
U26_gaa(x0, x1, x2)
U34_ga(x0, x1, x2, x3, x4)
U35_ga(x0, x1, x2, x3)
mergec33_in_gga(x0, x1)
U36_gga(x0, x1, x2, x3, x4)
U38_gga(x0, x1, x2, x3, x4)
lec68_in_gg(x0, x1)
U37_gga(x0, x1, x2, x3, x4)
gtc85_in_gg(x0, x1)
U39_gga(x0, x1, x2, x3, x4)
U40_gg(x0, x1, x2)
U41_gg(x0, x1, x2)

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

(50) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule MERGESORT32_IN_GA(.(T61, .(T62, T63))) → U4_GA(T61, T62, T63, U31_ggaa(T61, .(T62, T63), splitc21_in_gaa(.(T62, T63)))) at position [3,2] we obtained the following new rules [LPAR04]:

MERGESORT32_IN_GA(.(T61, .(T62, T63))) → U4_GA(T61, T62, T63, U31_ggaa(T61, .(T62, T63), U26_gaa(T62, T63, splitc21_in_gaa(T63))))

(51) Obligation:

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

U4_GA(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → MERGESORT32_IN_GA(T67)
U4_GA(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U6_GA(T61, T62, T63, T68, mergesortc32_in_ga(T67))
U6_GA(T61, T62, T63, T68, mergesortc32_out_ga(T67, T72)) → MERGESORT32_IN_GA(T68)
MERGESORT32_IN_GA(.(T61, .(T62, T63))) → U4_GA(T61, T62, T63, U31_ggaa(T61, .(T62, T63), U26_gaa(T62, T63, splitc21_in_gaa(T63))))

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37) → U31_ggaa(T36, T37, splitc21_in_gaa(T37))
mergesortc32_in_ga([]) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63))) → U32_ga(T61, T62, T63, splitc17_in_ggaa(T61, .(T62, T63)))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U32_ga(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, T68, mergesortc32_in_ga(T67))
splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U33_ga(T61, T62, T63, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, T72, mergesortc32_in_ga(T68))
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U34_ga(T61, T62, T63, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, mergec33_in_gga(T72, T73))
U35_ga(T61, T62, T63, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
mergec33_in_gga([], T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, []) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111)) → U36_gga(T108, T109, T110, T111, lec68_in_gg(T108, T110))
mergec33_in_gga(.(T149, T150), .(T151, T152)) → U38_gga(T149, T150, T151, T152, gtc85_in_gg(T149, T151))
U36_gga(T108, T109, T110, T111, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, mergec33_in_gga(T109, .(T110, T111)))
U38_gga(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, mergec33_in_gga(.(T149, T150), T152))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U37_gga(T108, T109, T110, T111, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U39_gga(T149, T150, T151, T152, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

splitc17_in_ggaa(x0, x1)
mergesortc32_in_ga(x0)
U31_ggaa(x0, x1, x2)
U32_ga(x0, x1, x2, x3)
splitc21_in_gaa(x0)
U33_ga(x0, x1, x2, x3, x4)
U26_gaa(x0, x1, x2)
U34_ga(x0, x1, x2, x3, x4)
U35_ga(x0, x1, x2, x3)
mergec33_in_gga(x0, x1)
U36_gga(x0, x1, x2, x3, x4)
U38_gga(x0, x1, x2, x3, x4)
lec68_in_gg(x0, x1)
U37_gga(x0, x1, x2, x3, x4)
gtc85_in_gg(x0, x1)
U39_gga(x0, x1, x2, x3, x4)
U40_gg(x0, x1, x2)
U41_gg(x0, x1, x2)

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

(52) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


MERGESORT32_IN_GA(.(T61, .(T62, T63))) → U4_GA(T61, T62, T63, U31_ggaa(T61, .(T62, T63), U26_gaa(T62, T63, splitc21_in_gaa(T63))))
The remaining pairs can at least be oriented weakly.
Used ordering: Matrix interpretation [MATRO]:

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

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

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

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

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

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

POL(mergesortc32_out_ga(x1, x2)) =
/1\
\1/
+
/00\
\00/
·x1 +
/00\
\10/
·x2

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

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

POL(splitc21_in_gaa(x1)) =
/0\
\0/
+
/10\
\10/
·x1

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

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

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

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

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

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

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

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

POL(mergec33_out_gga(x1, x2, x3)) =
/0\
\0/
+
/00\
\11/
·x1 +
/00\
\00/
·x2 +
/00\
\00/
·x3

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

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

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

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

POL(s(x1)) =
/0\
\0/
+
/11\
\11/
·x1

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

POL(0) =
/0\
\0/

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

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

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

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

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

The following usable rules [FROCOS05] were oriented:

splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)

(53) Obligation:

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

U4_GA(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → MERGESORT32_IN_GA(T67)
U4_GA(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U6_GA(T61, T62, T63, T68, mergesortc32_in_ga(T67))
U6_GA(T61, T62, T63, T68, mergesortc32_out_ga(T67, T72)) → MERGESORT32_IN_GA(T68)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37) → U31_ggaa(T36, T37, splitc21_in_gaa(T37))
mergesortc32_in_ga([]) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63))) → U32_ga(T61, T62, T63, splitc17_in_ggaa(T61, .(T62, T63)))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U32_ga(T61, T62, T63, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, T68, mergesortc32_in_ga(T67))
splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U33_ga(T61, T62, T63, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, T72, mergesortc32_in_ga(T68))
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U34_ga(T61, T62, T63, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, mergec33_in_gga(T72, T73))
U35_ga(T61, T62, T63, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
mergec33_in_gga([], T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, []) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111)) → U36_gga(T108, T109, T110, T111, lec68_in_gg(T108, T110))
mergec33_in_gga(.(T149, T150), .(T151, T152)) → U38_gga(T149, T150, T151, T152, gtc85_in_gg(T149, T151))
U36_gga(T108, T109, T110, T111, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, mergec33_in_gga(T109, .(T110, T111)))
U38_gga(T149, T150, T151, T152, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, mergec33_in_gga(.(T149, T150), T152))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U37_gga(T108, T109, T110, T111, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U39_gga(T149, T150, T151, T152, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))

The set Q consists of the following terms:

splitc17_in_ggaa(x0, x1)
mergesortc32_in_ga(x0)
U31_ggaa(x0, x1, x2)
U32_ga(x0, x1, x2, x3)
splitc21_in_gaa(x0)
U33_ga(x0, x1, x2, x3, x4)
U26_gaa(x0, x1, x2)
U34_ga(x0, x1, x2, x3, x4)
U35_ga(x0, x1, x2, x3)
mergec33_in_gga(x0, x1)
U36_gga(x0, x1, x2, x3, x4)
U38_gga(x0, x1, x2, x3, x4)
lec68_in_gg(x0, x1)
U37_gga(x0, x1, x2, x3, x4)
gtc85_in_gg(x0, x1)
U39_gga(x0, x1, x2, x3, x4)
U40_gg(x0, x1, x2)
U41_gg(x0, x1, x2)

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

(54) DependencyGraphProof (EQUIVALENT transformation)

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

(55) TRUE

(56) Obligation:

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

MERGESORT1_IN_GA(.(T23, .(T24, T25)), T14) → U19_GA(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U19_GA(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29), X23)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
mergesortc1_in_ga([], []) → mergesortc1_out_ga([], [])
mergesortc1_in_ga(.(T4, []), .(T4, [])) → mergesortc1_out_ga(.(T4, []), .(T4, []))
mergesortc1_in_ga(.(T23, .(T24, T25)), T14) → U27_ga(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U27_ga(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → U28_ga(T23, T24, T25, T14, T28, mergesortc1_in_ga(.(T23, T29), T46))
U28_ga(T23, T24, T25, T14, T28, mergesortc1_out_ga(.(T23, T29), T46)) → U29_ga(T23, T24, T25, T14, T46, mergesortc32_in_ga(T28, T49))
mergesortc32_in_ga([], []) → mergesortc32_out_ga([], [])
mergesortc32_in_ga(.(T54, []), .(T54, [])) → mergesortc32_out_ga(.(T54, []), .(T54, []))
mergesortc32_in_ga(.(T61, .(T62, T63)), X137) → U32_ga(T61, T62, T63, X137, splitc17_in_ggaa(T61, .(T62, T63), T67, T68))
U32_ga(T61, T62, T63, X137, splitc17_out_ggaa(T61, .(T62, T63), T67, T68)) → U33_ga(T61, T62, T63, X137, T68, mergesortc32_in_ga(T67, T72))
U33_ga(T61, T62, T63, X137, T68, mergesortc32_out_ga(T67, T72)) → U34_ga(T61, T62, T63, X137, T72, mergesortc32_in_ga(T68, T73))
U34_ga(T61, T62, T63, X137, T72, mergesortc32_out_ga(T68, T73)) → U35_ga(T61, T62, T63, X137, mergec33_in_gga(T72, T73, X137))
mergec33_in_gga([], T82, T82) → mergec33_out_gga([], T82, T82)
mergec33_in_gga(T87, [], T87) → mergec33_out_gga(T87, [], T87)
mergec33_in_gga(.(T108, T109), .(T110, T111), .(T108, T113)) → U36_gga(T108, T109, T110, T111, T113, lec68_in_gg(T108, T110))
lec68_in_gg(s(T126), s(T127)) → U40_gg(T126, T127, lec68_in_gg(T126, T127))
lec68_in_gg(0, s(T134)) → lec68_out_gg(0, s(T134))
lec68_in_gg(0, 0) → lec68_out_gg(0, 0)
U40_gg(T126, T127, lec68_out_gg(T126, T127)) → lec68_out_gg(s(T126), s(T127))
U36_gga(T108, T109, T110, T111, T113, lec68_out_gg(T108, T110)) → U37_gga(T108, T109, T110, T111, T113, mergec33_in_gga(T109, .(T110, T111), T113))
mergec33_in_gga(.(T149, T150), .(T151, T152), .(T151, T154)) → U38_gga(T149, T150, T151, T152, T154, gtc85_in_gg(T149, T151))
gtc85_in_gg(s(T167), s(T168)) → U41_gg(T167, T168, gtc85_in_gg(T167, T168))
gtc85_in_gg(s(T173), 0) → gtc85_out_gg(s(T173), 0)
U41_gg(T167, T168, gtc85_out_gg(T167, T168)) → gtc85_out_gg(s(T167), s(T168))
U38_gga(T149, T150, T151, T152, T154, gtc85_out_gg(T149, T151)) → U39_gga(T149, T150, T151, T152, T154, mergec33_in_gga(.(T149, T150), T152, T154))
U39_gga(T149, T150, T151, T152, T154, mergec33_out_gga(.(T149, T150), T152, T154)) → mergec33_out_gga(.(T149, T150), .(T151, T152), .(T151, T154))
U37_gga(T108, T109, T110, T111, T113, mergec33_out_gga(T109, .(T110, T111), T113)) → mergec33_out_gga(.(T108, T109), .(T110, T111), .(T108, T113))
U35_ga(T61, T62, T63, X137, mergec33_out_gga(T72, T73, X137)) → mergesortc32_out_ga(.(T61, .(T62, T63)), X137)
U29_ga(T23, T24, T25, T14, T46, mergesortc32_out_ga(T28, T49)) → U30_ga(T23, T24, T25, T14, mergec33_in_gga(T46, T49, T14))
U30_ga(T23, T24, T25, T14, mergec33_out_gga(T46, T49, T14)) → mergesortc1_out_ga(.(T23, .(T24, T25)), T14)

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
mergesortc1_in_ga(x1, x2)  =  mergesortc1_in_ga(x1)
mergesortc1_out_ga(x1, x2)  =  mergesortc1_out_ga(x1, x2)
U27_ga(x1, x2, x3, x4, x5)  =  U27_ga(x1, x2, x3, x5)
U28_ga(x1, x2, x3, x4, x5, x6)  =  U28_ga(x1, x2, x3, x5, x6)
U29_ga(x1, x2, x3, x4, x5, x6)  =  U29_ga(x1, x2, x3, x5, x6)
mergesortc32_in_ga(x1, x2)  =  mergesortc32_in_ga(x1)
mergesortc32_out_ga(x1, x2)  =  mergesortc32_out_ga(x1, x2)
U32_ga(x1, x2, x3, x4, x5)  =  U32_ga(x1, x2, x3, x5)
U33_ga(x1, x2, x3, x4, x5, x6)  =  U33_ga(x1, x2, x3, x5, x6)
U34_ga(x1, x2, x3, x4, x5, x6)  =  U34_ga(x1, x2, x3, x5, x6)
U35_ga(x1, x2, x3, x4, x5)  =  U35_ga(x1, x2, x3, x5)
mergec33_in_gga(x1, x2, x3)  =  mergec33_in_gga(x1, x2)
mergec33_out_gga(x1, x2, x3)  =  mergec33_out_gga(x1, x2, x3)
U36_gga(x1, x2, x3, x4, x5, x6)  =  U36_gga(x1, x2, x3, x4, x6)
lec68_in_gg(x1, x2)  =  lec68_in_gg(x1, x2)
s(x1)  =  s(x1)
U40_gg(x1, x2, x3)  =  U40_gg(x1, x2, x3)
0  =  0
lec68_out_gg(x1, x2)  =  lec68_out_gg(x1, x2)
U37_gga(x1, x2, x3, x4, x5, x6)  =  U37_gga(x1, x2, x3, x4, x6)
U38_gga(x1, x2, x3, x4, x5, x6)  =  U38_gga(x1, x2, x3, x4, x6)
gtc85_in_gg(x1, x2)  =  gtc85_in_gg(x1, x2)
U41_gg(x1, x2, x3)  =  U41_gg(x1, x2, x3)
gtc85_out_gg(x1, x2)  =  gtc85_out_gg(x1, x2)
U39_gga(x1, x2, x3, x4, x5, x6)  =  U39_gga(x1, x2, x3, x4, x6)
U30_ga(x1, x2, x3, x4, x5)  =  U30_ga(x1, x2, x3, x5)
MERGESORT1_IN_GA(x1, x2)  =  MERGESORT1_IN_GA(x1)
U19_GA(x1, x2, x3, x4, x5)  =  U19_GA(x1, x2, x3, x5)

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

(57) UsableRulesProof (EQUIVALENT transformation)

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

(58) Obligation:

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

MERGESORT1_IN_GA(.(T23, .(T24, T25)), T14) → U19_GA(T23, T24, T25, T14, splitc17_in_ggaa(T24, T25, T28, T29))
U19_GA(T23, T24, T25, T14, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29), X23)

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37, .(T36, X81), X82) → U31_ggaa(T36, T37, X81, X82, splitc21_in_gaa(T37, X82, X81))
U31_ggaa(T36, T37, X81, X82, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
splitc21_in_gaa([], [], []) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43), .(T42, X99), X100) → U26_gaa(T42, T43, X99, X100, splitc21_in_gaa(T43, X100, X99))
U26_gaa(T42, T43, X99, X100, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
splitc17_in_ggaa(x1, x2, x3, x4)  =  splitc17_in_ggaa(x1, x2)
U31_ggaa(x1, x2, x3, x4, x5)  =  U31_ggaa(x1, x2, x5)
splitc21_in_gaa(x1, x2, x3)  =  splitc21_in_gaa(x1)
[]  =  []
splitc21_out_gaa(x1, x2, x3)  =  splitc21_out_gaa(x1, x2, x3)
U26_gaa(x1, x2, x3, x4, x5)  =  U26_gaa(x1, x2, x5)
splitc17_out_ggaa(x1, x2, x3, x4)  =  splitc17_out_ggaa(x1, x2, x3, x4)
MERGESORT1_IN_GA(x1, x2)  =  MERGESORT1_IN_GA(x1)
U19_GA(x1, x2, x3, x4, x5)  =  U19_GA(x1, x2, x3, x5)

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

(59) PiDPToQDPProof (SOUND transformation)

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

(60) Obligation:

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

MERGESORT1_IN_GA(.(T23, .(T24, T25))) → U19_GA(T23, T24, T25, splitc17_in_ggaa(T24, T25))
U19_GA(T23, T24, T25, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29))

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37) → U31_ggaa(T36, T37, splitc21_in_gaa(T37))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)

The set Q consists of the following terms:

splitc17_in_ggaa(x0, x1)
U31_ggaa(x0, x1, x2)
splitc21_in_gaa(x0)
U26_gaa(x0, x1, x2)

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

(61) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule MERGESORT1_IN_GA(.(T23, .(T24, T25))) → U19_GA(T23, T24, T25, splitc17_in_ggaa(T24, T25)) at position [3] we obtained the following new rules [LPAR04]:

MERGESORT1_IN_GA(.(T23, .(T24, T25))) → U19_GA(T23, T24, T25, U31_ggaa(T24, T25, splitc21_in_gaa(T25)))

(62) Obligation:

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

U19_GA(T23, T24, T25, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29))
MERGESORT1_IN_GA(.(T23, .(T24, T25))) → U19_GA(T23, T24, T25, U31_ggaa(T24, T25, splitc21_in_gaa(T25)))

The TRS R consists of the following rules:

splitc17_in_ggaa(T36, T37) → U31_ggaa(T36, T37, splitc21_in_gaa(T37))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)

The set Q consists of the following terms:

splitc17_in_ggaa(x0, x1)
U31_ggaa(x0, x1, x2)
splitc21_in_gaa(x0)
U26_gaa(x0, x1, x2)

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

(63) UsableRulesProof (EQUIVALENT transformation)

As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.

(64) Obligation:

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

U19_GA(T23, T24, T25, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29))
MERGESORT1_IN_GA(.(T23, .(T24, T25))) → U19_GA(T23, T24, T25, U31_ggaa(T24, T25, splitc21_in_gaa(T25)))

The TRS R consists of the following rules:

splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)

The set Q consists of the following terms:

splitc17_in_ggaa(x0, x1)
U31_ggaa(x0, x1, x2)
splitc21_in_gaa(x0)
U26_gaa(x0, x1, x2)

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

(65) QReductionProof (EQUIVALENT transformation)

We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

splitc17_in_ggaa(x0, x1)

(66) Obligation:

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

U19_GA(T23, T24, T25, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29))
MERGESORT1_IN_GA(.(T23, .(T24, T25))) → U19_GA(T23, T24, T25, U31_ggaa(T24, T25, splitc21_in_gaa(T25)))

The TRS R consists of the following rules:

splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)

The set Q consists of the following terms:

U31_ggaa(x0, x1, x2)
splitc21_in_gaa(x0)
U26_gaa(x0, x1, x2)

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

(67) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


U19_GA(T23, T24, T25, splitc17_out_ggaa(T24, T25, T28, T29)) → MERGESORT1_IN_GA(.(T23, T29))
MERGESORT1_IN_GA(.(T23, .(T24, T25))) → U19_GA(T23, T24, T25, U31_ggaa(T24, T25, splitc21_in_gaa(T25)))
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( U19_GA(x1, ..., x4) ) = max{0, 2x1 + x2 + 2x4 - 2}


POL( U31_ggaa(x1, ..., x3) ) = 2x3 + 2


POL( splitc21_in_gaa(x1) ) = 2x1


POL( [] ) = 0


POL( splitc21_out_gaa(x1, ..., x3) ) = x2 + x3


POL( .(x1, x2) ) = x1 + 2x2 + 1


POL( U26_gaa(x1, ..., x3) ) = x1 + 2x3 + 1


POL( splitc17_out_ggaa(x1, ..., x4) ) = 2x4 + 2


POL( MERGESORT1_IN_GA(x1) ) = max{0, 2x1 - 1}



The following usable rules [FROCOS05] were oriented:

splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)

(68) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

splitc21_in_gaa([]) → splitc21_out_gaa([], [], [])
splitc21_in_gaa(.(T42, T43)) → U26_gaa(T42, T43, splitc21_in_gaa(T43))
U31_ggaa(T36, T37, splitc21_out_gaa(T37, X82, X81)) → splitc17_out_ggaa(T36, T37, .(T36, X81), X82)
U26_gaa(T42, T43, splitc21_out_gaa(T43, X100, X99)) → splitc21_out_gaa(.(T42, T43), .(T42, X99), X100)

The set Q consists of the following terms:

U31_ggaa(x0, x1, x2)
splitc21_in_gaa(x0)
U26_gaa(x0, x1, x2)

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

(69) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(70) YES