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

(0) Obligation:

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

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

Q is empty.

(1) Overlay + Local Confluence (EQUIVALENT transformation)

The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.

(2) Obligation:

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

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

The set Q consists of the following terms:

g(f(x0, x1))

(3) DependencyPairsProof (EQUIVALENT transformation)

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

(4) Obligation:

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

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

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

g(f(x0, x1))

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

(5) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule G(f(x, y)) → G(g(x)) at position [0] we obtained the following new rules [LPAR04]:

G(f(f(x0, x1), y1)) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))

(6) Obligation:

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

G(f(x, y)) → G(x)
G(f(x, y)) → G(g(y))
G(f(x, y)) → G(y)
G(f(f(x0, x1), y1)) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

g(f(x0, x1))

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

(7) Narrowing (EQUIVALENT transformation)

By narrowing [LPAR04] the rule G(f(x, y)) → G(g(y)) at position [0] we obtained the following new rules [LPAR04]:

G(f(y0, f(x0, x1))) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))

(8) Obligation:

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

G(f(x, y)) → G(x)
G(f(x, y)) → G(y)
G(f(f(x0, x1), y1)) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))
G(f(y0, f(x0, x1))) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

g(f(x0, x1))

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

(9) ForwardInstantiation (EQUIVALENT transformation)

By forward instantiating [JAR06] the rule G(f(x, y)) → G(x) we obtained the following new rules [LPAR04]:

G(f(f(y_0, y_1), x1)) → G(f(y_0, y_1))
G(f(f(f(y_0, y_1), y_2), x1)) → G(f(f(y_0, y_1), y_2))
G(f(f(y_0, f(y_1, y_2)), x1)) → G(f(y_0, f(y_1, y_2)))

(10) Obligation:

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

G(f(x, y)) → G(y)
G(f(f(x0, x1), y1)) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))
G(f(y0, f(x0, x1))) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))
G(f(f(y_0, y_1), x1)) → G(f(y_0, y_1))
G(f(f(f(y_0, y_1), y_2), x1)) → G(f(f(y_0, y_1), y_2))
G(f(f(y_0, f(y_1, y_2)), x1)) → G(f(y_0, f(y_1, y_2)))

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

g(f(x0, x1))

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

(11) ForwardInstantiation (EQUIVALENT transformation)

By forward instantiating [JAR06] the rule G(f(x, y)) → G(y) we obtained the following new rules [LPAR04]:

G(f(x0, f(y_0, y_1))) → G(f(y_0, y_1))
G(f(x0, f(f(y_0, y_1), y_2))) → G(f(f(y_0, y_1), y_2))
G(f(x0, f(y_0, f(y_1, y_2)))) → G(f(y_0, f(y_1, y_2)))
G(f(x0, f(f(f(y_0, y_1), y_2), y_3))) → G(f(f(f(y_0, y_1), y_2), y_3))
G(f(x0, f(f(y_0, f(y_1, y_2)), y_3))) → G(f(f(y_0, f(y_1, y_2)), y_3))

(12) Obligation:

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

G(f(f(x0, x1), y1)) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))
G(f(y0, f(x0, x1))) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))
G(f(f(y_0, y_1), x1)) → G(f(y_0, y_1))
G(f(f(f(y_0, y_1), y_2), x1)) → G(f(f(y_0, y_1), y_2))
G(f(f(y_0, f(y_1, y_2)), x1)) → G(f(y_0, f(y_1, y_2)))
G(f(x0, f(y_0, y_1))) → G(f(y_0, y_1))
G(f(x0, f(f(y_0, y_1), y_2))) → G(f(f(y_0, y_1), y_2))
G(f(x0, f(y_0, f(y_1, y_2)))) → G(f(y_0, f(y_1, y_2)))
G(f(x0, f(f(f(y_0, y_1), y_2), y_3))) → G(f(f(f(y_0, y_1), y_2), y_3))
G(f(x0, f(f(y_0, f(y_1, y_2)), y_3))) → G(f(f(y_0, f(y_1, y_2)), y_3))

The TRS R consists of the following rules:

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

The set Q consists of the following terms:

g(f(x0, x1))

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

(13) MNOCProof (EQUIVALENT transformation)

We use the modular non-overlap check [FROCOS05] to decrease Q to the empty set.

(14) Obligation:

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

G(f(f(x0, x1), y1)) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))
G(f(y0, f(x0, x1))) → G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))
G(f(f(y_0, y_1), x1)) → G(f(y_0, y_1))
G(f(f(f(y_0, y_1), y_2), x1)) → G(f(f(y_0, y_1), y_2))
G(f(f(y_0, f(y_1, y_2)), x1)) → G(f(y_0, f(y_1, y_2)))
G(f(x0, f(y_0, y_1))) → G(f(y_0, y_1))
G(f(x0, f(f(y_0, y_1), y_2))) → G(f(f(y_0, y_1), y_2))
G(f(x0, f(y_0, f(y_1, y_2)))) → G(f(y_0, f(y_1, y_2)))
G(f(x0, f(f(f(y_0, y_1), y_2), y_3))) → G(f(f(f(y_0, y_1), y_2), y_3))
G(f(x0, f(f(y_0, f(y_1, y_2)), y_3))) → G(f(f(y_0, f(y_1, y_2)), y_3))

The TRS R consists of the following rules:

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

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

(15) NonTerminationProof (EQUIVALENT transformation)

We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = G(f(f(x0, x1), y1)) evaluates to t =G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1)))))

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:

• Matcher: [x0 / g(g(x0)), x1 / g(g(x1)), y1 / f(g(g(x0)), g(g(x1)))]
• Semiunifier: [ ]

---

Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from G(f(f(x0, x1), y1)) to G(f(f(g(g(x0)), g(g(x1))), f(g(g(x0)), g(g(x1))))).

(16) FALSE