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(f(X)) → mark(if(X, c, f(true)))
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(f(X)) → f(active(X))
active(if(X1, X2, X3)) → if(active(X1), X2, X3)
active(if(X1, X2, X3)) → if(X1, active(X2), X3)
f(mark(X)) → mark(f(X))
if(mark(X1), X2, X3) → mark(if(X1, X2, X3))
if(X1, mark(X2), X3) → mark(if(X1, X2, X3))
proper(f(X)) → f(proper(X))
proper(if(X1, X2, X3)) → if(proper(X1), proper(X2), proper(X3))
proper(c) → ok(c)
proper(true) → ok(true)
proper(false) → ok(false)
f(ok(X)) → ok(f(X))
if(ok(X1), ok(X2), ok(X3)) → ok(if(X1, X2, X3))
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(f(X)) → mark(if(X, c, f(true)))
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(f(X)) → f(active(X))
active(if(X1, X2, X3)) → if(active(X1), X2, X3)
active(if(X1, X2, X3)) → if(X1, active(X2), X3)
f(mark(X)) → mark(f(X))
if(mark(X1), X2, X3) → mark(if(X1, X2, X3))
if(X1, mark(X2), X3) → mark(if(X1, X2, X3))
proper(f(X)) → f(proper(X))
proper(if(X1, X2, X3)) → if(proper(X1), proper(X2), proper(X3))
proper(c) → ok(c)
proper(true) → ok(true)
proper(false) → ok(false)
f(ok(X)) → ok(f(X))
if(ok(X1), ok(X2), ok(X3)) → ok(if(X1, X2, X3))
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:

f: {1}
if: {1, 2}
c: empty set
true: empty set
false: 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:

f(X) → if(X, c, f(true))
if(true, X, Y) → X
if(false, X, Y) → Y

The replacement map contains the following entries:

f: {1}
if: {1, 2}
c: empty set
true: empty set
false: empty set

(3) PoloCSRProof (EQUIVALENT transformation)

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

if(false, X, Y) → Y

Used ordering:
Polynomial interpretation [POLO]:

POL(c) = 0   
POL(f(x₁)) = x₁   
POL(false) = 2   
POL(if(x₁, x₂, x₃)) = x₁ + 2·x₂ + 2·x₃   
POL(true) = 0   

(4) Obligation:

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

f(X) → if(X, c, f(true))
if(true, X, Y) → X

The replacement map contains the following entries:

f: {1}
if: {1, 2}
c: empty set
true: empty set

(5) PoloCSRProof (EQUIVALENT transformation)

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

f(X) → if(X, c, f(true))
if(true, X, Y) → X

Used ordering:
Polynomial interpretation [POLO]:

POL(c) = 0   
POL(f(x₁)) = 2 + 2·x₁   
POL(if(x₁, x₂, x₃)) = 1 + x₁ + 2·x₂   
POL(true) = 1   

(6) Obligation:

Context-sensitive rewrite system:
R is empty.

(7) RisEmptyProof (EQUIVALENT transformation)

The CSR R is empty. Hence, termination is trivially proven.

(8) TRUE