Left Termination proof of /tmp/tmpGbm2LD/mergesort-oi.pl

Left Termination of the query pattern mergesort_in_2(a, g) w.r.t. the given Prolog program could not be shown:

0 Prolog

↳1 PredefinedPredicateTransformerProof (⇐)

↳2 Prolog

↳3 BuiltinConflictTransformerProof (⇐)

↳4 Prolog

↳5 PrologToDTProblemTransformerProof (⇐)

↳6 TRIPLES

↳7 UndefinedPredicateInTriplesTransformerProof (⇐)

↳8 TRIPLES

↳9 TriplesToPiDPProof (⇐)

↳10 PiDP

↳11 DependencyGraphProof (⇔)

↳12 AND

    ↳13 PiDP

        ↳14 UsableRulesProof (⇔)

        ↳15 PiDP

        ↳16 PiDPToQDPProof (⇐)

        ↳17 QDP

        ↳18 QDPSizeChangeProof (⇔)

        ↳19 YES

    ↳20 PiDP

        ↳21 UsableRulesProof (⇔)

        ↳22 PiDP

        ↳23 PiDPToQDPProof (⇐)

        ↳24 QDP

        ↳25 QDPSizeChangeProof (⇔)

        ↳26 YES

    ↳27 PiDP

        ↳28 UsableRulesProof (⇔)

        ↳29 PiDP

        ↳30 PiDPToQDPProof (⇐)

        ↳31 QDP

        ↳32 QDPSizeChangeProof (⇔)

        ↳33 YES

    ↳34 PiDP

        ↳35 UsableRulesProof (⇔)

        ↳36 PiDP

        ↳37 PiDPToQDPProof (⇐)

        ↳38 QDP

        ↳39 Rewriting (⇔)

        ↳40 QDP

        ↳41 Rewriting (⇔)

        ↳42 QDP

        ↳43 Rewriting (⇔)

        ↳44 QDP

        ↳45 Rewriting (⇔)

        ↳46 QDP

        ↳47 QDPOrderProof (⇔)

        ↳48 QDP

        ↳49 DependencyGraphProof (⇔)

        ↳50 TRUE

    ↳51 PiDP

        ↳52 UsableRulesProof (⇔)

        ↳53 PiDP

        ↳54 PiDPToQDPProof (⇐)

        ↳55 QDP

        ↳56 NonTerminationProof (⇔)

        ↳57 NO

(0) Obligation:

Clauses:

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

Queries:

mergesort(a,g).

(1) PredefinedPredicateTransformerProof (SOUND transformation)

Added definitions of predefined predicates [PROLOG].

(2) Obligation:

(3) BuiltinConflictTransformerProof (SOUND transformation)

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

(4) Obligation:

Clauses:

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

Queries:

mergesort(a,g).

(5) PrologToDTProblemTransformerProof (SOUND transformation)

Built DT problem from termination graph.

digraph dp_graph {
node [outthreshold=100, inthreshold=100];
1 [label="1: mergesort(T1, T2)\n\nT2 is ground", fontsize=16, style=filled, fillcolor=lightyellow, color=red];
2 [label="2: mergesort(T1, T2), SCOPE: 1, CLAUSE: 0 | mergesort(T1, T2), SCOPE: 1, CLAUSE: 1 | mergesort(T1, T2), SCOPE: 1, CLAUSE: 2\n\nT2 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
3 [label="3: true | mergesort(T1, []), SCOPE: 1, CLAUSE: 1 | mergesort(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
4 [label="4: mergesort(T1, T2), SCOPE: 1, CLAUSE: 1 | mergesort(T1, T2), SCOPE: 1, CLAUSE: 2\n\nT2 is ground\nmergesort(T1, T2) !=? mergesort([], [])", fontsize=16, style=filled, fillcolor=lightyellow];
5 [label="5: mergesort(T1, []), SCOPE: 1, CLAUSE: 1 | mergesort(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
6 [label="6: mergesort(T1, []), SCOPE: 1, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
7 [label="7: ','(split(.(T10, .(T11, T12)), X10, X11), ','(mergesort(X10, X12), ','(mergesort(X11, X13), merge(X12, X13, []))))\n\nX10 is free\nX11 is free; \nX12 is free; \nX13 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
8 [label="8: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
9 [label="9: ','(split(.(T10, .(T11, T12)), X10, X11), ','(mergesort(X10, X12), ','(mergesort(X11, X13), merge(X12, X13, [])))), SCOPE: 2, CLAUSE: 3 | ','(split(.(T10, .(T11, T12)), X10, X11), ','(mergesort(X10, X12), ','(mergesort(X11, X13), merge(X12, X13, [])))), SCOPE: 2, CLAUSE: 4\n\nX10 is free\nX11 is free; \nX12 is free; \nX13 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
10 [label="10: ','(split(.(T10, .(T11, T12)), X10, X11), ','(mergesort(X10, X12), ','(mergesort(X11, X13), merge(X12, X13, [])))), SCOPE: 2, CLAUSE: 4\n\nX10 is free\nX11 is free; \nX12 is free; \nX13 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
11 [label="11: ','(split(.(T27, T28), X41, X40), ','(mergesort(.(T29, X40), X12), ','(mergesort(X41, X13), merge(X12, X13, []))))\n\nX12 is free\nX13 is free; \nX40 is free; \nX41 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
12 [label="12: split(.(T27, T28), X41, X40)\n\nX40 is free\nX41 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
13 [label="13: ','(mergesort(.(T34, T33), X12), ','(mergesort(T32, X13), merge(X12, X13, [])))\n\nX12 is free\nX13 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
14 [label="14: split(.(T27, T28), X41, X40), SCOPE: 3, CLAUSE: 3 | split(.(T27, T28), X41, X40), SCOPE: 3, CLAUSE: 4\n\nX40 is free\nX41 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
15 [label="15: split(.(T27, T28), X41, X40), SCOPE: 3, CLAUSE: 4\n\nX40 is free\nX41 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
16 [label="16: split(T44, X71, X70)\n\nX70 is free\nX71 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
17 [label="17: split(T44, X71, X70), SCOPE: 4, CLAUSE: 3 | split(T44, X71, X70), SCOPE: 4, CLAUSE: 4\n\nX70 is free\nX71 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
18 [label="18: split(T44, X71, X70), SCOPE: 4, CLAUSE: 3\n\nX70 is free\nX71 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
19 [label="19: split(T44, X71, X70), SCOPE: 4, CLAUSE: 4\n\nX70 is free\nX71 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
20 [label="20: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
21 [label="21: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
22 [label="22: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
23 [label="23: split(T51, X89, X88)\n\nX88 is free\nX89 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
24 [label="24: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
25 [label="25: mergesort(.(T34, T33), X12)\n\nX12 is free", fontsize=16, style=filled, fillcolor=lightyellow];
26 [label="26: ','(mergesort(T55, X13), merge(T54, X13, []))\n\nX13 is free", fontsize=16, style=filled, fillcolor=lightyellow];
27 [label="27: mergesort(.(T34, T33), X12), SCOPE: 5, CLAUSE: 0 | mergesort(.(T34, T33), X12), SCOPE: 5, CLAUSE: 1 | mergesort(.(T34, T33), X12), SCOPE: 5, CLAUSE: 2\n\nX12 is free", fontsize=16, style=filled, fillcolor=lightyellow];
28 [label="28: mergesort(.(T34, T33), X12), SCOPE: 5, CLAUSE: 1 | mergesort(.(T34, T33), X12), SCOPE: 5, CLAUSE: 2\n\nX12 is free", fontsize=16, style=filled, fillcolor=lightyellow];
29 [label="29: mergesort(.(T34, T33), X12), SCOPE: 5, CLAUSE: 1\n\nX12 is free", fontsize=16, style=filled, fillcolor=lightyellow];
30 [label="30: mergesort(.(T34, T33), X12), SCOPE: 5, CLAUSE: 2\n\nX12 is free", fontsize=16, style=filled, fillcolor=lightyellow];
31 [label="31: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
32 [label="32: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
33 [label="33: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
34 [label="34: ','(split(.(T72, .(T73, T74)), X122, X123), ','(mergesort(X122, X124), ','(mergesort(X123, X125), merge(X124, X125, X126))))\n\nX126 is free\nX122 is free; \nX123 is free; \nX124 is free; \nX125 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
35 [label="35: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
36 [label="36: split(.(T72, .(T73, T74)), X122, X123)\n\nX122 is free\nX123 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
37 [label="37: ','(mergesort(T78, X124), ','(mergesort(T79, X125), merge(X124, X125, X126)))\n\nX126 is free\nX124 is free; \nX125 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
38 [label="38: mergesort(T78, X124)\n\nX124 is free", fontsize=16, style=filled, fillcolor=lightyellow];
39 [label="39: ','(mergesort(T84, X125), merge(T83, X125, X126))\n\nX126 is free\nX125 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
40 [label="40: mergesort(T78, X124), SCOPE: 6, CLAUSE: 0 | mergesort(T78, X124), SCOPE: 6, CLAUSE: 1 | mergesort(T78, X124), SCOPE: 6, CLAUSE: 2\n\nX124 is free", fontsize=16, style=filled, fillcolor=lightyellow];
41 [label="41: mergesort(T78, X124), SCOPE: 6, CLAUSE: 0\n\nX124 is free", fontsize=16, style=filled, fillcolor=lightyellow];
42 [label="42: mergesort(T78, X124), SCOPE: 6, CLAUSE: 1 | mergesort(T78, X124), SCOPE: 6, CLAUSE: 2\n\nX124 is free", fontsize=16, style=filled, fillcolor=lightyellow];
43 [label="43: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
44 [label="44: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
45 [label="45: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
46 [label="46: mergesort(T78, X124), SCOPE: 6, CLAUSE: 1\n\nX124 is free", fontsize=16, style=filled, fillcolor=lightyellow];
47 [label="47: mergesort(T78, X124), SCOPE: 6, CLAUSE: 2\n\nX124 is free", fontsize=16, style=filled, fillcolor=lightyellow];
48 [label="48: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
49 [label="49: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
50 [label="50: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
51 [label="51: ','(split(.(T99, .(T100, T101)), X167, X168), ','(mergesort(X167, X169), ','(mergesort(X168, X170), merge(X169, X170, X171))))\n\nX171 is free\nX167 is free; \nX168 is free; \nX169 is free; \nX170 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
52 [label="52: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
53 [label="53: mergesort(T84, X125)\n\nX125 is free", fontsize=16, style=filled, fillcolor=lightyellow];
54 [label="54: merge(T106, T105, X126)\n\nX126 is free", fontsize=16, style=filled, fillcolor=lightyellow];
55 [label="55: merge(T106, T105, X126), SCOPE: 7, CLAUSE: 5 | merge(T106, T105, X126), SCOPE: 7, CLAUSE: 6 | merge(T106, T105, X126), SCOPE: 7, CLAUSE: 7\n\nX126 is free", fontsize=16, style=filled, fillcolor=lightyellow];
56 [label="56: merge(T106, T105, X126), SCOPE: 7, CLAUSE: 5\n\nX126 is free", fontsize=16, style=filled, fillcolor=lightyellow];
57 [label="57: merge(T106, T105, X126), SCOPE: 7, CLAUSE: 6 | merge(T106, T105, X126), SCOPE: 7, CLAUSE: 7\n\nX126 is free", fontsize=16, style=filled, fillcolor=lightyellow];
58 [label="58: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
59 [label="59: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
60 [label="60: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
61 [label="61: merge(T106, T105, X126), SCOPE: 7, CLAUSE: 6\n\nX126 is free", fontsize=16, style=filled, fillcolor=lightyellow];
62 [label="62: merge(T106, T105, X126), SCOPE: 7, CLAUSE: 7\n\nX126 is free", fontsize=16, style=filled, fillcolor=lightyellow];
63 [label="63: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
64 [label="64: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
65 [label="65: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
66 [label="66: ','(user_defined_=(T131, T132), merge(.(T131, T134), T133, X213))\n\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
67 [label="67: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
68 [label="68: ','(user_defined_=(T131, T132), merge(.(T131, T134), T133, X213)), SCOPE: 8, CLAUSE: 8\n\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
69 [label="69: merge(.(T143, T144), T142, X213)\n\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
70 [label="70: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
71 [label="71: mergesort(T55, X13)\n\nX13 is free", fontsize=16, style=filled, fillcolor=lightyellow];
72 [label="72: merge(T150, T149, [])\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
73 [label="73: merge(T150, T149, []), SCOPE: 9, CLAUSE: 5 | merge(T150, T149, []), SCOPE: 9, CLAUSE: 6 | merge(T150, T149, []), SCOPE: 9, CLAUSE: 7\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
74 [label="74: merge(T150, T149, []), SCOPE: 9, CLAUSE: 5\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
75 [label="75: merge(T150, T149, []), SCOPE: 9, CLAUSE: 6 | merge(T150, T149, []), SCOPE: 9, CLAUSE: 7\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
76 [label="76: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
77 [label="77: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
78 [label="78: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
79 [label="79: merge(T150, T149, []), SCOPE: 9, CLAUSE: 6\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
80 [label="80: merge(T150, T149, []), SCOPE: 9, CLAUSE: 7\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
81 [label="81: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
82 [label="82: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
83 [label="83: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
84 [label="84: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
85 [label="85: true | mergesort(T1, .(T168, [])), SCOPE: 1, CLAUSE: 2\n\nT168 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
86 [label="86: mergesort(T1, T2), SCOPE: 1, CLAUSE: 2\n\nT2 is ground\nmergesort(T1, T2) !=? mergesort([], [])\nmergesort(T1, T2) !=? mergesort(.(X251, []), .(X251, []))", fontsize=16, style=filled, fillcolor=lightyellow];
87 [label="87: mergesort(T1, .(T168, [])), SCOPE: 1, CLAUSE: 2\n\nT168 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
88 [label="88: ','(split(.(T177, .(T178, T179)), X261, X262), ','(mergesort(X261, X263), ','(mergesort(X262, X264), merge(X263, X264, .(T176, [])))))\n\nT176 is ground\nX261 is free; \nX262 is free; \nX263 is free; \nX264 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
89 [label="89: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
90 [label="90: ','(split(.(T177, .(T178, T179)), X261, X262), ','(mergesort(X261, X263), ','(mergesort(X262, X264), merge(X263, X264, .(T176, []))))), SCOPE: 10, CLAUSE: 3 | ','(split(.(T177, .(T178, T179)), X261, X262), ','(mergesort(X261, X263), ','(mergesort(X262, X264), merge(X263, X264, .(T176, []))))), SCOPE: 10, CLAUSE: 4\n\nT176 is ground\nX261 is free; \nX262 is free; \nX263 is free; \nX264 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
91 [label="91: ','(split(.(T177, .(T178, T179)), X261, X262), ','(mergesort(X261, X263), ','(mergesort(X262, X264), merge(X263, X264, .(T176, []))))), SCOPE: 10, CLAUSE: 4\n\nT176 is ground\nX261 is free; \nX262 is free; \nX263 is free; \nX264 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
92 [label="92: ','(split(.(T194, T195), X292, X291), ','(mergesort(.(T196, X291), X263), ','(mergesort(X292, X264), merge(X263, X264, .(T176, [])))))\n\nT176 is ground\nX263 is free; \nX264 is free; \nX291 is free; \nX292 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
93 [label="93: split(.(T194, T195), X292, X291)\n\nX291 is free\nX292 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
94 [label="94: ','(mergesort(.(T201, T200), X263), ','(mergesort(T199, X264), merge(X263, X264, .(T176, []))))\n\nT176 is ground\nX263 is free; \nX264 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
95 [label="95: mergesort(.(T201, T200), X263)\n\nX263 is free", fontsize=16, style=filled, fillcolor=lightyellow];
96 [label="96: ','(mergesort(T207, X264), merge(T206, X264, .(T176, [])))\n\nT176 is ground\nX264 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
97 [label="97: mergesort(T207, X264)\n\nX264 is free", fontsize=16, style=filled, fillcolor=lightyellow];
98 [label="98: merge(T211, T210, .(T176, []))\n\nT176 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
99 [label="99: merge(T211, T210, .(T176, [])), SCOPE: 11, CLAUSE: 5 | merge(T211, T210, .(T176, [])), SCOPE: 11, CLAUSE: 6 | merge(T211, T210, .(T176, [])), SCOPE: 11, CLAUSE: 7\n\nT176 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
100 [label="100: merge(T211, T210, .(T176, [])), SCOPE: 11, CLAUSE: 5\n\nT176 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
101 [label="101: merge(T211, T210, .(T176, [])), SCOPE: 11, CLAUSE: 6 | merge(T211, T210, .(T176, [])), SCOPE: 11, CLAUSE: 7\n\nT176 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
102 [label="102: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
103 [label="103: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
104 [label="104: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
105 [label="105: merge(T211, T210, .(T176, [])), SCOPE: 11, CLAUSE: 6\n\nT176 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
106 [label="106: merge(T211, T210, .(T176, [])), SCOPE: 11, CLAUSE: 7\n\nT176 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
107 [label="107: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
108 [label="108: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
109 [label="109: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
110 [label="110: ','(user_defined_=(T244, T248), merge(.(T244, T250), T249, []))\n\nT244 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
111 [label="111: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
112 [label="112: ','(user_defined_=(T244, T248), merge(.(T244, T250), T249, [])), SCOPE: 12, CLAUSE: 8\n\nT244 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
113 [label="113: merge(.(T261, T263), T262, [])\n\nT261 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
114 [label="114: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
115 [label="115: ','(split(.(T280, .(T281, T282)), X373, X374), ','(mergesort(X373, X375), ','(mergesort(X374, X376), merge(X375, X376, T279))))\n\nT279 is ground\nX373 is free; \nX374 is free; \nX375 is free; \nX376 is free; \nmergesort(T1, T279) !=? mergesort([], [])\nmergesort(T1, T279) !=? mergesort(.(X251, []), .(X251, []))", fontsize=16, style=filled, fillcolor=lightyellow];
116 [label="116: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
117 [label="117: ','(split(.(T280, .(T281, T282)), X373, X374), ','(mergesort(X373, X375), ','(mergesort(X374, X376), merge(X375, X376, T279)))), SCOPE: 13, CLAUSE: 3 | ','(split(.(T280, .(T281, T282)), X373, X374), ','(mergesort(X373, X375), ','(mergesort(X374, X376), merge(X375, X376, T279)))), SCOPE: 13, CLAUSE: 4\n\nT279 is ground\nX373 is free; \nX374 is free; \nX375 is free; \nX376 is free; \nmergesort(T1, T279) !=? mergesort([], [])\nmergesort(T1, T279) !=? mergesort(.(X251, []), .(X251, []))", fontsize=16, style=filled, fillcolor=lightyellow];
118 [label="118: ','(split(.(T280, .(T281, T282)), X373, X374), ','(mergesort(X373, X375), ','(mergesort(X374, X376), merge(X375, X376, T279)))), SCOPE: 13, CLAUSE: 4\n\nT279 is ground\nX373 is free; \nX374 is free; \nX375 is free; \nX376 is free; \nmergesort(T1, T279) !=? mergesort([], [])\nmergesort(T1, T279) !=? mergesort(.(X251, []), .(X251, []))", fontsize=16, style=filled, fillcolor=lightyellow];
119 [label="119: ','(split(.(T297, T298), X404, X403), ','(mergesort(.(T299, X403), X375), ','(mergesort(X404, X376), merge(X375, X376, T279))))\n\nT279 is ground\nX375 is free; \nX376 is free; \nX403 is free; \nX404 is free; \nmergesort(T1, T279) !=? mergesort([], [])\nmergesort(T1, T279) !=? mergesort(.(X251, []), .(X251, []))", fontsize=16, style=filled, fillcolor=lightyellow];
120 [label="120: split(.(T297, T298), X404, X403)\n\nX403 is free\nX404 is free; ", fontsize=16, style=filled, fillcolor=lightyellow];
121 [label="121: ','(mergesort(.(T304, T303), X375), ','(mergesort(T302, X376), merge(X375, X376, T279)))\n\nT279 is ground\nX375 is free; \nX376 is free; \nmergesort(T305, T279) !=? mergesort([], [])\nmergesort(T305, T279) !=? mergesort(.(T306, []), .(T306, []))", fontsize=16, style=filled, fillcolor=lightyellow];
122 [label="122: mergesort(.(T304, T303), X375)\n\nX375 is free", fontsize=16, style=filled, fillcolor=lightyellow];
123 [label="123: ','(mergesort(T312, X376), merge(T311, X376, T279))\n\nT279 is ground\nX376 is free; \nmergesort(T313, T279) !=? mergesort([], [])\nmergesort(T313, T279) !=? mergesort(.(T314, []), .(T314, []))", fontsize=16, style=filled, fillcolor=lightyellow];
124 [label="124: mergesort(T312, X376)\n\nX376 is free", fontsize=16, style=filled, fillcolor=lightyellow];
125 [label="125: merge(T318, T317, T279)\n\nT279 is ground\nmergesort(T319, T279) !=? mergesort([], [])\nmergesort(T319, T279) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
126 [label="126: merge(T318, T317, T279), SCOPE: 14, CLAUSE: 5 | merge(T318, T317, T279), SCOPE: 14, CLAUSE: 6 | merge(T318, T317, T279), SCOPE: 14, CLAUSE: 7\n\nT279 is ground\nmergesort(T319, T279) !=? mergesort([], [])\nmergesort(T319, T279) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
127 [label="127: merge(T318, T317, T279), SCOPE: 14, CLAUSE: 5\n\nT279 is ground\nmergesort(T319, T279) !=? mergesort([], [])\nmergesort(T319, T279) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
128 [label="128: merge(T318, T317, T279), SCOPE: 14, CLAUSE: 6 | merge(T318, T317, T279), SCOPE: 14, CLAUSE: 7\n\nT279 is ground\nmergesort(T319, T279) !=? mergesort([], [])\nmergesort(T319, T279) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
129 [label="129: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
130 [label="130: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
131 [label="131: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
132 [label="132: merge(T318, T317, T279), SCOPE: 14, CLAUSE: 6\n\nT279 is ground\nmergesort(T319, T279) !=? mergesort([], [])\nmergesort(T319, T279) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
133 [label="133: merge(T318, T317, T279), SCOPE: 14, CLAUSE: 7\n\nT279 is ground\nmergesort(T319, T279) !=? mergesort([], [])\nmergesort(T319, T279) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
134 [label="134: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
135 [label="135: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
136 [label="136: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
137 [label="137: ','(user_defined_=(T343, T348), merge(.(T343, T350), T349, T347))\n\nT343 is ground\nT347 is ground\nmergesort(T319, .(T343, T347)) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
138 [label="138: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
139 [label="139: ','(user_defined_=(T343, T348), merge(.(T343, T350), T349, T347)), SCOPE: 15, CLAUSE: 8\n\nT343 is ground\nT347 is ground\nmergesort(T319, .(T343, T347)) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
140 [label="140: merge(.(T357, T359), T358, T347)\n\nT347 is ground\nT357 is ground\nmergesort(T319, .(T357, T347)) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
141 [label="141: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
142 [label="142: merge(.(T357, T359), T358, T347), SCOPE: 16, CLAUSE: 5 | merge(.(T357, T359), T358, T347), SCOPE: 16, CLAUSE: 6 | merge(.(T357, T359), T358, T347), SCOPE: 16, CLAUSE: 7\n\nT347 is ground\nT357 is ground\nmergesort(T319, .(T357, T347)) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
143 [label="143: merge(.(T357, T359), T358, T347), SCOPE: 16, CLAUSE: 6 | merge(.(T357, T359), T358, T347), SCOPE: 16, CLAUSE: 7\n\nT347 is ground\nT357 is ground\nmergesort(T319, .(T357, T347)) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
144 [label="144: merge(.(T357, T359), T358, T347), SCOPE: 16, CLAUSE: 6\n\nT347 is ground\nT357 is ground\nmergesort(T319, .(T357, T347)) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
145 [label="145: merge(.(T357, T359), T358, T347), SCOPE: 16, CLAUSE: 7\n\nT347 is ground\nT357 is ground\nmergesort(T319, .(T357, T347)) !=? mergesort(.(T320, []), .(T320, []))", fontsize=16, style=filled, fillcolor=lightyellow];
146 [label="146: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
147 [label="147: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
148 [label="148: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
149 [label="149: ','(user_defined_=(T384, T389), merge(.(T384, T391), T390, T388))\n\nT384 is ground\nT388 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
150 [label="150: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
151 [label="151: ','(user_defined_=(T384, T389), merge(.(T384, T391), T390, T388)), SCOPE: 17, CLAUSE: 8\n\nT384 is ground\nT388 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
152 [label="152: merge(.(T398, T400), T399, T388)\n\nT388 is ground\nT398 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
153 [label="153: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
154 [label="154: merge(.(T398, T400), T399, T388), SCOPE: 18, CLAUSE: 5 | merge(.(T398, T400), T399, T388), SCOPE: 18, CLAUSE: 6 | merge(.(T398, T400), T399, T388), SCOPE: 18, CLAUSE: 7\n\nT388 is ground\nT398 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
155 [label="155: merge(.(T398, T400), T399, T388), SCOPE: 18, CLAUSE: 6 | merge(.(T398, T400), T399, T388), SCOPE: 18, CLAUSE: 7\n\nT388 is ground\nT398 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
156 [label="156: merge(.(T398, T400), T399, T388), SCOPE: 18, CLAUSE: 6\n\nT388 is ground\nT398 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
157 [label="157: merge(.(T398, T400), T399, T388), SCOPE: 18, CLAUSE: 7\n\nT388 is ground\nT398 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
158 [label="158: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
159 [label="159: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
160 [label="160: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
161 [label="161: ','(user_defined_=(T425, T430), merge(.(T425, T432), T431, T429))\n\nT425 is ground\nT429 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
162 [label="162: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
163 [label="163: ','(user_defined_=(T425, T430), merge(.(T425, T432), T431, T429)), SCOPE: 19, CLAUSE: 8\n\nT425 is ground\nT429 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
164 [label="164: merge(.(T439, T441), T440, T429)\n\nT429 is ground\nT439 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
165 [label="165: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
166 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
1 -> 166 [arrowhead = none ];
166 -> 2;

167 [label="EVAL with clause\nmergesort([], []).\nand substitution\nT1 -> []\nT2 -> []", fontsize=14, style = filled, fillcolor = lightblue];
2 -> 167 [arrowhead = none ];
167 -> 3;

168 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
2 -> 168 [arrowhead = none ];
168 -> 4;

169 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
3 -> 169 [arrowhead = none ];
169 -> 5;

170 [label="EVAL with clause\nmergesort(.(X251, []), .(X251, [])).\nand substitution\nX251 -> T168\nT1 -> .(T168, [])\nT2 -> .(T168, [])", fontsize=14, style = filled, fillcolor = lightblue];
4 -> 170 [arrowhead = none ];
170 -> 85;

171 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
4 -> 171 [arrowhead = none ];
171 -> 86;

172 [label="BACKTRACK\nfor clause: mergesort(.(X, []), .(X, []))because of non-unification", fontsize=14, style = filled, fillcolor = white];
5 -> 172 [arrowhead = none ];
172 -> 6;

173 [label="EVAL with clause\nmergesort(.(X6, .(X7, X8)), X9) :- ','(split(.(X6, .(X7, X8)), X10, X11), ','(mergesort(X10, X12), ','(mergesort(X11, X13), merge(X12, X13, X9)))).\nand substitution\nX6 -> T10\nX7 -> T11\nX8 -> T12\nT1 -> .(T10, .(T11, T12))\nX9 -> []\nT7 -> T10\nT8 -> T11\nT9 -> T12", fontsize=14, style = filled, fillcolor = lightblue];
6 -> 173 [arrowhead = none ];
173 -> 7;

174 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
6 -> 174 [arrowhead = none ];
174 -> 8;

175 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
7 -> 175 [arrowhead = none ];
175 -> 9;

176 [label="BACKTRACK\nfor clause: split([], [], [])because of non-unification", fontsize=14, style = filled, fillcolor = white];
9 -> 176 [arrowhead = none ];
176 -> 10;

177 [label="ONLY EVAL with clause\nsplit(.(X36, X37), .(X36, X38), X39) :- split(X37, X39, X38).\nand substitution\nT10 -> T29\nX36 -> T29\nT11 -> T27\nT12 -> T28\nX37 -> .(T27, T28)\nX38 -> X40\nX10 -> .(T29, X40)\nX11 -> X41\nX39 -> X41\nT25 -> T27\nT26 -> T28\nT24 -> T29", fontsize=14, style = filled, fillcolor = white];
10 -> 177 [arrowhead = none ];
177 -> 11;

178 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
11 -> 178 [arrowhead = none ];
178 -> 12;

179 [label="SPLIT 2\nreplacements:\nX41 -> T32\nX40 -> T33\nT29 -> T34", fontsize=14, style = filled, fillcolor = violet];
11 -> 179 [arrowhead = none ];
179 -> 13;

180 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
12 -> 180 [arrowhead = none ];
180 -> 14;

181 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
13 -> 181 [arrowhead = none ];
181 -> 25;

182 [label="SPLIT 2\nreplacements:\nX12 -> T54\nT32 -> T55", fontsize=14, style = filled, fillcolor = violet];
13 -> 182 [arrowhead = none ];
182 -> 26;

183 [label="BACKTRACK\nfor clause: split([], [], [])because of non-unification", fontsize=14, style = filled, fillcolor = white];
14 -> 183 [arrowhead = none ];
183 -> 15;

184 [label="ONLY EVAL with clause\nsplit(.(X66, X67), .(X66, X68), X69) :- split(X67, X69, X68).\nand substitution\nT27 -> T42\nX66 -> T42\nT28 -> T44\nX67 -> T44\nX68 -> X70\nX41 -> .(T42, X70)\nX40 -> X71\nX69 -> X71\nT43 -> T44", fontsize=14, style = filled, fillcolor = white];
15 -> 184 [arrowhead = none ];
184 -> 16;

185 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
16 -> 185 [arrowhead = none ];
185 -> 17;

186 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
17 -> 186 [arrowhead = none ];
186 -> 18;

187 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
17 -> 187 [arrowhead = none ];
187 -> 19;

188 [label="EVAL with clause\nsplit([], [], []).\nand substitution\nT44 -> []\nX71 -> []\nX70 -> []", fontsize=14, style = filled, fillcolor = lightblue];
18 -> 188 [arrowhead = none ];
188 -> 20;

189 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
18 -> 189 [arrowhead = none ];
189 -> 21;

190 [label="EVAL with clause\nsplit(.(X84, X85), .(X84, X86), X87) :- split(X85, X87, X86).\nand substitution\nX84 -> T49\nX85 -> T51\nT44 -> .(T49, T51)\nX86 -> X88\nX71 -> .(T49, X88)\nX70 -> X89\nX87 -> X89\nT50 -> T51", fontsize=14, style = filled, fillcolor = lightblue];
19 -> 190 [arrowhead = none ];
190 -> 23;

191 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
19 -> 191 [arrowhead = none ];
191 -> 24;

192 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
20 -> 192 [arrowhead = none ];
192 -> 22;

193 [label="INSTANCE with matching:\nT44 -> T51\nX71 -> X89\nX70 -> X88", fontsize=14, style = filled, fillcolor = lightgrey];
23 -> 193 [arrowhead = none , style=dashed];
193 -> 16[style=dashed];

194 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
25 -> 194 [arrowhead = none ];
194 -> 27;

195 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
26 -> 195 [arrowhead = none ];
195 -> 71;

196 [label="SPLIT 2\nreplacements:\nX13 -> T149\nT54 -> T150", fontsize=14, style = filled, fillcolor = violet];
26 -> 196 [arrowhead = none ];
196 -> 72;

197 [label="BACKTRACK\nfor clause: mergesort([], [])because of non-unification", fontsize=14, style = filled, fillcolor = white];
27 -> 197 [arrowhead = none ];
197 -> 28;

198 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
28 -> 198 [arrowhead = none ];
198 -> 29;

199 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
28 -> 199 [arrowhead = none ];
199 -> 30;

200 [label="EVAL with clause\nmergesort(.(X102, []), .(X102, [])).\nand substitution\nT34 -> T62\nX102 -> T62\nT33 -> []\nX12 -> .(T62, [])", fontsize=14, style = filled, fillcolor = lightblue];
29 -> 200 [arrowhead = none ];
200 -> 31;

201 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
29 -> 201 [arrowhead = none ];
201 -> 32;

202 [label="EVAL with clause\nmergesort(.(X118, .(X119, X120)), X121) :- ','(split(.(X118, .(X119, X120)), X122, X123), ','(mergesort(X122, X124), ','(mergesort(X123, X125), merge(X124, X125, X121)))).\nand substitution\nT34 -> T72\nX118 -> T72\nX119 -> T73\nX120 -> T74\nT33 -> .(T73, T74)\nX12 -> X126\nX121 -> X126\nT69 -> T72\nT70 -> T73\nT71 -> T74", fontsize=14, style = filled, fillcolor = lightblue];
30 -> 202 [arrowhead = none ];
202 -> 34;

203 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
30 -> 203 [arrowhead = none ];
203 -> 35;

204 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
31 -> 204 [arrowhead = none ];
204 -> 33;

205 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
34 -> 205 [arrowhead = none ];
205 -> 36;

206 [label="SPLIT 2\nreplacements:\nX122 -> T78\nX123 -> T79", fontsize=14, style = filled, fillcolor = violet];
34 -> 206 [arrowhead = none ];
206 -> 37;

207 [label="INSTANCE with matching:\nT27 -> T72\nT28 -> .(T73, T74)\nX41 -> X122\nX40 -> X123", fontsize=14, style = filled, fillcolor = lightgrey];
36 -> 207 [arrowhead = none , style=dashed];
207 -> 12[style=dashed];

208 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
37 -> 208 [arrowhead = none ];
208 -> 38;

209 [label="SPLIT 2\nreplacements:\nX124 -> T83\nT79 -> T84", fontsize=14, style = filled, fillcolor = violet];
37 -> 209 [arrowhead = none ];
209 -> 39;

210 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
38 -> 210 [arrowhead = none ];
210 -> 40;

211 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
39 -> 211 [arrowhead = none ];
211 -> 53;

212 [label="SPLIT 2\nreplacements:\nX125 -> T105\nT83 -> T106", fontsize=14, style = filled, fillcolor = violet];
39 -> 212 [arrowhead = none ];
212 -> 54;

213 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
40 -> 213 [arrowhead = none ];
213 -> 41;

214 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
40 -> 214 [arrowhead = none ];
214 -> 42;

215 [label="EVAL with clause\nmergesort([], []).\nand substitution\nT78 -> []\nX124 -> []", fontsize=14, style = filled, fillcolor = lightblue];
41 -> 215 [arrowhead = none ];
215 -> 43;

216 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
41 -> 216 [arrowhead = none ];
216 -> 44;

217 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
42 -> 217 [arrowhead = none ];
217 -> 46;

218 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
42 -> 218 [arrowhead = none ];
218 -> 47;

219 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
43 -> 219 [arrowhead = none ];
219 -> 45;

220 [label="EVAL with clause\nmergesort(.(X147, []), .(X147, [])).\nand substitution\nX147 -> T89\nT78 -> .(T89, [])\nX124 -> .(T89, [])", fontsize=14, style = filled, fillcolor = lightblue];
46 -> 220 [arrowhead = none ];
220 -> 48;

221 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
46 -> 221 [arrowhead = none ];
221 -> 49;

222 [label="EVAL with clause\nmergesort(.(X163, .(X164, X165)), X166) :- ','(split(.(X163, .(X164, X165)), X167, X168), ','(mergesort(X167, X169), ','(mergesort(X168, X170), merge(X169, X170, X166)))).\nand substitution\nX163 -> T99\nX164 -> T100\nX165 -> T101\nT78 -> .(T99, .(T100, T101))\nX124 -> X171\nX166 -> X171\nT96 -> T99\nT97 -> T100\nT98 -> T101", fontsize=14, style = filled, fillcolor = lightblue];
47 -> 222 [arrowhead = none ];
222 -> 51;

223 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
47 -> 223 [arrowhead = none ];
223 -> 52;

224 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
48 -> 224 [arrowhead = none ];
224 -> 50;

225 [label="INSTANCE with matching:\nT72 -> T99\nT73 -> T100\nT74 -> T101\nX122 -> X167\nX123 -> X168\nX124 -> X169\nX125 -> X170\nX126 -> X171", fontsize=14, style = filled, fillcolor = lightgrey];
51 -> 225 [arrowhead = none , style=dashed];
225 -> 34[style=dashed];

226 [label="INSTANCE with matching:\nT78 -> T84\nX124 -> X125", fontsize=14, style = filled, fillcolor = lightgrey];
53 -> 226 [arrowhead = none , style=dashed];
226 -> 38[style=dashed];

227 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
54 -> 227 [arrowhead = none ];
227 -> 55;

228 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
55 -> 228 [arrowhead = none ];
228 -> 56;

229 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
55 -> 229 [arrowhead = none ];
229 -> 57;

230 [label="EVAL with clause\nmerge([], X188, X188).\nand substitution\nT106 -> []\nT105 -> T113\nX188 -> T113\nX126 -> T113", fontsize=14, style = filled, fillcolor = lightblue];
56 -> 230 [arrowhead = none ];
230 -> 58;

231 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
56 -> 231 [arrowhead = none ];
231 -> 59;

232 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
57 -> 232 [arrowhead = none ];
232 -> 61;

233 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
57 -> 233 [arrowhead = none ];
233 -> 62;

234 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
58 -> 234 [arrowhead = none ];
234 -> 60;

235 [label="EVAL with clause\nmerge(X194, [], X194).\nand substitution\nT106 -> T118\nX194 -> T118\nT105 -> []\nX126 -> T118", fontsize=14, style = filled, fillcolor = lightblue];
61 -> 235 [arrowhead = none ];
235 -> 63;

236 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
61 -> 236 [arrowhead = none ];
236 -> 64;

237 [label="EVAL with clause\nmerge(.(X208, X209), .(X210, X211), .(X208, X212)) :- ','(user_defined_=(X208, X210), merge(.(X208, X209), X211, X212)).\nand substitution\nX208 -> T131\nX209 -> T134\nT106 -> .(T131, T134)\nX210 -> T132\nX211 -> T133\nT105 -> .(T132, T133)\nX212 -> X213\nX126 -> .(T131, X213)\nT127 -> T131\nT129 -> T132\nT130 -> T133\nT128 -> T134", fontsize=14, style = filled, fillcolor = lightblue];
62 -> 237 [arrowhead = none ];
237 -> 66;

238 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
62 -> 238 [arrowhead = none ];
238 -> 67;

239 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
63 -> 239 [arrowhead = none ];
239 -> 65;

240 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
66 -> 240 [arrowhead = none ];
240 -> 68;

241 [label="EVAL with clause\nuser_defined_=(X225, X225).\nand substitution\nT131 -> T143\nX225 -> T143\nT132 -> T143\nT133 -> T142\nT141 -> T143\nT134 -> T144", fontsize=14, style = filled, fillcolor = lightblue];
68 -> 241 [arrowhead = none ];
241 -> 69;

242 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
68 -> 242 [arrowhead = none ];
242 -> 70;

243 [label="INSTANCE with matching:\nT106 -> .(T143, T144)\nT105 -> T142\nX126 -> X213", fontsize=14, style = filled, fillcolor = lightgrey];
69 -> 243 [arrowhead = none , style=dashed];
243 -> 54[style=dashed];

244 [label="INSTANCE with matching:\nT78 -> T55\nX124 -> X13", fontsize=14, style = filled, fillcolor = lightgrey];
71 -> 244 [arrowhead = none , style=dashed];
244 -> 38[style=dashed];

245 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
72 -> 245 [arrowhead = none ];
245 -> 73;

246 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
73 -> 246 [arrowhead = none ];
246 -> 74;

247 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
73 -> 247 [arrowhead = none ];
247 -> 75;

248 [label="EVAL with clause\nmerge([], X237, X237).\nand substitution\nT150 -> []\nT149 -> []\nX237 -> []\nT157 -> []", fontsize=14, style = filled, fillcolor = lightblue];
74 -> 248 [arrowhead = none ];
248 -> 76;

249 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
74 -> 249 [arrowhead = none ];
249 -> 77;

250 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
75 -> 250 [arrowhead = none ];
250 -> 79;

251 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
75 -> 251 [arrowhead = none ];
251 -> 80;

252 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
76 -> 252 [arrowhead = none ];
252 -> 78;

253 [label="EVAL with clause\nmerge(X243, [], X243).\nand substitution\nT150 -> []\nX243 -> []\nT149 -> []\nT162 -> []", fontsize=14, style = filled, fillcolor = lightblue];
79 -> 253 [arrowhead = none ];
253 -> 81;

254 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
79 -> 254 [arrowhead = none ];
254 -> 82;

255 [label="BACKTRACK\nfor clause: merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(user_defined_=(X, Y), merge(.(X, Xs), Ys, Zs))because of non-unification", fontsize=14, style = filled, fillcolor = white];
80 -> 255 [arrowhead = none ];
255 -> 84;

256 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
81 -> 256 [arrowhead = none ];
256 -> 83;

257 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
85 -> 257 [arrowhead = none ];
257 -> 87;

258 [label="EVAL with clause\nmergesort(.(X369, .(X370, X371)), X372) :- ','(split(.(X369, .(X370, X371)), X373, X374), ','(mergesort(X373, X375), ','(mergesort(X374, X376), merge(X375, X376, X372)))).\nand substitution\nX369 -> T280\nX370 -> T281\nX371 -> T282\nT1 -> .(T280, .(T281, T282))\nT2 -> T279\nX372 -> T279\nT276 -> T280\nT277 -> T281\nT278 -> T282", fontsize=14, style = filled, fillcolor = lightblue];
86 -> 258 [arrowhead = none ];
258 -> 115;

259 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
86 -> 259 [arrowhead = none ];
259 -> 116;

260 [label="EVAL with clause\nmergesort(.(X257, .(X258, X259)), X260) :- ','(split(.(X257, .(X258, X259)), X261, X262), ','(mergesort(X261, X263), ','(mergesort(X262, X264), merge(X263, X264, X260)))).\nand substitution\nX257 -> T177\nX258 -> T178\nX259 -> T179\nT1 -> .(T177, .(T178, T179))\nT168 -> T176\nX260 -> .(T176, [])\nT173 -> T177\nT174 -> T178\nT175 -> T179", fontsize=14, style = filled, fillcolor = lightblue];
87 -> 260 [arrowhead = none ];
260 -> 88;

261 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
87 -> 261 [arrowhead = none ];
261 -> 89;

262 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
88 -> 262 [arrowhead = none ];
262 -> 90;

263 [label="BACKTRACK\nfor clause: split([], [], [])because of non-unification", fontsize=14, style = filled, fillcolor = white];
90 -> 263 [arrowhead = none ];
263 -> 91;

264 [label="ONLY EVAL with clause\nsplit(.(X287, X288), .(X287, X289), X290) :- split(X288, X290, X289).\nand substitution\nT177 -> T196\nX287 -> T196\nT178 -> T194\nT179 -> T195\nX288 -> .(T194, T195)\nX289 -> X291\nX261 -> .(T196, X291)\nX262 -> X292\nX290 -> X292\nT192 -> T194\nT193 -> T195\nT191 -> T196", fontsize=14, style = filled, fillcolor = white];
91 -> 264 [arrowhead = none ];
264 -> 92;

265 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
92 -> 265 [arrowhead = none ];
265 -> 93;

266 [label="SPLIT 2\nreplacements:\nX292 -> T199\nX291 -> T200\nT196 -> T201", fontsize=14, style = filled, fillcolor = violet];
92 -> 266 [arrowhead = none ];
266 -> 94;

267 [label="INSTANCE with matching:\nT27 -> T194\nT28 -> T195\nX41 -> X292\nX40 -> X291", fontsize=14, style = filled, fillcolor = lightgrey];
93 -> 267 [arrowhead = none , style=dashed];
267 -> 12[style=dashed];

268 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
94 -> 268 [arrowhead = none ];
268 -> 95;

269 [label="SPLIT 2\nreplacements:\nX263 -> T206\nT199 -> T207", fontsize=14, style = filled, fillcolor = violet];
94 -> 269 [arrowhead = none ];
269 -> 96;

270 [label="INSTANCE with matching:\nT34 -> T201\nT33 -> T200\nX12 -> X263", fontsize=14, style = filled, fillcolor = lightgrey];
95 -> 270 [arrowhead = none , style=dashed];
270 -> 25[style=dashed];

271 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
96 -> 271 [arrowhead = none ];
271 -> 97;

272 [label="SPLIT 2\nreplacements:\nX264 -> T210\nT206 -> T211", fontsize=14, style = filled, fillcolor = violet];
96 -> 272 [arrowhead = none ];
272 -> 98;

273 [label="INSTANCE with matching:\nT55 -> T207\nX13 -> X264", fontsize=14, style = filled, fillcolor = lightgrey];
97 -> 273 [arrowhead = none , style=dashed];
273 -> 71[style=dashed];

274 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
98 -> 274 [arrowhead = none ];
274 -> 99;

275 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
99 -> 275 [arrowhead = none ];
275 -> 100;

276 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
99 -> 276 [arrowhead = none ];
276 -> 101;

277 [label="EVAL with clause\nmerge([], X315, X315).\nand substitution\nT211 -> []\nT210 -> .(T225, [])\nX315 -> .(T225, [])\nT176 -> T225\nT224 -> .(T225, [])", fontsize=14, style = filled, fillcolor = lightblue];
100 -> 277 [arrowhead = none ];
277 -> 102;

278 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
100 -> 278 [arrowhead = none ];
278 -> 103;

279 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
101 -> 279 [arrowhead = none ];
279 -> 105;

280 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
101 -> 280 [arrowhead = none ];
280 -> 106;

281 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
102 -> 281 [arrowhead = none ];
281 -> 104;

282 [label="EVAL with clause\nmerge(X321, [], X321).\nand substitution\nT211 -> .(T235, [])\nX321 -> .(T235, [])\nT210 -> []\nT176 -> T235\nT234 -> .(T235, [])", fontsize=14, style = filled, fillcolor = lightblue];
105 -> 282 [arrowhead = none ];
282 -> 107;

283 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
105 -> 283 [arrowhead = none ];
283 -> 108;

284 [label="EVAL with clause\nmerge(.(X333, X334), .(X335, X336), .(X333, X337)) :- ','(user_defined_=(X333, X335), merge(.(X333, X334), X336, X337)).\nand substitution\nX333 -> T244\nX334 -> T250\nT211 -> .(T244, T250)\nX335 -> T248\nX336 -> T249\nT210 -> .(T248, T249)\nT176 -> T244\nX337 -> []\nT246 -> T248\nT247 -> T249\nT245 -> T250", fontsize=14, style = filled, fillcolor = lightblue];
106 -> 284 [arrowhead = none ];
284 -> 110;

285 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
106 -> 285 [arrowhead = none ];
285 -> 111;

286 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
107 -> 286 [arrowhead = none ];
286 -> 109;

287 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
110 -> 287 [arrowhead = none ];
287 -> 112;

288 [label="EVAL with clause\nuser_defined_=(X354, X354).\nand substitution\nT244 -> T261\nX354 -> T261\nT248 -> T261\nT249 -> T262\nT250 -> T263", fontsize=14, style = filled, fillcolor = lightblue];
112 -> 288 [arrowhead = none ];
288 -> 113;

289 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
112 -> 289 [arrowhead = none ];
289 -> 114;

290 [label="INSTANCE with matching:\nT150 -> .(T261, T263)\nT149 -> T262", fontsize=14, style = filled, fillcolor = lightgrey];
113 -> 290 [arrowhead = none , style=dashed];
290 -> 72[style=dashed];

291 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
115 -> 291 [arrowhead = none ];
291 -> 117;

292 [label="BACKTRACK\nfor clause: split([], [], [])because of non-unification", fontsize=14, style = filled, fillcolor = white];
117 -> 292 [arrowhead = none ];
292 -> 118;

293 [label="ONLY EVAL with clause\nsplit(.(X399, X400), .(X399, X401), X402) :- split(X400, X402, X401).\nand substitution\nT280 -> T299\nX399 -> T299\nT281 -> T297\nT282 -> T298\nX400 -> .(T297, T298)\nX401 -> X403\nX373 -> .(T299, X403)\nX374 -> X404\nX402 -> X404\nT295 -> T297\nT296 -> T298\nT294 -> T299", fontsize=14, style = filled, fillcolor = white];
118 -> 293 [arrowhead = none ];
293 -> 119;

294 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
119 -> 294 [arrowhead = none ];
294 -> 120;

295 [label="SPLIT 2\nreplacements:\nX404 -> T302\nX403 -> T303\nT299 -> T304\nT1 -> T305\nX251 -> T306", fontsize=14, style = filled, fillcolor = violet];
119 -> 295 [arrowhead = none ];
295 -> 121;

296 [label="INSTANCE with matching:\nT27 -> T297\nT28 -> T298\nX41 -> X404\nX40 -> X403", fontsize=14, style = filled, fillcolor = lightgrey];
120 -> 296 [arrowhead = none , style=dashed];
296 -> 12[style=dashed];

297 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
121 -> 297 [arrowhead = none ];
297 -> 122;

298 [label="SPLIT 2\nreplacements:\nX375 -> T311\nT302 -> T312\nT305 -> T313\nT306 -> T314", fontsize=14, style = filled, fillcolor = violet];
121 -> 298 [arrowhead = none ];
298 -> 123;

299 [label="INSTANCE with matching:\nT34 -> T304\nT33 -> T303\nX12 -> X375", fontsize=14, style = filled, fillcolor = lightgrey];
122 -> 299 [arrowhead = none , style=dashed];
299 -> 25[style=dashed];

300 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
123 -> 300 [arrowhead = none ];
300 -> 124;

301 [label="SPLIT 2\nreplacements:\nX376 -> T317\nT311 -> T318\nT313 -> T319\nT314 -> T320", fontsize=14, style = filled, fillcolor = violet];
123 -> 301 [arrowhead = none ];
301 -> 125;

302 [label="INSTANCE with matching:\nT55 -> T312\nX13 -> X376", fontsize=14, style = filled, fillcolor = lightgrey];
124 -> 302 [arrowhead = none , style=dashed];
302 -> 71[style=dashed];

303 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
125 -> 303 [arrowhead = none ];
303 -> 126;

304 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
126 -> 304 [arrowhead = none ];
304 -> 127;

305 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
126 -> 305 [arrowhead = none ];
305 -> 128;

306 [label="EVAL with clause\nmerge([], X427, X427).\nand substitution\nT318 -> []\nT317 -> T327\nX427 -> T327\nT279 -> T327", fontsize=14, style = filled, fillcolor = lightblue];
127 -> 306 [arrowhead = none ];
306 -> 129;

307 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
127 -> 307 [arrowhead = none ];
307 -> 130;

308 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
128 -> 308 [arrowhead = none ];
308 -> 132;

309 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
128 -> 309 [arrowhead = none ];
309 -> 133;

310 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
129 -> 310 [arrowhead = none ];
310 -> 131;

311 [label="EVAL with clause\nmerge(X433, [], X433).\nand substitution\nT318 -> T332\nX433 -> T332\nT317 -> []\nT279 -> T332", fontsize=14, style = filled, fillcolor = lightblue];
132 -> 311 [arrowhead = none ];
311 -> 134;

312 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
132 -> 312 [arrowhead = none ];
312 -> 135;

313 [label="EVAL with clause\nmerge(.(X445, X446), .(X447, X448), .(X445, X449)) :- ','(user_defined_=(X445, X447), merge(.(X445, X446), X448, X449)).\nand substitution\nX445 -> T343\nX446 -> T350\nT318 -> .(T343, T350)\nX447 -> T348\nX448 -> T349\nT317 -> .(T348, T349)\nX449 -> T347\nT279 -> .(T343, T347)\nT345 -> T348\nT346 -> T349\nT344 -> T350", fontsize=14, style = filled, fillcolor = lightblue];
133 -> 313 [arrowhead = none ];
313 -> 137;

314 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
133 -> 314 [arrowhead = none ];
314 -> 138;

315 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
134 -> 315 [arrowhead = none ];
315 -> 136;

316 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
137 -> 316 [arrowhead = none ];
316 -> 139;

317 [label="EVAL with clause\nuser_defined_=(X461, X461).\nand substitution\nT343 -> T357\nX461 -> T357\nT348 -> T357\nT349 -> T358\nT350 -> T359", fontsize=14, style = filled, fillcolor = lightblue];
139 -> 317 [arrowhead = none ];
317 -> 140;

318 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
139 -> 318 [arrowhead = none ];
318 -> 141;

319 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
140 -> 319 [arrowhead = none ];
319 -> 142;

320 [label="BACKTRACK\nfor clause: merge([], Xs, Xs)because of non-unification", fontsize=14, style = filled, fillcolor = white];
142 -> 320 [arrowhead = none ];
320 -> 143;

321 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
143 -> 321 [arrowhead = none ];
321 -> 144;

322 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
143 -> 322 [arrowhead = none ];
322 -> 145;

323 [label="EVAL with clause\nmerge(X472, [], X472).\nand substitution\nT357 -> T372\nT359 -> T373\nX472 -> .(T372, T373)\nT358 -> []\nT347 -> .(T372, T373)", fontsize=14, style = filled, fillcolor = lightblue];
144 -> 323 [arrowhead = none ];
323 -> 146;

324 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
144 -> 324 [arrowhead = none ];
324 -> 147;

325 [label="EVAL with clause\nmerge(.(X484, X485), .(X486, X487), .(X484, X488)) :- ','(user_defined_=(X484, X486), merge(.(X484, X485), X487, X488)).\nand substitution\nT357 -> T384\nX484 -> T384\nT359 -> T391\nX485 -> T391\nX486 -> T389\nX487 -> T390\nT358 -> .(T389, T390)\nX488 -> T388\nT347 -> .(T384, T388)\nT386 -> T389\nT387 -> T390\nT385 -> T391", fontsize=14, style = filled, fillcolor = lightblue];
145 -> 325 [arrowhead = none ];
325 -> 149;

326 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
145 -> 326 [arrowhead = none ];
326 -> 150;

327 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
146 -> 327 [arrowhead = none ];
327 -> 148;

328 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
149 -> 328 [arrowhead = none ];
328 -> 151;

329 [label="EVAL with clause\nuser_defined_=(X500, X500).\nand substitution\nT384 -> T398\nX500 -> T398\nT389 -> T398\nT390 -> T399\nT391 -> T400", fontsize=14, style = filled, fillcolor = lightblue];
151 -> 329 [arrowhead = none ];
329 -> 152;

330 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
151 -> 330 [arrowhead = none ];
330 -> 153;

331 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
152 -> 331 [arrowhead = none ];
331 -> 154;

332 [label="BACKTRACK\nfor clause: merge([], Xs, Xs)because of non-unification", fontsize=14, style = filled, fillcolor = white];
154 -> 332 [arrowhead = none ];
332 -> 155;

333 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
155 -> 333 [arrowhead = none ];
333 -> 156;

334 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
155 -> 334 [arrowhead = none ];
334 -> 157;

335 [label="EVAL with clause\nmerge(X511, [], X511).\nand substitution\nT398 -> T413\nT400 -> T414\nX511 -> .(T413, T414)\nT399 -> []\nT388 -> .(T413, T414)", fontsize=14, style = filled, fillcolor = lightblue];
156 -> 335 [arrowhead = none ];
335 -> 158;

336 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
156 -> 336 [arrowhead = none ];
336 -> 159;

337 [label="EVAL with clause\nmerge(.(X523, X524), .(X525, X526), .(X523, X527)) :- ','(user_defined_=(X523, X525), merge(.(X523, X524), X526, X527)).\nand substitution\nT398 -> T425\nX523 -> T425\nT400 -> T432\nX524 -> T432\nX525 -> T430\nX526 -> T431\nT399 -> .(T430, T431)\nX527 -> T429\nT388 -> .(T425, T429)\nT427 -> T430\nT428 -> T431\nT426 -> T432", fontsize=14, style = filled, fillcolor = lightblue];
157 -> 337 [arrowhead = none ];
337 -> 161;

338 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
157 -> 338 [arrowhead = none ];
338 -> 162;

339 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
158 -> 339 [arrowhead = none ];
339 -> 160;

340 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
161 -> 340 [arrowhead = none ];
340 -> 163;

341 [label="EVAL with clause\nuser_defined_=(X539, X539).\nand substitution\nT425 -> T439\nX539 -> T439\nT430 -> T439\nT431 -> T440\nT432 -> T441", fontsize=14, style = filled, fillcolor = lightblue];
163 -> 341 [arrowhead = none ];
341 -> 164;

342 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
163 -> 342 [arrowhead = none ];
342 -> 165;

343 [label="INSTANCE with matching:\nT398 -> T439\nT400 -> T441\nT399 -> T440\nT388 -> T429", fontsize=14, style = filled, fillcolor = lightgrey];
164 -> 343 [arrowhead = none , style=dashed];
343 -> 152[style=dashed];

}

(6) Obligation:

Triples:

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

Clauses:

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

Afs:

mergesort1(x1, x2) = mergesort1(x2)

(7) UndefinedPredicateInTriplesTransformerProof (SOUND transformation)

Deleted triples and predicates having undefined goals [UNKNOWN].

(8) Obligation:

Triples:

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

Clauses:

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

Afs:

mergesort1(x1, x2) = mergesort1(x2)

(9) TriplesToPiDPProof (SOUND transformation)

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

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

The TRS R consists of the following rules:

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

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

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

Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES

(10) Obligation:

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

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

The TRS R consists of the following rules:

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

(11) DependencyGraphProof (EQUIVALENT transformation)

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

(12) Complex Obligation (AND)

(13) Obligation:

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

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

The TRS R consists of the following rules:

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

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

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

(14) UsableRulesProof (EQUIVALENT transformation)

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

(15) Obligation:

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

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

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

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

(16) PiDPToQDPProof (SOUND transformation)

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

(17) Obligation:

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

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

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

(18) QDPSizeChangeProof (EQUIVALENT transformation)

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

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

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

(19) YES

(20) Obligation:

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

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

The TRS R consists of the following rules:

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

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

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

(21) UsableRulesProof (EQUIVALENT transformation)

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

(22) Obligation:

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

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

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

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

(23) PiDPToQDPProof (SOUND transformation)

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

(24) Obligation:

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

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

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

(25) QDPSizeChangeProof (EQUIVALENT transformation)

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

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

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

(26) YES

(27) Obligation:

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

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

The TRS R consists of the following rules:

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

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

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

(28) UsableRulesProof (EQUIVALENT transformation)

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

(29) Obligation:

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

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

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

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

(30) PiDPToQDPProof (SOUND transformation)

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

(31) Obligation:

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

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

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

(32) QDPSizeChangeProof (EQUIVALENT transformation)

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

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

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

(33) YES

(34) Obligation:

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

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

The TRS R consists of the following rules:

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

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

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

(35) UsableRulesProof (EQUIVALENT transformation)

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

(36) Obligation:

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

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

The TRS R consists of the following rules:

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

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

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

(37) PiDPToQDPProof (SOUND transformation)

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

(38) Obligation:

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

(39) Rewriting (EQUIVALENT transformation)

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

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

(40) Obligation:

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

(41) Rewriting (EQUIVALENT transformation)

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

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

(42) Obligation:

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

(43) Rewriting (EQUIVALENT transformation)

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

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

(44) Obligation:

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

(45) Rewriting (EQUIVALENT transformation)

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

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

(46) Obligation:

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

(47) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

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

The remaining pairs can at least be oriented weakly.
Used ordering: Matrix interpretation [MATRO]:

POL(U4_AAGAAAAA(x₁, x₂)) = 0 +
[ 0, 0 ]

· x₁ +
[ 1, 0 ]

· x₂

POL(splitc12_out_agaa(x₁, x₂, x₃)) =
/ 0 \

\ 0 /

+
/ 0 0 \

\ 0 0 /

· x₁ +
/ 1 0 \

\ 0 0 /

· x₂ +
/ 1 0 \

\ 0 0 /

· x₃

POL(.(x₁)) =
/ 0 \

\ 1 /

+
/ 1 1 \

\ 1 1 /

· x₁

POL(MERGESORT38_IN_GA(x₁)) = 0 +
[ 1, 0 ]

· x₁

POL(P34_IN_AAGAAAAA(x₁)) = 1 +
[ 1, 1 ]

· x₁

POL(U6_AAGAAAAA(x₁, x₂)) = 0 +
[ 0, 0 ]

· x₁ +
[ 1, 0 ]

· x₂

POL(U7_AAGAAAAA(x₁, x₂, x₃, x₄)) = 0 +
[ 0, 0 ]

· x₁ +
[ 0, 0 ]

· x₂ +
[ 1, 0 ]

· x₃ +
[ 0, 0 ]

· x₄

POL(mergesortc38_in_ga(x₁)) =
/ 0 \

\ 0 /

+
/ 0 0 \

\ 0 0 /

· x₁

POL(mergesortc38_out_ga(x₁, x₂)) =
/ 0 \

\ 0 /

+
/ 0 0 \

\ 0 1 /

· x₁ +
/ 0 1 \

\ 0 1 /

· x₂

POL(U41_agaa(x₁, x₂)) =
/ 0 \

\ 0 /

+
/ 0 0 \

\ 0 0 /

· x₁ +
/ 1 0 \

\ 0 0 /

· x₂

POL(U40_gaa(x₁, x₂)) =
/ 0 \

\ 1 /

+
/ 0 0 \

\ 0 0 /

· x₁ +
/ 1 1 \

\ 1 0 /

· x₂

POL(splitc16_in_gaa(x₁)) =
/ 0 \

\ 0 /

+
/ 1 0 \

\ 0 1 /

· x₁

POL([]) =
/ 0 \

\ 0 /

POL(U46_ga(x₁, x₂)) =
/ 1 \

\ 1 /

+
/ 0 1 \

\ 1 1 /

· x₁ +
/ 0 0 \

\ 0 0 /

· x₂

POL(qc34_in_aagaaaaa(x₁)) =
/ 0 \

\ 0 /

+
/ 0 0 \

\ 0 0 /

· x₁

POL(splitc16_out_gaa(x₁, x₂, x₃)) =
/ 0 \

\ 0 /

+
/ 0 0 \

\ 0 0 /

· x₁ +
/ 1 0 \

\ 0 1 /

· x₂ +
/ 1 1 \

\ 0 0 /

· x₃

POL(U42_aagaaaaa(x₁, x₂)) =
/ 0 \

\ 0 /

+
/ 1 0 \

\ 0 0 /

· x₁ +
/ 0 0 \

\ 0 0 /

· x₂

POL(U43_aagaaaaa(x₁, x₂, x₃, x₄)) =
/ 1 \

\ 1 /

+
/ 1 1 \

\ 1 1 /

· x₁ +
/ 1 1 \

\ 0 1 /

· x₂ +
/ 1 0 \

\ 1 0 /

· x₃ +
/ 0 0 \

\ 0 0 /

· x₄

POL(qc34_out_aagaaaaa(x₁, x₂, x₃, x₄, x₅, x₆)) =
/ 1 \

\ 1 /

+
/ 1 1 \

\ 1 0 /

· x₁ +
/ 0 1 \

\ 1 1 /

· x₂ +
/ 0 1 \

\ 1 1 /

· x₃ +
/ 1 1 \

\ 1 1 /

· x₄ +
/ 1 1 \

\ 1 1 /

· x₅ +
/ 0 1 \

\ 1 1 /

· x₆

POL(splitc12_in_agaa(x₁)) =
/ 1 \

\ 1 /

+
/ 0 1 \

\ 0 0 /

· x₁

POL(U44_aagaaaaa(x₁, x₂, x₃, x₄, x₅)) =
/ 0 \

\ 0 /

+
/ 0 1 \

\ 0 0 /

· x₁ +
/ 0 1 \

\ 1 0 /

· x₂ +
/ 1 0 \

\ 0 1 /

· x₃ +
/ 0 0 \

\ 0 0 /

· x₄ +
/ 0 0 \

\ 0 0 /

· x₅

POL(U45_aagaaaaa(x₁, x₂, x₃, x₄, x₅, x₆)) =
/ 0 \

\ 0 /

+
/ 0 0 \

\ 0 1 /

· x₁ +
/ 0 0 \

\ 0 0 /

· x₂ +
/ 0 1 \

\ 1 0 /

· x₃ +
/ 0 0 \

\ 0 1 /

· x₄ +
/ 0 0 \

\ 0 0 /

· x₅ +
/ 0 0 \

\ 0 0 /

· x₆

POL(mergec54_in_gga(x₁, x₂)) =
/ 0 \

\ 0 /

+
/ 1 1 \

\ 0 0 /

· x₁ +
/ 1 0 \

\ 0 0 /

· x₂

POL(mergec54_out_gga(x₁, x₂, x₃)) =
/ 1 \

\ 0 /

+
/ 1 1 \

\ 0 0 /

· x₁ +
/ 1 0 \

\ 0 0 /

· x₂ +
/ 0 0 \

\ 0 0 /

· x₃

POL(U47_gga(x₁, x₂, x₃)) =
/ 0 \

\ 0 /

+
/ 1 0 \

\ 0 1 /

· x₁ +
/ 0 0 \

\ 1 0 /

· x₂ +
/ 0 0 \

\ 1 0 /

· x₃

The following usable rules [FROCOS05] were oriented:

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

(48) Obligation:

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

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

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

(49) DependencyGraphProof (EQUIVALENT transformation)

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

(50) TRUE

(51) Obligation:

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

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

The TRS R consists of the following rules:

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

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

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

(52) UsableRulesProof (EQUIVALENT transformation)

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

(53) Obligation:

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

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

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

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

(54) PiDPToQDPProof (SOUND transformation)

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

(55) Obligation:

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

SPLIT16_IN_AAA → SPLIT16_IN_AAA

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

(56) NonTerminationProof (EQUIVALENT transformation)

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

s = SPLIT16_IN_AAA evaluates to t =SPLIT16_IN_AAA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:

Semiunifier: [ ]
Matcher: [ ]

Rewriting sequence

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

(0) Obligation:

(1) PredefinedPredicateTransformerProof (SOUND transformation)

(2) Obligation:

(3) BuiltinConflictTransformerProof (SOUND transformation)

(4) Obligation:

(5) PrologToDTProblemTransformerProof (SOUND transformation)

(6) Obligation:

(7) UndefinedPredicateInTriplesTransformerProof (SOUND transformation)

(8) Obligation:

(9) TriplesToPiDPProof (SOUND transformation)

(10) Obligation:

(11) DependencyGraphProof (EQUIVALENT transformation)

(12) Complex Obligation (AND)

(13) Obligation:

(14) UsableRulesProof (EQUIVALENT transformation)

(15) Obligation:

(16) PiDPToQDPProof (SOUND transformation)

(17) Obligation:

(18) QDPSizeChangeProof (EQUIVALENT transformation)

(19) YES

(20) Obligation:

(21) UsableRulesProof (EQUIVALENT transformation)

(22) Obligation:

(23) PiDPToQDPProof (SOUND transformation)

(24) Obligation:

(25) QDPSizeChangeProof (EQUIVALENT transformation)

(26) YES

(27) Obligation:

(28) UsableRulesProof (EQUIVALENT transformation)

(29) Obligation:

(30) PiDPToQDPProof (SOUND transformation)

(31) Obligation:

(32) QDPSizeChangeProof (EQUIVALENT transformation)

(33) YES

(34) Obligation:

(35) UsableRulesProof (EQUIVALENT transformation)

(36) Obligation:

(37) PiDPToQDPProof (SOUND transformation)

(38) Obligation:

(39) Rewriting (EQUIVALENT transformation)

(40) Obligation:

(41) Rewriting (EQUIVALENT transformation)

(42) Obligation:

(43) Rewriting (EQUIVALENT transformation)

(44) Obligation:

(45) Rewriting (EQUIVALENT transformation)

(46) Obligation:

(47) QDPOrderProof (EQUIVALENT transformation)

(48) Obligation:

(49) DependencyGraphProof (EQUIVALENT transformation)

(50) TRUE

(51) Obligation:

(52) UsableRulesProof (EQUIVALENT transformation)

(53) Obligation:

(54) PiDPToQDPProof (SOUND transformation)

(55) Obligation:

(56) NonTerminationProof (EQUIVALENT transformation)

(57) NO