YES Termination w.r.t. Q proof of Transformed_CSR_04_Ex9_Luc04_C.ari

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

0 QTRS
↳1 QTRSToCSRProof (⇔, 0 ms)
↳2 CSR
↳3 CSDependencyPairsProof (⇔, 3 ms)
↳4 QCSDP
↳5 QCSDPForwardInstantiationProcessor (⇔, 0 ms)
↳6 QCSDP
↳7 PIsEmptyProof (⇔, 0 ms)
↳8 YES

(0) Obligation:

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

active(f(a, b, X)) → mark(f(X, X, X))
active(c) → mark(a)
active(c) → mark(b)
active(f(X1, X2, X3)) → f(active(X1), X2, X3)
active(f(X1, X2, X3)) → f(X1, X2, active(X3))
f(mark(X1), X2, X3) → mark(f(X1, X2, X3))
f(X1, X2, mark(X3)) → mark(f(X1, X2, X3))
proper(f(X1, X2, X3)) → f(proper(X1), proper(X2), proper(X3))
proper(a) → ok(a)
proper(b) → ok(b)
proper(c) → ok(c)
f(ok(X1), ok(X2), ok(X3)) → ok(f(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(a, b, X)) → mark(f(X, X, X))
active(c) → mark(a)
active(c) → mark(b)
active(f(X1, X2, X3)) → f(active(X1), X2, X3)
active(f(X1, X2, X3)) → f(X1, X2, active(X3))
f(mark(X1), X2, X3) → mark(f(X1, X2, X3))
f(X1, X2, mark(X3)) → mark(f(X1, X2, X3))
proper(f(X1, X2, X3)) → f(proper(X1), proper(X2), proper(X3))
proper(a) → ok(a)
proper(b) → ok(b)
proper(c) → ok(c)
f(ok(X1), ok(X2), ok(X3)) → ok(f(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, 3}
a: empty set
b: empty set
c: 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(a, b, X) → f(X, X, X)
c → a
c → b

The replacement map contains the following entries:

f: {1, 3}
a: empty set
b: empty set
c: empty set

(3) CSDependencyPairsProof (EQUIVALENT transformation)

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

(4) Obligation:

Q-restricted context-sensitive dependency pair problem:
For all symbols f in {f, F} we have µ(f) = {1, 3}.

The ordinary context-sensitive dependency pairs DPo are:

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

The TRS R consists of the following rules:

f(a, b, X) → f(X, X, X)
c → a
c → b

Q is empty.

(5) QCSDPForwardInstantiationProcessor (EQUIVALENT transformation)

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

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

(6) Obligation:

Q-restricted context-sensitive dependency pair problem:
For all symbols f in {f} we have µ(f) = {1, 3}.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

f(a, b, X) → f(X, X, X)
c → a
c → b

Q is empty.

(7) PIsEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R,µ)-chain.

(8) YES