/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


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


YES

Problem 1: 

(VAR M N X X1 X2 X3 Y)
(RULES
a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
a__filter(X1,X2,X3) -> filter(X1,X2,X3)
a__nats(N) -> cons(mark(N),nats(s(N)))
a__nats(X) -> nats(X)
a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
a__sieve(X) -> sieve(X)
a__zprimes -> a__sieve(a__nats(s(s(0))))
a__zprimes -> zprimes
mark(0) -> 0
mark(cons(X1,X2)) -> cons(mark(X1),X2)
mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
mark(nats(X)) -> a__nats(mark(X))
mark(s(X)) -> s(mark(X))
mark(sieve(X)) -> a__sieve(mark(X))
mark(zprimes) -> a__zprimes
)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 A__FILTER(cons(X,Y),s(N),M) -> MARK(X)
 A__NATS(N) -> MARK(N)
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__NATS(s(s(0)))
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> A__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(nats(X)) -> A__NATS(mark(X))
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes

Problem 1: 

SCC Processor:
-> Pairs:
 A__FILTER(cons(X,Y),s(N),M) -> MARK(X)
 A__NATS(N) -> MARK(N)
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__NATS(s(s(0)))
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> A__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(nats(X)) -> A__NATS(mark(X))
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__FILTER(cons(X,Y),s(N),M) -> MARK(X)
 A__NATS(N) -> MARK(N)
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__NATS(s(s(0)))
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> A__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(nats(X)) -> A__NATS(mark(X))
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
->->-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes

Problem 1: 

Reduction Pair Processor:
-> Pairs:
 A__FILTER(cons(X,Y),s(N),M) -> MARK(X)
 A__NATS(N) -> MARK(N)
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__NATS(s(s(0)))
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> A__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(nats(X)) -> A__NATS(mark(X))
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
-> Usable rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__filter](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2
[a__nats](X) = 2.X + 2
[a__sieve](X) = X
[a__zprimes] = 2
[mark](X) = X
[0] = 0
[cons](X1,X2) = 2.X1 + 2
[filter](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2
[nats](X) = 2.X + 2
[s](X) = 2.X
[sieve](X) = X
[zprimes] = 2
[A__FILTER](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2
[A__NATS](X) = 2.X + 2
[A__SIEVE](X) = X
[A__ZPRIMES] = 2
[MARK](X) = 2.X + 2

Problem 1: 

SCC Processor:
-> Pairs:
 A__NATS(N) -> MARK(N)
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__NATS(s(s(0)))
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> A__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(nats(X)) -> A__NATS(mark(X))
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__NATS(N) -> MARK(N)
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__NATS(s(s(0)))
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X2)
 MARK(filter(X1,X2,X3)) -> MARK(X3)
 MARK(nats(X)) -> A__NATS(mark(X))
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
->->-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes

Problem 1: 

Reduction Pair Processor:
-> Pairs:
 A__NATS(N) -> MARK(N)
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__NATS(s(s(0)))
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X2)
 MARK(filter(X1,X2,X3)) -> MARK(X3)
 MARK(nats(X)) -> A__NATS(mark(X))
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
-> Usable rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__filter](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 1
[a__nats](X) = 2.X + 1
[a__sieve](X) = 2.X
[a__zprimes] = 2
[mark](X) = 2.X
[0] = 0
[cons](X1,X2) = X1 + 1
[filter](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 1
[nats](X) = 2.X + 1
[s](X) = 2.X
[sieve](X) = 2.X
[zprimes] = 1
[A__NATS](X) = 2.X + 2
[A__SIEVE](X) = 2.X
[A__ZPRIMES] = 2
[MARK](X) = 2.X

Problem 1: 

SCC Processor:
-> Pairs:
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__NATS(s(s(0)))
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X2)
 MARK(filter(X1,X2,X3)) -> MARK(X3)
 MARK(nats(X)) -> A__NATS(mark(X))
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X2)
 MARK(filter(X1,X2,X3)) -> MARK(X3)
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
->->-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes

Problem 1: 

Reduction Pair Processor:
-> Pairs:
 A__SIEVE(cons(s(N),Y)) -> MARK(N)
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X2)
 MARK(filter(X1,X2,X3)) -> MARK(X3)
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
-> Usable rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__filter](X1,X2,X3) = 2.X1 + X2 + 2.X3 + 2
[a__nats](X) = 2.X
[a__sieve](X) = 2.X + 2
[a__zprimes] = 2
[mark](X) = X
[0] = 0
[cons](X1,X2) = X1
[filter](X1,X2,X3) = 2.X1 + X2 + 2.X3 + 2
[nats](X) = 2.X
[s](X) = 2.X
[sieve](X) = 2.X + 2
[zprimes] = 2
[A__SIEVE](X) = 2.X + 1
[A__ZPRIMES] = 2
[MARK](X) = 2.X

Problem 1: 

SCC Processor:
-> Pairs:
 A__ZPRIMES -> A__SIEVE(a__nats(s(s(0))))
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X2)
 MARK(filter(X1,X2,X3)) -> MARK(X3)
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> A__SIEVE(mark(X))
 MARK(sieve(X)) -> MARK(X)
 MARK(zprimes) -> A__ZPRIMES
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X2)
 MARK(filter(X1,X2,X3)) -> MARK(X3)
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> MARK(X)
->->-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes

Problem 1: 

Subterm Processor:
-> Pairs:
 MARK(cons(X1,X2)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X1)
 MARK(filter(X1,X2,X3)) -> MARK(X2)
 MARK(filter(X1,X2,X3)) -> MARK(X3)
 MARK(nats(X)) -> MARK(X)
 MARK(s(X)) -> MARK(X)
 MARK(sieve(X)) -> MARK(X)
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Projection:
 pi(MARK) = 1

Problem 1: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 a__filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
 a__filter(cons(X,Y),s(N),M) -> cons(mark(X),filter(Y,N,M))
 a__filter(X1,X2,X3) -> filter(X1,X2,X3)
 a__nats(N) -> cons(mark(N),nats(s(N)))
 a__nats(X) -> nats(X)
 a__sieve(cons(0,Y)) -> cons(0,sieve(Y))
 a__sieve(cons(s(N),Y)) -> cons(s(mark(N)),sieve(filter(Y,N,N)))
 a__sieve(X) -> sieve(X)
 a__zprimes -> a__sieve(a__nats(s(s(0))))
 a__zprimes -> zprimes
 mark(0) -> 0
 mark(cons(X1,X2)) -> cons(mark(X1),X2)
 mark(filter(X1,X2,X3)) -> a__filter(mark(X1),mark(X2),mark(X3))
 mark(nats(X)) -> a__nats(mark(X))
 mark(s(X)) -> s(mark(X))
 mark(sieve(X)) -> a__sieve(mark(X))
 mark(zprimes) -> a__zprimes
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.