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

(0) Obligation:

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

active(h(X)) → mark(g(X, X))
active(g(a, X)) → mark(f(b, X))
active(f(X, X)) → mark(h(a))
active(a) → mark(b)
active(h(X)) → h(active(X))
active(g(X1, X2)) → g(active(X1), X2)
active(f(X1, X2)) → f(active(X1), X2)
h(mark(X)) → mark(h(X))
g(mark(X1), X2) → mark(g(X1, X2))
f(mark(X1), X2) → mark(f(X1, X2))
proper(h(X)) → h(proper(X))
proper(g(X1, X2)) → g(proper(X1), proper(X2))
proper(a) → ok(a)
proper(f(X1, X2)) → f(proper(X1), proper(X2))
proper(b) → ok(b)
h(ok(X)) → ok(h(X))
g(ok(X1), ok(X2)) → ok(g(X1, X2))
f(ok(X1), ok(X2)) → ok(f(X1, X2))
top(mark(X)) → top(proper(X))
top(ok(X)) → top(active(X))

Q is empty.

(1) QTRSToCSRProof (EQUIVALENT transformation)

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

active(h(X)) → mark(g(X, X))
active(g(a, X)) → mark(f(b, X))
active(f(X, X)) → mark(h(a))
active(a) → mark(b)
active(h(X)) → h(active(X))
active(g(X1, X2)) → g(active(X1), X2)
active(f(X1, X2)) → f(active(X1), X2)
h(mark(X)) → mark(h(X))
g(mark(X1), X2) → mark(g(X1, X2))
f(mark(X1), X2) → mark(f(X1, X2))
proper(h(X)) → h(proper(X))
proper(g(X1, X2)) → g(proper(X1), proper(X2))
proper(a) → ok(a)
proper(f(X1, X2)) → f(proper(X1), proper(X2))
proper(b) → ok(b)
h(ok(X)) → ok(h(X))
g(ok(X1), ok(X2)) → ok(g(X1, X2))
f(ok(X1), ok(X2)) → ok(f(X1, X2))
top(mark(X)) → top(proper(X))
top(ok(X)) → top(active(X))

Q is empty.
Special symbols used for the transformation (see [GM04]):
top: top, active: active, mark: mark, ok: ok, proper: proper
The replacement map contains the following entries:

h: {1}
g: {1}
a: empty set
f: {1}
b: empty set
The QTRS contained all rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is complete (and sound).

(2) Obligation:

Context-sensitive rewrite system:
The TRS R consists of the following rules:

h(X) → g(X, X)
g(a, X) → f(b, X)
f(X, X) → h(a)
a → b

The replacement map contains the following entries:

h: {1}
g: {1}
a: empty set
f: {1}
b: empty set

(3) PoloCSRProof (EQUIVALENT transformation)

The following rules can be removed because they are oriented strictly by a µ-monotonic polynomial ordering:

a → b

Used ordering:
Polynomial interpretation [POLO]:

POL(a) = 1   
POL(b) = 0   
POL(f(x₁, x₂)) = 2 + 2·x₁   
POL(g(x₁, x₂)) = 2·x₁   
POL(h(x₁)) = 2·x₁   

(4) Obligation:

Context-sensitive rewrite system:
The TRS R consists of the following rules:

h(X) → g(X, X)
g(a, X) → f(b, X)
f(X, X) → h(a)

The replacement map contains the following entries:

h: {1}
g: {1}
a: empty set
f: {1}
b: empty set

(5) CSDependencyPairsProof (EQUIVALENT transformation)

Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.

(6) Obligation:

Q-restricted context-sensitive dependency pair problem:
The symbols in {h, H} are replacing on all positions.
For all symbols f in {g, f, G, F} we have µ(f) = {1}.

The ordinary context-sensitive dependency pairs DP_o are:

H(X) → G(X, X)
G(a, X) → F(b, X)
F(X, X) → H(a)

The TRS R consists of the following rules:

h(X) → g(X, X)
g(a, X) → f(b, X)
f(X, X) → h(a)

Q is empty.

(7) QCSDPInstantiationProcessor (EQUIVALENT transformation)

Using the Context-Sensitive Instantiation[LPAR08,DA_EMMES] Processor
the pair H(X) → G(X, X)
was transformed to the following new pairs:

H(a) → G(a, a)

(8) Obligation:

Q-restricted context-sensitive dependency pair problem:
The symbols in {h, H} are replacing on all positions.
For all symbols f in {g, f, F, G} we have µ(f) = {1}.

The TRS P consists of the following rules:

G(a, X) → F(b, X)
F(X, X) → H(a)
H(a) → G(a, a)

The TRS R consists of the following rules:

h(X) → g(X, X)
g(a, X) → f(b, X)
f(X, X) → h(a)

Q is empty.

(9) QCSUsableRulesProof (EQUIVALENT transformation)

The following rules are not useable [DA_EMMES] and can be deleted:

h(x0) → g(x0, x0)
g(a, x0) → f(b, x0)
f(x0, x0) → h(a)

(10) Obligation:

Q-restricted context-sensitive dependency pair problem:
The symbols in {H} are replacing on all positions.
For all symbols f in {F, G} we have µ(f) = {1}.

The TRS P consists of the following rules:

G(a, X) → F(b, X)
F(X, X) → H(a)
H(a) → G(a, a)

R is empty.
Q is empty.

(11) QCSDPInstantiationProcessor (EQUIVALENT transformation)

Using the Context-Sensitive Instantiation[LPAR08,DA_EMMES] Processor
the pair G(a, X) → F(b, X)
was transformed to the following new pairs:

G(a, a) → F(b, a)

(12) Obligation:

Q-restricted context-sensitive dependency pair problem:
The symbols in {H} are replacing on all positions.
For all symbols f in {F, G} we have µ(f) = {1}.

The TRS P consists of the following rules:

F(X, X) → H(a)
H(a) → G(a, a)
G(a, a) → F(b, a)

R is empty.
Q is empty.

(13) QCSDependencyGraphProof (EQUIVALENT transformation)

The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 3 less nodes.
The rules G(a, a) → F(b, a) and F(x0, x0) → H(a) form no chain, because ECap^µ(F(b, a)) = F(b, a) does not unify with F(x0, x0).

(14) TRUE