(VAR X Y M N)
(STRATEGY CONTEXTSENSITIVE 
  (filter 1 2 3)
  (cons 1)
  (0)
  (s 1)
  (sieve 1)
  (nats 1)
  (zprimes)
)
(RULES 
filter(cons(X,Y),0,M) -> cons(0,filter(Y,M,M))
filter(cons(X,Y),s(N),M) -> cons(X,filter(Y,N,M))
sieve(cons(0,Y)) -> cons(0,sieve(Y))
sieve(cons(s(N),Y)) -> cons(s(N),sieve(filter(Y,N,N)))
nats(N) -> cons(N,nats(s(N)))
zprimes -> sieve(nats(s(s(0))))
)

The TRS is orthogonal, thus termination of innermost context-sensitive rewriting is equivalent to termination of context-sensitive rewriting.

Proving termination of context-sensitive rewriting for Ex9_BLR02:

-> Dependency pairs:
nF_zprimes -> nF_sieve(nats(s(s(0))))
nF_zprimes -> nF_nats(s(s(0)))

-> Proof of termination for Ex9_BLR02_1:
Termination proved: No cycles in dependency graph.

SETTINGS:
Base ordering: Polynomial ordering
Proof mode: SCCs in CSDG + base ordering
Upper bound for coeffs: 1
Rationals below 1 for all non-replacing args: No
Polynomial interpretation: Linear
Coeffs in polynomials: No rationals
Delta: automatic



Termination was proved succesfully.