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

0 QTRS
↳1 DependencyPairsProof (⇔)
↳2 QDP
↳3 DependencyGraphProof (⇔)
↳4 AND
  ↳5 QDP
    ↳6 QDPOrderProof (⇔)
    ↳7 QDP
    ↳8 DependencyGraphProof (⇔)
    ↳9 AND
      ↳10 QDP
      ↳11 QDP
  ↳12 QDP

(0) Obligation:

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

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))
g(x, g(y, g(x, y))) → g(a, g(x, g(y, b)))

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(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)
G(x, g(y, g(x, y))) → G(a, g(x, g(y, b)))
G(x, g(y, g(x, y))) → G(x, g(y, b))
G(x, g(y, g(x, y))) → G(y, b)

The TRS R consists of the following rules:

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))
g(x, g(y, g(x, y))) → g(a, g(x, g(y, b)))

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)
G(x, g(y, g(x, y))) → G(a, g(x, g(y, b)))
G(x, g(y, g(x, y))) → G(x, g(y, b))

The TRS R consists of the following rules:

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))
g(x, g(y, g(x, y))) → g(a, g(x, g(y, b)))

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)
G(x, g(y, g(x, y))) → G(x, g(y, b))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
G(x1, x2)  =  x2
e  =  e
g(x1, x2)  =  g(x2)
d  =  d
c  =  c
a  =  a
b  =  b
f(x1)  =  f(x1)

Lexicographic Path Order [LPO].
Precedence:
e > b
d > b
c > b
f1 > g1 > b
f1 > a > b

The following usable rules [FROCOS05] were oriented:

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))
g(x, g(y, g(x, y))) → g(a, g(x, g(y, b)))

(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))
G(x, g(y, g(x, y))) → G(a, g(x, g(y, b)))

The TRS R consists of the following rules:

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))
g(x, g(y, g(x, y))) → g(a, g(x, g(y, b)))

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

(8) DependencyGraphProof (EQUIVALENT transformation)

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

(9) Complex Obligation (AND)

(10) Obligation:

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

G(x, g(y, g(x, y))) → G(a, g(x, g(y, b)))

The TRS R consists of the following rules:

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))
g(x, g(y, g(x, y))) → g(a, g(x, g(y, b)))

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

(11) Obligation:

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

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(d, g(c, x))

The TRS R consists of the following rules:

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))
g(x, g(y, g(x, y))) → g(a, g(x, g(y, b)))

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

(12) 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(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))
g(x, g(y, g(x, y))) → g(a, g(x, g(y, b)))

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