WORST_CASE(Omega(n^1), ?)
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, INF).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 339 ms]
(4) CpxRelTRS
(5) RenamingProof [BOTH BOUNDS(ID, ID), 1 ms]
(6) CpxRelTRS
(7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(8) typed CpxTrs
(9) OrderProof [LOWER BOUND(ID), 0 ms]
(10) typed CpxTrs
(11) RewriteLemmaProof [LOWER BOUND(ID), 324 ms]
(12) BEST
    (13) proven lower bound
        (14) LowerBoundPropagationProof [FINISHED, 0 ms]
        (15) BOUNDS(n^1, INF)
    (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 2505 ms]
        (18) BOUNDS(1, INF)


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

(0)
Obligation:
The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following 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__sieve(cons(0, Y)) -> cons(0, sieve(Y))
   a__sieve(cons(s(N), Y)) -> cons(s(mark(N)), sieve(filter(Y, N, N)))
   a__nats(N) -> cons(mark(N), nats(s(N)))
   a__zprimes -> a__sieve(a__nats(s(s(0))))
   mark(filter(X1, X2, X3)) -> a__filter(mark(X1), mark(X2), mark(X3))
   mark(sieve(X)) -> a__sieve(mark(X))
   mark(nats(X)) -> a__nats(mark(X))
   mark(zprimes) -> a__zprimes
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(0) -> 0
   mark(s(X)) -> s(mark(X))
   a__filter(X1, X2, X3) -> filter(X1, X2, X3)
   a__sieve(X) -> sieve(X)
   a__nats(X) -> nats(X)
   a__zprimes -> zprimes

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(0) -> 0
   encArg(filter(x_1, x_2, x_3)) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(sieve(x_1)) -> sieve(encArg(x_1))
   encArg(nats(x_1)) -> nats(encArg(x_1))
   encArg(zprimes) -> zprimes
   encArg(cons_a__filter(x_1, x_2, x_3)) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_a__sieve(x_1)) -> a__sieve(encArg(x_1))
   encArg(cons_a__nats(x_1)) -> a__nats(encArg(x_1))
   encArg(cons_a__zprimes) -> a__zprimes
   encArg(cons_mark(x_1)) -> mark(encArg(x_1))
   encode_a__filter(x_1, x_2, x_3) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_filter(x_1, x_2, x_3) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_s(x_1) -> s(encArg(x_1))
   encode_mark(x_1) -> mark(encArg(x_1))
   encode_a__sieve(x_1) -> a__sieve(encArg(x_1))
   encode_sieve(x_1) -> sieve(encArg(x_1))
   encode_a__nats(x_1) -> a__nats(encArg(x_1))
   encode_nats(x_1) -> nats(encArg(x_1))
   encode_a__zprimes -> a__zprimes
   encode_zprimes -> zprimes


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

(2)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following 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__sieve(cons(0, Y)) -> cons(0, sieve(Y))
   a__sieve(cons(s(N), Y)) -> cons(s(mark(N)), sieve(filter(Y, N, N)))
   a__nats(N) -> cons(mark(N), nats(s(N)))
   a__zprimes -> a__sieve(a__nats(s(s(0))))
   mark(filter(X1, X2, X3)) -> a__filter(mark(X1), mark(X2), mark(X3))
   mark(sieve(X)) -> a__sieve(mark(X))
   mark(nats(X)) -> a__nats(mark(X))
   mark(zprimes) -> a__zprimes
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(0) -> 0
   mark(s(X)) -> s(mark(X))
   a__filter(X1, X2, X3) -> filter(X1, X2, X3)
   a__sieve(X) -> sieve(X)
   a__nats(X) -> nats(X)
   a__zprimes -> zprimes

The (relative) TRS S consists of the following rules:

   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(0) -> 0
   encArg(filter(x_1, x_2, x_3)) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(sieve(x_1)) -> sieve(encArg(x_1))
   encArg(nats(x_1)) -> nats(encArg(x_1))
   encArg(zprimes) -> zprimes
   encArg(cons_a__filter(x_1, x_2, x_3)) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_a__sieve(x_1)) -> a__sieve(encArg(x_1))
   encArg(cons_a__nats(x_1)) -> a__nats(encArg(x_1))
   encArg(cons_a__zprimes) -> a__zprimes
   encArg(cons_mark(x_1)) -> mark(encArg(x_1))
   encode_a__filter(x_1, x_2, x_3) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_filter(x_1, x_2, x_3) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_s(x_1) -> s(encArg(x_1))
   encode_mark(x_1) -> mark(encArg(x_1))
   encode_a__sieve(x_1) -> a__sieve(encArg(x_1))
   encode_sieve(x_1) -> sieve(encArg(x_1))
   encode_a__nats(x_1) -> a__nats(encArg(x_1))
   encode_nats(x_1) -> nats(encArg(x_1))
   encode_a__zprimes -> a__zprimes
   encode_zprimes -> zprimes

Rewrite Strategy: INNERMOST
----------------------------------------

(3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
proved innermost termination of relative rules
----------------------------------------

(4)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following 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__sieve(cons(0, Y)) -> cons(0, sieve(Y))
   a__sieve(cons(s(N), Y)) -> cons(s(mark(N)), sieve(filter(Y, N, N)))
   a__nats(N) -> cons(mark(N), nats(s(N)))
   a__zprimes -> a__sieve(a__nats(s(s(0))))
   mark(filter(X1, X2, X3)) -> a__filter(mark(X1), mark(X2), mark(X3))
   mark(sieve(X)) -> a__sieve(mark(X))
   mark(nats(X)) -> a__nats(mark(X))
   mark(zprimes) -> a__zprimes
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(0) -> 0
   mark(s(X)) -> s(mark(X))
   a__filter(X1, X2, X3) -> filter(X1, X2, X3)
   a__sieve(X) -> sieve(X)
   a__nats(X) -> nats(X)
   a__zprimes -> zprimes

The (relative) TRS S consists of the following rules:

   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(0) -> 0
   encArg(filter(x_1, x_2, x_3)) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(sieve(x_1)) -> sieve(encArg(x_1))
   encArg(nats(x_1)) -> nats(encArg(x_1))
   encArg(zprimes) -> zprimes
   encArg(cons_a__filter(x_1, x_2, x_3)) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_a__sieve(x_1)) -> a__sieve(encArg(x_1))
   encArg(cons_a__nats(x_1)) -> a__nats(encArg(x_1))
   encArg(cons_a__zprimes) -> a__zprimes
   encArg(cons_mark(x_1)) -> mark(encArg(x_1))
   encode_a__filter(x_1, x_2, x_3) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_0 -> 0
   encode_filter(x_1, x_2, x_3) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_s(x_1) -> s(encArg(x_1))
   encode_mark(x_1) -> mark(encArg(x_1))
   encode_a__sieve(x_1) -> a__sieve(encArg(x_1))
   encode_sieve(x_1) -> sieve(encArg(x_1))
   encode_a__nats(x_1) -> a__nats(encArg(x_1))
   encode_nats(x_1) -> nats(encArg(x_1))
   encode_a__zprimes -> a__zprimes
   encode_zprimes -> zprimes

Rewrite Strategy: INNERMOST
----------------------------------------

(5) RenamingProof (BOTH BOUNDS(ID, ID))
Renamed function symbols to avoid clashes with predefined symbol.
----------------------------------------

(6)
Obligation:
The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following 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__sieve(cons(0', Y)) -> cons(0', sieve(Y))
   a__sieve(cons(s(N), Y)) -> cons(s(mark(N)), sieve(filter(Y, N, N)))
   a__nats(N) -> cons(mark(N), nats(s(N)))
   a__zprimes -> a__sieve(a__nats(s(s(0'))))
   mark(filter(X1, X2, X3)) -> a__filter(mark(X1), mark(X2), mark(X3))
   mark(sieve(X)) -> a__sieve(mark(X))
   mark(nats(X)) -> a__nats(mark(X))
   mark(zprimes) -> a__zprimes
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(0') -> 0'
   mark(s(X)) -> s(mark(X))
   a__filter(X1, X2, X3) -> filter(X1, X2, X3)
   a__sieve(X) -> sieve(X)
   a__nats(X) -> nats(X)
   a__zprimes -> zprimes

The (relative) TRS S consists of the following rules:

   encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
   encArg(0') -> 0'
   encArg(filter(x_1, x_2, x_3)) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(s(x_1)) -> s(encArg(x_1))
   encArg(sieve(x_1)) -> sieve(encArg(x_1))
   encArg(nats(x_1)) -> nats(encArg(x_1))
   encArg(zprimes) -> zprimes
   encArg(cons_a__filter(x_1, x_2, x_3)) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(cons_a__sieve(x_1)) -> a__sieve(encArg(x_1))
   encArg(cons_a__nats(x_1)) -> a__nats(encArg(x_1))
   encArg(cons_a__zprimes) -> a__zprimes
   encArg(cons_mark(x_1)) -> mark(encArg(x_1))
   encode_a__filter(x_1, x_2, x_3) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
   encode_0 -> 0'
   encode_filter(x_1, x_2, x_3) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
   encode_s(x_1) -> s(encArg(x_1))
   encode_mark(x_1) -> mark(encArg(x_1))
   encode_a__sieve(x_1) -> a__sieve(encArg(x_1))
   encode_sieve(x_1) -> sieve(encArg(x_1))
   encode_a__nats(x_1) -> a__nats(encArg(x_1))
   encode_nats(x_1) -> nats(encArg(x_1))
   encode_a__zprimes -> a__zprimes
   encode_zprimes -> zprimes

Rewrite Strategy: INNERMOST
----------------------------------------

(7) TypeInferenceProof (BOTH BOUNDS(ID, ID))
Infered types.
----------------------------------------

(8)
Obligation:
Innermost TRS:
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__sieve(cons(0', Y)) -> cons(0', sieve(Y))
a__sieve(cons(s(N), Y)) -> cons(s(mark(N)), sieve(filter(Y, N, N)))
a__nats(N) -> cons(mark(N), nats(s(N)))
a__zprimes -> a__sieve(a__nats(s(s(0'))))
mark(filter(X1, X2, X3)) -> a__filter(mark(X1), mark(X2), mark(X3))
mark(sieve(X)) -> a__sieve(mark(X))
mark(nats(X)) -> a__nats(mark(X))
mark(zprimes) -> a__zprimes
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(0') -> 0'
mark(s(X)) -> s(mark(X))
a__filter(X1, X2, X3) -> filter(X1, X2, X3)
a__sieve(X) -> sieve(X)
a__nats(X) -> nats(X)
a__zprimes -> zprimes
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(0') -> 0'
encArg(filter(x_1, x_2, x_3)) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(s(x_1)) -> s(encArg(x_1))
encArg(sieve(x_1)) -> sieve(encArg(x_1))
encArg(nats(x_1)) -> nats(encArg(x_1))
encArg(zprimes) -> zprimes
encArg(cons_a__filter(x_1, x_2, x_3)) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_a__sieve(x_1)) -> a__sieve(encArg(x_1))
encArg(cons_a__nats(x_1)) -> a__nats(encArg(x_1))
encArg(cons_a__zprimes) -> a__zprimes
encArg(cons_mark(x_1)) -> mark(encArg(x_1))
encode_a__filter(x_1, x_2, x_3) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_filter(x_1, x_2, x_3) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_s(x_1) -> s(encArg(x_1))
encode_mark(x_1) -> mark(encArg(x_1))
encode_a__sieve(x_1) -> a__sieve(encArg(x_1))
encode_sieve(x_1) -> sieve(encArg(x_1))
encode_a__nats(x_1) -> a__nats(encArg(x_1))
encode_nats(x_1) -> nats(encArg(x_1))
encode_a__zprimes -> a__zprimes
encode_zprimes -> zprimes

Types:
a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
0' :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
s :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encArg :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_cons :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_0 :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_s :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
hole_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark1_4 :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4 :: Nat -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark

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

(9) OrderProof (LOWER BOUND(ID))
Heuristically decided to analyse the following defined symbols:
a__filter, mark, a__sieve, a__nats, a__zprimes, encArg

They will be analysed ascendingly in the following order:
a__filter = mark
a__filter = a__sieve
a__filter = a__nats
a__filter = a__zprimes
a__filter < encArg
mark = a__sieve
mark = a__nats
mark = a__zprimes
mark < encArg
a__sieve = a__nats
a__sieve = a__zprimes
a__sieve < encArg
a__nats = a__zprimes
a__nats < encArg
a__zprimes < encArg

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

(10)
Obligation:
Innermost TRS:
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__sieve(cons(0', Y)) -> cons(0', sieve(Y))
a__sieve(cons(s(N), Y)) -> cons(s(mark(N)), sieve(filter(Y, N, N)))
a__nats(N) -> cons(mark(N), nats(s(N)))
a__zprimes -> a__sieve(a__nats(s(s(0'))))
mark(filter(X1, X2, X3)) -> a__filter(mark(X1), mark(X2), mark(X3))
mark(sieve(X)) -> a__sieve(mark(X))
mark(nats(X)) -> a__nats(mark(X))
mark(zprimes) -> a__zprimes
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(0') -> 0'
mark(s(X)) -> s(mark(X))
a__filter(X1, X2, X3) -> filter(X1, X2, X3)
a__sieve(X) -> sieve(X)
a__nats(X) -> nats(X)
a__zprimes -> zprimes
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(0') -> 0'
encArg(filter(x_1, x_2, x_3)) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(s(x_1)) -> s(encArg(x_1))
encArg(sieve(x_1)) -> sieve(encArg(x_1))
encArg(nats(x_1)) -> nats(encArg(x_1))
encArg(zprimes) -> zprimes
encArg(cons_a__filter(x_1, x_2, x_3)) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_a__sieve(x_1)) -> a__sieve(encArg(x_1))
encArg(cons_a__nats(x_1)) -> a__nats(encArg(x_1))
encArg(cons_a__zprimes) -> a__zprimes
encArg(cons_mark(x_1)) -> mark(encArg(x_1))
encode_a__filter(x_1, x_2, x_3) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_filter(x_1, x_2, x_3) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_s(x_1) -> s(encArg(x_1))
encode_mark(x_1) -> mark(encArg(x_1))
encode_a__sieve(x_1) -> a__sieve(encArg(x_1))
encode_sieve(x_1) -> sieve(encArg(x_1))
encode_a__nats(x_1) -> a__nats(encArg(x_1))
encode_nats(x_1) -> nats(encArg(x_1))
encode_a__zprimes -> a__zprimes
encode_zprimes -> zprimes

Types:
a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
0' :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
s :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encArg :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_cons :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_0 :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_s :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
hole_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark1_4 :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4 :: Nat -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark


Generator Equations:
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(0) <=> 0'
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(+(x, 1)) <=> cons(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(x), 0')


The following defined symbols remain to be analysed:
mark, a__filter, a__sieve, a__nats, a__zprimes, encArg

They will be analysed ascendingly in the following order:
a__filter = mark
a__filter = a__sieve
a__filter = a__nats
a__filter = a__zprimes
a__filter < encArg
mark = a__sieve
mark = a__nats
mark = a__zprimes
mark < encArg
a__sieve = a__nats
a__sieve = a__zprimes
a__sieve < encArg
a__nats = a__zprimes
a__nats < encArg
a__zprimes < encArg

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

(11) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
mark(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n4_4)) -> gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n4_4), rt in Omega(1 + n4_4)

Induction Base:
mark(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(0)) ->_R^Omega(1)
0'

Induction Step:
mark(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(+(n4_4, 1))) ->_R^Omega(1)
cons(mark(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n4_4)), 0') ->_IH
cons(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(c5_4), 0')

We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
----------------------------------------

(12)
Complex Obligation (BEST)

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

(13)
Obligation:
Proved the lower bound n^1 for the following obligation:

Innermost TRS:
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__sieve(cons(0', Y)) -> cons(0', sieve(Y))
a__sieve(cons(s(N), Y)) -> cons(s(mark(N)), sieve(filter(Y, N, N)))
a__nats(N) -> cons(mark(N), nats(s(N)))
a__zprimes -> a__sieve(a__nats(s(s(0'))))
mark(filter(X1, X2, X3)) -> a__filter(mark(X1), mark(X2), mark(X3))
mark(sieve(X)) -> a__sieve(mark(X))
mark(nats(X)) -> a__nats(mark(X))
mark(zprimes) -> a__zprimes
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(0') -> 0'
mark(s(X)) -> s(mark(X))
a__filter(X1, X2, X3) -> filter(X1, X2, X3)
a__sieve(X) -> sieve(X)
a__nats(X) -> nats(X)
a__zprimes -> zprimes
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(0') -> 0'
encArg(filter(x_1, x_2, x_3)) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(s(x_1)) -> s(encArg(x_1))
encArg(sieve(x_1)) -> sieve(encArg(x_1))
encArg(nats(x_1)) -> nats(encArg(x_1))
encArg(zprimes) -> zprimes
encArg(cons_a__filter(x_1, x_2, x_3)) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_a__sieve(x_1)) -> a__sieve(encArg(x_1))
encArg(cons_a__nats(x_1)) -> a__nats(encArg(x_1))
encArg(cons_a__zprimes) -> a__zprimes
encArg(cons_mark(x_1)) -> mark(encArg(x_1))
encode_a__filter(x_1, x_2, x_3) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_filter(x_1, x_2, x_3) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_s(x_1) -> s(encArg(x_1))
encode_mark(x_1) -> mark(encArg(x_1))
encode_a__sieve(x_1) -> a__sieve(encArg(x_1))
encode_sieve(x_1) -> sieve(encArg(x_1))
encode_a__nats(x_1) -> a__nats(encArg(x_1))
encode_nats(x_1) -> nats(encArg(x_1))
encode_a__zprimes -> a__zprimes
encode_zprimes -> zprimes

Types:
a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
0' :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
s :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encArg :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_cons :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_0 :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_s :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
hole_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark1_4 :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4 :: Nat -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark


Generator Equations:
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(0) <=> 0'
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(+(x, 1)) <=> cons(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(x), 0')


The following defined symbols remain to be analysed:
mark, a__filter, a__sieve, a__nats, a__zprimes, encArg

They will be analysed ascendingly in the following order:
a__filter = mark
a__filter = a__sieve
a__filter = a__nats
a__filter = a__zprimes
a__filter < encArg
mark = a__sieve
mark = a__nats
mark = a__zprimes
mark < encArg
a__sieve = a__nats
a__sieve = a__zprimes
a__sieve < encArg
a__nats = a__zprimes
a__nats < encArg
a__zprimes < encArg

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

(14) LowerBoundPropagationProof (FINISHED)
Propagated lower bound.
----------------------------------------

(15)
BOUNDS(n^1, INF)

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

(16)
Obligation:
Innermost TRS:
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__sieve(cons(0', Y)) -> cons(0', sieve(Y))
a__sieve(cons(s(N), Y)) -> cons(s(mark(N)), sieve(filter(Y, N, N)))
a__nats(N) -> cons(mark(N), nats(s(N)))
a__zprimes -> a__sieve(a__nats(s(s(0'))))
mark(filter(X1, X2, X3)) -> a__filter(mark(X1), mark(X2), mark(X3))
mark(sieve(X)) -> a__sieve(mark(X))
mark(nats(X)) -> a__nats(mark(X))
mark(zprimes) -> a__zprimes
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(0') -> 0'
mark(s(X)) -> s(mark(X))
a__filter(X1, X2, X3) -> filter(X1, X2, X3)
a__sieve(X) -> sieve(X)
a__nats(X) -> nats(X)
a__zprimes -> zprimes
encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2))
encArg(0') -> 0'
encArg(filter(x_1, x_2, x_3)) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(s(x_1)) -> s(encArg(x_1))
encArg(sieve(x_1)) -> sieve(encArg(x_1))
encArg(nats(x_1)) -> nats(encArg(x_1))
encArg(zprimes) -> zprimes
encArg(cons_a__filter(x_1, x_2, x_3)) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
encArg(cons_a__sieve(x_1)) -> a__sieve(encArg(x_1))
encArg(cons_a__nats(x_1)) -> a__nats(encArg(x_1))
encArg(cons_a__zprimes) -> a__zprimes
encArg(cons_mark(x_1)) -> mark(encArg(x_1))
encode_a__filter(x_1, x_2, x_3) -> a__filter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2))
encode_0 -> 0'
encode_filter(x_1, x_2, x_3) -> filter(encArg(x_1), encArg(x_2), encArg(x_3))
encode_s(x_1) -> s(encArg(x_1))
encode_mark(x_1) -> mark(encArg(x_1))
encode_a__sieve(x_1) -> a__sieve(encArg(x_1))
encode_sieve(x_1) -> sieve(encArg(x_1))
encode_a__nats(x_1) -> a__nats(encArg(x_1))
encode_nats(x_1) -> nats(encArg(x_1))
encode_a__zprimes -> a__zprimes
encode_zprimes -> zprimes

Types:
a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
0' :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
s :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encArg :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
cons_mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_cons :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_0 :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_filter :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_s :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_mark :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_sieve :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_nats :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_a__zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
encode_zprimes :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
hole_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark1_4 :: cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4 :: Nat -> cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark


Lemmas:
mark(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n4_4)) -> gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n4_4), rt in Omega(1 + n4_4)


Generator Equations:
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(0) <=> 0'
gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(+(x, 1)) <=> cons(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(x), 0')


The following defined symbols remain to be analysed:
a__filter, a__sieve, a__nats, a__zprimes, encArg

They will be analysed ascendingly in the following order:
a__filter = mark
a__filter = a__sieve
a__filter = a__nats
a__filter = a__zprimes
a__filter < encArg
mark = a__sieve
mark = a__nats
mark = a__zprimes
mark < encArg
a__sieve = a__nats
a__sieve = a__zprimes
a__sieve < encArg
a__nats = a__zprimes
a__nats < encArg
a__zprimes < encArg

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

(17) RewriteLemmaProof (LOWER BOUND(ID))
Proved the following rewrite lemma:
encArg(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n3113_4)) -> gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n3113_4), rt in Omega(0)

Induction Base:
encArg(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(0)) ->_R^Omega(0)
0'

Induction Step:
encArg(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(+(n3113_4, 1))) ->_R^Omega(0)
cons(encArg(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n3113_4)), encArg(0')) ->_IH
cons(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(c3114_4), encArg(0')) ->_R^Omega(0)
cons(gen_cons:0':filter:s:sieve:nats:zprimes:cons_a__filter:cons_a__sieve:cons_a__nats:cons_a__zprimes:cons_mark2_4(n3113_4), 0')

We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0).
----------------------------------------

(18)
BOUNDS(1, INF)