Termination w.r.t. Q of the given QTRS could not be shown:

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

g(x, x) → g(a, b)
g(c, g(c, x)) → g(e, g(d, x))
g(d, g(d, x)) → g(c, g(e, x))
g(e, g(e, x)) → g(d, g(c, x))
f(g(x, y)) → g(y, g(f(f(x)), a))

Q is empty.

(1) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(2) Obligation:

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

G(x, x) → G(a, b)
G(c, g(c, x)) → G(e, g(d, x))
G(c, g(c, x)) → G(d, x)
G(d, g(d, x)) → G(c, g(e, x))
G(d, g(d, x)) → G(e, x)
G(e, g(e, x)) → G(d, g(c, x))
G(e, g(e, x)) → G(c, x)
F(g(x, y)) → G(y, g(f(f(x)), a))
F(g(x, y)) → G(f(f(x)), a)
F(g(x, y)) → F(f(x))
F(g(x, y)) → F(x)

The TRS R consists of the following rules:

g(x, x) → g(a, b)
g(c, g(c, x)) → g(e, g(d, x))
g(d, g(d, x)) → g(c, g(e, x))
g(e, g(e, x)) → g(d, g(c, x))
f(g(x, y)) → g(y, g(f(f(x)), a))

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

(3) DependencyGraphProof (EQUIVALENT transformation)

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

(4) Complex Obligation (AND)

(5) Obligation:

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

G(e, g(e, x)) → G(d, g(c, x))
G(d, g(d, x)) → G(c, g(e, x))
G(c, g(c, x)) → G(e, g(d, x))
G(e, g(e, x)) → G(c, x)
G(c, g(c, x)) → G(d, x)
G(d, g(d, x)) → G(e, x)

The TRS R consists of the following rules:

g(x, x) → g(a, b)
g(c, g(c, x)) → g(e, g(d, x))
g(d, g(d, x)) → g(c, g(e, x))
g(e, g(e, x)) → g(d, g(c, x))
f(g(x, y)) → g(y, g(f(f(x)), a))

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

(6) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

G(e, g(e, x)) → G(c, x)
G(c, g(c, x)) → G(d, x)
G(d, g(d, x)) → G(e, x)

The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
G(x1, x2)  =  G(x2)
e  =  e
g(x1, x2)  =  g(x2)
d  =  d
c  =  c
a  =  a
b  =  b
f(x1)  =  f(x1)

Lexicographic path order with status [LPO].
Precedence:

G₁ > e > c > g₁ > a > b
G₁ > d > c > g₁ > a > b
f₁ > g₁ > a > b

Status:

c: []
a: []
f₁: [1]
g₁: [1]
e: []
b: []
d: []
G₁: [1]

The following usable rules [FROCOS05] were oriented:

g(x, x) → g(a, b)
g(c, g(c, x)) → g(e, g(d, x))
g(d, g(d, x)) → g(c, g(e, x))
g(e, g(e, x)) → g(d, g(c, x))
f(g(x, y)) → g(y, g(f(f(x)), a))

(7) Obligation:

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

G(e, g(e, x)) → G(d, g(c, x))
G(d, g(d, x)) → G(c, g(e, x))
G(c, g(c, x)) → G(e, g(d, x))

The TRS R consists of the following rules:

g(x, x) → g(a, b)
g(c, g(c, x)) → g(e, g(d, x))
g(d, g(d, x)) → g(c, g(e, x))
g(e, g(e, x)) → g(d, g(c, x))
f(g(x, y)) → g(y, g(f(f(x)), a))

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

(8) Obligation:

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

F(g(x, y)) → F(x)
F(g(x, y)) → F(f(x))

The TRS R consists of the following rules:

g(x, x) → g(a, b)
g(c, g(c, x)) → g(e, g(d, x))
g(d, g(d, x)) → g(c, g(e, x))
g(e, g(e, x)) → g(d, g(c, x))
f(g(x, y)) → g(y, g(f(f(x)), a))

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