/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 56 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 0 ms]
        (7) QDP
        (8) QReductionProof [EQUIVALENT, 0 ms]
        (9) QDP
        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) QDP
        (13) UsableRulesProof [EQUIVALENT, 0 ms]
        (14) QDP
        (15) QReductionProof [EQUIVALENT, 0 ms]
        (16) QDP
        (17) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (18) YES
    (19) QDP
        (20) UsableRulesProof [EQUIVALENT, 0 ms]
        (21) QDP
        (22) QReductionProof [EQUIVALENT, 0 ms]
        (23) QDP
        (24) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (25) YES
    (26) QDP
        (27) UsableRulesProof [EQUIVALENT, 0 ms]
        (28) QDP
        (29) QReductionProof [EQUIVALENT, 0 ms]
        (30) QDP
        (31) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (32) YES
    (33) QDP
        (34) UsableRulesProof [EQUIVALENT, 0 ms]
        (35) QDP
        (36) QReductionProof [EQUIVALENT, 0 ms]
        (37) QDP
        (38) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (39) YES
    (40) QDP
        (41) QDPOrderProof [EQUIVALENT, 36 ms]
        (42) QDP
        (43) QDPOrderProof [EQUIVALENT, 20 ms]
        (44) QDP
        (45) DependencyGraphProof [EQUIVALENT, 0 ms]
        (46) QDP
        (47) QDPOrderProof [EQUIVALENT, 21 ms]
        (48) QDP
        (49) QDPOrderProof [EQUIVALENT, 0 ms]
        (50) QDP
        (51) QDPOrderProof [EQUIVALENT, 14 ms]
        (52) QDP
        (53) QDPOrderProof [EQUIVALENT, 2 ms]
        (54) QDP
        (55) QDPOrderProof [EQUIVALENT, 23 ms]
        (56) QDP
        (57) UsableRulesProof [EQUIVALENT, 0 ms]
        (58) QDP
        (59) QReductionProof [EQUIVALENT, 0 ms]
        (60) QDP
        (61) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (62) 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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))


----------------------------------------

(1) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

(2)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M)))
   ACTIVE(filter(cons(X, Y), 0, M)) -> CONS(0, filter(Y, M, M))
   ACTIVE(filter(cons(X, Y), 0, M)) -> FILTER(Y, M, M)
   ACTIVE(filter(cons(X, Y), s(N), M)) -> MARK(cons(X, filter(Y, N, M)))
   ACTIVE(filter(cons(X, Y), s(N), M)) -> CONS(X, filter(Y, N, M))
   ACTIVE(filter(cons(X, Y), s(N), M)) -> FILTER(Y, N, M)
   ACTIVE(sieve(cons(0, Y))) -> MARK(cons(0, sieve(Y)))
   ACTIVE(sieve(cons(0, Y))) -> CONS(0, sieve(Y))
   ACTIVE(sieve(cons(0, Y))) -> SIEVE(Y)
   ACTIVE(sieve(cons(s(N), Y))) -> MARK(cons(s(N), sieve(filter(Y, N, N))))
   ACTIVE(sieve(cons(s(N), Y))) -> CONS(s(N), sieve(filter(Y, N, N)))
   ACTIVE(sieve(cons(s(N), Y))) -> SIEVE(filter(Y, N, N))
   ACTIVE(sieve(cons(s(N), Y))) -> FILTER(Y, N, N)
   ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N))))
   ACTIVE(nats(N)) -> CONS(N, nats(s(N)))
   ACTIVE(nats(N)) -> NATS(s(N))
   ACTIVE(nats(N)) -> S(N)
   ACTIVE(zprimes) -> MARK(sieve(nats(s(s(0)))))
   ACTIVE(zprimes) -> SIEVE(nats(s(s(0))))
   ACTIVE(zprimes) -> NATS(s(s(0)))
   ACTIVE(zprimes) -> S(s(0))
   ACTIVE(zprimes) -> S(0)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   MARK(filter(X1, X2, X3)) -> FILTER(mark(X1), mark(X2), mark(X3))
   MARK(filter(X1, X2, X3)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> MARK(X2)
   MARK(filter(X1, X2, X3)) -> MARK(X3)
   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
   MARK(cons(X1, X2)) -> CONS(mark(X1), X2)
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(0) -> ACTIVE(0)
   MARK(s(X)) -> ACTIVE(s(mark(X)))
   MARK(s(X)) -> S(mark(X))
   MARK(s(X)) -> MARK(X)
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> SIEVE(mark(X))
   MARK(sieve(X)) -> MARK(X)
   MARK(nats(X)) -> ACTIVE(nats(mark(X)))
   MARK(nats(X)) -> NATS(mark(X))
   MARK(nats(X)) -> MARK(X)
   MARK(zprimes) -> ACTIVE(zprimes)
   FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3)
   FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3)
   FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3)
   FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3)
   FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3)
   FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3)
   CONS(mark(X1), X2) -> CONS(X1, X2)
   CONS(X1, mark(X2)) -> CONS(X1, X2)
   CONS(active(X1), X2) -> CONS(X1, X2)
   CONS(X1, active(X2)) -> CONS(X1, X2)
   S(mark(X)) -> S(X)
   S(active(X)) -> S(X)
   SIEVE(mark(X)) -> SIEVE(X)
   SIEVE(active(X)) -> SIEVE(X)
   NATS(mark(X)) -> NATS(X)
   NATS(active(X)) -> NATS(X)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(3) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 6 SCCs with 22 less nodes.
----------------------------------------

(4)
Complex Obligation (AND)

----------------------------------------

(5)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   NATS(active(X)) -> NATS(X)
   NATS(mark(X)) -> NATS(X)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(6) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(7)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   NATS(active(X)) -> NATS(X)
   NATS(mark(X)) -> NATS(X)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(8) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))


----------------------------------------

(9)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   NATS(active(X)) -> NATS(X)
   NATS(mark(X)) -> NATS(X)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(10) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*NATS(active(X)) -> NATS(X)
The graph contains the following edges 1 > 1


*NATS(mark(X)) -> NATS(X)
The graph contains the following edges 1 > 1


----------------------------------------

(11)
YES

----------------------------------------

(12)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SIEVE(active(X)) -> SIEVE(X)
   SIEVE(mark(X)) -> SIEVE(X)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(13) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SIEVE(active(X)) -> SIEVE(X)
   SIEVE(mark(X)) -> SIEVE(X)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(15) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))


----------------------------------------

(16)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SIEVE(active(X)) -> SIEVE(X)
   SIEVE(mark(X)) -> SIEVE(X)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(17) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*SIEVE(active(X)) -> SIEVE(X)
The graph contains the following edges 1 > 1


*SIEVE(mark(X)) -> SIEVE(X)
The graph contains the following edges 1 > 1


----------------------------------------

(18)
YES

----------------------------------------

(19)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   S(active(X)) -> S(X)
   S(mark(X)) -> S(X)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(20) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(21)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   S(active(X)) -> S(X)
   S(mark(X)) -> S(X)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(22) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))


----------------------------------------

(23)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   S(active(X)) -> S(X)
   S(mark(X)) -> S(X)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(24) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*S(active(X)) -> S(X)
The graph contains the following edges 1 > 1


*S(mark(X)) -> S(X)
The graph contains the following edges 1 > 1


----------------------------------------

(25)
YES

----------------------------------------

(26)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   CONS(X1, mark(X2)) -> CONS(X1, X2)
   CONS(mark(X1), X2) -> CONS(X1, X2)
   CONS(active(X1), X2) -> CONS(X1, X2)
   CONS(X1, active(X2)) -> CONS(X1, X2)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(27) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(28)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   CONS(X1, mark(X2)) -> CONS(X1, X2)
   CONS(mark(X1), X2) -> CONS(X1, X2)
   CONS(active(X1), X2) -> CONS(X1, X2)
   CONS(X1, active(X2)) -> CONS(X1, X2)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(29) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))


----------------------------------------

(30)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   CONS(X1, mark(X2)) -> CONS(X1, X2)
   CONS(mark(X1), X2) -> CONS(X1, X2)
   CONS(active(X1), X2) -> CONS(X1, X2)
   CONS(X1, active(X2)) -> CONS(X1, X2)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(31) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*CONS(X1, mark(X2)) -> CONS(X1, X2)
The graph contains the following edges 1 >= 1, 2 > 2


*CONS(mark(X1), X2) -> CONS(X1, X2)
The graph contains the following edges 1 > 1, 2 >= 2


*CONS(active(X1), X2) -> CONS(X1, X2)
The graph contains the following edges 1 > 1, 2 >= 2


*CONS(X1, active(X2)) -> CONS(X1, X2)
The graph contains the following edges 1 >= 1, 2 > 2


----------------------------------------

(32)
YES

----------------------------------------

(33)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3)
   FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3)
   FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3)
   FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3)
   FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3)
   FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(34) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(35)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3)
   FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3)
   FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3)
   FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3)
   FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3)
   FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(36) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))


----------------------------------------

(37)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3)
   FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3)
   FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3)
   FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3)
   FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3)
   FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(38) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*FILTER(X1, mark(X2), X3) -> FILTER(X1, X2, X3)
The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3


*FILTER(mark(X1), X2, X3) -> FILTER(X1, X2, X3)
The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3


*FILTER(X1, X2, mark(X3)) -> FILTER(X1, X2, X3)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3


*FILTER(active(X1), X2, X3) -> FILTER(X1, X2, X3)
The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3


*FILTER(X1, active(X2), X3) -> FILTER(X1, X2, X3)
The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3


*FILTER(X1, X2, active(X3)) -> FILTER(X1, X2, X3)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3


----------------------------------------

(39)
YES

----------------------------------------

(40)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
   ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M)))
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(filter(X1, X2, X3)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> MARK(X2)
   MARK(filter(X1, X2, X3)) -> MARK(X3)
   MARK(s(X)) -> ACTIVE(s(mark(X)))
   MARK(s(X)) -> MARK(X)
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)
   MARK(nats(X)) -> ACTIVE(nats(mark(X)))
   MARK(nats(X)) -> MARK(X)
   MARK(zprimes) -> ACTIVE(zprimes)
   ACTIVE(zprimes) -> MARK(sieve(nats(s(s(0)))))

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(41) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
   MARK(s(X)) -> ACTIVE(s(mark(X)))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = x_1
   POL(MARK(x_1)) = 1
   POL(active(x_1)) = 0
   POL(cons(x_1, x_2)) = 0
   POL(filter(x_1, x_2, x_3)) = 1
   POL(mark(x_1)) = 0
   POL(nats(x_1)) = 1
   POL(s(x_1)) = 0
   POL(sieve(x_1)) = 1
   POL(zprimes) = 1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   sieve(active(X)) -> sieve(X)
   sieve(mark(X)) -> sieve(X)
   nats(active(X)) -> nats(X)
   nats(mark(X)) -> nats(X)


----------------------------------------

(42)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M)))
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(filter(X1, X2, X3)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> MARK(X2)
   MARK(filter(X1, X2, X3)) -> MARK(X3)
   MARK(s(X)) -> MARK(X)
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)
   MARK(nats(X)) -> ACTIVE(nats(mark(X)))
   MARK(nats(X)) -> MARK(X)
   MARK(zprimes) -> ACTIVE(zprimes)
   ACTIVE(zprimes) -> MARK(sieve(nats(s(s(0)))))

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(43) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   ACTIVE(zprimes) -> MARK(sieve(nats(s(s(0)))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = x_1
   POL(MARK(x_1)) = x_1
   POL(active(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1
   POL(filter(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(mark(x_1)) = x_1
   POL(nats(x_1)) = x_1
   POL(s(x_1)) = x_1
   POL(sieve(x_1)) = x_1
   POL(zprimes) = 1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   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)))))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   sieve(active(X)) -> sieve(X)
   sieve(mark(X)) -> sieve(X)
   nats(active(X)) -> nats(X)
   nats(mark(X)) -> nats(X)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)


----------------------------------------

(44)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(filter(cons(X, Y), 0, M)) -> MARK(cons(0, filter(Y, M, M)))
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(filter(X1, X2, X3)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> MARK(X2)
   MARK(filter(X1, X2, X3)) -> MARK(X3)
   MARK(s(X)) -> MARK(X)
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)
   MARK(nats(X)) -> ACTIVE(nats(mark(X)))
   MARK(nats(X)) -> MARK(X)
   MARK(zprimes) -> ACTIVE(zprimes)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(45) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------

(46)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(filter(X1, X2, X3)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> MARK(X2)
   MARK(filter(X1, X2, X3)) -> MARK(X3)
   MARK(s(X)) -> MARK(X)
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)
   MARK(nats(X)) -> ACTIVE(nats(mark(X)))
   MARK(nats(X)) -> MARK(X)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(47) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   ACTIVE(nats(N)) -> MARK(cons(N, nats(s(N))))
   MARK(nats(X)) -> MARK(X)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = x_1
   POL(MARK(x_1)) = x_1
   POL(active(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1
   POL(filter(x_1, x_2, x_3)) = x_1 + x_2 + x_3
   POL(mark(x_1)) = x_1
   POL(nats(x_1)) = 1 + x_1
   POL(s(x_1)) = x_1
   POL(sieve(x_1)) = x_1
   POL(zprimes) = 1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   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)))))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   sieve(active(X)) -> sieve(X)
   sieve(mark(X)) -> sieve(X)
   nats(active(X)) -> nats(X)
   nats(mark(X)) -> nats(X)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)


----------------------------------------

(48)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(filter(X1, X2, X3)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> MARK(X2)
   MARK(filter(X1, X2, X3)) -> MARK(X3)
   MARK(s(X)) -> MARK(X)
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)
   MARK(nats(X)) -> ACTIVE(nats(mark(X)))

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(49) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   MARK(nats(X)) -> ACTIVE(nats(mark(X)))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = x_1
   POL(MARK(x_1)) = 1
   POL(active(x_1)) = 0
   POL(cons(x_1, x_2)) = 0
   POL(filter(x_1, x_2, x_3)) = 1
   POL(mark(x_1)) = 0
   POL(nats(x_1)) = 0
   POL(s(x_1)) = 0
   POL(sieve(x_1)) = 1
   POL(zprimes) = 0

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   sieve(active(X)) -> sieve(X)
   sieve(mark(X)) -> sieve(X)
   nats(active(X)) -> nats(X)
   nats(mark(X)) -> nats(X)


----------------------------------------

(50)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(filter(X1, X2, X3)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> MARK(X2)
   MARK(filter(X1, X2, X3)) -> MARK(X3)
   MARK(s(X)) -> MARK(X)
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(51) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   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)))
   MARK(filter(X1, X2, X3)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> MARK(X2)
   MARK(filter(X1, X2, X3)) -> MARK(X3)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = x_1
   POL(MARK(x_1)) = x_1
   POL(active(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1
   POL(filter(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3
   POL(mark(x_1)) = x_1
   POL(nats(x_1)) = x_1
   POL(s(x_1)) = x_1
   POL(sieve(x_1)) = x_1
   POL(zprimes) = 0

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   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)))))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   sieve(active(X)) -> sieve(X)
   sieve(mark(X)) -> sieve(X)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   nats(active(X)) -> nats(X)
   nats(mark(X)) -> nats(X)


----------------------------------------

(52)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(s(X)) -> MARK(X)
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(53) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   MARK(s(X)) -> MARK(X)
The remaining pairs can at least be oriented weakly.
Used ordering:  Combined order from the following AFS and order.
MARK(x1)  =  x1

cons(x1, x2)  =  x1

filter(x1, x2, x3)  =  x1

ACTIVE(x1)  =  x1

mark(x1)  =  x1

sieve(x1)  =  x1

0  =  0

s(x1)  =  s(x1)

active(x1)  =  x1

nats(x1)  =  x1

zprimes  =  zprimes


Knuth-Bendix order [KBO] with precedence:trivial

and weight map:

   s_1=1
   0=1
   zprimes=4

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   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)))))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   sieve(active(X)) -> sieve(X)
   sieve(mark(X)) -> sieve(X)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   nats(active(X)) -> nats(X)
   nats(mark(X)) -> nats(X)


----------------------------------------

(54)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(55) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   MARK(filter(X1, X2, X3)) -> ACTIVE(filter(mark(X1), mark(X2), mark(X3)))
   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))))
   MARK(sieve(X)) -> ACTIVE(sieve(mark(X)))
   MARK(sieve(X)) -> MARK(X)
The remaining pairs can at least be oriented weakly.
Used ordering:  Combined order from the following AFS and order.
MARK(x1)  =  x1

cons(x1, x2)  =  x1

filter(x1, x2, x3)  =  filter

ACTIVE(x1)  =  ACTIVE

0  =  0

s(x1)  =  s

sieve(x1)  =  sieve(x1)

mark(x1)  =  x1

active(x1)  =  x1


Knuth-Bendix order [KBO] with precedence:trivial

and weight map:

   s=1
   0=2
   filter=4
   ACTIVE=3
   sieve_1=3

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
none


----------------------------------------

(56)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> MARK(X1)

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)))))
   mark(filter(X1, X2, X3)) -> active(filter(mark(X1), mark(X2), mark(X3)))
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(sieve(X)) -> active(sieve(mark(X)))
   mark(nats(X)) -> active(nats(mark(X)))
   mark(zprimes) -> active(zprimes)
   filter(mark(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, mark(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, mark(X3)) -> filter(X1, X2, X3)
   filter(active(X1), X2, X3) -> filter(X1, X2, X3)
   filter(X1, active(X2), X3) -> filter(X1, X2, X3)
   filter(X1, X2, active(X3)) -> filter(X1, X2, X3)
   cons(mark(X1), X2) -> cons(X1, X2)
   cons(X1, mark(X2)) -> cons(X1, X2)
   cons(active(X1), X2) -> cons(X1, X2)
   cons(X1, active(X2)) -> cons(X1, X2)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   sieve(mark(X)) -> sieve(X)
   sieve(active(X)) -> sieve(X)
   nats(mark(X)) -> nats(X)
   nats(active(X)) -> nats(X)

The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(57) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(58)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> MARK(X1)

R is empty.
The set Q consists of the following terms:

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(59) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   active(filter(cons(x0, x1), 0, x2))
   active(filter(cons(x0, x1), s(x2), x3))
   active(sieve(cons(0, x0)))
   active(sieve(cons(s(x0), x1)))
   active(nats(x0))
   active(zprimes)
   mark(filter(x0, x1, x2))
   mark(cons(x0, x1))
   mark(0)
   mark(s(x0))
   mark(sieve(x0))
   mark(nats(x0))
   mark(zprimes)
   filter(mark(x0), x1, x2)
   filter(x0, mark(x1), x2)
   filter(x0, x1, mark(x2))
   filter(active(x0), x1, x2)
   filter(x0, active(x1), x2)
   filter(x0, x1, active(x2))
   s(mark(x0))
   s(active(x0))
   sieve(mark(x0))
   sieve(active(x0))
   nats(mark(x0))
   nats(active(x0))


----------------------------------------

(60)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> MARK(X1)

R is empty.
The set Q consists of the following terms:

   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(61) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*MARK(cons(X1, X2)) -> MARK(X1)
The graph contains the following edges 1 > 1


----------------------------------------

(62)
YES