Left Termination of the query pattern f_in_3(g, g, a) w.r.t. the given Prolog program could successfully be proven:

(0) Obligation:

Clauses:

f(A, [], RES) :- g(A, [], RES).
f(.(A, As), .(B, Bs), RES) :- f(.(B, .(A, As)), Bs, RES).
g([], RES, RES).
g(.(C, Cs), D, RES) :- g(Cs, .(C, D), RES).

Queries:

f(g,g,a).

(1) PrologToDTProblemTransformerProof (SOUND transformation)

Built DT problem from termination graph.

digraph dp_graph {
node [outthreshold=100, inthreshold=100];
1 [label="1: f(T1, T2, T3)\n\nT1 is ground\nT2 is ground", fontsize=16, style=filled, fillcolor=lightyellow, color=red];
2 [label="2: f(T1, T2, T3), SCOPE: 1, CLAUSE: 0 | f(T1, T2, T3), SCOPE: 1, CLAUSE: 1\n\nT1 is ground\nT2 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
3 [label="3: g(T6, [], T8) | f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
4 [label="4: f(T1, T2, T3), SCOPE: 1, CLAUSE: 1\n\nT1 is ground\nT2 is ground\nf(T1, T2, T3) !=? f(X3, [], X4)", fontsize=16, style=filled, fillcolor=lightyellow];
5 [label="5: g(T6, [], T8), SCOPE: 2, CLAUSE: 2 | g(T6, [], T8), SCOPE: 2, CLAUSE: 3 | ?_2 | f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
6 [label="6: g(T6, [], T8), SCOPE: 2, CLAUSE: 2\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
7 [label="7: g(T6, [], T8), SCOPE: 2, CLAUSE: 3 | ?_2 | f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
8 [label="8: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
9 [label="9: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
10 [label="10: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
11 [label="11: g(T6, [], T8), SCOPE: 2, CLAUSE: 3\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
12 [label="12: ?_2 | f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
13 [label="13: g(T22, .(T21, []), T24)\n\nT21 is ground\nT22 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
14 [label="14: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
15 [label="15: g(T22, .(T21, []), T24), SCOPE: 3, CLAUSE: 2 | g(T22, .(T21, []), T24), SCOPE: 3, CLAUSE: 3\n\nT21 is ground\nT22 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
16 [label="16: g(T22, .(T21, []), T24), SCOPE: 3, CLAUSE: 2\n\nT21 is ground\nT22 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
17 [label="17: g(T22, .(T21, []), T24), SCOPE: 3, CLAUSE: 3\n\nT21 is ground\nT22 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
18 [label="18: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
19 [label="19: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
20 [label="20: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
21 [label="21: g(T41, .(T40, .(T42, [])), T44)\n\nT40 is ground\nT41 is ground\nT42 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
22 [label="22: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
23 [label="23: g(T41, .(T40, .(T42, [])), T44), SCOPE: 4, CLAUSE: 2 | g(T41, .(T40, .(T42, [])), T44), SCOPE: 4, CLAUSE: 3\n\nT40 is ground\nT41 is ground\nT42 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
24 [label="24: g(T41, .(T40, .(T42, [])), T44), SCOPE: 4, CLAUSE: 2\n\nT40 is ground\nT41 is ground\nT42 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
25 [label="25: g(T41, .(T40, .(T42, [])), T44), SCOPE: 4, CLAUSE: 3\n\nT40 is ground\nT41 is ground\nT42 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
26 [label="26: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
27 [label="27: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
28 [label="28: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
29 [label="29: g(T70, .(T69, .(T71, .(T72, []))), T74)\n\nT69 is ground\nT70 is ground\nT71 is ground\nT72 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
30 [label="30: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
31 [label="31: g(T70, .(T69, .(T71, .(T72, []))), T74), SCOPE: 5, CLAUSE: 2 | g(T70, .(T69, .(T71, .(T72, []))), T74), SCOPE: 5, CLAUSE: 3\n\nT69 is ground\nT70 is ground\nT71 is ground\nT72 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
32 [label="32: g(T70, .(T69, .(T71, .(T72, []))), T74), SCOPE: 5, CLAUSE: 2\n\nT69 is ground\nT70 is ground\nT71 is ground\nT72 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
33 [label="33: g(T70, .(T69, .(T71, .(T72, []))), T74), SCOPE: 5, CLAUSE: 3\n\nT69 is ground\nT70 is ground\nT71 is ground\nT72 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
34 [label="34: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
35 [label="35: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
36 [label="36: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
37 [label="37: g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114)\n\nT108 is ground\nT109 is ground\nT110 is ground\nT111 is ground\nT112 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
38 [label="38: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
39 [label="39: g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114), SCOPE: 6, CLAUSE: 2 | g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114), SCOPE: 6, CLAUSE: 3\n\nT108 is ground\nT109 is ground\nT110 is ground\nT111 is ground\nT112 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
40 [label="40: g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114), SCOPE: 6, CLAUSE: 2\n\nT108 is ground\nT109 is ground\nT110 is ground\nT111 is ground\nT112 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
41 [label="41: g(T109, .(T108, .(T110, .(T111, .(T112, [])))), T114), SCOPE: 6, CLAUSE: 3\n\nT108 is ground\nT109 is ground\nT110 is ground\nT111 is ground\nT112 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
42 [label="42: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
43 [label="43: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
44 [label="44: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
45 [label="45: g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164)\n\nT157 is ground\nT158 is ground\nT159 is ground\nT160 is ground\nT161 is ground\nT162 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
46 [label="46: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
47 [label="47: g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164), SCOPE: 7, CLAUSE: 2 | g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164), SCOPE: 7, CLAUSE: 3\n\nT157 is ground\nT158 is ground\nT159 is ground\nT160 is ground\nT161 is ground\nT162 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
48 [label="48: g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164), SCOPE: 7, CLAUSE: 2\n\nT157 is ground\nT158 is ground\nT159 is ground\nT160 is ground\nT161 is ground\nT162 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
49 [label="49: g(T158, .(T157, .(T159, .(T160, .(T161, .(T162, []))))), T164), SCOPE: 7, CLAUSE: 3\n\nT157 is ground\nT158 is ground\nT159 is ground\nT160 is ground\nT161 is ground\nT162 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
50 [label="50: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
51 [label="51: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
52 [label="52: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
53 [label="53: g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224)\n\nT216 is ground\nT217 is ground\nT218 is ground\nT219 is ground\nT220 is ground\nT221 is ground\nT222 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
54 [label="54: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
55 [label="55: g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224), SCOPE: 8, CLAUSE: 2 | g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224), SCOPE: 8, CLAUSE: 3\n\nT216 is ground\nT217 is ground\nT218 is ground\nT219 is ground\nT220 is ground\nT221 is ground\nT222 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
56 [label="56: g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224), SCOPE: 8, CLAUSE: 2\n\nT216 is ground\nT217 is ground\nT218 is ground\nT219 is ground\nT220 is ground\nT221 is ground\nT222 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
57 [label="57: g(T217, .(T216, .(T218, .(T219, .(T220, .(T221, .(T222, [])))))), T224), SCOPE: 8, CLAUSE: 3\n\nT216 is ground\nT217 is ground\nT218 is ground\nT219 is ground\nT220 is ground\nT221 is ground\nT222 is ground", 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: g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294)\n\nT285 is ground\nT286 is ground\nT287 is ground\nT288 is ground\nT289 is ground\nT290 is ground\nT291 is ground\nT292 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
62 [label="62: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
63 [label="63: g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294), SCOPE: 9, CLAUSE: 2 | g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294), SCOPE: 9, CLAUSE: 3\n\nT285 is ground\nT286 is ground\nT287 is ground\nT288 is ground\nT289 is ground\nT290 is ground\nT291 is ground\nT292 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
64 [label="64: g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294), SCOPE: 9, CLAUSE: 2\n\nT285 is ground\nT286 is ground\nT287 is ground\nT288 is ground\nT289 is ground\nT290 is ground\nT291 is ground\nT292 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
65 [label="65: g(T286, .(T285, .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))), T294), SCOPE: 9, CLAUSE: 3\n\nT285 is ground\nT286 is ground\nT287 is ground\nT288 is ground\nT289 is ground\nT290 is ground\nT291 is ground\nT292 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
66 [label="66: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
67 [label="67: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
68 [label="68: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
69 [label="69: g(T365, .(T364, .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, [])))))))), T374)\n\nT364 is ground\nT365 is ground\nT366 is ground\nT367 is ground\nT368 is ground\nT369 is ground\nT370 is ground\nT371 is ground\nT372 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
70 [label="70: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
71 [label="71: g(T365, .(T364, T391), T374)\n\nT364 is ground\nT365 is ground\nT391 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
72 [label="72: g(T365, .(T364, T391), T374), SCOPE: 10, CLAUSE: 2 | g(T365, .(T364, T391), T374), SCOPE: 10, CLAUSE: 3\n\nT364 is ground\nT365 is ground\nT391 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
73 [label="73: g(T365, .(T364, T391), T374), SCOPE: 10, CLAUSE: 2\n\nT364 is ground\nT365 is ground\nT391 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
74 [label="74: g(T365, .(T364, T391), T374), SCOPE: 10, CLAUSE: 3\n\nT364 is ground\nT365 is ground\nT391 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
75 [label="75: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
76 [label="76: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
77 [label="77: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
78 [label="78: g(T417, .(T416, .(T418, T419)), T421)\n\nT416 is ground\nT417 is ground\nT418 is ground\nT419 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
79 [label="79: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
80 [label="80: f(T6, [], T3), SCOPE: 1, CLAUSE: 1\n\nT6 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
81 [label="81: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
82 [label="82: f(.(T437, .(T435, T436)), T438, T440)\n\nT435 is ground\nT436 is ground\nT437 is ground\nT438 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
83 [label="83: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
84 [label="84: f(.(T437, .(T435, T436)), T438, T440), SCOPE: 11, CLAUSE: 0 | f(.(T437, .(T435, T436)), T438, T440), SCOPE: 11, CLAUSE: 1\n\nT435 is ground\nT436 is ground\nT437 is ground\nT438 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
85 [label="85: f(.(T437, .(T435, T436)), T438, T440), SCOPE: 11, CLAUSE: 0\n\nT435 is ground\nT436 is ground\nT437 is ground\nT438 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
86 [label="86: f(.(T437, .(T435, T436)), T438, T440), SCOPE: 11, CLAUSE: 1\n\nT435 is ground\nT436 is ground\nT437 is ground\nT438 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
87 [label="87: g(.(T457, .(T458, T459)), [], T461)\n\nT457 is ground\nT458 is ground\nT459 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
88 [label="88: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
89 [label="89: g(.(T457, .(T458, T459)), [], T461), SCOPE: 12, CLAUSE: 2 | g(.(T457, .(T458, T459)), [], T461), SCOPE: 12, CLAUSE: 3\n\nT457 is ground\nT458 is ground\nT459 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
90 [label="90: g(.(T457, .(T458, T459)), [], T461), SCOPE: 12, CLAUSE: 3\n\nT457 is ground\nT458 is ground\nT459 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
91 [label="91: g(.(T480, T481), .(T479, []), T483)\n\nT479 is ground\nT480 is ground\nT481 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
92 [label="92: f(.(T503, .(T500, .(T501, T502))), T504, T506)\n\nT500 is ground\nT501 is ground\nT502 is ground\nT503 is ground\nT504 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
93 [label="93: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
94 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
1 -> 94 [arrowhead = none ];
94 -> 2;

95 [label="EVAL with clause\nf(X3, [], X4) :- g(X3, [], X4).\nand substitution\nT1 -> T6\nX3 -> T6\nT2 -> []\nT3 -> T8\nX4 -> T8\nT7 -> T8", fontsize=14, style = filled, fillcolor = lightblue];
2 -> 95 [arrowhead = none ];
95 -> 3;

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

97 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
3 -> 97 [arrowhead = none ];
97 -> 5;

98 [label="EVAL with clause\nf(.(X243, X244), .(X245, X246), X247) :- f(.(X245, .(X243, X244)), X246, X247).\nand substitution\nX243 -> T435\nX244 -> T436\nT1 -> .(T435, T436)\nX245 -> T437\nX246 -> T438\nT2 -> .(T437, T438)\nT3 -> T440\nX247 -> T440\nT439 -> T440", fontsize=14, style = filled, fillcolor = lightblue];
4 -> 98 [arrowhead = none ];
98 -> 82;

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

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

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

102 [label="EVAL with clause\ng([], X11, X11).\nand substitution\nT6 -> []\nX11 -> []\nT8 -> []", fontsize=14, style = filled, fillcolor = lightblue];
6 -> 102 [arrowhead = none ];
102 -> 8;

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

104 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
7 -> 104 [arrowhead = none ];
104 -> 11;

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

106 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
8 -> 106 [arrowhead = none ];
106 -> 10;

107 [label="EVAL with clause\ng(.(X29, X30), X31, X32) :- g(X30, .(X29, X31), X32).\nand substitution\nX29 -> T21\nX30 -> T22\nT6 -> .(T21, T22)\nX31 -> []\nT8 -> T24\nX32 -> T24\nT23 -> T24", fontsize=14, style = filled, fillcolor = lightblue];
11 -> 107 [arrowhead = none ];
107 -> 13;

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

109 [label="FAILURE", fontsize=14, style = filled, fillcolor = lightgreen];
12 -> 109 [arrowhead = none ];
109 -> 80;

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

111 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
15 -> 111 [arrowhead = none ];
111 -> 16;

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

113 [label="EVAL with clause\ng([], X43, X43).\nand substitution\nT22 -> []\nT21 -> T31\nX43 -> .(T31, [])\nT24 -> .(T31, [])", fontsize=14, style = filled, fillcolor = lightblue];
16 -> 113 [arrowhead = none ];
113 -> 18;

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

115 [label="EVAL with clause\ng(.(X53, X54), X55, X56) :- g(X54, .(X53, X55), X56).\nand substitution\nX53 -> T40\nX54 -> T41\nT22 -> .(T40, T41)\nT21 -> T42\nX55 -> .(T42, [])\nT24 -> T44\nX56 -> T44\nT43 -> T44", fontsize=14, style = filled, fillcolor = lightblue];
17 -> 115 [arrowhead = none ];
115 -> 21;

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

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

118 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
21 -> 118 [arrowhead = none ];
118 -> 23;

119 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
23 -> 119 [arrowhead = none ];
119 -> 24;

120 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
23 -> 120 [arrowhead = none ];
120 -> 25;

121 [label="EVAL with clause\ng([], X67, X67).\nand substitution\nT41 -> []\nT40 -> T57\nT42 -> T58\nX67 -> .(T57, .(T58, []))\nT44 -> .(T57, .(T58, []))", fontsize=14, style = filled, fillcolor = lightblue];
24 -> 121 [arrowhead = none ];
121 -> 26;

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

123 [label="EVAL with clause\ng(.(X77, X78), X79, X80) :- g(X78, .(X77, X79), X80).\nand substitution\nX77 -> T69\nX78 -> T70\nT41 -> .(T69, T70)\nT40 -> T71\nT42 -> T72\nX79 -> .(T71, .(T72, []))\nT44 -> T74\nX80 -> T74\nT73 -> T74", fontsize=14, style = filled, fillcolor = lightblue];
25 -> 123 [arrowhead = none ];
123 -> 29;

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

125 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
26 -> 125 [arrowhead = none ];
125 -> 28;

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

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

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

129 [label="EVAL with clause\ng([], X91, X91).\nand substitution\nT70 -> []\nT69 -> T93\nT71 -> T94\nT72 -> T95\nX91 -> .(T93, .(T94, .(T95, [])))\nT74 -> .(T93, .(T94, .(T95, [])))", fontsize=14, style = filled, fillcolor = lightblue];
32 -> 129 [arrowhead = none ];
129 -> 34;

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

131 [label="EVAL with clause\ng(.(X101, X102), X103, X104) :- g(X102, .(X101, X103), X104).\nand substitution\nX101 -> T108\nX102 -> T109\nT70 -> .(T108, T109)\nT69 -> T110\nT71 -> T111\nT72 -> T112\nX103 -> .(T110, .(T111, .(T112, [])))\nT74 -> T114\nX104 -> T114\nT113 -> T114", fontsize=14, style = filled, fillcolor = lightblue];
33 -> 131 [arrowhead = none ];
131 -> 37;

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

133 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
34 -> 133 [arrowhead = none ];
133 -> 36;

134 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
37 -> 134 [arrowhead = none ];
134 -> 39;

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

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

137 [label="EVAL with clause\ng([], X115, X115).\nand substitution\nT109 -> []\nT108 -> T139\nT110 -> T140\nT111 -> T141\nT112 -> T142\nX115 -> .(T139, .(T140, .(T141, .(T142, []))))\nT114 -> .(T139, .(T140, .(T141, .(T142, []))))", fontsize=14, style = filled, fillcolor = lightblue];
40 -> 137 [arrowhead = none ];
137 -> 42;

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

139 [label="EVAL with clause\ng(.(X125, X126), X127, X128) :- g(X126, .(X125, X127), X128).\nand substitution\nX125 -> T157\nX126 -> T158\nT109 -> .(T157, T158)\nT108 -> T159\nT110 -> T160\nT111 -> T161\nT112 -> T162\nX127 -> .(T159, .(T160, .(T161, .(T162, []))))\nT114 -> T164\nX128 -> T164\nT163 -> T164", fontsize=14, style = filled, fillcolor = lightblue];
41 -> 139 [arrowhead = none ];
139 -> 45;

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

141 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
42 -> 141 [arrowhead = none ];
141 -> 44;

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

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

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

145 [label="EVAL with clause\ng([], X139, X139).\nand substitution\nT158 -> []\nT157 -> T195\nT159 -> T196\nT160 -> T197\nT161 -> T198\nT162 -> T199\nX139 -> .(T195, .(T196, .(T197, .(T198, .(T199, [])))))\nT164 -> .(T195, .(T196, .(T197, .(T198, .(T199, [])))))", fontsize=14, style = filled, fillcolor = lightblue];
48 -> 145 [arrowhead = none ];
145 -> 50;

146 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
48 -> 146 [arrowhead = none ];
146 -> 51;

147 [label="EVAL with clause\ng(.(X149, X150), X151, X152) :- g(X150, .(X149, X151), X152).\nand substitution\nX149 -> T216\nX150 -> T217\nT158 -> .(T216, T217)\nT157 -> T218\nT159 -> T219\nT160 -> T220\nT161 -> T221\nT162 -> T222\nX151 -> .(T218, .(T219, .(T220, .(T221, .(T222, [])))))\nT164 -> T224\nX152 -> T224\nT223 -> T224", fontsize=14, style = filled, fillcolor = lightblue];
49 -> 147 [arrowhead = none ];
147 -> 53;

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

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

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

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

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

153 [label="EVAL with clause\ng([], X163, X163).\nand substitution\nT217 -> []\nT216 -> T261\nT218 -> T262\nT219 -> T263\nT220 -> T264\nT221 -> T265\nT222 -> T266\nX163 -> .(T261, .(T262, .(T263, .(T264, .(T265, .(T266, []))))))\nT224 -> .(T261, .(T262, .(T263, .(T264, .(T265, .(T266, []))))))", fontsize=14, style = filled, fillcolor = lightblue];
56 -> 153 [arrowhead = none ];
153 -> 58;

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

155 [label="EVAL with clause\ng(.(X173, X174), X175, X176) :- g(X174, .(X173, X175), X176).\nand substitution\nX173 -> T285\nX174 -> T286\nT217 -> .(T285, T286)\nT216 -> T287\nT218 -> T288\nT219 -> T289\nT220 -> T290\nT221 -> T291\nT222 -> T292\nX175 -> .(T287, .(T288, .(T289, .(T290, .(T291, .(T292, []))))))\nT224 -> T294\nX176 -> T294\nT293 -> T294", fontsize=14, style = filled, fillcolor = lightblue];
57 -> 155 [arrowhead = none ];
155 -> 61;

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

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

158 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
61 -> 158 [arrowhead = none ];
158 -> 63;

159 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
63 -> 159 [arrowhead = none ];
159 -> 64;

160 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
63 -> 160 [arrowhead = none ];
160 -> 65;

161 [label="EVAL with clause\ng([], X187, X187).\nand substitution\nT286 -> []\nT285 -> T337\nT287 -> T338\nT288 -> T339\nT289 -> T340\nT290 -> T341\nT291 -> T342\nT292 -> T343\nX187 -> .(T337, .(T338, .(T339, .(T340, .(T341, .(T342, .(T343, [])))))))\nT294 -> .(T337, .(T338, .(T339, .(T340, .(T341, .(T342, .(T343, [])))))))", fontsize=14, style = filled, fillcolor = lightblue];
64 -> 161 [arrowhead = none ];
161 -> 66;

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

163 [label="EVAL with clause\ng(.(X197, X198), X199, X200) :- g(X198, .(X197, X199), X200).\nand substitution\nX197 -> T364\nX198 -> T365\nT286 -> .(T364, T365)\nT285 -> T366\nT287 -> T367\nT288 -> T368\nT289 -> T369\nT290 -> T370\nT291 -> T371\nT292 -> T372\nX199 -> .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, [])))))))\nT294 -> T374\nX200 -> T374\nT373 -> T374", fontsize=14, style = filled, fillcolor = lightblue];
65 -> 163 [arrowhead = none ];
163 -> 69;

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

165 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
66 -> 165 [arrowhead = none ];
165 -> 68;

166 [label="GENERALIZATION\nT391 <-- .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, [])))))))\n\nNew Knowledge:\nT391 is ground", fontsize=14, style = filled, fillcolor = violet];
69 -> 166 [arrowhead = none ];
166 -> 71;

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

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

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

170 [label="EVAL with clause\ng([], X213, X213).\nand substitution\nT365 -> []\nT364 -> T404\nT391 -> T405\nX213 -> .(T404, T405)\nT374 -> .(T404, T405)", fontsize=14, style = filled, fillcolor = lightblue];
73 -> 170 [arrowhead = none ];
170 -> 75;

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

172 [label="EVAL with clause\ng(.(X223, X224), X225, X226) :- g(X224, .(X223, X225), X226).\nand substitution\nX223 -> T416\nX224 -> T417\nT365 -> .(T416, T417)\nT364 -> T418\nT391 -> T419\nX225 -> .(T418, T419)\nT374 -> T421\nX226 -> T421\nT420 -> T421", fontsize=14, style = filled, fillcolor = lightblue];
74 -> 172 [arrowhead = none ];
172 -> 78;

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

174 [label="SUCCESS", fontsize=14, style = filled, fillcolor = lightgreen];
75 -> 174 [arrowhead = none ];
174 -> 77;

175 [label="INSTANCE with matching:\nT365 -> T417\nT364 -> T416\nT391 -> .(T418, T419)\nT374 -> T421", fontsize=14, style = filled, fillcolor = lightgrey];
78 -> 175 [arrowhead = none , style=dashed];
175 -> 71[style=dashed];

176 [label="BACKTRACK\nfor clause: f(.(A, As), .(B, Bs), RES) :- f(.(B, .(A, As)), Bs, RES)because of non-unification", fontsize=14, style = filled, fillcolor = white];
80 -> 176 [arrowhead = none ];
176 -> 81;

177 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
82 -> 177 [arrowhead = none ];
177 -> 84;

178 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
84 -> 178 [arrowhead = none ];
178 -> 85;

179 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
84 -> 179 [arrowhead = none ];
179 -> 86;

180 [label="EVAL with clause\nf(X261, [], X262) :- g(X261, [], X262).\nand substitution\nT437 -> T457\nT435 -> T458\nT436 -> T459\nX261 -> .(T457, .(T458, T459))\nT438 -> []\nT440 -> T461\nX262 -> T461\nT460 -> T461", fontsize=14, style = filled, fillcolor = lightblue];
85 -> 180 [arrowhead = none ];
180 -> 87;

181 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightblue];
85 -> 181 [arrowhead = none ];
181 -> 88;

182 [label="EVAL with clause\nf(.(X306, X307), .(X308, X309), X310) :- f(.(X308, .(X306, X307)), X309, X310).\nand substitution\nT437 -> T500\nX306 -> T500\nT435 -> T501\nT436 -> T502\nX307 -> .(T501, T502)\nX308 -> T503\nX309 -> T504\nT438 -> .(T503, T504)\nT440 -> T506\nX310 -> T506\nT505 -> T506", fontsize=14, style = filled, fillcolor = lightblue];
86 -> 182 [arrowhead = none ];
182 -> 92;

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

184 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
87 -> 184 [arrowhead = none ];
184 -> 89;

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

186 [label="ONLY EVAL with clause\ng(.(X286, X287), X288, X289) :- g(X287, .(X286, X288), X289).\nand substitution\nT457 -> T479\nX286 -> T479\nT458 -> T480\nT459 -> T481\nX287 -> .(T480, T481)\nX288 -> []\nT461 -> T483\nX289 -> T483\nT482 -> T483", fontsize=14, style = filled, fillcolor = white];
90 -> 186 [arrowhead = none ];
186 -> 91;

187 [label="INSTANCE with matching:\nT22 -> .(T480, T481)\nT21 -> T479\nT24 -> T483", fontsize=14, style = filled, fillcolor = lightgrey];
91 -> 187 [arrowhead = none , style=dashed];
187 -> 13[style=dashed];

188 [label="INSTANCE with matching:\nT1 -> .(T503, .(T500, .(T501, T502)))\nT2 -> T504\nT3 -> T506", fontsize=14, style = filled, fillcolor = lightgrey];
92 -> 188 [arrowhead = none , style=dashed];
188 -> 1[style=dashed];

}

(2) Obligation:

Triples:

g71(.(T416, T417), T418, T419, T421) :- g71(T417, T416, .(T418, T419), T421).
g13(.(T371, .(T370, .(T369, .(T368, .(T367, .(T366, .(T364, T365))))))), T372, T374) :- g71(T365, T364, .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, []))))))), T374).
f1(.(T21, T22), [], T24) :- g13(T22, T21, T24).
f1(.(T480, T481), .(T479, []), T483) :- g13(.(T480, T481), T479, T483).
f1(.(T501, T502), .(T500, .(T503, T504)), T506) :- f1(.(T503, .(T500, .(T501, T502))), T504, T506).

Clauses:

gc71([], T404, T405, .(T404, T405)).
gc71(.(T416, T417), T418, T419, T421) :- gc71(T417, T416, .(T418, T419), T421).
gc13([], T31, .(T31, [])).
gc13(.(T57, []), T58, .(T57, .(T58, []))).
gc13(.(T94, .(T93, [])), T95, .(T93, .(T94, .(T95, [])))).
gc13(.(T141, .(T140, .(T139, []))), T142, .(T139, .(T140, .(T141, .(T142, []))))).
gc13(.(T198, .(T197, .(T196, .(T195, [])))), T199, .(T195, .(T196, .(T197, .(T198, .(T199, [])))))).
gc13(.(T265, .(T264, .(T263, .(T262, .(T261, []))))), T266, .(T261, .(T262, .(T263, .(T264, .(T265, .(T266, []))))))).
gc13(.(T342, .(T341, .(T340, .(T339, .(T338, .(T337, [])))))), T343, .(T337, .(T338, .(T339, .(T340, .(T341, .(T342, .(T343, [])))))))).
gc13(.(T371, .(T370, .(T369, .(T368, .(T367, .(T366, .(T364, T365))))))), T372, T374) :- gc71(T365, T364, .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, []))))))), T374).
fc1([], [], []).
fc1(.(T21, T22), [], T24) :- gc13(T22, T21, T24).
fc1(.(T480, T481), .(T479, []), T483) :- gc13(.(T480, T481), T479, T483).
fc1(.(T501, T502), .(T500, .(T503, T504)), T506) :- fc1(.(T503, .(T500, .(T501, T502))), T504, T506).

Afs:

f1(x1, x2, x3)  =  f1(x1, x2)

(3) TriplesToPiDPProof (SOUND transformation)

We use the technique of [LOPSTR]. With regard to the inferred argument filtering the predicates were used in the following modes:
f1_in: (b,b,f)
g13_in: (b,b,f)
g71_in: (b,b,b,f)
Transforming TRIPLES into the following Term Rewriting System:
Pi DP problem:
The TRS P consists of the following rules:

F1_IN_GGA(.(T21, T22), [], T24) → U3_GGA(T21, T22, T24, g13_in_gga(T22, T21, T24))
F1_IN_GGA(.(T21, T22), [], T24) → G13_IN_GGA(T22, T21, T24)
G13_IN_GGA(.(T371, .(T370, .(T369, .(T368, .(T367, .(T366, .(T364, T365))))))), T372, T374) → U2_GGA(T371, T370, T369, T368, T367, T366, T364, T365, T372, T374, g71_in_ggga(T365, T364, .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, []))))))), T374))
G13_IN_GGA(.(T371, .(T370, .(T369, .(T368, .(T367, .(T366, .(T364, T365))))))), T372, T374) → G71_IN_GGGA(T365, T364, .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, []))))))), T374)
G71_IN_GGGA(.(T416, T417), T418, T419, T421) → U1_GGGA(T416, T417, T418, T419, T421, g71_in_ggga(T417, T416, .(T418, T419), T421))
G71_IN_GGGA(.(T416, T417), T418, T419, T421) → G71_IN_GGGA(T417, T416, .(T418, T419), T421)
F1_IN_GGA(.(T480, T481), .(T479, []), T483) → U4_GGA(T480, T481, T479, T483, g13_in_gga(.(T480, T481), T479, T483))
F1_IN_GGA(.(T480, T481), .(T479, []), T483) → G13_IN_GGA(.(T480, T481), T479, T483)
F1_IN_GGA(.(T501, T502), .(T500, .(T503, T504)), T506) → U5_GGA(T501, T502, T500, T503, T504, T506, f1_in_gga(.(T503, .(T500, .(T501, T502))), T504, T506))
F1_IN_GGA(.(T501, T502), .(T500, .(T503, T504)), T506) → F1_IN_GGA(.(T503, .(T500, .(T501, T502))), T504, T506)

R is empty.
The argument filtering Pi contains the following mapping:
f1_in_gga(x1, x2, x3)  =  f1_in_gga(x1, x2)
.(x1, x2)  =  .(x1, x2)
[]  =  []
g13_in_gga(x1, x2, x3)  =  g13_in_gga(x1, x2)
g71_in_ggga(x1, x2, x3, x4)  =  g71_in_ggga(x1, x2, x3)
F1_IN_GGA(x1, x2, x3)  =  F1_IN_GGA(x1, x2)
U3_GGA(x1, x2, x3, x4)  =  U3_GGA(x1, x2, x4)
G13_IN_GGA(x1, x2, x3)  =  G13_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11)  =  U2_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x11)
G71_IN_GGGA(x1, x2, x3, x4)  =  G71_IN_GGGA(x1, x2, x3)
U1_GGGA(x1, x2, x3, x4, x5, x6)  =  U1_GGGA(x1, x2, x3, x4, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x1, x2, x3, x5)
U5_GGA(x1, x2, x3, x4, x5, x6, x7)  =  U5_GGA(x1, x2, x3, x4, x5, x7)

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

Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES

(4) Obligation:

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

F1_IN_GGA(.(T21, T22), [], T24) → U3_GGA(T21, T22, T24, g13_in_gga(T22, T21, T24))
F1_IN_GGA(.(T21, T22), [], T24) → G13_IN_GGA(T22, T21, T24)
G13_IN_GGA(.(T371, .(T370, .(T369, .(T368, .(T367, .(T366, .(T364, T365))))))), T372, T374) → U2_GGA(T371, T370, T369, T368, T367, T366, T364, T365, T372, T374, g71_in_ggga(T365, T364, .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, []))))))), T374))
G13_IN_GGA(.(T371, .(T370, .(T369, .(T368, .(T367, .(T366, .(T364, T365))))))), T372, T374) → G71_IN_GGGA(T365, T364, .(T366, .(T367, .(T368, .(T369, .(T370, .(T371, .(T372, []))))))), T374)
G71_IN_GGGA(.(T416, T417), T418, T419, T421) → U1_GGGA(T416, T417, T418, T419, T421, g71_in_ggga(T417, T416, .(T418, T419), T421))
G71_IN_GGGA(.(T416, T417), T418, T419, T421) → G71_IN_GGGA(T417, T416, .(T418, T419), T421)
F1_IN_GGA(.(T480, T481), .(T479, []), T483) → U4_GGA(T480, T481, T479, T483, g13_in_gga(.(T480, T481), T479, T483))
F1_IN_GGA(.(T480, T481), .(T479, []), T483) → G13_IN_GGA(.(T480, T481), T479, T483)
F1_IN_GGA(.(T501, T502), .(T500, .(T503, T504)), T506) → U5_GGA(T501, T502, T500, T503, T504, T506, f1_in_gga(.(T503, .(T500, .(T501, T502))), T504, T506))
F1_IN_GGA(.(T501, T502), .(T500, .(T503, T504)), T506) → F1_IN_GGA(.(T503, .(T500, .(T501, T502))), T504, T506)

R is empty.
The argument filtering Pi contains the following mapping:
f1_in_gga(x1, x2, x3)  =  f1_in_gga(x1, x2)
.(x1, x2)  =  .(x1, x2)
[]  =  []
g13_in_gga(x1, x2, x3)  =  g13_in_gga(x1, x2)
g71_in_ggga(x1, x2, x3, x4)  =  g71_in_ggga(x1, x2, x3)
F1_IN_GGA(x1, x2, x3)  =  F1_IN_GGA(x1, x2)
U3_GGA(x1, x2, x3, x4)  =  U3_GGA(x1, x2, x4)
G13_IN_GGA(x1, x2, x3)  =  G13_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11)  =  U2_GGA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x11)
G71_IN_GGGA(x1, x2, x3, x4)  =  G71_IN_GGGA(x1, x2, x3)
U1_GGGA(x1, x2, x3, x4, x5, x6)  =  U1_GGGA(x1, x2, x3, x4, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x1, x2, x3, x5)
U5_GGA(x1, x2, x3, x4, x5, x6, x7)  =  U5_GGA(x1, x2, x3, x4, x5, x7)

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

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 8 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

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

G71_IN_GGGA(.(T416, T417), T418, T419, T421) → G71_IN_GGGA(T417, T416, .(T418, T419), T421)

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

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

(8) PiDPToQDPProof (SOUND transformation)

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

(9) Obligation:

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

G71_IN_GGGA(.(T416, T417), T418, T419) → G71_IN_GGGA(T417, T416, .(T418, T419))

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

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

• G71_IN_GGGA(.(T416, T417), T418, T419) → G71_IN_GGGA(T417, T416, .(T418, T419))
  The graph contains the following edges 1 > 1, 1 > 2

(11) YES

(12) Obligation:

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

F1_IN_GGA(.(T501, T502), .(T500, .(T503, T504)), T506) → F1_IN_GGA(.(T503, .(T500, .(T501, T502))), T504, T506)

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

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

(13) PiDPToQDPProof (SOUND transformation)

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

(14) Obligation:

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

F1_IN_GGA(.(T501, T502), .(T500, .(T503, T504))) → F1_IN_GGA(.(T503, .(T500, .(T501, T502))), T504)

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

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

• F1_IN_GGA(.(T501, T502), .(T500, .(T503, T504))) → F1_IN_GGA(.(T503, .(T500, .(T501, T502))), T504)
  The graph contains the following edges 2 > 2

(16) YES