(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
active(f(a, X, X)) → mark(f(X, b, b))
active(b) → mark(a)
active(f(X1, X2, X3)) → f(X1, active(X2), X3)
f(X1, mark(X2), 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)
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, X, X)) → mark(f(X, b, b))
active(b) → mark(a)
active(f(X1, X2, X3)) → f(X1, active(X2), X3)
f(X1, mark(X2), 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)
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:
properThe replacement map contains the following entries:
f: {2}
a: empty set
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:
f(a, X, X) → f(X, b, b)
b → a
The replacement map contains the following entries:
f: {2}
a: empty set
b: 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) = {2}.
The ordinary context-sensitive dependency pairs DP
o are:
F(a, X, X) → F(X, b, b)
F(a, X, X) → B
The TRS R consists of the following rules:
f(a, X, X) → f(X, b, b)
b → a
Q is empty.
(5) QCSDependencyGraphProof (EQUIVALENT transformation)
The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 1 SCC with 1 less node.
(6) Obligation:
Q-restricted context-sensitive dependency pair problem:
For all symbols f in {
f,
F} we have µ(f) = {2}.
The TRS P consists of the following rules:
F(a, X, X) → F(X, b, b)
The TRS R consists of the following rules:
f(a, X, X) → f(X, b, b)
b → a
Q is empty.
(7) QCSUsableRulesProof (EQUIVALENT transformation)
The following rules are not useable [DA_EMMES] and can be deleted:
f(a, x0, x0) → f(x0, b, b)
(8) Obligation:
Q-restricted context-sensitive dependency pair problem:
For all symbols f in {
F} we have µ(f) = {2}.
The TRS P consists of the following rules:
F(a, X, X) → F(X, b, b)
The TRS R consists of the following rules:
b → a
Q is empty.
(9) QCSDPInstantiationProcessor (EQUIVALENT transformation)
Using the Context-Sensitive Instantiation[LPAR08,DA_EMMES] Processor
the pair
F(
a,
X,
X) →
F(
X,
b,
b)
was transformed to the following new pairs:
F(a, b, b) → F(b, b, b)
(10) Obligation:
Q-restricted context-sensitive dependency pair problem:
The TRS P consists of the following rules:
none
The TRS R consists of the following rules:
b → a
Q is empty.
(11) PIsEmptyProof (EQUIVALENT transformation)
The TRS P is empty. Hence, there is no (P,Q,R,µ)-chain.
(12) YES