Termination w.r.t. Q proof of /tmp/tmpwCKiMd/ExIntrod_GM99

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

0 QTRS

↳1 QTRSToCSRProof (⇔)

↳2 CSR

↳3 CSRInnermostProof (⇔)

↳4 CSR

↳5 CSDependencyPairsProof (⇔)

↳6 QCSDP

↳7 QCSDependencyGraphProof (⇔)

↳8 QCSDP

↳9 QCSDPSubtermProof (⇔)

↳10 QCSDP

↳11 PIsEmptyProof (⇔)

↳12 TRUE

(0) Obligation:

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

active(primes) → mark(sieve(from(s(s(0)))))
active(from(X)) → mark(cons(X, from(s(X))))
active(head(cons(X, Y))) → mark(X)
active(tail(cons(X, Y))) → mark(Y)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(filter(s(s(X)), cons(Y, Z))) → mark(if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))))
active(sieve(cons(X, Y))) → mark(cons(X, filter(X, sieve(Y))))
active(sieve(X)) → sieve(active(X))
active(from(X)) → from(active(X))
active(s(X)) → s(active(X))
active(cons(X1, X2)) → cons(active(X1), X2)
active(head(X)) → head(active(X))
active(tail(X)) → tail(active(X))
active(if(X1, X2, X3)) → if(active(X1), X2, X3)
active(filter(X1, X2)) → filter(active(X1), X2)
active(filter(X1, X2)) → filter(X1, active(X2))
active(divides(X1, X2)) → divides(active(X1), X2)
active(divides(X1, X2)) → divides(X1, active(X2))
sieve(mark(X)) → mark(sieve(X))
from(mark(X)) → mark(from(X))
s(mark(X)) → mark(s(X))
cons(mark(X1), X2) → mark(cons(X1, X2))
head(mark(X)) → mark(head(X))
tail(mark(X)) → mark(tail(X))
if(mark(X1), X2, X3) → mark(if(X1, X2, X3))
filter(mark(X1), X2) → mark(filter(X1, X2))
filter(X1, mark(X2)) → mark(filter(X1, X2))
divides(mark(X1), X2) → mark(divides(X1, X2))
divides(X1, mark(X2)) → mark(divides(X1, X2))
proper(primes) → ok(primes)
proper(sieve(X)) → sieve(proper(X))
proper(from(X)) → from(proper(X))
proper(s(X)) → s(proper(X))
proper(0) → ok(0)
proper(cons(X1, X2)) → cons(proper(X1), proper(X2))
proper(head(X)) → head(proper(X))
proper(tail(X)) → tail(proper(X))
proper(if(X1, X2, X3)) → if(proper(X1), proper(X2), proper(X3))
proper(true) → ok(true)
proper(false) → ok(false)
proper(filter(X1, X2)) → filter(proper(X1), proper(X2))
proper(divides(X1, X2)) → divides(proper(X1), proper(X2))
sieve(ok(X)) → ok(sieve(X))
from(ok(X)) → ok(from(X))
s(ok(X)) → ok(s(X))
cons(ok(X1), ok(X2)) → ok(cons(X1, X2))
head(ok(X)) → ok(head(X))
tail(ok(X)) → ok(tail(X))
if(ok(X1), ok(X2), ok(X3)) → ok(if(X1, X2, X3))
filter(ok(X1), ok(X2)) → ok(filter(X1, X2))
divides(ok(X1), ok(X2)) → ok(divides(X1, X2))
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(primes) → mark(sieve(from(s(s(0)))))
active(from(X)) → mark(cons(X, from(s(X))))
active(head(cons(X, Y))) → mark(X)
active(tail(cons(X, Y))) → mark(Y)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(filter(s(s(X)), cons(Y, Z))) → mark(if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))))
active(sieve(cons(X, Y))) → mark(cons(X, filter(X, sieve(Y))))
active(sieve(X)) → sieve(active(X))
active(from(X)) → from(active(X))
active(s(X)) → s(active(X))
active(cons(X1, X2)) → cons(active(X1), X2)
active(head(X)) → head(active(X))
active(tail(X)) → tail(active(X))
active(if(X1, X2, X3)) → if(active(X1), X2, X3)
active(filter(X1, X2)) → filter(active(X1), X2)
active(filter(X1, X2)) → filter(X1, active(X2))
active(divides(X1, X2)) → divides(active(X1), X2)
active(divides(X1, X2)) → divides(X1, active(X2))
sieve(mark(X)) → mark(sieve(X))
from(mark(X)) → mark(from(X))
s(mark(X)) → mark(s(X))
cons(mark(X1), X2) → mark(cons(X1, X2))
head(mark(X)) → mark(head(X))
tail(mark(X)) → mark(tail(X))
if(mark(X1), X2, X3) → mark(if(X1, X2, X3))
filter(mark(X1), X2) → mark(filter(X1, X2))
filter(X1, mark(X2)) → mark(filter(X1, X2))
divides(mark(X1), X2) → mark(divides(X1, X2))
divides(X1, mark(X2)) → mark(divides(X1, X2))
proper(primes) → ok(primes)
proper(sieve(X)) → sieve(proper(X))
proper(from(X)) → from(proper(X))
proper(s(X)) → s(proper(X))
proper(0) → ok(0)
proper(cons(X1, X2)) → cons(proper(X1), proper(X2))
proper(head(X)) → head(proper(X))
proper(tail(X)) → tail(proper(X))
proper(if(X1, X2, X3)) → if(proper(X1), proper(X2), proper(X3))
proper(true) → ok(true)
proper(false) → ok(false)
proper(filter(X1, X2)) → filter(proper(X1), proper(X2))
proper(divides(X1, X2)) → divides(proper(X1), proper(X2))
sieve(ok(X)) → ok(sieve(X))
from(ok(X)) → ok(from(X))
s(ok(X)) → ok(s(X))
cons(ok(X1), ok(X2)) → ok(cons(X1, X2))
head(ok(X)) → ok(head(X))
tail(ok(X)) → ok(tail(X))
if(ok(X1), ok(X2), ok(X3)) → ok(if(X1, X2, X3))
filter(ok(X1), ok(X2)) → ok(filter(X1, X2))
divides(ok(X1), ok(X2)) → ok(divides(X1, X2))
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:

primes: empty set
sieve: {1}
from: {1}
s: {1}
0: empty set
cons: {1}
head: {1}
tail: {1}
if: {1}
true: empty set
false: empty set
filter: {1, 2}
divides: {1, 2}
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:

primes → sieve(from(s(s(0))))
from(X) → cons(X, from(s(X)))
head(cons(X, Y)) → X
tail(cons(X, Y)) → Y
if(true, X, Y) → X
if(false, X, Y) → Y
filter(s(s(X)), cons(Y, Z)) → if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))
sieve(cons(X, Y)) → cons(X, filter(X, sieve(Y)))

The replacement map contains the following entries:

primes: empty set
sieve: {1}
from: {1}
s: {1}
0: empty set
cons: {1}
head: {1}
tail: {1}
if: {1}
true: empty set
false: empty set
filter: {1, 2}
divides: {1, 2}

(3) CSRInnermostProof (EQUIVALENT transformation)

The CSR is orthogonal. By [CS_Inn] we can switch to innermost.

(4) Obligation:

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

primes → sieve(from(s(s(0))))
from(X) → cons(X, from(s(X)))
head(cons(X, Y)) → X
tail(cons(X, Y)) → Y
if(true, X, Y) → X
if(false, X, Y) → Y
filter(s(s(X)), cons(Y, Z)) → if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))
sieve(cons(X, Y)) → cons(X, filter(X, sieve(Y)))

The replacement map contains the following entries:

primes: empty set
sieve: {1}
from: {1}
s: {1}
0: empty set
cons: {1}
head: {1}
tail: {1}
if: {1}
true: empty set
false: empty set
filter: {1, 2}
divides: {1, 2}

Innermost Strategy.

(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 {sieve, from, s, head, tail, filter, divides, SIEVE, FROM, FILTER, TAIL} are replacing on all positions.
For all symbols f in {cons, if, IF} we have µ(f) = {1}.
The symbols in {U} are not replacing on any position.

The ordinary context-sensitive dependency pairs DP_o are:

PRIMES → SIEVE(from(s(s(0))))
PRIMES → FROM(s(s(0)))
FILTER(s(s(X)), cons(Y, Z)) → IF(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))

The collapsing dependency pairs are DP_c:

TAIL(cons(X, Y)) → Y
IF(true, X, Y) → X
IF(false, X, Y) → Y

The hidden terms of R are:

from(s(x0))
filter(s(s(x0)), x1)
filter(x0, sieve(x1))
sieve(x0)

Every hiding context is built from:

s on positions {1}
from on positions {1}
filter on positions {1, 2}
sieve on positions {1}
cons on positions {1}

Hence, the new unhiding pairs DP_u are :

TAIL(cons(X, Y)) → U(Y)
IF(true, X, Y) → U(X)
IF(false, X, Y) → U(Y)
U(s(x_0)) → U(x_0)
U(from(x_0)) → U(x_0)
U(filter(x_0, x_1)) → U(x_0)
U(filter(x_0, x_1)) → U(x_1)
U(sieve(x_0)) → U(x_0)
U(cons(x_0, x_1)) → U(x_0)
U(from(s(x0))) → FROM(s(x0))
U(filter(s(s(x0)), x1)) → FILTER(s(s(x0)), x1)
U(filter(x0, sieve(x1))) → FILTER(x0, sieve(x1))
U(sieve(x0)) → SIEVE(x0)

The TRS R consists of the following rules:

primes → sieve(from(s(s(0))))
from(X) → cons(X, from(s(X)))
head(cons(X, Y)) → X
tail(cons(X, Y)) → Y
if(true, X, Y) → X
if(false, X, Y) → Y
filter(s(s(X)), cons(Y, Z)) → if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))
sieve(cons(X, Y)) → cons(X, filter(X, sieve(Y)))

The set Q consists of the following terms:

primes
from(x0)
head(cons(x0, x1))
tail(cons(x0, x1))
if(true, x0, x1)
if(false, x0, x1)
filter(s(s(x0)), cons(x1, x2))
sieve(cons(x0, x1))

(7) QCSDependencyGraphProof (EQUIVALENT transformation)

The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 1 SCC with 8 less nodes.
The rules FILTER(s(s(z0)), cons(z1, z2)) → IF(divides(s(s(z0)), z1), filter(s(s(z0)), z2), cons(z1, filter(z0, sieve(z1)))) and IF(true, x0, x1) → U(x0) form no chain, because ECap^µ(IF(divides(s(s(z0)), z1), filter(s(s(z0)), z2), cons(z1, filter(z0, sieve(z1))))) = IF(divides(s(s(z0)), z1), filter(s(s(z0)), z2), cons(z1, filter(z0, sieve(z1)))) does not unify with IF(true, x0, x1). The rules FILTER(s(s(z0)), cons(z1, z2)) → IF(divides(s(s(z0)), z1), filter(s(s(z0)), z2), cons(z1, filter(z0, sieve(z1)))) and IF(false, x0, x1) → U(x1) form no chain, because ECap^µ(IF(divides(s(s(z0)), z1), filter(s(s(z0)), z2), cons(z1, filter(z0, sieve(z1))))) = IF(divides(s(s(z0)), z1), filter(s(s(z0)), z2), cons(z1, filter(z0, sieve(z1)))) does not unify with IF(false, x0, x1).

(8) Obligation:

Q-restricted context-sensitive dependency pair problem:
The symbols in {sieve, from, s, head, tail, filter, divides} are replacing on all positions.
For all symbols f in {cons, if} we have µ(f) = {1}.
The symbols in {U} are not replacing on any position.

The TRS P consists of the following rules:

U(s(x_0)) → U(x_0)
U(from(x_0)) → U(x_0)
U(filter(x_0, x_1)) → U(x_0)
U(filter(x_0, x_1)) → U(x_1)
U(sieve(x_0)) → U(x_0)
U(cons(x_0, x_1)) → U(x_0)

The TRS R consists of the following rules:

primes → sieve(from(s(s(0))))
from(X) → cons(X, from(s(X)))
head(cons(X, Y)) → X
tail(cons(X, Y)) → Y
if(true, X, Y) → X
if(false, X, Y) → Y
filter(s(s(X)), cons(Y, Z)) → if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))
sieve(cons(X, Y)) → cons(X, filter(X, sieve(Y)))

The set Q consists of the following terms:

primes
from(x0)
head(cons(x0, x1))
tail(cons(x0, x1))
if(true, x0, x1)
if(false, x0, x1)
filter(s(s(x0)), cons(x1, x2))
sieve(cons(x0, x1))

(9) QCSDPSubtermProof (EQUIVALENT transformation)

We use the subterm processor [DA_EMMES].

The following pairs can be oriented strictly and are deleted.

U(s(x_0)) → U(x_0)
U(from(x_0)) → U(x_0)
U(filter(x_0, x_1)) → U(x_0)
U(filter(x_0, x_1)) → U(x_1)
U(sieve(x_0)) → U(x_0)
U(cons(x_0, x_1)) → U(x_0)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
U(x1) = x1

Subterm Order

(10) Obligation:

Q-restricted context-sensitive dependency pair problem:
The symbols in {sieve, from, s, head, tail, filter, divides} are replacing on all positions.
For all symbols f in {cons, if} we have µ(f) = {1}.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

primes → sieve(from(s(s(0))))
from(X) → cons(X, from(s(X)))
head(cons(X, Y)) → X
tail(cons(X, Y)) → Y
if(true, X, Y) → X
if(false, X, Y) → Y
filter(s(s(X)), cons(Y, Z)) → if(divides(s(s(X)), Y), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y))))
sieve(cons(X, Y)) → cons(X, filter(X, sieve(Y)))

The set Q consists of the following terms:

primes
from(x0)
head(cons(x0, x1))
tail(cons(x0, x1))
if(true, x0, x1)
if(false, x0, x1)
filter(s(s(x0)), cons(x1, x2))
sieve(cons(x0, x1))

(11) PIsEmptyProof (EQUIVALENT transformation)

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

(0) Obligation:

(1) QTRSToCSRProof (EQUIVALENT transformation)

(2) Obligation:

(3) CSRInnermostProof (EQUIVALENT transformation)

(4) Obligation:

(5) CSDependencyPairsProof (EQUIVALENT transformation)

(6) Obligation:

(7) QCSDependencyGraphProof (EQUIVALENT transformation)

(8) Obligation:

(9) QCSDPSubtermProof (EQUIVALENT transformation)

(10) Obligation:

(11) PIsEmptyProof (EQUIVALENT transformation)

(12) TRUE