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

(0) Obligation:

Clauses:

goal(X) :- ','(s2t(X, T), tree(T)).
tree(nil) :- !.
tree(X) :- ','(left(T, L), ','(right(T, R), ','(tree(L), tree(R)))).
s2t(0, L) :- ','(!, eq(L, nil)).
s2t(X, node(T, X1, T)) :- ','(p(X, P), s2t(P, T)).
s2t(X, node(nil, X2, T)) :- ','(p(X, P), s2t(P, T)).
s2t(X, node(T, X3, nil)) :- ','(p(X, P), s2t(P, T)).
s2t(X, node(nil, X4, nil)).
left(nil, nil).
left(node(L, X5, X6), L).
right(nil, nil).
right(node(X7, X8, R), R).
p(0, 0).
p(s(X), X).
eq(X, X).

Query: goal(g)

(1) PrologToPrologProblemTransformerProof (SOUND transformation)

Built Prolog problem from termination graph ICLP10.

digraph dp_graph {
node [outthreshold=100, inthreshold=100];
1 [label="1: goal(T1)\n\nT1 is ground", fontsize=16, style=filled, fillcolor=lightyellow, color=red];
2 [label="2: goal(T1), SCOPE: 1, CLAUSE: 0\n\nT1 is ground", fontsize=16, style=filled, fillcolor=lightyellow];
3 [label="3: ','(s2t(T3, X11), tree(X11))\n\nT3 is ground\nX11 is free", fontsize=16, style=filled, fillcolor=lightyellow];
4 [label="4: ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 3 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 4 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 5 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 6 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 7\n\nT3 is ground\nX11 is free", fontsize=16, style=filled, fillcolor=lightyellow];
5 [label="5: ','(','(!_2, eq(X17, nil)), tree(X17)) | ','(s2t(0, X11), tree(X11)), SCOPE: 2, CLAUSE: 4 | ','(s2t(0, X11), tree(X11)), SCOPE: 2, CLAUSE: 5 | ','(s2t(0, X11), tree(X11)), SCOPE: 2, CLAUSE: 6 | ','(s2t(0, X11), tree(X11)), SCOPE: 2, CLAUSE: 7\n\nX11 is free\nX17 is free", fontsize=16, style=filled, fillcolor=lightyellow];
6 [label="6: ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 4 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 5 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 6 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 7\n\nT3 is ground\nX11 is free\nX16 is free\ns2t(T3, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
7 [label="7: ','(eq(X17, nil), tree(X17))\n\nX17 is free", fontsize=16, style=filled, fillcolor=lightyellow];
8 [label="8: ','(eq(X17, nil), tree(X17)), SCOPE: 3, CLAUSE: 14\n\nX17 is free", fontsize=16, style=filled, fillcolor=lightyellow];
9 [label="9: tree(nil)\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
10 [label="10: tree(nil), SCOPE: 4, CLAUSE: 1 | tree(nil), SCOPE: 4, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
11 [label="11: !_4 | tree(nil), SCOPE: 4, CLAUSE: 2\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
12 [label="12: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
13 [label="13: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
14 [label="14: ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 4\n\nT3 is ground\nX11 is free\nX16 is free\ns2t(T3, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
15 [label="15: ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 5 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 6 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 7\n\nT3 is ground\nX11 is free\nX16 is free\ns2t(T3, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
16 [label="16: ','(','(p(T8, X53), s2t(X53, X54)), tree(node(X54, X55, X54)))\n\nT8 is ground\nX11 is free\nX16 is free\nX54 is free\nX55 is free\nX53 is free\ns2t(T8, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
17 [label="17: ','(','(p(T8, X53), s2t(X53, X54)), tree(node(X54, X55, X54))), SCOPE: 5, CLAUSE: 12 | ','(','(p(T8, X53), s2t(X53, X54)), tree(node(X54, X55, X54))), SCOPE: 5, CLAUSE: 13\n\nT8 is ground\nX11 is free\nX16 is free\nX54 is free\nX55 is free\nX53 is free\ns2t(T8, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
18 [label="18: ','(','(p(T8, X53), s2t(X53, X54)), tree(node(X54, X55, X54))), SCOPE: 5, CLAUSE: 13\n\nT8 is ground\nX11 is free\nX16 is free\nX54 is free\nX55 is free\nX53 is free\ns2t(T8, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
19 [label="19: ','(s2t(T11, X54), tree(node(X54, X55, X54)))\n\nT11 is ground\nX54 is free\nX55 is free", fontsize=16, style=filled, fillcolor=lightyellow];
20 [label="20: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
21 [label="21: s2t(T11, X54)\n\nT11 is ground\nX54 is free", fontsize=16, style=filled, fillcolor=lightyellow];
22 [label="22: tree(node(T12, X55, T12))\n\nX55 is free", fontsize=16, style=filled, fillcolor=lightyellow];
23 [label="23: s2t(T11, X54), SCOPE: 6, CLAUSE: 3 | s2t(T11, X54), SCOPE: 6, CLAUSE: 4 | s2t(T11, X54), SCOPE: 6, CLAUSE: 5 | s2t(T11, X54), SCOPE: 6, CLAUSE: 6 | s2t(T11, X54), SCOPE: 6, CLAUSE: 7\n\nT11 is ground\nX54 is free", fontsize=16, style=filled, fillcolor=lightyellow];
24 [label="24: ','(!_6, eq(X70, nil)) | s2t(0, X54), SCOPE: 6, CLAUSE: 4 | s2t(0, X54), SCOPE: 6, CLAUSE: 5 | s2t(0, X54), SCOPE: 6, CLAUSE: 6 | s2t(0, X54), SCOPE: 6, CLAUSE: 7\n\nX54 is free\nX70 is free", fontsize=16, style=filled, fillcolor=lightyellow];
25 [label="25: s2t(T11, X54), SCOPE: 6, CLAUSE: 4 | s2t(T11, X54), SCOPE: 6, CLAUSE: 5 | s2t(T11, X54), SCOPE: 6, CLAUSE: 6 | s2t(T11, X54), SCOPE: 6, CLAUSE: 7\n\nT11 is ground\nX54 is free\nX69 is free\ns2t(T11, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
26 [label="26: eq(X70, nil)\n\nX70 is free", fontsize=16, style=filled, fillcolor=lightyellow];
27 [label="27: eq(X70, nil), SCOPE: 7, CLAUSE: 14\n\nX70 is free", fontsize=16, style=filled, fillcolor=lightyellow];
28 [label="28: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
29 [label="29: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
30 [label="30: s2t(T11, X54), SCOPE: 6, CLAUSE: 4\n\nT11 is ground\nX54 is free\nX69 is free\ns2t(T11, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
31 [label="31: s2t(T11, X54), SCOPE: 6, CLAUSE: 5 | s2t(T11, X54), SCOPE: 6, CLAUSE: 6 | s2t(T11, X54), SCOPE: 6, CLAUSE: 7\n\nT11 is ground\nX54 is free\nX69 is free\ns2t(T11, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
32 [label="32: ','(p(T17, X106), s2t(X106, X107))\n\nT17 is ground\nX54 is free\nX69 is free\nX107 is free\nX106 is free\ns2t(T17, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
33 [label="33: ','(p(T17, X106), s2t(X106, X107)), SCOPE: 8, CLAUSE: 12 | ','(p(T17, X106), s2t(X106, X107)), SCOPE: 8, CLAUSE: 13\n\nT17 is ground\nX54 is free\nX69 is free\nX107 is free\nX106 is free\ns2t(T17, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
34 [label="34: ','(p(T17, X106), s2t(X106, X107)), SCOPE: 8, CLAUSE: 13\n\nT17 is ground\nX54 is free\nX69 is free\nX107 is free\nX106 is free\ns2t(T17, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
35 [label="35: s2t(T20, X107)\n\nT20 is ground\nX107 is free", fontsize=16, style=filled, fillcolor=lightyellow];
36 [label="36: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
37 [label="37: s2t(T11, X54), SCOPE: 6, CLAUSE: 5\n\nT11 is ground\nX54 is free\nX69 is free\ns2t(T11, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
38 [label="38: s2t(T11, X54), SCOPE: 6, CLAUSE: 6 | s2t(T11, X54), SCOPE: 6, CLAUSE: 7\n\nT11 is ground\nX54 is free\nX69 is free\ns2t(T11, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
39 [label="39: ','(p(T25, X145), s2t(X145, X147))\n\nT25 is ground\nX54 is free\nX69 is free\nX147 is free\nX145 is free\ns2t(T25, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
40 [label="40: ','(p(T25, X145), s2t(X145, X147)), SCOPE: 9, CLAUSE: 12 | ','(p(T25, X145), s2t(X145, X147)), SCOPE: 9, CLAUSE: 13\n\nT25 is ground\nX54 is free\nX69 is free\nX147 is free\nX145 is free\ns2t(T25, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
41 [label="41: ','(p(T25, X145), s2t(X145, X147)), SCOPE: 9, CLAUSE: 13\n\nT25 is ground\nX54 is free\nX69 is free\nX147 is free\nX145 is free\ns2t(T25, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
42 [label="42: s2t(T28, X147)\n\nT28 is ground\nX147 is free", fontsize=16, style=filled, fillcolor=lightyellow];
43 [label="43: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
44 [label="44: s2t(T11, X54), SCOPE: 6, CLAUSE: 6\n\nT11 is ground\nX54 is free\nX69 is free\ns2t(T11, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
45 [label="45: s2t(T11, X54), SCOPE: 6, CLAUSE: 7\n\nT11 is ground\nX54 is free\nX69 is free\ns2t(T11, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
46 [label="46: ','(p(T33, X184), s2t(X184, X185))\n\nT33 is ground\nX54 is free\nX69 is free\nX185 is free\nX184 is free\ns2t(T33, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
47 [label="47: ','(p(T33, X184), s2t(X184, X185)), SCOPE: 10, CLAUSE: 12 | ','(p(T33, X184), s2t(X184, X185)), SCOPE: 10, CLAUSE: 13\n\nT33 is ground\nX54 is free\nX69 is free\nX185 is free\nX184 is free\ns2t(T33, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
48 [label="48: ','(p(T33, X184), s2t(X184, X185)), SCOPE: 10, CLAUSE: 13\n\nT33 is ground\nX54 is free\nX69 is free\nX185 is free\nX184 is free\ns2t(T33, X54) !=? s2t(0, X69)", fontsize=16, style=filled, fillcolor=lightyellow];
49 [label="49: s2t(T36, X185)\n\nT36 is ground\nX185 is free", fontsize=16, style=filled, fillcolor=lightyellow];
50 [label="50: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
51 [label="51: true\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
52 [label="52: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
53 [label="53: tree(node(T12, X55, T12)), SCOPE: 11, CLAUSE: 1 | tree(node(T12, X55, T12)), SCOPE: 11, CLAUSE: 2\n\nX55 is free", fontsize=16, style=filled, fillcolor=lightyellow];
54 [label="54: tree(node(T12, X55, T12)), SCOPE: 11, CLAUSE: 2\n\nX55 is free", fontsize=16, style=filled, fillcolor=lightyellow];
55 [label="55: ','(left(X211, X212), ','(right(X211, X213), ','(tree(X212), tree(X213))))\n\nX211 is free\nX212 is free\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
56 [label="56: ','(left(X211, X212), ','(right(X211, X213), ','(tree(X212), tree(X213)))), SCOPE: 12, CLAUSE: 8 | ','(left(X211, X212), ','(right(X211, X213), ','(tree(X212), tree(X213)))), SCOPE: 12, CLAUSE: 9\n\nX211 is free\nX212 is free\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
57 [label="57: ','(left(X211, X212), ','(right(X211, X213), ','(tree(X212), tree(X213)))), SCOPE: 12, CLAUSE: 8\n\nX211 is free\nX212 is free\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
58 [label="58: ','(left(X211, X212), ','(right(X211, X213), ','(tree(X212), tree(X213)))), SCOPE: 12, CLAUSE: 9\n\nX211 is free\nX212 is free\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
59 [label="59: ','(right(nil, X213), ','(tree(nil), tree(X213)))\n\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
60 [label="60: ','(right(nil, X213), ','(tree(nil), tree(X213))), SCOPE: 13, CLAUSE: 10 | ','(right(nil, X213), ','(tree(nil), tree(X213))), SCOPE: 13, CLAUSE: 11\n\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
61 [label="61: ','(right(nil, X213), ','(tree(nil), tree(X213))), SCOPE: 13, CLAUSE: 10\n\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
62 [label="62: ','(right(nil, X213), ','(tree(nil), tree(X213))), SCOPE: 13, CLAUSE: 11\n\nX213 is free", fontsize=16, style=filled, fillcolor=lightyellow];
63 [label="63: ','(tree(nil), tree(nil))\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
64 [label="64: tree(nil)\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
65 [label="65: tree(nil)\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
66 [label="66: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
67 [label="67: ','(right(node(X233, X234, X235), X213), ','(tree(X233), tree(X213)))\n\nX213 is free\nX233 is free\nX234 is free\nX235 is free", fontsize=16, style=filled, fillcolor=lightyellow];
68 [label="68: ','(right(node(X233, X234, X235), X213), ','(tree(X233), tree(X213))), SCOPE: 14, CLAUSE: 10 | ','(right(node(X233, X234, X235), X213), ','(tree(X233), tree(X213))), SCOPE: 14, CLAUSE: 11\n\nX213 is free\nX233 is free\nX234 is free\nX235 is free", fontsize=16, style=filled, fillcolor=lightyellow];
69 [label="69: ','(right(node(X233, X234, X235), X213), ','(tree(X233), tree(X213))), SCOPE: 14, CLAUSE: 11\n\nX213 is free\nX233 is free\nX234 is free\nX235 is free", fontsize=16, style=filled, fillcolor=lightyellow];
70 [label="70: ','(tree(X251), tree(X253))\n\nX251 is free\nX253 is free", fontsize=16, style=filled, fillcolor=lightyellow];
71 [label="71: tree(X251)\n\nX251 is free", fontsize=16, style=filled, fillcolor=lightyellow];
72 [label="72: tree(X253)\n\nX253 is free", fontsize=16, style=filled, fillcolor=lightyellow];
73 [label="73: tree(X253), SCOPE: 15, CLAUSE: 1 | tree(X253), SCOPE: 15, CLAUSE: 2\n\nX253 is free", fontsize=16, style=filled, fillcolor=lightyellow];
74 [label="74: !_15 | tree(X253), SCOPE: 15, CLAUSE: 2\n\nX253 is free", 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: ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 5\n\nT3 is ground\nX11 is free\nX16 is free\ns2t(T3, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
78 [label="78: ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 6 | ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 7\n\nT3 is ground\nX11 is free\nX16 is free\ns2t(T3, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
79 [label="79: ','(','(p(T48, X283), s2t(X283, X285)), tree(node(nil, X284, X285)))\n\nT48 is ground\nX11 is free\nX16 is free\nX284 is free\nX285 is free\nX283 is free\ns2t(T48, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
80 [label="80: ','(','(p(T48, X283), s2t(X283, X285)), tree(node(nil, X284, X285))), SCOPE: 16, CLAUSE: 12 | ','(','(p(T48, X283), s2t(X283, X285)), tree(node(nil, X284, X285))), SCOPE: 16, CLAUSE: 13\n\nT48 is ground\nX11 is free\nX16 is free\nX284 is free\nX285 is free\nX283 is free\ns2t(T48, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
81 [label="81: ','(','(p(T48, X283), s2t(X283, X285)), tree(node(nil, X284, X285))), SCOPE: 16, CLAUSE: 13\n\nT48 is ground\nX11 is free\nX16 is free\nX284 is free\nX285 is free\nX283 is free\ns2t(T48, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
82 [label="82: ','(s2t(T51, X285), tree(node(nil, X284, X285)))\n\nT51 is ground\nX284 is free\nX285 is free", fontsize=16, style=filled, fillcolor=lightyellow];
83 [label="83: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
84 [label="84: s2t(T51, X285)\n\nT51 is ground\nX285 is free", fontsize=16, style=filled, fillcolor=lightyellow];
85 [label="85: tree(node(nil, X284, T52))\n\nX284 is free", fontsize=16, style=filled, fillcolor=lightyellow];
86 [label="86: tree(node(nil, X284, T52)), SCOPE: 17, CLAUSE: 1 | tree(node(nil, X284, T52)), SCOPE: 17, CLAUSE: 2\n\nX284 is free", fontsize=16, style=filled, fillcolor=lightyellow];
87 [label="87: tree(node(nil, X284, T52)), SCOPE: 17, CLAUSE: 2\n\nX284 is free", fontsize=16, style=filled, fillcolor=lightyellow];
88 [label="88: ','(left(X303, X304), ','(right(X303, X305), ','(tree(X304), tree(X305))))\n\nX303 is free\nX304 is free\nX305 is free", fontsize=16, style=filled, fillcolor=lightyellow];
89 [label="89: ','(left(X303, X304), ','(right(X303, X305), ','(tree(X304), tree(X305)))), SCOPE: 18, CLAUSE: 8 | ','(left(X303, X304), ','(right(X303, X305), ','(tree(X304), tree(X305)))), SCOPE: 18, CLAUSE: 9\n\nX303 is free\nX304 is free\nX305 is free", fontsize=16, style=filled, fillcolor=lightyellow];
90 [label="90: ','(left(X303, X304), ','(right(X303, X305), ','(tree(X304), tree(X305)))), SCOPE: 18, CLAUSE: 8\n\nX303 is free\nX304 is free\nX305 is free", fontsize=16, style=filled, fillcolor=lightyellow];
91 [label="91: ','(left(X303, X304), ','(right(X303, X305), ','(tree(X304), tree(X305)))), SCOPE: 18, CLAUSE: 9\n\nX303 is free\nX304 is free\nX305 is free", fontsize=16, style=filled, fillcolor=lightyellow];
92 [label="92: ','(right(nil, X305), ','(tree(nil), tree(X305)))\n\nX305 is free", fontsize=16, style=filled, fillcolor=lightyellow];
93 [label="93: ','(right(nil, X305), ','(tree(nil), tree(X305))), SCOPE: 19, CLAUSE: 10 | ','(right(nil, X305), ','(tree(nil), tree(X305))), SCOPE: 19, CLAUSE: 11\n\nX305 is free", fontsize=16, style=filled, fillcolor=lightyellow];
94 [label="94: ','(right(nil, X305), ','(tree(nil), tree(X305))), SCOPE: 19, CLAUSE: 10\n\nX305 is free", fontsize=16, style=filled, fillcolor=lightyellow];
95 [label="95: ','(right(nil, X305), ','(tree(nil), tree(X305))), SCOPE: 19, CLAUSE: 11\n\nX305 is free", fontsize=16, style=filled, fillcolor=lightyellow];
96 [label="96: ','(tree(nil), tree(nil))\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
97 [label="97: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
98 [label="98: ','(right(node(X325, X326, X327), X305), ','(tree(X325), tree(X305)))\n\nX305 is free\nX325 is free\nX326 is free\nX327 is free", fontsize=16, style=filled, fillcolor=lightyellow];
99 [label="99: ','(right(node(X325, X326, X327), X305), ','(tree(X325), tree(X305))), SCOPE: 20, CLAUSE: 10 | ','(right(node(X325, X326, X327), X305), ','(tree(X325), tree(X305))), SCOPE: 20, CLAUSE: 11\n\nX305 is free\nX325 is free\nX326 is free\nX327 is free", fontsize=16, style=filled, fillcolor=lightyellow];
100 [label="100: ','(right(node(X325, X326, X327), X305), ','(tree(X325), tree(X305))), SCOPE: 20, CLAUSE: 11\n\nX305 is free\nX325 is free\nX326 is free\nX327 is free", fontsize=16, style=filled, fillcolor=lightyellow];
101 [label="101: ','(tree(X343), tree(X345))\n\nX343 is free\nX345 is free", fontsize=16, style=filled, fillcolor=lightyellow];
102 [label="102: ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 6\n\nT3 is ground\nX11 is free\nX16 is free\ns2t(T3, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
103 [label="103: ','(s2t(T3, X11), tree(X11)), SCOPE: 2, CLAUSE: 7\n\nT3 is ground\nX11 is free\nX16 is free\ns2t(T3, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
104 [label="104: ','(','(p(T60, X375), s2t(X375, X376)), tree(node(X376, X377, nil)))\n\nT60 is ground\nX11 is free\nX16 is free\nX376 is free\nX377 is free\nX375 is free\ns2t(T60, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
105 [label="105: ','(','(p(T60, X375), s2t(X375, X376)), tree(node(X376, X377, nil))), SCOPE: 21, CLAUSE: 12 | ','(','(p(T60, X375), s2t(X375, X376)), tree(node(X376, X377, nil))), SCOPE: 21, CLAUSE: 13\n\nT60 is ground\nX11 is free\nX16 is free\nX376 is free\nX377 is free\nX375 is free\ns2t(T60, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
106 [label="106: ','(','(p(T60, X375), s2t(X375, X376)), tree(node(X376, X377, nil))), SCOPE: 21, CLAUSE: 13\n\nT60 is ground\nX11 is free\nX16 is free\nX376 is free\nX377 is free\nX375 is free\ns2t(T60, X11) !=? s2t(0, X16)", fontsize=16, style=filled, fillcolor=lightyellow];
107 [label="107: ','(s2t(T63, X376), tree(node(X376, X377, nil)))\n\nT63 is ground\nX376 is free\nX377 is free", fontsize=16, style=filled, fillcolor=lightyellow];
108 [label="108: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
109 [label="109: s2t(T63, X376)\n\nT63 is ground\nX376 is free", fontsize=16, style=filled, fillcolor=lightyellow];
110 [label="110: tree(node(T64, X377, nil))\n\nX377 is free", fontsize=16, style=filled, fillcolor=lightyellow];
111 [label="111: tree(node(T64, X377, nil)), SCOPE: 22, CLAUSE: 1 | tree(node(T64, X377, nil)), SCOPE: 22, CLAUSE: 2\n\nX377 is free", fontsize=16, style=filled, fillcolor=lightyellow];
112 [label="112: tree(node(T64, X377, nil)), SCOPE: 22, CLAUSE: 2\n\nX377 is free", fontsize=16, style=filled, fillcolor=lightyellow];
113 [label="113: ','(left(X395, X396), ','(right(X395, X397), ','(tree(X396), tree(X397))))\n\nX395 is free\nX396 is free\nX397 is free", fontsize=16, style=filled, fillcolor=lightyellow];
114 [label="114: ','(left(X395, X396), ','(right(X395, X397), ','(tree(X396), tree(X397)))), SCOPE: 23, CLAUSE: 8 | ','(left(X395, X396), ','(right(X395, X397), ','(tree(X396), tree(X397)))), SCOPE: 23, CLAUSE: 9\n\nX395 is free\nX396 is free\nX397 is free", fontsize=16, style=filled, fillcolor=lightyellow];
115 [label="115: ','(left(X395, X396), ','(right(X395, X397), ','(tree(X396), tree(X397)))), SCOPE: 23, CLAUSE: 8\n\nX395 is free\nX396 is free\nX397 is free", fontsize=16, style=filled, fillcolor=lightyellow];
116 [label="116: ','(left(X395, X396), ','(right(X395, X397), ','(tree(X396), tree(X397)))), SCOPE: 23, CLAUSE: 9\n\nX395 is free\nX396 is free\nX397 is free", fontsize=16, style=filled, fillcolor=lightyellow];
117 [label="117: ','(right(nil, X397), ','(tree(nil), tree(X397)))\n\nX397 is free", fontsize=16, style=filled, fillcolor=lightyellow];
118 [label="118: ','(right(nil, X397), ','(tree(nil), tree(X397))), SCOPE: 24, CLAUSE: 10 | ','(right(nil, X397), ','(tree(nil), tree(X397))), SCOPE: 24, CLAUSE: 11\n\nX397 is free", fontsize=16, style=filled, fillcolor=lightyellow];
119 [label="119: ','(right(nil, X397), ','(tree(nil), tree(X397))), SCOPE: 24, CLAUSE: 10\n\nX397 is free", fontsize=16, style=filled, fillcolor=lightyellow];
120 [label="120: ','(right(nil, X397), ','(tree(nil), tree(X397))), SCOPE: 24, CLAUSE: 11\n\nX397 is free", fontsize=16, style=filled, fillcolor=lightyellow];
121 [label="121: ','(tree(nil), tree(nil))\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
122 [label="122: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
123 [label="123: ','(right(node(X417, X418, X419), X397), ','(tree(X417), tree(X397)))\n\nX397 is free\nX417 is free\nX418 is free\nX419 is free", fontsize=16, style=filled, fillcolor=lightyellow];
124 [label="124: ','(right(node(X417, X418, X419), X397), ','(tree(X417), tree(X397))), SCOPE: 25, CLAUSE: 10 | ','(right(node(X417, X418, X419), X397), ','(tree(X417), tree(X397))), SCOPE: 25, CLAUSE: 11\n\nX397 is free\nX417 is free\nX418 is free\nX419 is free", fontsize=16, style=filled, fillcolor=lightyellow];
125 [label="125: ','(right(node(X417, X418, X419), X397), ','(tree(X417), tree(X397))), SCOPE: 25, CLAUSE: 11\n\nX397 is free\nX417 is free\nX418 is free\nX419 is free", fontsize=16, style=filled, fillcolor=lightyellow];
126 [label="126: ','(tree(X435), tree(X437))\n\nX435 is free\nX437 is free", fontsize=16, style=filled, fillcolor=lightyellow];
127 [label="127: tree(node(nil, X446, nil))\n\nX446 is free", fontsize=16, style=filled, fillcolor=lightyellow];
128 [label="128: tree(node(nil, X446, nil)), SCOPE: 26, CLAUSE: 1 | tree(node(nil, X446, nil)), SCOPE: 26, CLAUSE: 2\n\nX446 is free", fontsize=16, style=filled, fillcolor=lightyellow];
129 [label="129: tree(node(nil, X446, nil)), SCOPE: 26, CLAUSE: 2\n\nX446 is free", fontsize=16, style=filled, fillcolor=lightyellow];
130 [label="130: ','(left(X455, X456), ','(right(X455, X457), ','(tree(X456), tree(X457))))\n\nX455 is free\nX456 is free\nX457 is free", fontsize=16, style=filled, fillcolor=lightyellow];
131 [label="131: ','(left(X455, X456), ','(right(X455, X457), ','(tree(X456), tree(X457)))), SCOPE: 27, CLAUSE: 8 | ','(left(X455, X456), ','(right(X455, X457), ','(tree(X456), tree(X457)))), SCOPE: 27, CLAUSE: 9\n\nX455 is free\nX456 is free\nX457 is free", fontsize=16, style=filled, fillcolor=lightyellow];
132 [label="132: ','(left(X455, X456), ','(right(X455, X457), ','(tree(X456), tree(X457)))), SCOPE: 27, CLAUSE: 8\n\nX455 is free\nX456 is free\nX457 is free", fontsize=16, style=filled, fillcolor=lightyellow];
133 [label="133: ','(left(X455, X456), ','(right(X455, X457), ','(tree(X456), tree(X457)))), SCOPE: 27, CLAUSE: 9\n\nX455 is free\nX456 is free\nX457 is free", fontsize=16, style=filled, fillcolor=lightyellow];
134 [label="134: ','(right(nil, X457), ','(tree(nil), tree(X457)))\n\nX457 is free", fontsize=16, style=filled, fillcolor=lightyellow];
135 [label="135: ','(right(nil, X457), ','(tree(nil), tree(X457))), SCOPE: 28, CLAUSE: 10 | ','(right(nil, X457), ','(tree(nil), tree(X457))), SCOPE: 28, CLAUSE: 11\n\nX457 is free", fontsize=16, style=filled, fillcolor=lightyellow];
136 [label="136: ','(right(nil, X457), ','(tree(nil), tree(X457))), SCOPE: 28, CLAUSE: 10\n\nX457 is free", fontsize=16, style=filled, fillcolor=lightyellow];
137 [label="137: ','(right(nil, X457), ','(tree(nil), tree(X457))), SCOPE: 28, CLAUSE: 11\n\nX457 is free", fontsize=16, style=filled, fillcolor=lightyellow];
138 [label="138: ','(tree(nil), tree(nil))\n\n", fontsize=16, style=filled, fillcolor=lightyellow];
139 [label="139: \n\n", fontsize=16, style=filled, fillcolor=lightyellow];
140 [label="140: ','(right(node(X477, X478, X479), X457), ','(tree(X477), tree(X457)))\n\nX457 is free\nX477 is free\nX478 is free\nX479 is free", fontsize=16, style=filled, fillcolor=lightyellow];
141 [label="141: ','(right(node(X477, X478, X479), X457), ','(tree(X477), tree(X457))), SCOPE: 29, CLAUSE: 10 | ','(right(node(X477, X478, X479), X457), ','(tree(X477), tree(X457))), SCOPE: 29, CLAUSE: 11\n\nX457 is free\nX477 is free\nX478 is free\nX479 is free", fontsize=16, style=filled, fillcolor=lightyellow];
142 [label="142: ','(right(node(X477, X478, X479), X457), ','(tree(X477), tree(X457))), SCOPE: 29, CLAUSE: 11\n\nX457 is free\nX477 is free\nX478 is free\nX479 is free", fontsize=16, style=filled, fillcolor=lightyellow];
143 [label="143: ','(tree(X495), tree(X497))\n\nX495 is free\nX497 is free", fontsize=16, style=filled, fillcolor=lightyellow];
144 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
1 -> 144 [arrowhead = none ];
144 -> 2;

145 [label="ONLY EVAL with clause\ngoal(X10) :- ','(s2t(X10, X11), tree(X11)).\nand substitutionT1 -> T3,\nX10 -> T3", fontsize=14, style = filled, fillcolor = lightblue];
2 -> 145 [arrowhead = none ];
145 -> 3;

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

147 [label="EVAL with clause\ns2t(0, X16) :- ','(!_2, eq(X16, nil)).\nand substitutionT3 -> 0,\nX11 -> X17,\nX16 -> X17", fontsize=14, style = filled, fillcolor = lightblue];
4 -> 147 [arrowhead = none ];
147 -> 5;

148 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
4 -> 148 [arrowhead = none ];
148 -> 6;

149 [label="CUT", fontsize=14, style = filled, fillcolor = lightgreen];
5 -> 149 [arrowhead = none ];
149 -> 7;

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

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

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

153 [label="ONLY EVAL with clause\neq(X22, X22).\nand substitutionX17 -> nil,\nX22 -> nil,\nX23 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
8 -> 153 [arrowhead = none ];
153 -> 9;

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

155 [label="ONLY EVAL with clause\ntree(nil) :- !_4.\nand substitution", fontsize=14, style = filled, fillcolor = lightblue];
10 -> 155 [arrowhead = none ];
155 -> 11;

156 [label="CUT", fontsize=14, style = filled, fillcolor = lightgreen];
11 -> 156 [arrowhead = none ];
156 -> 12;

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

158 [label="ONLY EVAL with clause\ns2t(X50, node(X51, X52, X51)) :- ','(p(X50, X53), s2t(X53, X51)).\nand substitutionT3 -> T8,\nX50 -> T8,\nX51 -> X54,\nX52 -> X55,\nX11 -> node(X54, X55, X54)", fontsize=14, style = filled, fillcolor = lightblue];
14 -> 158 [arrowhead = none ];
158 -> 16;

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

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

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

162 [label="BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2t(T8, X11), s2t(0, X16))", fontsize=14, style = filled, fillcolor = lightgreen];
17 -> 162 [arrowhead = none ];
162 -> 18;

163 [label="EVAL with clause\np(s(X60), X60).\nand substitutionX60 -> T11,\nT8 -> s(T11),\nX53 -> T11", fontsize=14, style = filled, fillcolor = lightblue];
18 -> 163 [arrowhead = none ];
163 -> 19;

164 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
18 -> 164 [arrowhead = none ];
164 -> 20;

165 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
19 -> 165 [arrowhead = none ];
165 -> 21;

166 [label="SPLIT 2\nnew knowledge:\nT11 is ground\nreplacements:X54 -> T12", fontsize=14, style = filled, fillcolor = violet];
19 -> 166 [arrowhead = none ];
166 -> 22;

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

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

169 [label="EVAL with clause\ns2t(0, X69) :- ','(!_6, eq(X69, nil)).\nand substitutionT11 -> 0,\nX54 -> X70,\nX69 -> X70", fontsize=14, style = filled, fillcolor = lightblue];
23 -> 169 [arrowhead = none ];
169 -> 24;

170 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
23 -> 170 [arrowhead = none ];
170 -> 25;

171 [label="CUT", fontsize=14, style = filled, fillcolor = lightgreen];
24 -> 171 [arrowhead = none ];
171 -> 26;

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

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

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

175 [label="ONLY EVAL with clause\neq(X75, X75).\nand substitutionX70 -> nil,\nX75 -> nil,\nX76 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
27 -> 175 [arrowhead = none ];
175 -> 28;

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

177 [label="ONLY EVAL with clause\ns2t(X103, node(X104, X105, X104)) :- ','(p(X103, X106), s2t(X106, X104)).\nand substitutionT11 -> T17,\nX103 -> T17,\nX104 -> X107,\nX105 -> X108,\nX54 -> node(X107, X108, X107)", fontsize=14, style = filled, fillcolor = lightblue];
30 -> 177 [arrowhead = none ];
177 -> 32;

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

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

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

181 [label="BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2t(T17, X54), s2t(0, X69))", fontsize=14, style = filled, fillcolor = lightgreen];
33 -> 181 [arrowhead = none ];
181 -> 34;

182 [label="EVAL with clause\np(s(X113), X113).\nand substitutionX113 -> T20,\nT17 -> s(T20),\nX106 -> T20", fontsize=14, style = filled, fillcolor = lightblue];
34 -> 182 [arrowhead = none ];
182 -> 35;

183 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
34 -> 183 [arrowhead = none ];
183 -> 36;

184 [label="INSTANCE with matching:\nT11 -> T20\nX54 -> X107", fontsize=14, style = filled, fillcolor = lightgrey];
35 -> 184 [arrowhead = none , style=dashed];
184 -> 21[style=dashed];

185 [label="ONLY EVAL with clause\ns2t(X142, node(nil, X143, X144)) :- ','(p(X142, X145), s2t(X145, X144)).\nand substitutionT11 -> T25,\nX142 -> T25,\nX143 -> X146,\nX144 -> X147,\nX54 -> node(nil, X146, X147)", fontsize=14, style = filled, fillcolor = lightblue];
37 -> 185 [arrowhead = none ];
185 -> 39;

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

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

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

189 [label="BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2t(T25, X54), s2t(0, X69))", fontsize=14, style = filled, fillcolor = lightgreen];
40 -> 189 [arrowhead = none ];
189 -> 41;

190 [label="EVAL with clause\np(s(X152), X152).\nand substitutionX152 -> T28,\nT25 -> s(T28),\nX145 -> T28", fontsize=14, style = filled, fillcolor = lightblue];
41 -> 190 [arrowhead = none ];
190 -> 42;

191 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
41 -> 191 [arrowhead = none ];
191 -> 43;

192 [label="INSTANCE with matching:\nT11 -> T28\nX54 -> X147", fontsize=14, style = filled, fillcolor = lightgrey];
42 -> 192 [arrowhead = none , style=dashed];
192 -> 21[style=dashed];

193 [label="ONLY EVAL with clause\ns2t(X181, node(X182, X183, nil)) :- ','(p(X181, X184), s2t(X184, X182)).\nand substitutionT11 -> T33,\nX181 -> T33,\nX182 -> X185,\nX183 -> X186,\nX54 -> node(X185, X186, nil)", fontsize=14, style = filled, fillcolor = lightblue];
44 -> 193 [arrowhead = none ];
193 -> 46;

194 [label="ONLY EVAL with clause\ns2t(X200, node(nil, X201, nil)).\nand substitutionT11 -> T39,\nX200 -> T39,\nX201 -> X202,\nX54 -> node(nil, X202, nil)", fontsize=14, style = filled, fillcolor = lightblue];
45 -> 194 [arrowhead = none ];
194 -> 51;

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

196 [label="BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2t(T33, X54), s2t(0, X69))", fontsize=14, style = filled, fillcolor = lightgreen];
47 -> 196 [arrowhead = none ];
196 -> 48;

197 [label="EVAL with clause\np(s(X191), X191).\nand substitutionX191 -> T36,\nT33 -> s(T36),\nX184 -> T36", fontsize=14, style = filled, fillcolor = lightblue];
48 -> 197 [arrowhead = none ];
197 -> 49;

198 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
48 -> 198 [arrowhead = none ];
198 -> 50;

199 [label="INSTANCE with matching:\nT11 -> T36\nX54 -> X185", fontsize=14, style = filled, fillcolor = lightgrey];
49 -> 199 [arrowhead = none , style=dashed];
199 -> 21[style=dashed];

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

201 [label="BACKTRACK\nfor clause: tree(nil) :- !because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
53 -> 201 [arrowhead = none ];
201 -> 54;

202 [label="ONLY EVAL with clause\ntree(X210) :- ','(left(X211, X212), ','(right(X211, X213), ','(tree(X212), tree(X213)))).\nand substitutionT12 -> T42,\nX55 -> X214,\nX210 -> node(T42, X214, T42)", fontsize=14, style = filled, fillcolor = lightblue];
54 -> 202 [arrowhead = none ];
202 -> 55;

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

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

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

206 [label="ONLY EVAL with clause\nleft(nil, nil).\nand substitutionX211 -> nil,\nX212 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
57 -> 206 [arrowhead = none ];
206 -> 59;

207 [label="ONLY EVAL with clause\nleft(node(X230, X231, X232), X230).\nand substitutionX230 -> X233,\nX231 -> X234,\nX232 -> X235,\nX211 -> node(X233, X234, X235),\nX212 -> X233", fontsize=14, style = filled, fillcolor = lightblue];
58 -> 207 [arrowhead = none ];
207 -> 67;

208 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
59 -> 208 [arrowhead = none ];
208 -> 60;

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

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

211 [label="ONLY EVAL with clause\nright(nil, nil).\nand substitutionX213 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
61 -> 211 [arrowhead = none ];
211 -> 63;

212 [label="BACKTRACK\nfor clause: right(node(X7, X8, R), R)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
62 -> 212 [arrowhead = none ];
212 -> 66;

213 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
63 -> 213 [arrowhead = none ];
213 -> 64;

214 [label="SPLIT 2", fontsize=14, style = filled, fillcolor = violet];
63 -> 214 [arrowhead = none ];
214 -> 65;

215 [label="INSTANCE", fontsize=14, style = filled, fillcolor = lightgrey];
64 -> 215 [arrowhead = none , style=dashed];
215 -> 9[style=dashed];

216 [label="INSTANCE", fontsize=14, style = filled, fillcolor = lightgrey];
65 -> 216 [arrowhead = none , style=dashed];
216 -> 9[style=dashed];

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

218 [label="BACKTRACK\nfor clause: right(nil, nil)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
68 -> 218 [arrowhead = none ];
218 -> 69;

219 [label="ONLY EVAL with clause\nright(node(X248, X249, X250), X250).\nand substitutionX233 -> X251,\nX248 -> X251,\nX234 -> X252,\nX249 -> X252,\nX235 -> X253,\nX250 -> X253,\nX213 -> X253", fontsize=14, style = filled, fillcolor = lightblue];
69 -> 219 [arrowhead = none ];
219 -> 70;

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

221 [label="SPLIT 2\nreplacements:X251 -> T43", fontsize=14, style = filled, fillcolor = violet];
70 -> 221 [arrowhead = none ];
221 -> 72;

222 [label="INSTANCE with matching:\nX253 -> X251", fontsize=14, style = filled, fillcolor = lightgrey];
71 -> 222 [arrowhead = none , style=dashed];
222 -> 72[style=dashed];

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

224 [label="ONLY EVAL with clause\ntree(nil) :- !_15.\nand substitutionX253 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
73 -> 224 [arrowhead = none ];
224 -> 74;

225 [label="CUT", fontsize=14, style = filled, fillcolor = lightgreen];
74 -> 225 [arrowhead = none ];
225 -> 75;

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

227 [label="ONLY EVAL with clause\ns2t(X280, node(nil, X281, X282)) :- ','(p(X280, X283), s2t(X283, X282)).\nand substitutionT3 -> T48,\nX280 -> T48,\nX281 -> X284,\nX282 -> X285,\nX11 -> node(nil, X284, X285)", fontsize=14, style = filled, fillcolor = lightblue];
77 -> 227 [arrowhead = none ];
227 -> 79;

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

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

230 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
79 -> 230 [arrowhead = none ];
230 -> 80;

231 [label="BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2t(T48, X11), s2t(0, X16))", fontsize=14, style = filled, fillcolor = lightgreen];
80 -> 231 [arrowhead = none ];
231 -> 81;

232 [label="EVAL with clause\np(s(X290), X290).\nand substitutionX290 -> T51,\nT48 -> s(T51),\nX283 -> T51", fontsize=14, style = filled, fillcolor = lightblue];
81 -> 232 [arrowhead = none ];
232 -> 82;

233 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
81 -> 233 [arrowhead = none ];
233 -> 83;

234 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
82 -> 234 [arrowhead = none ];
234 -> 84;

235 [label="SPLIT 2\nnew knowledge:\nT51 is ground\nreplacements:X285 -> T52", fontsize=14, style = filled, fillcolor = violet];
82 -> 235 [arrowhead = none ];
235 -> 85;

236 [label="INSTANCE with matching:\nT11 -> T51\nX54 -> X285", fontsize=14, style = filled, fillcolor = lightgrey];
84 -> 236 [arrowhead = none , style=dashed];
236 -> 21[style=dashed];

237 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
85 -> 237 [arrowhead = none ];
237 -> 86;

238 [label="BACKTRACK\nfor clause: tree(nil) :- !because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
86 -> 238 [arrowhead = none ];
238 -> 87;

239 [label="ONLY EVAL with clause\ntree(X302) :- ','(left(X303, X304), ','(right(X303, X305), ','(tree(X304), tree(X305)))).\nand substitutionX284 -> X306,\nT52 -> T55,\nX302 -> node(nil, X306, T55)", fontsize=14, style = filled, fillcolor = lightblue];
87 -> 239 [arrowhead = none ];
239 -> 88;

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

241 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
89 -> 241 [arrowhead = none ];
241 -> 90;

242 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
89 -> 242 [arrowhead = none ];
242 -> 91;

243 [label="ONLY EVAL with clause\nleft(nil, nil).\nand substitutionX303 -> nil,\nX304 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
90 -> 243 [arrowhead = none ];
243 -> 92;

244 [label="ONLY EVAL with clause\nleft(node(X322, X323, X324), X322).\nand substitutionX322 -> X325,\nX323 -> X326,\nX324 -> X327,\nX303 -> node(X325, X326, X327),\nX304 -> X325", fontsize=14, style = filled, fillcolor = lightblue];
91 -> 244 [arrowhead = none ];
244 -> 98;

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

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

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

248 [label="ONLY EVAL with clause\nright(nil, nil).\nand substitutionX305 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
94 -> 248 [arrowhead = none ];
248 -> 96;

249 [label="BACKTRACK\nfor clause: right(node(X7, X8, R), R)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
95 -> 249 [arrowhead = none ];
249 -> 97;

250 [label="INSTANCE", fontsize=14, style = filled, fillcolor = lightgrey];
96 -> 250 [arrowhead = none , style=dashed];
250 -> 63[style=dashed];

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

252 [label="BACKTRACK\nfor clause: right(nil, nil)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
99 -> 252 [arrowhead = none ];
252 -> 100;

253 [label="ONLY EVAL with clause\nright(node(X340, X341, X342), X342).\nand substitutionX325 -> X343,\nX340 -> X343,\nX326 -> X344,\nX341 -> X344,\nX327 -> X345,\nX342 -> X345,\nX305 -> X345", fontsize=14, style = filled, fillcolor = lightblue];
100 -> 253 [arrowhead = none ];
253 -> 101;

254 [label="INSTANCE with matching:\nX251 -> X343\nX253 -> X345", fontsize=14, style = filled, fillcolor = lightgrey];
101 -> 254 [arrowhead = none , style=dashed];
254 -> 70[style=dashed];

255 [label="ONLY EVAL with clause\ns2t(X372, node(X373, X374, nil)) :- ','(p(X372, X375), s2t(X375, X373)).\nand substitutionT3 -> T60,\nX372 -> T60,\nX373 -> X376,\nX374 -> X377,\nX11 -> node(X376, X377, nil)", fontsize=14, style = filled, fillcolor = lightblue];
102 -> 255 [arrowhead = none ];
255 -> 104;

256 [label="ONLY EVAL with clause\ns2t(X444, node(nil, X445, nil)).\nand substitutionT3 -> T70,\nX444 -> T70,\nX445 -> X446,\nX11 -> node(nil, X446, nil)", fontsize=14, style = filled, fillcolor = lightblue];
103 -> 256 [arrowhead = none ];
256 -> 127;

257 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
104 -> 257 [arrowhead = none ];
257 -> 105;

258 [label="BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2t(T60, X11), s2t(0, X16))", fontsize=14, style = filled, fillcolor = lightgreen];
105 -> 258 [arrowhead = none ];
258 -> 106;

259 [label="EVAL with clause\np(s(X382), X382).\nand substitutionX382 -> T63,\nT60 -> s(T63),\nX375 -> T63", fontsize=14, style = filled, fillcolor = lightblue];
106 -> 259 [arrowhead = none ];
259 -> 107;

260 [label="EVAL-BACKTRACK", fontsize=14, style = filled, fillcolor = lightgreen];
106 -> 260 [arrowhead = none ];
260 -> 108;

261 [label="SPLIT 1", fontsize=14, style = filled, fillcolor = violet];
107 -> 261 [arrowhead = none ];
261 -> 109;

262 [label="SPLIT 2\nnew knowledge:\nT63 is ground\nreplacements:X376 -> T64", fontsize=14, style = filled, fillcolor = violet];
107 -> 262 [arrowhead = none ];
262 -> 110;

263 [label="INSTANCE with matching:\nT11 -> T63\nX54 -> X376", fontsize=14, style = filled, fillcolor = lightgrey];
109 -> 263 [arrowhead = none , style=dashed];
263 -> 21[style=dashed];

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

265 [label="BACKTRACK\nfor clause: tree(nil) :- !because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
111 -> 265 [arrowhead = none ];
265 -> 112;

266 [label="ONLY EVAL with clause\ntree(X394) :- ','(left(X395, X396), ','(right(X395, X397), ','(tree(X396), tree(X397)))).\nand substitutionT64 -> T67,\nX377 -> X398,\nX394 -> node(T67, X398, nil)", fontsize=14, style = filled, fillcolor = lightblue];
112 -> 266 [arrowhead = none ];
266 -> 113;

267 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
113 -> 267 [arrowhead = none ];
267 -> 114;

268 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
114 -> 268 [arrowhead = none ];
268 -> 115;

269 [label="PARALLEL", fontsize=14, style = filled, fillcolor = violet];
114 -> 269 [arrowhead = none ];
269 -> 116;

270 [label="ONLY EVAL with clause\nleft(nil, nil).\nand substitutionX395 -> nil,\nX396 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
115 -> 270 [arrowhead = none ];
270 -> 117;

271 [label="ONLY EVAL with clause\nleft(node(X414, X415, X416), X414).\nand substitutionX414 -> X417,\nX415 -> X418,\nX416 -> X419,\nX395 -> node(X417, X418, X419),\nX396 -> X417", fontsize=14, style = filled, fillcolor = lightblue];
116 -> 271 [arrowhead = none ];
271 -> 123;

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

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

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

275 [label="ONLY EVAL with clause\nright(nil, nil).\nand substitutionX397 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
119 -> 275 [arrowhead = none ];
275 -> 121;

276 [label="BACKTRACK\nfor clause: right(node(X7, X8, R), R)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
120 -> 276 [arrowhead = none ];
276 -> 122;

277 [label="INSTANCE", fontsize=14, style = filled, fillcolor = lightgrey];
121 -> 277 [arrowhead = none , style=dashed];
277 -> 63[style=dashed];

278 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
123 -> 278 [arrowhead = none ];
278 -> 124;

279 [label="BACKTRACK\nfor clause: right(nil, nil)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
124 -> 279 [arrowhead = none ];
279 -> 125;

280 [label="ONLY EVAL with clause\nright(node(X432, X433, X434), X434).\nand substitutionX417 -> X435,\nX432 -> X435,\nX418 -> X436,\nX433 -> X436,\nX419 -> X437,\nX434 -> X437,\nX397 -> X437", fontsize=14, style = filled, fillcolor = lightblue];
125 -> 280 [arrowhead = none ];
280 -> 126;

281 [label="INSTANCE with matching:\nX251 -> X435\nX253 -> X437", fontsize=14, style = filled, fillcolor = lightgrey];
126 -> 281 [arrowhead = none , style=dashed];
281 -> 70[style=dashed];

282 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
127 -> 282 [arrowhead = none ];
282 -> 128;

283 [label="BACKTRACK\nfor clause: tree(nil) :- !because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
128 -> 283 [arrowhead = none ];
283 -> 129;

284 [label="ONLY EVAL with clause\ntree(X454) :- ','(left(X455, X456), ','(right(X455, X457), ','(tree(X456), tree(X457)))).\nand substitutionX446 -> X458,\nX454 -> node(nil, X458, nil)", fontsize=14, style = filled, fillcolor = lightblue];
129 -> 284 [arrowhead = none ];
284 -> 130;

285 [label="CASE", fontsize=14, style = filled, fillcolor = lightcyan];
130 -> 285 [arrowhead = none ];
285 -> 131;

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

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

288 [label="ONLY EVAL with clause\nleft(nil, nil).\nand substitutionX455 -> nil,\nX456 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
132 -> 288 [arrowhead = none ];
288 -> 134;

289 [label="ONLY EVAL with clause\nleft(node(X474, X475, X476), X474).\nand substitutionX474 -> X477,\nX475 -> X478,\nX476 -> X479,\nX455 -> node(X477, X478, X479),\nX456 -> X477", fontsize=14, style = filled, fillcolor = lightblue];
133 -> 289 [arrowhead = none ];
289 -> 140;

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

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

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

293 [label="ONLY EVAL with clause\nright(nil, nil).\nand substitutionX457 -> nil", fontsize=14, style = filled, fillcolor = lightblue];
136 -> 293 [arrowhead = none ];
293 -> 138;

294 [label="BACKTRACK\nfor clause: right(node(X7, X8, R), R)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
137 -> 294 [arrowhead = none ];
294 -> 139;

295 [label="INSTANCE", fontsize=14, style = filled, fillcolor = lightgrey];
138 -> 295 [arrowhead = none , style=dashed];
295 -> 63[style=dashed];

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

297 [label="BACKTRACK\nfor clause: right(nil, nil)because of non-unification", fontsize=14, style = filled, fillcolor = lightgreen];
141 -> 297 [arrowhead = none ];
297 -> 142;

298 [label="ONLY EVAL with clause\nright(node(X492, X493, X494), X494).\nand substitutionX477 -> X495,\nX492 -> X495,\nX478 -> X496,\nX493 -> X496,\nX479 -> X497,\nX494 -> X497,\nX457 -> X497", fontsize=14, style = filled, fillcolor = lightblue];
142 -> 298 [arrowhead = none ];
298 -> 143;

299 [label="INSTANCE with matching:\nX251 -> X495\nX253 -> X497", fontsize=14, style = filled, fillcolor = lightgrey];
143 -> 299 [arrowhead = none , style=dashed];
299 -> 70[style=dashed];

}

(2) Obligation:

Clauses:

s2tA(0, nil).
s2tA(s(T20), node(X107, X108, X107)) :- s2tA(T20, X107).
s2tA(s(T28), node(nil, X146, X147)) :- s2tA(T28, X147).
s2tA(s(T36), node(X185, X186, nil)) :- s2tA(T36, X185).
s2tA(T39, node(nil, X202, nil)).
treeB.
treeC(nil).
pD :- treeB.
pD :- ','(treeB, treeB).
pE(X251, X253) :- treeC(X251).
pE(T43, X253) :- ','(treeC(T43), treeC(X253)).
goalF(0) :- treeB.
goalF(s(T11)) :- s2tA(T11, X54).
goalF(s(T11)) :- ','(s2tA(T11, T42), pD).
goalF(s(T11)) :- ','(s2tA(T11, T42), pE(X251, X253)).
goalF(s(T51)) :- s2tA(T51, X285).
goalF(s(T51)) :- ','(s2tA(T51, T55), pD).
goalF(s(T51)) :- ','(s2tA(T51, T55), pE(X343, X345)).
goalF(s(T63)) :- s2tA(T63, X376).
goalF(s(T63)) :- ','(s2tA(T63, T67), pD).
goalF(s(T63)) :- ','(s2tA(T63, T67), pE(X435, X437)).
goalF(T70) :- pD.
goalF(T70) :- pE(X495, X497).

Query: goalF(g)

(3) PrologToPiTRSProof (SOUND transformation)

We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:
goalF_in: (b)
s2tA_in: (b,f)
pE_in: (f,f)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

goalF_in_g(0) → U9_g(treeB_in_)
treeB_in_ → treeB_out_
U9_g(treeB_out_) → goalF_out_g(0)
goalF_in_g(s(T11)) → U10_g(T11, s2tA_in_ga(T11, X54))
s2tA_in_ga(0, nil) → s2tA_out_ga(0, nil)
s2tA_in_ga(s(T20), node(X107, X108, X107)) → U1_ga(T20, X107, X108, s2tA_in_ga(T20, X107))
s2tA_in_ga(s(T28), node(nil, X146, X147)) → U2_ga(T28, X146, X147, s2tA_in_ga(T28, X147))
s2tA_in_ga(s(T36), node(X185, X186, nil)) → U3_ga(T36, X185, X186, s2tA_in_ga(T36, X185))
s2tA_in_ga(T39, node(nil, X202, nil)) → s2tA_out_ga(T39, node(nil, X202, nil))
U3_ga(T36, X185, X186, s2tA_out_ga(T36, X185)) → s2tA_out_ga(s(T36), node(X185, X186, nil))
U2_ga(T28, X146, X147, s2tA_out_ga(T28, X147)) → s2tA_out_ga(s(T28), node(nil, X146, X147))
U1_ga(T20, X107, X108, s2tA_out_ga(T20, X107)) → s2tA_out_ga(s(T20), node(X107, X108, X107))
U10_g(T11, s2tA_out_ga(T11, X54)) → goalF_out_g(s(T11))
goalF_in_g(s(T11)) → U11_g(T11, s2tA_in_ga(T11, T42))
U11_g(T11, s2tA_out_ga(T11, T42)) → U12_g(T11, pD_in_)
pD_in_ → U4_(treeB_in_)
U4_(treeB_out_) → pD_out_
U4_(treeB_out_) → U5_(treeB_in_)
U5_(treeB_out_) → pD_out_
U12_g(T11, pD_out_) → goalF_out_g(s(T11))
U11_g(T11, s2tA_out_ga(T11, T42)) → U13_g(T11, pE_in_aa(X251, X253))
pE_in_aa(X251, X253) → U6_aa(X251, X253, treeC_in_a(X251))
treeC_in_a(nil) → treeC_out_a(nil)
U6_aa(X251, X253, treeC_out_a(X251)) → pE_out_aa(X251, X253)
pE_in_aa(T43, X253) → U7_aa(T43, X253, treeC_in_a(T43))
U7_aa(T43, X253, treeC_out_a(T43)) → U8_aa(T43, X253, treeC_in_a(X253))
U8_aa(T43, X253, treeC_out_a(X253)) → pE_out_aa(T43, X253)
U13_g(T11, pE_out_aa(X251, X253)) → goalF_out_g(s(T11))
goalF_in_g(s(T51)) → U14_g(T51, s2tA_in_ga(T51, X285))
U14_g(T51, s2tA_out_ga(T51, X285)) → goalF_out_g(s(T51))
goalF_in_g(s(T51)) → U15_g(T51, s2tA_in_ga(T51, T55))
U15_g(T51, s2tA_out_ga(T51, T55)) → U16_g(T51, pD_in_)
U16_g(T51, pD_out_) → goalF_out_g(s(T51))
U15_g(T51, s2tA_out_ga(T51, T55)) → U17_g(T51, pE_in_aa(X343, X345))
U17_g(T51, pE_out_aa(X343, X345)) → goalF_out_g(s(T51))
goalF_in_g(s(T63)) → U18_g(T63, s2tA_in_ga(T63, X376))
U18_g(T63, s2tA_out_ga(T63, X376)) → goalF_out_g(s(T63))
goalF_in_g(s(T63)) → U19_g(T63, s2tA_in_ga(T63, T67))
U19_g(T63, s2tA_out_ga(T63, T67)) → U20_g(T63, pD_in_)
U20_g(T63, pD_out_) → goalF_out_g(s(T63))
U19_g(T63, s2tA_out_ga(T63, T67)) → U21_g(T63, pE_in_aa(X435, X437))
U21_g(T63, pE_out_aa(X435, X437)) → goalF_out_g(s(T63))
goalF_in_g(T70) → U22_g(T70, pD_in_)
U22_g(T70, pD_out_) → goalF_out_g(T70)
goalF_in_g(T70) → U23_g(T70, pE_in_aa(X495, X497))
U23_g(T70, pE_out_aa(X495, X497)) → goalF_out_g(T70)

The argument filtering Pi contains the following mapping:
goalF_in_g(x1)  =  goalF_in_g(x1)
0  =  0
U9_g(x1)  =  U9_g(x1)
treeB_in_  =  treeB_in_
treeB_out_  =  treeB_out_
goalF_out_g(x1)  =  goalF_out_g
s(x1)  =  s(x1)
U10_g(x1, x2)  =  U10_g(x2)
s2tA_in_ga(x1, x2)  =  s2tA_in_ga(x1)
s2tA_out_ga(x1, x2)  =  s2tA_out_ga(x2)
U1_ga(x1, x2, x3, x4)  =  U1_ga(x4)
U2_ga(x1, x2, x3, x4)  =  U2_ga(x4)
U3_ga(x1, x2, x3, x4)  =  U3_ga(x4)
node(x1, x2, x3)  =  node(x1, x3)
U11_g(x1, x2)  =  U11_g(x2)
U12_g(x1, x2)  =  U12_g(x2)
pD_in_  =  pD_in_
U4_(x1)  =  U4_(x1)
pD_out_  =  pD_out_
U5_(x1)  =  U5_(x1)
U13_g(x1, x2)  =  U13_g(x2)
pE_in_aa(x1, x2)  =  pE_in_aa
U6_aa(x1, x2, x3)  =  U6_aa(x3)
treeC_in_a(x1)  =  treeC_in_a
treeC_out_a(x1)  =  treeC_out_a(x1)
pE_out_aa(x1, x2)  =  pE_out_aa(x1)
U7_aa(x1, x2, x3)  =  U7_aa(x3)
U8_aa(x1, x2, x3)  =  U8_aa(x1, x3)
U14_g(x1, x2)  =  U14_g(x2)
U15_g(x1, x2)  =  U15_g(x2)
U16_g(x1, x2)  =  U16_g(x2)
U17_g(x1, x2)  =  U17_g(x2)
U18_g(x1, x2)  =  U18_g(x2)
U19_g(x1, x2)  =  U19_g(x2)
U20_g(x1, x2)  =  U20_g(x2)
U21_g(x1, x2)  =  U21_g(x2)
U22_g(x1, x2)  =  U22_g(x2)
U23_g(x1, x2)  =  U23_g(x2)
nil  =  nil

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog

(4) Obligation:

Pi-finite rewrite system:
The TRS R consists of the following rules:

goalF_in_g(0) → U9_g(treeB_in_)
treeB_in_ → treeB_out_
U9_g(treeB_out_) → goalF_out_g(0)
goalF_in_g(s(T11)) → U10_g(T11, s2tA_in_ga(T11, X54))
s2tA_in_ga(0, nil) → s2tA_out_ga(0, nil)
s2tA_in_ga(s(T20), node(X107, X108, X107)) → U1_ga(T20, X107, X108, s2tA_in_ga(T20, X107))
s2tA_in_ga(s(T28), node(nil, X146, X147)) → U2_ga(T28, X146, X147, s2tA_in_ga(T28, X147))
s2tA_in_ga(s(T36), node(X185, X186, nil)) → U3_ga(T36, X185, X186, s2tA_in_ga(T36, X185))
s2tA_in_ga(T39, node(nil, X202, nil)) → s2tA_out_ga(T39, node(nil, X202, nil))
U3_ga(T36, X185, X186, s2tA_out_ga(T36, X185)) → s2tA_out_ga(s(T36), node(X185, X186, nil))
U2_ga(T28, X146, X147, s2tA_out_ga(T28, X147)) → s2tA_out_ga(s(T28), node(nil, X146, X147))
U1_ga(T20, X107, X108, s2tA_out_ga(T20, X107)) → s2tA_out_ga(s(T20), node(X107, X108, X107))
U10_g(T11, s2tA_out_ga(T11, X54)) → goalF_out_g(s(T11))
goalF_in_g(s(T11)) → U11_g(T11, s2tA_in_ga(T11, T42))
U11_g(T11, s2tA_out_ga(T11, T42)) → U12_g(T11, pD_in_)
pD_in_ → U4_(treeB_in_)
U4_(treeB_out_) → pD_out_
U4_(treeB_out_) → U5_(treeB_in_)
U5_(treeB_out_) → pD_out_
U12_g(T11, pD_out_) → goalF_out_g(s(T11))
U11_g(T11, s2tA_out_ga(T11, T42)) → U13_g(T11, pE_in_aa(X251, X253))
pE_in_aa(X251, X253) → U6_aa(X251, X253, treeC_in_a(X251))
treeC_in_a(nil) → treeC_out_a(nil)
U6_aa(X251, X253, treeC_out_a(X251)) → pE_out_aa(X251, X253)
pE_in_aa(T43, X253) → U7_aa(T43, X253, treeC_in_a(T43))
U7_aa(T43, X253, treeC_out_a(T43)) → U8_aa(T43, X253, treeC_in_a(X253))
U8_aa(T43, X253, treeC_out_a(X253)) → pE_out_aa(T43, X253)
U13_g(T11, pE_out_aa(X251, X253)) → goalF_out_g(s(T11))
goalF_in_g(s(T51)) → U14_g(T51, s2tA_in_ga(T51, X285))
U14_g(T51, s2tA_out_ga(T51, X285)) → goalF_out_g(s(T51))
goalF_in_g(s(T51)) → U15_g(T51, s2tA_in_ga(T51, T55))
U15_g(T51, s2tA_out_ga(T51, T55)) → U16_g(T51, pD_in_)
U16_g(T51, pD_out_) → goalF_out_g(s(T51))
U15_g(T51, s2tA_out_ga(T51, T55)) → U17_g(T51, pE_in_aa(X343, X345))
U17_g(T51, pE_out_aa(X343, X345)) → goalF_out_g(s(T51))
goalF_in_g(s(T63)) → U18_g(T63, s2tA_in_ga(T63, X376))
U18_g(T63, s2tA_out_ga(T63, X376)) → goalF_out_g(s(T63))
goalF_in_g(s(T63)) → U19_g(T63, s2tA_in_ga(T63, T67))
U19_g(T63, s2tA_out_ga(T63, T67)) → U20_g(T63, pD_in_)
U20_g(T63, pD_out_) → goalF_out_g(s(T63))
U19_g(T63, s2tA_out_ga(T63, T67)) → U21_g(T63, pE_in_aa(X435, X437))
U21_g(T63, pE_out_aa(X435, X437)) → goalF_out_g(s(T63))
goalF_in_g(T70) → U22_g(T70, pD_in_)
U22_g(T70, pD_out_) → goalF_out_g(T70)
goalF_in_g(T70) → U23_g(T70, pE_in_aa(X495, X497))
U23_g(T70, pE_out_aa(X495, X497)) → goalF_out_g(T70)

The argument filtering Pi contains the following mapping:
goalF_in_g(x1)  =  goalF_in_g(x1)
0  =  0
U9_g(x1)  =  U9_g(x1)
treeB_in_  =  treeB_in_
treeB_out_  =  treeB_out_
goalF_out_g(x1)  =  goalF_out_g
s(x1)  =  s(x1)
U10_g(x1, x2)  =  U10_g(x2)
s2tA_in_ga(x1, x2)  =  s2tA_in_ga(x1)
s2tA_out_ga(x1, x2)  =  s2tA_out_ga(x2)
U1_ga(x1, x2, x3, x4)  =  U1_ga(x4)
U2_ga(x1, x2, x3, x4)  =  U2_ga(x4)
U3_ga(x1, x2, x3, x4)  =  U3_ga(x4)
node(x1, x2, x3)  =  node(x1, x3)
U11_g(x1, x2)  =  U11_g(x2)
U12_g(x1, x2)  =  U12_g(x2)
pD_in_  =  pD_in_
U4_(x1)  =  U4_(x1)
pD_out_  =  pD_out_
U5_(x1)  =  U5_(x1)
U13_g(x1, x2)  =  U13_g(x2)
pE_in_aa(x1, x2)  =  pE_in_aa
U6_aa(x1, x2, x3)  =  U6_aa(x3)
treeC_in_a(x1)  =  treeC_in_a
treeC_out_a(x1)  =  treeC_out_a(x1)
pE_out_aa(x1, x2)  =  pE_out_aa(x1)
U7_aa(x1, x2, x3)  =  U7_aa(x3)
U8_aa(x1, x2, x3)  =  U8_aa(x1, x3)
U14_g(x1, x2)  =  U14_g(x2)
U15_g(x1, x2)  =  U15_g(x2)
U16_g(x1, x2)  =  U16_g(x2)
U17_g(x1, x2)  =  U17_g(x2)
U18_g(x1, x2)  =  U18_g(x2)
U19_g(x1, x2)  =  U19_g(x2)
U20_g(x1, x2)  =  U20_g(x2)
U21_g(x1, x2)  =  U21_g(x2)
U22_g(x1, x2)  =  U22_g(x2)
U23_g(x1, x2)  =  U23_g(x2)
nil  =  nil

(5) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

GOALF_IN_G(0) → U9_G(treeB_in_)
GOALF_IN_G(0) → TREEB_IN_
GOALF_IN_G(s(T11)) → U10_G(T11, s2tA_in_ga(T11, X54))
GOALF_IN_G(s(T11)) → S2TA_IN_GA(T11, X54)
S2TA_IN_GA(s(T20), node(X107, X108, X107)) → U1_GA(T20, X107, X108, s2tA_in_ga(T20, X107))
S2TA_IN_GA(s(T20), node(X107, X108, X107)) → S2TA_IN_GA(T20, X107)
S2TA_IN_GA(s(T28), node(nil, X146, X147)) → U2_GA(T28, X146, X147, s2tA_in_ga(T28, X147))
S2TA_IN_GA(s(T28), node(nil, X146, X147)) → S2TA_IN_GA(T28, X147)
S2TA_IN_GA(s(T36), node(X185, X186, nil)) → U3_GA(T36, X185, X186, s2tA_in_ga(T36, X185))
S2TA_IN_GA(s(T36), node(X185, X186, nil)) → S2TA_IN_GA(T36, X185)
GOALF_IN_G(s(T11)) → U11_G(T11, s2tA_in_ga(T11, T42))
U11_G(T11, s2tA_out_ga(T11, T42)) → U12_G(T11, pD_in_)
U11_G(T11, s2tA_out_ga(T11, T42)) → PD_IN_
PD_IN_ → U4_¹(treeB_in_)
PD_IN_ → TREEB_IN_
U4_¹(treeB_out_) → U5_¹(treeB_in_)
U4_¹(treeB_out_) → TREEB_IN_
U11_G(T11, s2tA_out_ga(T11, T42)) → U13_G(T11, pE_in_aa(X251, X253))
U11_G(T11, s2tA_out_ga(T11, T42)) → PE_IN_AA(X251, X253)
PE_IN_AA(X251, X253) → U6_AA(X251, X253, treeC_in_a(X251))
PE_IN_AA(X251, X253) → TREEC_IN_A(X251)
PE_IN_AA(T43, X253) → U7_AA(T43, X253, treeC_in_a(T43))
U7_AA(T43, X253, treeC_out_a(T43)) → U8_AA(T43, X253, treeC_in_a(X253))
U7_AA(T43, X253, treeC_out_a(T43)) → TREEC_IN_A(X253)
GOALF_IN_G(s(T51)) → U14_G(T51, s2tA_in_ga(T51, X285))
GOALF_IN_G(s(T51)) → U15_G(T51, s2tA_in_ga(T51, T55))
U15_G(T51, s2tA_out_ga(T51, T55)) → U16_G(T51, pD_in_)
U15_G(T51, s2tA_out_ga(T51, T55)) → PD_IN_
U15_G(T51, s2tA_out_ga(T51, T55)) → U17_G(T51, pE_in_aa(X343, X345))
U15_G(T51, s2tA_out_ga(T51, T55)) → PE_IN_AA(X343, X345)
GOALF_IN_G(s(T63)) → U18_G(T63, s2tA_in_ga(T63, X376))
GOALF_IN_G(s(T63)) → U19_G(T63, s2tA_in_ga(T63, T67))
U19_G(T63, s2tA_out_ga(T63, T67)) → U20_G(T63, pD_in_)
U19_G(T63, s2tA_out_ga(T63, T67)) → PD_IN_
U19_G(T63, s2tA_out_ga(T63, T67)) → U21_G(T63, pE_in_aa(X435, X437))
U19_G(T63, s2tA_out_ga(T63, T67)) → PE_IN_AA(X435, X437)
GOALF_IN_G(T70) → U22_G(T70, pD_in_)
GOALF_IN_G(T70) → PD_IN_
GOALF_IN_G(T70) → U23_G(T70, pE_in_aa(X495, X497))
GOALF_IN_G(T70) → PE_IN_AA(X495, X497)

The TRS R consists of the following rules:

goalF_in_g(0) → U9_g(treeB_in_)
treeB_in_ → treeB_out_
U9_g(treeB_out_) → goalF_out_g(0)
goalF_in_g(s(T11)) → U10_g(T11, s2tA_in_ga(T11, X54))
s2tA_in_ga(0, nil) → s2tA_out_ga(0, nil)
s2tA_in_ga(s(T20), node(X107, X108, X107)) → U1_ga(T20, X107, X108, s2tA_in_ga(T20, X107))
s2tA_in_ga(s(T28), node(nil, X146, X147)) → U2_ga(T28, X146, X147, s2tA_in_ga(T28, X147))
s2tA_in_ga(s(T36), node(X185, X186, nil)) → U3_ga(T36, X185, X186, s2tA_in_ga(T36, X185))
s2tA_in_ga(T39, node(nil, X202, nil)) → s2tA_out_ga(T39, node(nil, X202, nil))
U3_ga(T36, X185, X186, s2tA_out_ga(T36, X185)) → s2tA_out_ga(s(T36), node(X185, X186, nil))
U2_ga(T28, X146, X147, s2tA_out_ga(T28, X147)) → s2tA_out_ga(s(T28), node(nil, X146, X147))
U1_ga(T20, X107, X108, s2tA_out_ga(T20, X107)) → s2tA_out_ga(s(T20), node(X107, X108, X107))
U10_g(T11, s2tA_out_ga(T11, X54)) → goalF_out_g(s(T11))
goalF_in_g(s(T11)) → U11_g(T11, s2tA_in_ga(T11, T42))
U11_g(T11, s2tA_out_ga(T11, T42)) → U12_g(T11, pD_in_)
pD_in_ → U4_(treeB_in_)
U4_(treeB_out_) → pD_out_
U4_(treeB_out_) → U5_(treeB_in_)
U5_(treeB_out_) → pD_out_
U12_g(T11, pD_out_) → goalF_out_g(s(T11))
U11_g(T11, s2tA_out_ga(T11, T42)) → U13_g(T11, pE_in_aa(X251, X253))
pE_in_aa(X251, X253) → U6_aa(X251, X253, treeC_in_a(X251))
treeC_in_a(nil) → treeC_out_a(nil)
U6_aa(X251, X253, treeC_out_a(X251)) → pE_out_aa(X251, X253)
pE_in_aa(T43, X253) → U7_aa(T43, X253, treeC_in_a(T43))
U7_aa(T43, X253, treeC_out_a(T43)) → U8_aa(T43, X253, treeC_in_a(X253))
U8_aa(T43, X253, treeC_out_a(X253)) → pE_out_aa(T43, X253)
U13_g(T11, pE_out_aa(X251, X253)) → goalF_out_g(s(T11))
goalF_in_g(s(T51)) → U14_g(T51, s2tA_in_ga(T51, X285))
U14_g(T51, s2tA_out_ga(T51, X285)) → goalF_out_g(s(T51))
goalF_in_g(s(T51)) → U15_g(T51, s2tA_in_ga(T51, T55))
U15_g(T51, s2tA_out_ga(T51, T55)) → U16_g(T51, pD_in_)
U16_g(T51, pD_out_) → goalF_out_g(s(T51))
U15_g(T51, s2tA_out_ga(T51, T55)) → U17_g(T51, pE_in_aa(X343, X345))
U17_g(T51, pE_out_aa(X343, X345)) → goalF_out_g(s(T51))
goalF_in_g(s(T63)) → U18_g(T63, s2tA_in_ga(T63, X376))
U18_g(T63, s2tA_out_ga(T63, X376)) → goalF_out_g(s(T63))
goalF_in_g(s(T63)) → U19_g(T63, s2tA_in_ga(T63, T67))
U19_g(T63, s2tA_out_ga(T63, T67)) → U20_g(T63, pD_in_)
U20_g(T63, pD_out_) → goalF_out_g(s(T63))
U19_g(T63, s2tA_out_ga(T63, T67)) → U21_g(T63, pE_in_aa(X435, X437))
U21_g(T63, pE_out_aa(X435, X437)) → goalF_out_g(s(T63))
goalF_in_g(T70) → U22_g(T70, pD_in_)
U22_g(T70, pD_out_) → goalF_out_g(T70)
goalF_in_g(T70) → U23_g(T70, pE_in_aa(X495, X497))
U23_g(T70, pE_out_aa(X495, X497)) → goalF_out_g(T70)

The argument filtering Pi contains the following mapping:
goalF_in_g(x1)  =  goalF_in_g(x1)
0  =  0
U9_g(x1)  =  U9_g(x1)
treeB_in_  =  treeB_in_
treeB_out_  =  treeB_out_
goalF_out_g(x1)  =  goalF_out_g
s(x1)  =  s(x1)
U10_g(x1, x2)  =  U10_g(x2)
s2tA_in_ga(x1, x2)  =  s2tA_in_ga(x1)
s2tA_out_ga(x1, x2)  =  s2tA_out_ga(x2)
U1_ga(x1, x2, x3, x4)  =  U1_ga(x4)
U2_ga(x1, x2, x3, x4)  =  U2_ga(x4)
U3_ga(x1, x2, x3, x4)  =  U3_ga(x4)
node(x1, x2, x3)  =  node(x1, x3)
U11_g(x1, x2)  =  U11_g(x2)
U12_g(x1, x2)  =  U12_g(x2)
pD_in_  =  pD_in_
U4_(x1)  =  U4_(x1)
pD_out_  =  pD_out_
U5_(x1)  =  U5_(x1)
U13_g(x1, x2)  =  U13_g(x2)
pE_in_aa(x1, x2)  =  pE_in_aa
U6_aa(x1, x2, x3)  =  U6_aa(x3)
treeC_in_a(x1)  =  treeC_in_a
treeC_out_a(x1)  =  treeC_out_a(x1)
pE_out_aa(x1, x2)  =  pE_out_aa(x1)
U7_aa(x1, x2, x3)  =  U7_aa(x3)
U8_aa(x1, x2, x3)  =  U8_aa(x1, x3)
U14_g(x1, x2)  =  U14_g(x2)
U15_g(x1, x2)  =  U15_g(x2)
U16_g(x1, x2)  =  U16_g(x2)
U17_g(x1, x2)  =  U17_g(x2)
U18_g(x1, x2)  =  U18_g(x2)
U19_g(x1, x2)  =  U19_g(x2)
U20_g(x1, x2)  =  U20_g(x2)
U21_g(x1, x2)  =  U21_g(x2)
U22_g(x1, x2)  =  U22_g(x2)
U23_g(x1, x2)  =  U23_g(x2)
nil  =  nil
GOALF_IN_G(x1)  =  GOALF_IN_G(x1)
U9_G(x1)  =  U9_G(x1)
TREEB_IN_  =  TREEB_IN_
U10_G(x1, x2)  =  U10_G(x2)
S2TA_IN_GA(x1, x2)  =  S2TA_IN_GA(x1)
U1_GA(x1, x2, x3, x4)  =  U1_GA(x4)
U2_GA(x1, x2, x3, x4)  =  U2_GA(x4)
U3_GA(x1, x2, x3, x4)  =  U3_GA(x4)
U11_G(x1, x2)  =  U11_G(x2)
U12_G(x1, x2)  =  U12_G(x2)
PD_IN_  =  PD_IN_
U4_¹(x1)  =  U4_¹(x1)
U5_¹(x1)  =  U5_¹(x1)
U13_G(x1, x2)  =  U13_G(x2)
PE_IN_AA(x1, x2)  =  PE_IN_AA
U6_AA(x1, x2, x3)  =  U6_AA(x3)
TREEC_IN_A(x1)  =  TREEC_IN_A
U7_AA(x1, x2, x3)  =  U7_AA(x3)
U8_AA(x1, x2, x3)  =  U8_AA(x1, x3)
U14_G(x1, x2)  =  U14_G(x2)
U15_G(x1, x2)  =  U15_G(x2)
U16_G(x1, x2)  =  U16_G(x2)
U17_G(x1, x2)  =  U17_G(x2)
U18_G(x1, x2)  =  U18_G(x2)
U19_G(x1, x2)  =  U19_G(x2)
U20_G(x1, x2)  =  U20_G(x2)
U21_G(x1, x2)  =  U21_G(x2)
U22_G(x1, x2)  =  U22_G(x2)
U23_G(x1, x2)  =  U23_G(x2)

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

(6) Obligation:

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

GOALF_IN_G(0) → U9_G(treeB_in_)
GOALF_IN_G(0) → TREEB_IN_
GOALF_IN_G(s(T11)) → U10_G(T11, s2tA_in_ga(T11, X54))
GOALF_IN_G(s(T11)) → S2TA_IN_GA(T11, X54)
S2TA_IN_GA(s(T20), node(X107, X108, X107)) → U1_GA(T20, X107, X108, s2tA_in_ga(T20, X107))
S2TA_IN_GA(s(T20), node(X107, X108, X107)) → S2TA_IN_GA(T20, X107)
S2TA_IN_GA(s(T28), node(nil, X146, X147)) → U2_GA(T28, X146, X147, s2tA_in_ga(T28, X147))
S2TA_IN_GA(s(T28), node(nil, X146, X147)) → S2TA_IN_GA(T28, X147)
S2TA_IN_GA(s(T36), node(X185, X186, nil)) → U3_GA(T36, X185, X186, s2tA_in_ga(T36, X185))
S2TA_IN_GA(s(T36), node(X185, X186, nil)) → S2TA_IN_GA(T36, X185)
GOALF_IN_G(s(T11)) → U11_G(T11, s2tA_in_ga(T11, T42))
U11_G(T11, s2tA_out_ga(T11, T42)) → U12_G(T11, pD_in_)
U11_G(T11, s2tA_out_ga(T11, T42)) → PD_IN_
PD_IN_ → U4_¹(treeB_in_)
PD_IN_ → TREEB_IN_
U4_¹(treeB_out_) → U5_¹(treeB_in_)
U4_¹(treeB_out_) → TREEB_IN_
U11_G(T11, s2tA_out_ga(T11, T42)) → U13_G(T11, pE_in_aa(X251, X253))
U11_G(T11, s2tA_out_ga(T11, T42)) → PE_IN_AA(X251, X253)
PE_IN_AA(X251, X253) → U6_AA(X251, X253, treeC_in_a(X251))
PE_IN_AA(X251, X253) → TREEC_IN_A(X251)
PE_IN_AA(T43, X253) → U7_AA(T43, X253, treeC_in_a(T43))
U7_AA(T43, X253, treeC_out_a(T43)) → U8_AA(T43, X253, treeC_in_a(X253))
U7_AA(T43, X253, treeC_out_a(T43)) → TREEC_IN_A(X253)
GOALF_IN_G(s(T51)) → U14_G(T51, s2tA_in_ga(T51, X285))
GOALF_IN_G(s(T51)) → U15_G(T51, s2tA_in_ga(T51, T55))
U15_G(T51, s2tA_out_ga(T51, T55)) → U16_G(T51, pD_in_)
U15_G(T51, s2tA_out_ga(T51, T55)) → PD_IN_
U15_G(T51, s2tA_out_ga(T51, T55)) → U17_G(T51, pE_in_aa(X343, X345))
U15_G(T51, s2tA_out_ga(T51, T55)) → PE_IN_AA(X343, X345)
GOALF_IN_G(s(T63)) → U18_G(T63, s2tA_in_ga(T63, X376))
GOALF_IN_G(s(T63)) → U19_G(T63, s2tA_in_ga(T63, T67))
U19_G(T63, s2tA_out_ga(T63, T67)) → U20_G(T63, pD_in_)
U19_G(T63, s2tA_out_ga(T63, T67)) → PD_IN_
U19_G(T63, s2tA_out_ga(T63, T67)) → U21_G(T63, pE_in_aa(X435, X437))
U19_G(T63, s2tA_out_ga(T63, T67)) → PE_IN_AA(X435, X437)
GOALF_IN_G(T70) → U22_G(T70, pD_in_)
GOALF_IN_G(T70) → PD_IN_
GOALF_IN_G(T70) → U23_G(T70, pE_in_aa(X495, X497))
GOALF_IN_G(T70) → PE_IN_AA(X495, X497)

The TRS R consists of the following rules:

goalF_in_g(0) → U9_g(treeB_in_)
treeB_in_ → treeB_out_
U9_g(treeB_out_) → goalF_out_g(0)
goalF_in_g(s(T11)) → U10_g(T11, s2tA_in_ga(T11, X54))
s2tA_in_ga(0, nil) → s2tA_out_ga(0, nil)
s2tA_in_ga(s(T20), node(X107, X108, X107)) → U1_ga(T20, X107, X108, s2tA_in_ga(T20, X107))
s2tA_in_ga(s(T28), node(nil, X146, X147)) → U2_ga(T28, X146, X147, s2tA_in_ga(T28, X147))
s2tA_in_ga(s(T36), node(X185, X186, nil)) → U3_ga(T36, X185, X186, s2tA_in_ga(T36, X185))
s2tA_in_ga(T39, node(nil, X202, nil)) → s2tA_out_ga(T39, node(nil, X202, nil))
U3_ga(T36, X185, X186, s2tA_out_ga(T36, X185)) → s2tA_out_ga(s(T36), node(X185, X186, nil))
U2_ga(T28, X146, X147, s2tA_out_ga(T28, X147)) → s2tA_out_ga(s(T28), node(nil, X146, X147))
U1_ga(T20, X107, X108, s2tA_out_ga(T20, X107)) → s2tA_out_ga(s(T20), node(X107, X108, X107))
U10_g(T11, s2tA_out_ga(T11, X54)) → goalF_out_g(s(T11))
goalF_in_g(s(T11)) → U11_g(T11, s2tA_in_ga(T11, T42))
U11_g(T11, s2tA_out_ga(T11, T42)) → U12_g(T11, pD_in_)
pD_in_ → U4_(treeB_in_)
U4_(treeB_out_) → pD_out_
U4_(treeB_out_) → U5_(treeB_in_)
U5_(treeB_out_) → pD_out_
U12_g(T11, pD_out_) → goalF_out_g(s(T11))
U11_g(T11, s2tA_out_ga(T11, T42)) → U13_g(T11, pE_in_aa(X251, X253))
pE_in_aa(X251, X253) → U6_aa(X251, X253, treeC_in_a(X251))
treeC_in_a(nil) → treeC_out_a(nil)
U6_aa(X251, X253, treeC_out_a(X251)) → pE_out_aa(X251, X253)
pE_in_aa(T43, X253) → U7_aa(T43, X253, treeC_in_a(T43))
U7_aa(T43, X253, treeC_out_a(T43)) → U8_aa(T43, X253, treeC_in_a(X253))
U8_aa(T43, X253, treeC_out_a(X253)) → pE_out_aa(T43, X253)
U13_g(T11, pE_out_aa(X251, X253)) → goalF_out_g(s(T11))
goalF_in_g(s(T51)) → U14_g(T51, s2tA_in_ga(T51, X285))
U14_g(T51, s2tA_out_ga(T51, X285)) → goalF_out_g(s(T51))
goalF_in_g(s(T51)) → U15_g(T51, s2tA_in_ga(T51, T55))
U15_g(T51, s2tA_out_ga(T51, T55)) → U16_g(T51, pD_in_)
U16_g(T51, pD_out_) → goalF_out_g(s(T51))
U15_g(T51, s2tA_out_ga(T51, T55)) → U17_g(T51, pE_in_aa(X343, X345))
U17_g(T51, pE_out_aa(X343, X345)) → goalF_out_g(s(T51))
goalF_in_g(s(T63)) → U18_g(T63, s2tA_in_ga(T63, X376))
U18_g(T63, s2tA_out_ga(T63, X376)) → goalF_out_g(s(T63))
goalF_in_g(s(T63)) → U19_g(T63, s2tA_in_ga(T63, T67))
U19_g(T63, s2tA_out_ga(T63, T67)) → U20_g(T63, pD_in_)
U20_g(T63, pD_out_) → goalF_out_g(s(T63))
U19_g(T63, s2tA_out_ga(T63, T67)) → U21_g(T63, pE_in_aa(X435, X437))
U21_g(T63, pE_out_aa(X435, X437)) → goalF_out_g(s(T63))
goalF_in_g(T70) → U22_g(T70, pD_in_)
U22_g(T70, pD_out_) → goalF_out_g(T70)
goalF_in_g(T70) → U23_g(T70, pE_in_aa(X495, X497))
U23_g(T70, pE_out_aa(X495, X497)) → goalF_out_g(T70)

The argument filtering Pi contains the following mapping:
goalF_in_g(x1)  =  goalF_in_g(x1)
0  =  0
U9_g(x1)  =  U9_g(x1)
treeB_in_  =  treeB_in_
treeB_out_  =  treeB_out_
goalF_out_g(x1)  =  goalF_out_g
s(x1)  =  s(x1)
U10_g(x1, x2)  =  U10_g(x2)
s2tA_in_ga(x1, x2)  =  s2tA_in_ga(x1)
s2tA_out_ga(x1, x2)  =  s2tA_out_ga(x2)
U1_ga(x1, x2, x3, x4)  =  U1_ga(x4)
U2_ga(x1, x2, x3, x4)  =  U2_ga(x4)
U3_ga(x1, x2, x3, x4)  =  U3_ga(x4)
node(x1, x2, x3)  =  node(x1, x3)
U11_g(x1, x2)  =  U11_g(x2)
U12_g(x1, x2)  =  U12_g(x2)
pD_in_  =  pD_in_
U4_(x1)  =  U4_(x1)
pD_out_  =  pD_out_
U5_(x1)  =  U5_(x1)
U13_g(x1, x2)  =  U13_g(x2)
pE_in_aa(x1, x2)  =  pE_in_aa
U6_aa(x1, x2, x3)  =  U6_aa(x3)
treeC_in_a(x1)  =  treeC_in_a
treeC_out_a(x1)  =  treeC_out_a(x1)
pE_out_aa(x1, x2)  =  pE_out_aa(x1)
U7_aa(x1, x2, x3)  =  U7_aa(x3)
U8_aa(x1, x2, x3)  =  U8_aa(x1, x3)
U14_g(x1, x2)  =  U14_g(x2)
U15_g(x1, x2)  =  U15_g(x2)
U16_g(x1, x2)  =  U16_g(x2)
U17_g(x1, x2)  =  U17_g(x2)
U18_g(x1, x2)  =  U18_g(x2)
U19_g(x1, x2)  =  U19_g(x2)
U20_g(x1, x2)  =  U20_g(x2)
U21_g(x1, x2)  =  U21_g(x2)
U22_g(x1, x2)  =  U22_g(x2)
U23_g(x1, x2)  =  U23_g(x2)
nil  =  nil
GOALF_IN_G(x1)  =  GOALF_IN_G(x1)
U9_G(x1)  =  U9_G(x1)
TREEB_IN_  =  TREEB_IN_
U10_G(x1, x2)  =  U10_G(x2)
S2TA_IN_GA(x1, x2)  =  S2TA_IN_GA(x1)
U1_GA(x1, x2, x3, x4)  =  U1_GA(x4)
U2_GA(x1, x2, x3, x4)  =  U2_GA(x4)
U3_GA(x1, x2, x3, x4)  =  U3_GA(x4)
U11_G(x1, x2)  =  U11_G(x2)
U12_G(x1, x2)  =  U12_G(x2)
PD_IN_  =  PD_IN_
U4_¹(x1)  =  U4_¹(x1)
U5_¹(x1)  =  U5_¹(x1)
U13_G(x1, x2)  =  U13_G(x2)
PE_IN_AA(x1, x2)  =  PE_IN_AA
U6_AA(x1, x2, x3)  =  U6_AA(x3)
TREEC_IN_A(x1)  =  TREEC_IN_A
U7_AA(x1, x2, x3)  =  U7_AA(x3)
U8_AA(x1, x2, x3)  =  U8_AA(x1, x3)
U14_G(x1, x2)  =  U14_G(x2)
U15_G(x1, x2)  =  U15_G(x2)
U16_G(x1, x2)  =  U16_G(x2)
U17_G(x1, x2)  =  U17_G(x2)
U18_G(x1, x2)  =  U18_G(x2)
U19_G(x1, x2)  =  U19_G(x2)
U20_G(x1, x2)  =  U20_G(x2)
U21_G(x1, x2)  =  U21_G(x2)
U22_G(x1, x2)  =  U22_G(x2)
U23_G(x1, x2)  =  U23_G(x2)

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

(7) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 37 less nodes.

(8) Obligation:

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

S2TA_IN_GA(s(T28), node(nil, X146, X147)) → S2TA_IN_GA(T28, X147)
S2TA_IN_GA(s(T20), node(X107, X108, X107)) → S2TA_IN_GA(T20, X107)
S2TA_IN_GA(s(T36), node(X185, X186, nil)) → S2TA_IN_GA(T36, X185)

The TRS R consists of the following rules:

goalF_in_g(0) → U9_g(treeB_in_)
treeB_in_ → treeB_out_
U9_g(treeB_out_) → goalF_out_g(0)
goalF_in_g(s(T11)) → U10_g(T11, s2tA_in_ga(T11, X54))
s2tA_in_ga(0, nil) → s2tA_out_ga(0, nil)
s2tA_in_ga(s(T20), node(X107, X108, X107)) → U1_ga(T20, X107, X108, s2tA_in_ga(T20, X107))
s2tA_in_ga(s(T28), node(nil, X146, X147)) → U2_ga(T28, X146, X147, s2tA_in_ga(T28, X147))
s2tA_in_ga(s(T36), node(X185, X186, nil)) → U3_ga(T36, X185, X186, s2tA_in_ga(T36, X185))
s2tA_in_ga(T39, node(nil, X202, nil)) → s2tA_out_ga(T39, node(nil, X202, nil))
U3_ga(T36, X185, X186, s2tA_out_ga(T36, X185)) → s2tA_out_ga(s(T36), node(X185, X186, nil))
U2_ga(T28, X146, X147, s2tA_out_ga(T28, X147)) → s2tA_out_ga(s(T28), node(nil, X146, X147))
U1_ga(T20, X107, X108, s2tA_out_ga(T20, X107)) → s2tA_out_ga(s(T20), node(X107, X108, X107))
U10_g(T11, s2tA_out_ga(T11, X54)) → goalF_out_g(s(T11))
goalF_in_g(s(T11)) → U11_g(T11, s2tA_in_ga(T11, T42))
U11_g(T11, s2tA_out_ga(T11, T42)) → U12_g(T11, pD_in_)
pD_in_ → U4_(treeB_in_)
U4_(treeB_out_) → pD_out_
U4_(treeB_out_) → U5_(treeB_in_)
U5_(treeB_out_) → pD_out_
U12_g(T11, pD_out_) → goalF_out_g(s(T11))
U11_g(T11, s2tA_out_ga(T11, T42)) → U13_g(T11, pE_in_aa(X251, X253))
pE_in_aa(X251, X253) → U6_aa(X251, X253, treeC_in_a(X251))
treeC_in_a(nil) → treeC_out_a(nil)
U6_aa(X251, X253, treeC_out_a(X251)) → pE_out_aa(X251, X253)
pE_in_aa(T43, X253) → U7_aa(T43, X253, treeC_in_a(T43))
U7_aa(T43, X253, treeC_out_a(T43)) → U8_aa(T43, X253, treeC_in_a(X253))
U8_aa(T43, X253, treeC_out_a(X253)) → pE_out_aa(T43, X253)
U13_g(T11, pE_out_aa(X251, X253)) → goalF_out_g(s(T11))
goalF_in_g(s(T51)) → U14_g(T51, s2tA_in_ga(T51, X285))
U14_g(T51, s2tA_out_ga(T51, X285)) → goalF_out_g(s(T51))
goalF_in_g(s(T51)) → U15_g(T51, s2tA_in_ga(T51, T55))
U15_g(T51, s2tA_out_ga(T51, T55)) → U16_g(T51, pD_in_)
U16_g(T51, pD_out_) → goalF_out_g(s(T51))
U15_g(T51, s2tA_out_ga(T51, T55)) → U17_g(T51, pE_in_aa(X343, X345))
U17_g(T51, pE_out_aa(X343, X345)) → goalF_out_g(s(T51))
goalF_in_g(s(T63)) → U18_g(T63, s2tA_in_ga(T63, X376))
U18_g(T63, s2tA_out_ga(T63, X376)) → goalF_out_g(s(T63))
goalF_in_g(s(T63)) → U19_g(T63, s2tA_in_ga(T63, T67))
U19_g(T63, s2tA_out_ga(T63, T67)) → U20_g(T63, pD_in_)
U20_g(T63, pD_out_) → goalF_out_g(s(T63))
U19_g(T63, s2tA_out_ga(T63, T67)) → U21_g(T63, pE_in_aa(X435, X437))
U21_g(T63, pE_out_aa(X435, X437)) → goalF_out_g(s(T63))
goalF_in_g(T70) → U22_g(T70, pD_in_)
U22_g(T70, pD_out_) → goalF_out_g(T70)
goalF_in_g(T70) → U23_g(T70, pE_in_aa(X495, X497))
U23_g(T70, pE_out_aa(X495, X497)) → goalF_out_g(T70)

The argument filtering Pi contains the following mapping:
goalF_in_g(x1)  =  goalF_in_g(x1)
0  =  0
U9_g(x1)  =  U9_g(x1)
treeB_in_  =  treeB_in_
treeB_out_  =  treeB_out_
goalF_out_g(x1)  =  goalF_out_g
s(x1)  =  s(x1)
U10_g(x1, x2)  =  U10_g(x2)
s2tA_in_ga(x1, x2)  =  s2tA_in_ga(x1)
s2tA_out_ga(x1, x2)  =  s2tA_out_ga(x2)
U1_ga(x1, x2, x3, x4)  =  U1_ga(x4)
U2_ga(x1, x2, x3, x4)  =  U2_ga(x4)
U3_ga(x1, x2, x3, x4)  =  U3_ga(x4)
node(x1, x2, x3)  =  node(x1, x3)
U11_g(x1, x2)  =  U11_g(x2)
U12_g(x1, x2)  =  U12_g(x2)
pD_in_  =  pD_in_
U4_(x1)  =  U4_(x1)
pD_out_  =  pD_out_
U5_(x1)  =  U5_(x1)
U13_g(x1, x2)  =  U13_g(x2)
pE_in_aa(x1, x2)  =  pE_in_aa
U6_aa(x1, x2, x3)  =  U6_aa(x3)
treeC_in_a(x1)  =  treeC_in_a
treeC_out_a(x1)  =  treeC_out_a(x1)
pE_out_aa(x1, x2)  =  pE_out_aa(x1)
U7_aa(x1, x2, x3)  =  U7_aa(x3)
U8_aa(x1, x2, x3)  =  U8_aa(x1, x3)
U14_g(x1, x2)  =  U14_g(x2)
U15_g(x1, x2)  =  U15_g(x2)
U16_g(x1, x2)  =  U16_g(x2)
U17_g(x1, x2)  =  U17_g(x2)
U18_g(x1, x2)  =  U18_g(x2)
U19_g(x1, x2)  =  U19_g(x2)
U20_g(x1, x2)  =  U20_g(x2)
U21_g(x1, x2)  =  U21_g(x2)
U22_g(x1, x2)  =  U22_g(x2)
U23_g(x1, x2)  =  U23_g(x2)
nil  =  nil
S2TA_IN_GA(x1, x2)  =  S2TA_IN_GA(x1)

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

(9) UsableRulesProof (EQUIVALENT transformation)

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

(10) Obligation:

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

S2TA_IN_GA(s(T28), node(nil, X146, X147)) → S2TA_IN_GA(T28, X147)
S2TA_IN_GA(s(T20), node(X107, X108, X107)) → S2TA_IN_GA(T20, X107)
S2TA_IN_GA(s(T36), node(X185, X186, nil)) → S2TA_IN_GA(T36, X185)

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

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

(11) PiDPToQDPProof (SOUND transformation)

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

(12) Obligation:

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

S2TA_IN_GA(s(T28)) → S2TA_IN_GA(T28)

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

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

• S2TA_IN_GA(s(T28)) → S2TA_IN_GA(T28)
  The graph contains the following edges 1 > 1

(14) YES