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:

a(f, a(g, a(f, x))) → a(f, a(g, a(g, a(f, x))))
a(g, a(f, a(g, x))) → a(g, a(f, a(f, a(g, x))))

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:

A(f, a(g, a(f, x))) → A(f, a(g, a(g, a(f, x))))
A(f, a(g, a(f, x))) → A(g, a(g, a(f, x)))
A(g, a(f, a(g, x))) → A(g, a(f, a(f, a(g, x))))
A(g, a(f, a(g, x))) → A(f, a(f, a(g, x)))

The TRS R consists of the following rules:

a(f, a(g, a(f, x))) → a(f, a(g, a(g, a(f, x))))
a(g, a(f, a(g, x))) → a(g, a(f, a(f, a(g, x))))

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

(3) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem.
The a-transformed P is

f1(g(f(x))) → f1(g(g(f(x))))
f1(g(f(x))) → g1(g(f(x)))
g1(f(g(x))) → g1(f(f(g(x))))
g1(f(g(x))) → f1(f(g(x)))

The a-transformed usable rules are

g(f(g(x))) → g(f(f(g(x))))
f(g(f(x))) → f(g(g(f(x))))

The following pairs can be oriented strictly and are deleted.

A(f, a(g, a(f, x))) → A(g, a(g, a(f, x)))
A(g, a(f, a(g, x))) → A(f, a(f, a(g, x)))

The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
f1(x1)  =  f1(x1)
g(x1)  =  g
f(x1)  =  f
g1(x1)  =  g1

Lexicographic path order with status [LPO].
Precedence:

g > g1 > f1₁ > f

Status:

f1₁: [1]
g: []
f: []
g1: []

The following usable rules [FROCOS05] were oriented:

a(g, a(f, a(g, x))) → a(g, a(f, a(f, a(g, x))))
a(f, a(g, a(f, x))) → a(f, a(g, a(g, a(f, x))))

(4) Obligation:

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

A(f, a(g, a(f, x))) → A(f, a(g, a(g, a(f, x))))
A(g, a(f, a(g, x))) → A(g, a(f, a(f, a(g, x))))

The TRS R consists of the following rules:

a(f, a(g, a(f, x))) → a(f, a(g, a(g, a(f, x))))
a(g, a(f, a(g, x))) → a(g, a(f, a(f, a(g, x))))

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

(5) DependencyGraphProof (EQUIVALENT transformation)

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

(6) Complex Obligation (AND)

(7) Obligation:

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

A(g, a(f, a(g, x))) → A(g, a(f, a(f, a(g, x))))

The TRS R consists of the following rules:

a(f, a(g, a(f, x))) → a(f, a(g, a(g, a(f, x))))
a(g, a(f, a(g, x))) → a(g, a(f, a(f, a(g, x))))

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:

A(f, a(g, a(f, x))) → A(f, a(g, a(g, a(f, x))))

The TRS R consists of the following rules:

a(f, a(g, a(f, x))) → a(f, a(g, a(g, a(f, x))))
a(g, a(f, a(g, x))) → a(g, a(f, a(f, a(g, x))))

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