Termination w.r.t. Q proof of Transformed_CSR_04_Ex9_BLR02

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

0 QTRS

↳1 QTRSToCSRProof (⇔, 0 ms)

↳2 CSR

↳3 CSRRRRProof (⇔, 53 ms)

↳4 CSR

↳5 CSRRRRProof (⇔, 0 ms)

↳6 CSR

↳7 CSRRRRProof (⇔, 0 ms)

↳8 CSR

↳9 RisEmptyProof (⇔, 0 ms)

↳10 YES

(0) Obligation:

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

active(filter(cons(X, Y), 0, M)) → mark(cons(0, filter(Y, M, M)))
active(filter(cons(X, Y), s(N), M)) → mark(cons(X, filter(Y, N, M)))
active(sieve(cons(0, Y))) → mark(cons(0, sieve(Y)))
active(sieve(cons(s(N), Y))) → mark(cons(s(N), sieve(filter(Y, N, N))))
active(nats(N)) → mark(cons(N, nats(s(N))))
active(zprimes) → mark(sieve(nats(s(s(0)))))
active(filter(X1, X2, X3)) → filter(active(X1), X2, X3)
active(filter(X1, X2, X3)) → filter(X1, active(X2), X3)
active(filter(X1, X2, X3)) → filter(X1, X2, active(X3))
active(cons(X1, X2)) → cons(active(X1), X2)
active(s(X)) → s(active(X))
active(sieve(X)) → sieve(active(X))
active(nats(X)) → nats(active(X))
filter(mark(X1), X2, X3) → mark(filter(X1, X2, X3))
filter(X1, mark(X2), X3) → mark(filter(X1, X2, X3))
filter(X1, X2, mark(X3)) → mark(filter(X1, X2, X3))
cons(mark(X1), X2) → mark(cons(X1, X2))
s(mark(X)) → mark(s(X))
sieve(mark(X)) → mark(sieve(X))
nats(mark(X)) → mark(nats(X))
proper(filter(X1, X2, X3)) → filter(proper(X1), proper(X2), proper(X3))
proper(cons(X1, X2)) → cons(proper(X1), proper(X2))
proper(0) → ok(0)
proper(s(X)) → s(proper(X))
proper(sieve(X)) → sieve(proper(X))
proper(nats(X)) → nats(proper(X))
proper(zprimes) → ok(zprimes)
filter(ok(X1), ok(X2), ok(X3)) → ok(filter(X1, X2, X3))
cons(ok(X1), ok(X2)) → ok(cons(X1, X2))
s(ok(X)) → ok(s(X))
sieve(ok(X)) → ok(sieve(X))
nats(ok(X)) → ok(nats(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(filter(cons(X, Y), 0, M)) → mark(cons(0, filter(Y, M, M)))
active(filter(cons(X, Y), s(N), M)) → mark(cons(X, filter(Y, N, M)))
active(sieve(cons(0, Y))) → mark(cons(0, sieve(Y)))
active(sieve(cons(s(N), Y))) → mark(cons(s(N), sieve(filter(Y, N, N))))
active(nats(N)) → mark(cons(N, nats(s(N))))
active(zprimes) → mark(sieve(nats(s(s(0)))))
active(filter(X1, X2, X3)) → filter(active(X1), X2, X3)
active(filter(X1, X2, X3)) → filter(X1, active(X2), X3)
active(filter(X1, X2, X3)) → filter(X1, X2, active(X3))
active(cons(X1, X2)) → cons(active(X1), X2)
active(s(X)) → s(active(X))
active(sieve(X)) → sieve(active(X))
active(nats(X)) → nats(active(X))
filter(mark(X1), X2, X3) → mark(filter(X1, X2, X3))
filter(X1, mark(X2), X3) → mark(filter(X1, X2, X3))
filter(X1, X2, mark(X3)) → mark(filter(X1, X2, X3))
cons(mark(X1), X2) → mark(cons(X1, X2))
s(mark(X)) → mark(s(X))
sieve(mark(X)) → mark(sieve(X))
nats(mark(X)) → mark(nats(X))
proper(filter(X1, X2, X3)) → filter(proper(X1), proper(X2), proper(X3))
proper(cons(X1, X2)) → cons(proper(X1), proper(X2))
proper(0) → ok(0)
proper(s(X)) → s(proper(X))
proper(sieve(X)) → sieve(proper(X))
proper(nats(X)) → nats(proper(X))
proper(zprimes) → ok(zprimes)
filter(ok(X1), ok(X2), ok(X3)) → ok(filter(X1, X2, X3))
cons(ok(X1), ok(X2)) → ok(cons(X1, X2))
s(ok(X)) → ok(s(X))
sieve(ok(X)) → ok(sieve(X))
nats(ok(X)) → ok(nats(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: proper
The replacement map contains the following entries:

filter: {1, 2, 3}
cons: {1}
0: empty set
s: {1}
sieve: {1}
nats: {1}
zprimes: 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:

filter(cons(X, Y), 0, M) → cons(0, filter(Y, M, M))
filter(cons(X, Y), s(N), M) → cons(X, filter(Y, N, M))
sieve(cons(0, Y)) → cons(0, sieve(Y))
sieve(cons(s(N), Y)) → cons(s(N), sieve(filter(Y, N, N)))
nats(N) → cons(N, nats(s(N)))
zprimes → sieve(nats(s(s(0))))

The replacement map contains the following entries:

filter: {1, 2, 3}
cons: {1}
0: empty set
s: {1}
sieve: {1}
nats: {1}
zprimes: empty set

(3) CSRRRRProof (EQUIVALENT transformation)

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

filter(cons(X, Y), 0, M) → cons(0, filter(Y, M, M))
filter(cons(X, Y), s(N), M) → cons(X, filter(Y, N, M))
sieve(cons(0, Y)) → cons(0, sieve(Y))
sieve(cons(s(N), Y)) → cons(s(N), sieve(filter(Y, N, N)))
nats(N) → cons(N, nats(s(N)))
zprimes → sieve(nats(s(s(0))))

The replacement map contains the following entries:

filter: {1, 2, 3}
cons: {1}
0: empty set
s: {1}
sieve: {1}
nats: {1}
zprimes: empty set
Used ordering:
Polynomial interpretation [POLO]:

POL(0) = 0
POL(cons(x₁, x₂)) = x₁
POL(filter(x₁, x₂, x₃)) = 1 + x₁ + x₂ + x₃
POL(nats(x₁)) = x₁
POL(s(x₁)) = x₁
POL(sieve(x₁)) = x₁
POL(zprimes) = 0

With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

filter(cons(X, Y), 0, M) → cons(0, filter(Y, M, M))
filter(cons(X, Y), s(N), M) → cons(X, filter(Y, N, M))

(4) Obligation:

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

sieve(cons(0, Y)) → cons(0, sieve(Y))
sieve(cons(s(N), Y)) → cons(s(N), sieve(filter(Y, N, N)))
nats(N) → cons(N, nats(s(N)))
zprimes → sieve(nats(s(s(0))))

The replacement map contains the following entries:

filter: {1, 2, 3}
cons: {1}
0: empty set
s: {1}
sieve: {1}
nats: {1}
zprimes: empty set

(5) CSRRRRProof (EQUIVALENT transformation)

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

sieve(cons(0, Y)) → cons(0, sieve(Y))
sieve(cons(s(N), Y)) → cons(s(N), sieve(filter(Y, N, N)))
nats(N) → cons(N, nats(s(N)))
zprimes → sieve(nats(s(s(0))))

The replacement map contains the following entries:

filter: {1, 2, 3}
cons: {1}
0: empty set
s: {1}
sieve: {1}
nats: {1}
zprimes: empty set
Used ordering:
Polynomial interpretation [POLO]:

POL(0) = 0
POL(cons(x₁, x₂)) = x₁
POL(filter(x₁, x₂, x₃)) = x₁ + x₂ + x₃
POL(nats(x₁)) = x₁
POL(s(x₁)) = x₁
POL(sieve(x₁)) = x₁
POL(zprimes) = 1

With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

zprimes → sieve(nats(s(s(0))))

(6) Obligation:

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

sieve(cons(0, Y)) → cons(0, sieve(Y))
sieve(cons(s(N), Y)) → cons(s(N), sieve(filter(Y, N, N)))
nats(N) → cons(N, nats(s(N)))

The replacement map contains the following entries:

filter: {1, 2, 3}
cons: {1}
0: empty set
s: {1}
sieve: {1}
nats: {1}

(7) CSRRRRProof (EQUIVALENT transformation)

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

sieve(cons(0, Y)) → cons(0, sieve(Y))
sieve(cons(s(N), Y)) → cons(s(N), sieve(filter(Y, N, N)))
nats(N) → cons(N, nats(s(N)))

The replacement map contains the following entries:

filter: {1, 2, 3}
cons: {1}
0: empty set
s: {1}
sieve: {1}
nats: {1}
Used ordering:
Polynomial interpretation [POLO]:

POL(0) = 0
POL(cons(x₁, x₂)) = x₁
POL(filter(x₁, x₂, x₃)) = x₁ + x₂ + x₃
POL(nats(x₁)) = 1 + x₁
POL(s(x₁)) = x₁
POL(sieve(x₁)) = 1 + x₁

With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

sieve(cons(0, Y)) → cons(0, sieve(Y))
sieve(cons(s(N), Y)) → cons(s(N), sieve(filter(Y, N, N)))
nats(N) → cons(N, nats(s(N)))

(0) Obligation:

(1) QTRSToCSRProof (EQUIVALENT transformation)

(2) Obligation:

(3) CSRRRRProof (EQUIVALENT transformation)

(4) Obligation:

(5) CSRRRRProof (EQUIVALENT transformation)

(6) Obligation:

(7) CSRRRRProof (EQUIVALENT transformation)

(8) Obligation:

(9) RisEmptyProof (EQUIVALENT transformation)

(10) YES