(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
active(f(X, g(X), Y)) → mark(f(Y, Y, Y))
active(g(b)) → mark(c)
active(b) → mark(c)
active(g(X)) → g(active(X))
g(mark(X)) → mark(g(X))
proper(f(X1, X2, X3)) → f(proper(X1), proper(X2), proper(X3))
proper(g(X)) → g(proper(X))
proper(b) → ok(b)
proper(c) → ok(c)
f(ok(X1), ok(X2), ok(X3)) → ok(f(X1, X2, X3))
g(ok(X)) → ok(g(X))
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, g(X), Y)) → mark(f(Y, Y, Y))
active(g(b)) → mark(c)
active(b) → mark(c)
active(g(X)) → g(active(X))
g(mark(X)) → mark(g(X))
proper(f(X1, X2, X3)) → f(proper(X1), proper(X2), proper(X3))
proper(g(X)) → g(proper(X))
proper(b) → ok(b)
proper(c) → ok(c)
f(ok(X1), ok(X2), ok(X3)) → ok(f(X1, X2, X3))
g(ok(X)) → ok(g(X))
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: empty set
g: {1}
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(X, g(X), Y) → f(Y, Y, Y)
g(b) → c
b → c
The replacement map contains the following entries:
f: empty set
g: {1}
b: empty set
c: empty set
(3) PoloCSRProof (EQUIVALENT transformation)
The following rules can be removed because they are oriented strictly by a µ-monotonic polynomial ordering:
g(b) → c
b → c
Used ordering:
Polynomial interpretation [POLO]:
POL(b) = 2
POL(c) = 1
POL(f(x1, x2, x3)) = 0
POL(g(x1)) = 2 + 2·x1
(4) Obligation:
Context-sensitive rewrite system:
The TRS R consists of the following rules:
f(X, g(X), Y) → f(Y, Y, Y)
The replacement map contains the following entries:
f: empty set
g: {1}
(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 {
g} are replacing on all positions.
The symbols in {
f,
F} are not replacing on any position.
The ordinary context-sensitive dependency pairs DP
o are:
F(X, g(X), Y) → F(Y, Y, Y)
The TRS R consists of the following rules:
f(X, g(X), Y) → f(Y, Y, Y)
Q is empty.
(7) QCSDependencyGraphProof (EQUIVALENT transformation)
The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs.
The rules F(z0, g(z0), z1) → F(z1, z1, z1) and F(x0, g(x0), x1) → F(x1, x1, x1) form no chain, because ECapµ(F(z1, z1, z1)) = F(z1, z1, z1) does not unify with F(x0, g(x0), x1).
(8) TRUE