329.28/291.55	WORST_CASE(Omega(n^1), ?)
329.28/291.56	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
329.28/291.56	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
329.28/291.56	
329.28/291.56	
329.28/291.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
329.28/291.56	
329.28/291.56	(0) CpxTRS
329.28/291.56	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
329.28/291.56	(2) CpxTRS
329.28/291.56	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
329.28/291.56	(4) typed CpxTrs
329.28/291.56	(5) OrderProof [LOWER BOUND(ID), 0 ms]
329.28/291.56	(6) typed CpxTrs
329.28/291.56	(7) RewriteLemmaProof [LOWER BOUND(ID), 478 ms]
329.28/291.56	(8) BEST
329.28/291.56	    (9) proven lower bound
329.28/291.56	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
329.28/291.56	        (11) BOUNDS(n^1, INF)
329.28/291.56	    (12) typed CpxTrs
329.28/291.56	        (13) RewriteLemmaProof [LOWER BOUND(ID), 173 ms]
329.28/291.56	        (14) typed CpxTrs
329.28/291.56	        (15) RewriteLemmaProof [LOWER BOUND(ID), 79 ms]
329.28/291.56	        (16) typed CpxTrs
329.28/291.56	        (17) RewriteLemmaProof [LOWER BOUND(ID), 56 ms]
329.28/291.56	        (18) typed CpxTrs
329.28/291.56	        (19) RewriteLemmaProof [LOWER BOUND(ID), 37 ms]
329.28/291.56	        (20) typed CpxTrs
329.28/291.56	
329.28/291.56	
329.28/291.56	----------------------------------------
329.28/291.56	
329.28/291.56	(0)
329.28/291.56	Obligation:
329.28/291.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
329.28/291.56	
329.28/291.56	
329.28/291.56	The TRS R consists of the following rules:
329.28/291.56	
329.28/291.56	   active(filter(cons(X, Y), 0, M)) -> mark(cons(0, filter(Y, M, M)))
329.28/291.56	   active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.28/291.56	   active(sieve(cons(0, Y))) -> mark(cons(0, sieve(Y)))
329.28/291.56	   active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.28/291.56	   active(nats(N)) -> mark(cons(N, nats(s(N))))
329.28/291.56	   active(zprimes) -> mark(sieve(nats(s(s(0)))))
329.28/291.56	   active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.28/291.56	   active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.28/291.56	   active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.28/291.56	   active(cons(X1, X2)) -> cons(active(X1), X2)
329.28/291.56	   active(s(X)) -> s(active(X))
329.28/291.56	   active(sieve(X)) -> sieve(active(X))
329.28/291.56	   active(nats(X)) -> nats(active(X))
329.28/291.56	   filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.28/291.56	   filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.28/291.56	   filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.28/291.56	   cons(mark(X1), X2) -> mark(cons(X1, X2))
329.28/291.56	   s(mark(X)) -> mark(s(X))
329.28/291.56	   sieve(mark(X)) -> mark(sieve(X))
329.28/291.56	   nats(mark(X)) -> mark(nats(X))
329.28/291.56	   proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.28/291.56	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.28/291.56	   proper(0) -> ok(0)
329.28/291.56	   proper(s(X)) -> s(proper(X))
329.28/291.56	   proper(sieve(X)) -> sieve(proper(X))
329.28/291.56	   proper(nats(X)) -> nats(proper(X))
329.28/291.56	   proper(zprimes) -> ok(zprimes)
329.28/291.56	   filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.28/291.56	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.28/291.56	   s(ok(X)) -> ok(s(X))
329.28/291.56	   sieve(ok(X)) -> ok(sieve(X))
329.28/291.56	   nats(ok(X)) -> ok(nats(X))
329.28/291.56	   top(mark(X)) -> top(proper(X))
329.28/291.56	   top(ok(X)) -> top(active(X))
329.28/291.56	
329.28/291.56	S is empty.
329.28/291.56	Rewrite Strategy: FULL
329.28/291.56	----------------------------------------
329.28/291.56	
329.28/291.56	(1) RenamingProof (BOTH BOUNDS(ID, ID))
329.28/291.56	Renamed function symbols to avoid clashes with predefined symbol.
329.28/291.56	----------------------------------------
329.28/291.56	
329.28/291.56	(2)
329.28/291.56	Obligation:
329.28/291.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
329.28/291.56	
329.28/291.56	
329.28/291.56	The TRS R consists of the following rules:
329.28/291.56	
329.28/291.56	   active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.28/291.56	   active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.28/291.56	   active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.28/291.56	   active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.28/291.56	   active(nats(N)) -> mark(cons(N, nats(s(N))))
329.28/291.56	   active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.28/291.56	   active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.28/291.56	   active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.28/291.56	   active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.28/291.56	   active(cons(X1, X2)) -> cons(active(X1), X2)
329.28/291.56	   active(s(X)) -> s(active(X))
329.28/291.56	   active(sieve(X)) -> sieve(active(X))
329.28/291.56	   active(nats(X)) -> nats(active(X))
329.28/291.56	   filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.28/291.56	   filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.28/291.56	   filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.28/291.56	   cons(mark(X1), X2) -> mark(cons(X1, X2))
329.28/291.56	   s(mark(X)) -> mark(s(X))
329.28/291.56	   sieve(mark(X)) -> mark(sieve(X))
329.28/291.56	   nats(mark(X)) -> mark(nats(X))
329.28/291.56	   proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.28/291.56	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.28/291.56	   proper(0') -> ok(0')
329.28/291.56	   proper(s(X)) -> s(proper(X))
329.28/291.56	   proper(sieve(X)) -> sieve(proper(X))
329.28/291.56	   proper(nats(X)) -> nats(proper(X))
329.28/291.56	   proper(zprimes) -> ok(zprimes)
329.28/291.56	   filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.28/291.56	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.28/291.56	   s(ok(X)) -> ok(s(X))
329.28/291.56	   sieve(ok(X)) -> ok(sieve(X))
329.28/291.56	   nats(ok(X)) -> ok(nats(X))
329.28/291.56	   top(mark(X)) -> top(proper(X))
329.28/291.56	   top(ok(X)) -> top(active(X))
329.28/291.56	
329.28/291.56	S is empty.
329.28/291.56	Rewrite Strategy: FULL
329.28/291.56	----------------------------------------
329.28/291.56	
329.28/291.56	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
329.28/291.56	Infered types.
329.28/291.56	----------------------------------------
329.28/291.56	
329.28/291.56	(4)
329.28/291.56	Obligation:
329.28/291.56	TRS:
329.28/291.56	Rules:
329.28/291.56	active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.28/291.56	active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.28/291.56	active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.28/291.56	active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.28/291.56	active(nats(N)) -> mark(cons(N, nats(s(N))))
329.28/291.56	active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.28/291.56	active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.28/291.56	active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.28/291.56	active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.28/291.56	active(cons(X1, X2)) -> cons(active(X1), X2)
329.28/291.56	active(s(X)) -> s(active(X))
329.28/291.56	active(sieve(X)) -> sieve(active(X))
329.28/291.56	active(nats(X)) -> nats(active(X))
329.28/291.56	filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.28/291.56	filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.28/291.56	filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.28/291.56	cons(mark(X1), X2) -> mark(cons(X1, X2))
329.28/291.56	s(mark(X)) -> mark(s(X))
329.28/291.56	sieve(mark(X)) -> mark(sieve(X))
329.28/291.56	nats(mark(X)) -> mark(nats(X))
329.28/291.56	proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.28/291.56	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.28/291.56	proper(0') -> ok(0')
329.28/291.56	proper(s(X)) -> s(proper(X))
329.28/291.56	proper(sieve(X)) -> sieve(proper(X))
329.28/291.56	proper(nats(X)) -> nats(proper(X))
329.28/291.56	proper(zprimes) -> ok(zprimes)
329.28/291.56	filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.28/291.56	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.28/291.56	s(ok(X)) -> ok(s(X))
329.28/291.56	sieve(ok(X)) -> ok(sieve(X))
329.28/291.56	nats(ok(X)) -> ok(nats(X))
329.28/291.56	top(mark(X)) -> top(proper(X))
329.28/291.56	top(ok(X)) -> top(active(X))
329.28/291.56	
329.28/291.56	Types:
329.28/291.56	active :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	filter :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	cons :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	0' :: 0':mark:zprimes:ok
329.28/291.56	mark :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	s :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	sieve :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	nats :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	zprimes :: 0':mark:zprimes:ok
329.28/291.56	proper :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	ok :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	top :: 0':mark:zprimes:ok -> top
329.28/291.56	hole_0':mark:zprimes:ok1_0 :: 0':mark:zprimes:ok
329.28/291.56	hole_top2_0 :: top
329.28/291.56	gen_0':mark:zprimes:ok3_0 :: Nat -> 0':mark:zprimes:ok
329.28/291.56	
329.28/291.56	----------------------------------------
329.28/291.56	
329.28/291.56	(5) OrderProof (LOWER BOUND(ID))
329.28/291.56	Heuristically decided to analyse the following defined symbols:
329.28/291.56	active, cons, filter, sieve, s, nats, proper, top
329.28/291.56	
329.28/291.56	They will be analysed ascendingly in the following order:
329.28/291.56	cons < active
329.28/291.56	filter < active
329.28/291.56	sieve < active
329.28/291.56	s < active
329.28/291.56	nats < active
329.28/291.56	active < top
329.28/291.56	cons < proper
329.28/291.56	filter < proper
329.28/291.56	sieve < proper
329.28/291.56	s < proper
329.28/291.56	nats < proper
329.28/291.56	proper < top
329.28/291.56	
329.28/291.56	----------------------------------------
329.28/291.56	
329.28/291.56	(6)
329.28/291.56	Obligation:
329.28/291.56	TRS:
329.28/291.56	Rules:
329.28/291.56	active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.28/291.56	active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.28/291.56	active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.28/291.56	active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.28/291.56	active(nats(N)) -> mark(cons(N, nats(s(N))))
329.28/291.56	active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.28/291.56	active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.28/291.56	active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.28/291.56	active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.28/291.56	active(cons(X1, X2)) -> cons(active(X1), X2)
329.28/291.56	active(s(X)) -> s(active(X))
329.28/291.56	active(sieve(X)) -> sieve(active(X))
329.28/291.56	active(nats(X)) -> nats(active(X))
329.28/291.56	filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.28/291.56	filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.28/291.56	filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.28/291.56	cons(mark(X1), X2) -> mark(cons(X1, X2))
329.28/291.56	s(mark(X)) -> mark(s(X))
329.28/291.56	sieve(mark(X)) -> mark(sieve(X))
329.28/291.56	nats(mark(X)) -> mark(nats(X))
329.28/291.56	proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.28/291.56	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.28/291.56	proper(0') -> ok(0')
329.28/291.56	proper(s(X)) -> s(proper(X))
329.28/291.56	proper(sieve(X)) -> sieve(proper(X))
329.28/291.56	proper(nats(X)) -> nats(proper(X))
329.28/291.56	proper(zprimes) -> ok(zprimes)
329.28/291.56	filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.28/291.56	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.28/291.56	s(ok(X)) -> ok(s(X))
329.28/291.56	sieve(ok(X)) -> ok(sieve(X))
329.28/291.56	nats(ok(X)) -> ok(nats(X))
329.28/291.56	top(mark(X)) -> top(proper(X))
329.28/291.56	top(ok(X)) -> top(active(X))
329.28/291.56	
329.28/291.56	Types:
329.28/291.56	active :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	filter :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	cons :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	0' :: 0':mark:zprimes:ok
329.28/291.56	mark :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	s :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	sieve :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	nats :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	zprimes :: 0':mark:zprimes:ok
329.28/291.56	proper :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	ok :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.28/291.56	top :: 0':mark:zprimes:ok -> top
329.28/291.56	hole_0':mark:zprimes:ok1_0 :: 0':mark:zprimes:ok
329.28/291.56	hole_top2_0 :: top
329.28/291.56	gen_0':mark:zprimes:ok3_0 :: Nat -> 0':mark:zprimes:ok
329.28/291.56	
329.28/291.56	
329.28/291.56	Generator Equations:
329.28/291.56	gen_0':mark:zprimes:ok3_0(0) <=> 0'
329.28/291.56	gen_0':mark:zprimes:ok3_0(+(x, 1)) <=> mark(gen_0':mark:zprimes:ok3_0(x))
329.28/291.56	
329.28/291.56	
329.28/291.56	The following defined symbols remain to be analysed:
329.28/291.56	cons, active, filter, sieve, s, nats, proper, top
329.28/291.56	
329.28/291.56	They will be analysed ascendingly in the following order:
329.28/291.56	cons < active
329.28/291.56	filter < active
329.28/291.56	sieve < active
329.28/291.56	s < active
329.28/291.56	nats < active
329.28/291.56	active < top
329.28/291.56	cons < proper
329.28/291.56	filter < proper
329.28/291.56	sieve < proper
329.28/291.56	s < proper
329.28/291.56	nats < proper
329.28/291.57	proper < top
329.28/291.57	
329.28/291.57	----------------------------------------
329.28/291.57	
329.28/291.57	(7) RewriteLemmaProof (LOWER BOUND(ID))
329.28/291.57	Proved the following rewrite lemma:
329.28/291.57	cons(gen_0':mark:zprimes:ok3_0(+(1, n5_0)), gen_0':mark:zprimes:ok3_0(b)) -> *4_0, rt in Omega(n5_0)
329.28/291.57	
329.28/291.57	Induction Base:
329.28/291.57	cons(gen_0':mark:zprimes:ok3_0(+(1, 0)), gen_0':mark:zprimes:ok3_0(b))
329.28/291.57	
329.28/291.57	Induction Step:
329.28/291.57	cons(gen_0':mark:zprimes:ok3_0(+(1, +(n5_0, 1))), gen_0':mark:zprimes:ok3_0(b)) ->_R^Omega(1)
329.28/291.57	mark(cons(gen_0':mark:zprimes:ok3_0(+(1, n5_0)), gen_0':mark:zprimes:ok3_0(b))) ->_IH
329.28/291.57	mark(*4_0)
329.28/291.57	
329.28/291.57	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
329.28/291.57	----------------------------------------
329.28/291.57	
329.28/291.57	(8)
329.28/291.57	Complex Obligation (BEST)
329.28/291.57	
329.28/291.57	----------------------------------------
329.28/291.57	
329.28/291.57	(9)
329.28/291.57	Obligation:
329.28/291.57	Proved the lower bound n^1 for the following obligation:
329.28/291.57	
329.28/291.57	TRS:
329.28/291.57	Rules:
329.28/291.57	active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.28/291.57	active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.28/291.57	active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.28/291.57	active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.37/291.57	active(nats(N)) -> mark(cons(N, nats(s(N))))
329.37/291.57	active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.37/291.57	active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.37/291.57	active(cons(X1, X2)) -> cons(active(X1), X2)
329.37/291.57	active(s(X)) -> s(active(X))
329.37/291.57	active(sieve(X)) -> sieve(active(X))
329.37/291.57	active(nats(X)) -> nats(active(X))
329.37/291.57	filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.37/291.57	cons(mark(X1), X2) -> mark(cons(X1, X2))
329.37/291.57	s(mark(X)) -> mark(s(X))
329.37/291.57	sieve(mark(X)) -> mark(sieve(X))
329.37/291.57	nats(mark(X)) -> mark(nats(X))
329.37/291.57	proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.37/291.57	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.37/291.57	proper(0') -> ok(0')
329.37/291.57	proper(s(X)) -> s(proper(X))
329.37/291.57	proper(sieve(X)) -> sieve(proper(X))
329.37/291.57	proper(nats(X)) -> nats(proper(X))
329.37/291.57	proper(zprimes) -> ok(zprimes)
329.37/291.57	filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.37/291.57	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.37/291.57	s(ok(X)) -> ok(s(X))
329.37/291.57	sieve(ok(X)) -> ok(sieve(X))
329.37/291.57	nats(ok(X)) -> ok(nats(X))
329.37/291.57	top(mark(X)) -> top(proper(X))
329.37/291.57	top(ok(X)) -> top(active(X))
329.37/291.57	
329.37/291.57	Types:
329.37/291.57	active :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	filter :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	cons :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	0' :: 0':mark:zprimes:ok
329.37/291.57	mark :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	s :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	sieve :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	nats :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	zprimes :: 0':mark:zprimes:ok
329.37/291.57	proper :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	ok :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	top :: 0':mark:zprimes:ok -> top
329.37/291.57	hole_0':mark:zprimes:ok1_0 :: 0':mark:zprimes:ok
329.37/291.57	hole_top2_0 :: top
329.37/291.57	gen_0':mark:zprimes:ok3_0 :: Nat -> 0':mark:zprimes:ok
329.37/291.57	
329.37/291.57	
329.37/291.57	Generator Equations:
329.37/291.57	gen_0':mark:zprimes:ok3_0(0) <=> 0'
329.37/291.57	gen_0':mark:zprimes:ok3_0(+(x, 1)) <=> mark(gen_0':mark:zprimes:ok3_0(x))
329.37/291.57	
329.37/291.57	
329.37/291.57	The following defined symbols remain to be analysed:
329.37/291.57	cons, active, filter, sieve, s, nats, proper, top
329.37/291.57	
329.37/291.57	They will be analysed ascendingly in the following order:
329.37/291.57	cons < active
329.37/291.57	filter < active
329.37/291.57	sieve < active
329.37/291.57	s < active
329.37/291.57	nats < active
329.37/291.57	active < top
329.37/291.57	cons < proper
329.37/291.57	filter < proper
329.37/291.57	sieve < proper
329.37/291.57	s < proper
329.37/291.57	nats < proper
329.37/291.57	proper < top
329.37/291.57	
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(10) LowerBoundPropagationProof (FINISHED)
329.37/291.57	Propagated lower bound.
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(11)
329.37/291.57	BOUNDS(n^1, INF)
329.37/291.57	
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(12)
329.37/291.57	Obligation:
329.37/291.57	TRS:
329.37/291.57	Rules:
329.37/291.57	active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.37/291.57	active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.37/291.57	active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.37/291.57	active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.37/291.57	active(nats(N)) -> mark(cons(N, nats(s(N))))
329.37/291.57	active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.37/291.57	active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.37/291.57	active(cons(X1, X2)) -> cons(active(X1), X2)
329.37/291.57	active(s(X)) -> s(active(X))
329.37/291.57	active(sieve(X)) -> sieve(active(X))
329.37/291.57	active(nats(X)) -> nats(active(X))
329.37/291.57	filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.37/291.57	cons(mark(X1), X2) -> mark(cons(X1, X2))
329.37/291.57	s(mark(X)) -> mark(s(X))
329.37/291.57	sieve(mark(X)) -> mark(sieve(X))
329.37/291.57	nats(mark(X)) -> mark(nats(X))
329.37/291.57	proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.37/291.57	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.37/291.57	proper(0') -> ok(0')
329.37/291.57	proper(s(X)) -> s(proper(X))
329.37/291.57	proper(sieve(X)) -> sieve(proper(X))
329.37/291.57	proper(nats(X)) -> nats(proper(X))
329.37/291.57	proper(zprimes) -> ok(zprimes)
329.37/291.57	filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.37/291.57	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.37/291.57	s(ok(X)) -> ok(s(X))
329.37/291.57	sieve(ok(X)) -> ok(sieve(X))
329.37/291.57	nats(ok(X)) -> ok(nats(X))
329.37/291.57	top(mark(X)) -> top(proper(X))
329.37/291.57	top(ok(X)) -> top(active(X))
329.37/291.57	
329.37/291.57	Types:
329.37/291.57	active :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	filter :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	cons :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	0' :: 0':mark:zprimes:ok
329.37/291.57	mark :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	s :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	sieve :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	nats :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	zprimes :: 0':mark:zprimes:ok
329.37/291.57	proper :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	ok :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	top :: 0':mark:zprimes:ok -> top
329.37/291.57	hole_0':mark:zprimes:ok1_0 :: 0':mark:zprimes:ok
329.37/291.57	hole_top2_0 :: top
329.37/291.57	gen_0':mark:zprimes:ok3_0 :: Nat -> 0':mark:zprimes:ok
329.37/291.57	
329.37/291.57	
329.37/291.57	Lemmas:
329.37/291.57	cons(gen_0':mark:zprimes:ok3_0(+(1, n5_0)), gen_0':mark:zprimes:ok3_0(b)) -> *4_0, rt in Omega(n5_0)
329.37/291.57	
329.37/291.57	
329.37/291.57	Generator Equations:
329.37/291.57	gen_0':mark:zprimes:ok3_0(0) <=> 0'
329.37/291.57	gen_0':mark:zprimes:ok3_0(+(x, 1)) <=> mark(gen_0':mark:zprimes:ok3_0(x))
329.37/291.57	
329.37/291.57	
329.37/291.57	The following defined symbols remain to be analysed:
329.37/291.57	filter, active, sieve, s, nats, proper, top
329.37/291.57	
329.37/291.57	They will be analysed ascendingly in the following order:
329.37/291.57	filter < active
329.37/291.57	sieve < active
329.37/291.57	s < active
329.37/291.57	nats < active
329.37/291.57	active < top
329.37/291.57	filter < proper
329.37/291.57	sieve < proper
329.37/291.57	s < proper
329.37/291.57	nats < proper
329.37/291.57	proper < top
329.37/291.57	
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(13) RewriteLemmaProof (LOWER BOUND(ID))
329.37/291.57	Proved the following rewrite lemma:
329.37/291.57	filter(gen_0':mark:zprimes:ok3_0(+(1, n916_0)), gen_0':mark:zprimes:ok3_0(b), gen_0':mark:zprimes:ok3_0(c)) -> *4_0, rt in Omega(n916_0)
329.37/291.57	
329.37/291.57	Induction Base:
329.37/291.57	filter(gen_0':mark:zprimes:ok3_0(+(1, 0)), gen_0':mark:zprimes:ok3_0(b), gen_0':mark:zprimes:ok3_0(c))
329.37/291.57	
329.37/291.57	Induction Step:
329.37/291.57	filter(gen_0':mark:zprimes:ok3_0(+(1, +(n916_0, 1))), gen_0':mark:zprimes:ok3_0(b), gen_0':mark:zprimes:ok3_0(c)) ->_R^Omega(1)
329.37/291.57	mark(filter(gen_0':mark:zprimes:ok3_0(+(1, n916_0)), gen_0':mark:zprimes:ok3_0(b), gen_0':mark:zprimes:ok3_0(c))) ->_IH
329.37/291.57	mark(*4_0)
329.37/291.57	
329.37/291.57	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(14)
329.37/291.57	Obligation:
329.37/291.57	TRS:
329.37/291.57	Rules:
329.37/291.57	active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.37/291.57	active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.37/291.57	active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.37/291.57	active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.37/291.57	active(nats(N)) -> mark(cons(N, nats(s(N))))
329.37/291.57	active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.37/291.57	active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.37/291.57	active(cons(X1, X2)) -> cons(active(X1), X2)
329.37/291.57	active(s(X)) -> s(active(X))
329.37/291.57	active(sieve(X)) -> sieve(active(X))
329.37/291.57	active(nats(X)) -> nats(active(X))
329.37/291.57	filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.37/291.57	cons(mark(X1), X2) -> mark(cons(X1, X2))
329.37/291.57	s(mark(X)) -> mark(s(X))
329.37/291.57	sieve(mark(X)) -> mark(sieve(X))
329.37/291.57	nats(mark(X)) -> mark(nats(X))
329.37/291.57	proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.37/291.57	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.37/291.57	proper(0') -> ok(0')
329.37/291.57	proper(s(X)) -> s(proper(X))
329.37/291.57	proper(sieve(X)) -> sieve(proper(X))
329.37/291.57	proper(nats(X)) -> nats(proper(X))
329.37/291.57	proper(zprimes) -> ok(zprimes)
329.37/291.57	filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.37/291.57	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.37/291.57	s(ok(X)) -> ok(s(X))
329.37/291.57	sieve(ok(X)) -> ok(sieve(X))
329.37/291.57	nats(ok(X)) -> ok(nats(X))
329.37/291.57	top(mark(X)) -> top(proper(X))
329.37/291.57	top(ok(X)) -> top(active(X))
329.37/291.57	
329.37/291.57	Types:
329.37/291.57	active :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	filter :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	cons :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	0' :: 0':mark:zprimes:ok
329.37/291.57	mark :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	s :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	sieve :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	nats :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	zprimes :: 0':mark:zprimes:ok
329.37/291.57	proper :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	ok :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	top :: 0':mark:zprimes:ok -> top
329.37/291.57	hole_0':mark:zprimes:ok1_0 :: 0':mark:zprimes:ok
329.37/291.57	hole_top2_0 :: top
329.37/291.57	gen_0':mark:zprimes:ok3_0 :: Nat -> 0':mark:zprimes:ok
329.37/291.57	
329.37/291.57	
329.37/291.57	Lemmas:
329.37/291.57	cons(gen_0':mark:zprimes:ok3_0(+(1, n5_0)), gen_0':mark:zprimes:ok3_0(b)) -> *4_0, rt in Omega(n5_0)
329.37/291.57	filter(gen_0':mark:zprimes:ok3_0(+(1, n916_0)), gen_0':mark:zprimes:ok3_0(b), gen_0':mark:zprimes:ok3_0(c)) -> *4_0, rt in Omega(n916_0)
329.37/291.57	
329.37/291.57	
329.37/291.57	Generator Equations:
329.37/291.57	gen_0':mark:zprimes:ok3_0(0) <=> 0'
329.37/291.57	gen_0':mark:zprimes:ok3_0(+(x, 1)) <=> mark(gen_0':mark:zprimes:ok3_0(x))
329.37/291.57	
329.37/291.57	
329.37/291.57	The following defined symbols remain to be analysed:
329.37/291.57	sieve, active, s, nats, proper, top
329.37/291.57	
329.37/291.57	They will be analysed ascendingly in the following order:
329.37/291.57	sieve < active
329.37/291.57	s < active
329.37/291.57	nats < active
329.37/291.57	active < top
329.37/291.57	sieve < proper
329.37/291.57	s < proper
329.37/291.57	nats < proper
329.37/291.57	proper < top
329.37/291.57	
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(15) RewriteLemmaProof (LOWER BOUND(ID))
329.37/291.57	Proved the following rewrite lemma:
329.37/291.57	sieve(gen_0':mark:zprimes:ok3_0(+(1, n3572_0))) -> *4_0, rt in Omega(n3572_0)
329.37/291.57	
329.37/291.57	Induction Base:
329.37/291.57	sieve(gen_0':mark:zprimes:ok3_0(+(1, 0)))
329.37/291.57	
329.37/291.57	Induction Step:
329.37/291.57	sieve(gen_0':mark:zprimes:ok3_0(+(1, +(n3572_0, 1)))) ->_R^Omega(1)
329.37/291.57	mark(sieve(gen_0':mark:zprimes:ok3_0(+(1, n3572_0)))) ->_IH
329.37/291.57	mark(*4_0)
329.37/291.57	
329.37/291.57	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(16)
329.37/291.57	Obligation:
329.37/291.57	TRS:
329.37/291.57	Rules:
329.37/291.57	active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.37/291.57	active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.37/291.57	active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.37/291.57	active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.37/291.57	active(nats(N)) -> mark(cons(N, nats(s(N))))
329.37/291.57	active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.37/291.57	active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.37/291.57	active(cons(X1, X2)) -> cons(active(X1), X2)
329.37/291.57	active(s(X)) -> s(active(X))
329.37/291.57	active(sieve(X)) -> sieve(active(X))
329.37/291.57	active(nats(X)) -> nats(active(X))
329.37/291.57	filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.37/291.57	cons(mark(X1), X2) -> mark(cons(X1, X2))
329.37/291.57	s(mark(X)) -> mark(s(X))
329.37/291.57	sieve(mark(X)) -> mark(sieve(X))
329.37/291.57	nats(mark(X)) -> mark(nats(X))
329.37/291.57	proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.37/291.57	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.37/291.57	proper(0') -> ok(0')
329.37/291.57	proper(s(X)) -> s(proper(X))
329.37/291.57	proper(sieve(X)) -> sieve(proper(X))
329.37/291.57	proper(nats(X)) -> nats(proper(X))
329.37/291.57	proper(zprimes) -> ok(zprimes)
329.37/291.57	filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.37/291.57	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.37/291.57	s(ok(X)) -> ok(s(X))
329.37/291.57	sieve(ok(X)) -> ok(sieve(X))
329.37/291.57	nats(ok(X)) -> ok(nats(X))
329.37/291.57	top(mark(X)) -> top(proper(X))
329.37/291.57	top(ok(X)) -> top(active(X))
329.37/291.57	
329.37/291.57	Types:
329.37/291.57	active :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	filter :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	cons :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	0' :: 0':mark:zprimes:ok
329.37/291.57	mark :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	s :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	sieve :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	nats :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	zprimes :: 0':mark:zprimes:ok
329.37/291.57	proper :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	ok :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	top :: 0':mark:zprimes:ok -> top
329.37/291.57	hole_0':mark:zprimes:ok1_0 :: 0':mark:zprimes:ok
329.37/291.57	hole_top2_0 :: top
329.37/291.57	gen_0':mark:zprimes:ok3_0 :: Nat -> 0':mark:zprimes:ok
329.37/291.57	
329.37/291.57	
329.37/291.57	Lemmas:
329.37/291.57	cons(gen_0':mark:zprimes:ok3_0(+(1, n5_0)), gen_0':mark:zprimes:ok3_0(b)) -> *4_0, rt in Omega(n5_0)
329.37/291.57	filter(gen_0':mark:zprimes:ok3_0(+(1, n916_0)), gen_0':mark:zprimes:ok3_0(b), gen_0':mark:zprimes:ok3_0(c)) -> *4_0, rt in Omega(n916_0)
329.37/291.57	sieve(gen_0':mark:zprimes:ok3_0(+(1, n3572_0))) -> *4_0, rt in Omega(n3572_0)
329.37/291.57	
329.37/291.57	
329.37/291.57	Generator Equations:
329.37/291.57	gen_0':mark:zprimes:ok3_0(0) <=> 0'
329.37/291.57	gen_0':mark:zprimes:ok3_0(+(x, 1)) <=> mark(gen_0':mark:zprimes:ok3_0(x))
329.37/291.57	
329.37/291.57	
329.37/291.57	The following defined symbols remain to be analysed:
329.37/291.57	s, active, nats, proper, top
329.37/291.57	
329.37/291.57	They will be analysed ascendingly in the following order:
329.37/291.57	s < active
329.37/291.57	nats < active
329.37/291.57	active < top
329.37/291.57	s < proper
329.37/291.57	nats < proper
329.37/291.57	proper < top
329.37/291.57	
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(17) RewriteLemmaProof (LOWER BOUND(ID))
329.37/291.57	Proved the following rewrite lemma:
329.37/291.57	s(gen_0':mark:zprimes:ok3_0(+(1, n4290_0))) -> *4_0, rt in Omega(n4290_0)
329.37/291.57	
329.37/291.57	Induction Base:
329.37/291.57	s(gen_0':mark:zprimes:ok3_0(+(1, 0)))
329.37/291.57	
329.37/291.57	Induction Step:
329.37/291.57	s(gen_0':mark:zprimes:ok3_0(+(1, +(n4290_0, 1)))) ->_R^Omega(1)
329.37/291.57	mark(s(gen_0':mark:zprimes:ok3_0(+(1, n4290_0)))) ->_IH
329.37/291.57	mark(*4_0)
329.37/291.57	
329.37/291.57	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(18)
329.37/291.57	Obligation:
329.37/291.57	TRS:
329.37/291.57	Rules:
329.37/291.57	active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.37/291.57	active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.37/291.57	active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.37/291.57	active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.37/291.57	active(nats(N)) -> mark(cons(N, nats(s(N))))
329.37/291.57	active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.37/291.57	active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.37/291.57	active(cons(X1, X2)) -> cons(active(X1), X2)
329.37/291.57	active(s(X)) -> s(active(X))
329.37/291.57	active(sieve(X)) -> sieve(active(X))
329.37/291.57	active(nats(X)) -> nats(active(X))
329.37/291.57	filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.37/291.57	cons(mark(X1), X2) -> mark(cons(X1, X2))
329.37/291.57	s(mark(X)) -> mark(s(X))
329.37/291.57	sieve(mark(X)) -> mark(sieve(X))
329.37/291.57	nats(mark(X)) -> mark(nats(X))
329.37/291.57	proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.37/291.57	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.37/291.57	proper(0') -> ok(0')
329.37/291.57	proper(s(X)) -> s(proper(X))
329.37/291.57	proper(sieve(X)) -> sieve(proper(X))
329.37/291.57	proper(nats(X)) -> nats(proper(X))
329.37/291.57	proper(zprimes) -> ok(zprimes)
329.37/291.57	filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.37/291.57	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.37/291.57	s(ok(X)) -> ok(s(X))
329.37/291.57	sieve(ok(X)) -> ok(sieve(X))
329.37/291.57	nats(ok(X)) -> ok(nats(X))
329.37/291.57	top(mark(X)) -> top(proper(X))
329.37/291.57	top(ok(X)) -> top(active(X))
329.37/291.57	
329.37/291.57	Types:
329.37/291.57	active :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	filter :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	cons :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	0' :: 0':mark:zprimes:ok
329.37/291.57	mark :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	s :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	sieve :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	nats :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	zprimes :: 0':mark:zprimes:ok
329.37/291.57	proper :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	ok :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	top :: 0':mark:zprimes:ok -> top
329.37/291.57	hole_0':mark:zprimes:ok1_0 :: 0':mark:zprimes:ok
329.37/291.57	hole_top2_0 :: top
329.37/291.57	gen_0':mark:zprimes:ok3_0 :: Nat -> 0':mark:zprimes:ok
329.37/291.57	
329.37/291.57	
329.37/291.57	Lemmas:
329.37/291.57	cons(gen_0':mark:zprimes:ok3_0(+(1, n5_0)), gen_0':mark:zprimes:ok3_0(b)) -> *4_0, rt in Omega(n5_0)
329.37/291.57	filter(gen_0':mark:zprimes:ok3_0(+(1, n916_0)), gen_0':mark:zprimes:ok3_0(b), gen_0':mark:zprimes:ok3_0(c)) -> *4_0, rt in Omega(n916_0)
329.37/291.57	sieve(gen_0':mark:zprimes:ok3_0(+(1, n3572_0))) -> *4_0, rt in Omega(n3572_0)
329.37/291.57	s(gen_0':mark:zprimes:ok3_0(+(1, n4290_0))) -> *4_0, rt in Omega(n4290_0)
329.37/291.57	
329.37/291.57	
329.37/291.57	Generator Equations:
329.37/291.57	gen_0':mark:zprimes:ok3_0(0) <=> 0'
329.37/291.57	gen_0':mark:zprimes:ok3_0(+(x, 1)) <=> mark(gen_0':mark:zprimes:ok3_0(x))
329.37/291.57	
329.37/291.57	
329.37/291.57	The following defined symbols remain to be analysed:
329.37/291.57	nats, active, proper, top
329.37/291.57	
329.37/291.57	They will be analysed ascendingly in the following order:
329.37/291.57	nats < active
329.37/291.57	active < top
329.37/291.57	nats < proper
329.37/291.57	proper < top
329.37/291.57	
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(19) RewriteLemmaProof (LOWER BOUND(ID))
329.37/291.57	Proved the following rewrite lemma:
329.37/291.57	nats(gen_0':mark:zprimes:ok3_0(+(1, n5109_0))) -> *4_0, rt in Omega(n5109_0)
329.37/291.57	
329.37/291.57	Induction Base:
329.37/291.57	nats(gen_0':mark:zprimes:ok3_0(+(1, 0)))
329.37/291.57	
329.37/291.57	Induction Step:
329.37/291.57	nats(gen_0':mark:zprimes:ok3_0(+(1, +(n5109_0, 1)))) ->_R^Omega(1)
329.37/291.57	mark(nats(gen_0':mark:zprimes:ok3_0(+(1, n5109_0)))) ->_IH
329.37/291.57	mark(*4_0)
329.37/291.57	
329.37/291.57	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
329.37/291.57	----------------------------------------
329.37/291.57	
329.37/291.57	(20)
329.37/291.57	Obligation:
329.37/291.57	TRS:
329.37/291.57	Rules:
329.37/291.57	active(filter(cons(X, Y), 0', M)) -> mark(cons(0', filter(Y, M, M)))
329.37/291.57	active(filter(cons(X, Y), s(N), M)) -> mark(cons(X, filter(Y, N, M)))
329.37/291.57	active(sieve(cons(0', Y))) -> mark(cons(0', sieve(Y)))
329.37/291.57	active(sieve(cons(s(N), Y))) -> mark(cons(s(N), sieve(filter(Y, N, N))))
329.37/291.57	active(nats(N)) -> mark(cons(N, nats(s(N))))
329.37/291.57	active(zprimes) -> mark(sieve(nats(s(s(0')))))
329.37/291.57	active(filter(X1, X2, X3)) -> filter(active(X1), X2, X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, active(X2), X3)
329.37/291.57	active(filter(X1, X2, X3)) -> filter(X1, X2, active(X3))
329.37/291.57	active(cons(X1, X2)) -> cons(active(X1), X2)
329.37/291.57	active(s(X)) -> s(active(X))
329.37/291.57	active(sieve(X)) -> sieve(active(X))
329.37/291.57	active(nats(X)) -> nats(active(X))
329.37/291.57	filter(mark(X1), X2, X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, mark(X2), X3) -> mark(filter(X1, X2, X3))
329.37/291.57	filter(X1, X2, mark(X3)) -> mark(filter(X1, X2, X3))
329.37/291.57	cons(mark(X1), X2) -> mark(cons(X1, X2))
329.37/291.57	s(mark(X)) -> mark(s(X))
329.37/291.57	sieve(mark(X)) -> mark(sieve(X))
329.37/291.57	nats(mark(X)) -> mark(nats(X))
329.37/291.57	proper(filter(X1, X2, X3)) -> filter(proper(X1), proper(X2), proper(X3))
329.37/291.57	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
329.37/291.57	proper(0') -> ok(0')
329.37/291.57	proper(s(X)) -> s(proper(X))
329.37/291.57	proper(sieve(X)) -> sieve(proper(X))
329.37/291.57	proper(nats(X)) -> nats(proper(X))
329.37/291.57	proper(zprimes) -> ok(zprimes)
329.37/291.57	filter(ok(X1), ok(X2), ok(X3)) -> ok(filter(X1, X2, X3))
329.37/291.57	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
329.37/291.57	s(ok(X)) -> ok(s(X))
329.37/291.57	sieve(ok(X)) -> ok(sieve(X))
329.37/291.57	nats(ok(X)) -> ok(nats(X))
329.37/291.57	top(mark(X)) -> top(proper(X))
329.37/291.57	top(ok(X)) -> top(active(X))
329.37/291.57	
329.37/291.57	Types:
329.37/291.57	active :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	filter :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	cons :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	0' :: 0':mark:zprimes:ok
329.37/291.57	mark :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	s :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	sieve :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	nats :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	zprimes :: 0':mark:zprimes:ok
329.37/291.57	proper :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	ok :: 0':mark:zprimes:ok -> 0':mark:zprimes:ok
329.37/291.57	top :: 0':mark:zprimes:ok -> top
329.37/291.57	hole_0':mark:zprimes:ok1_0 :: 0':mark:zprimes:ok
329.37/291.57	hole_top2_0 :: top
329.37/291.57	gen_0':mark:zprimes:ok3_0 :: Nat -> 0':mark:zprimes:ok
329.37/291.57	
329.37/291.57	
329.37/291.57	Lemmas:
329.37/291.57	cons(gen_0':mark:zprimes:ok3_0(+(1, n5_0)), gen_0':mark:zprimes:ok3_0(b)) -> *4_0, rt in Omega(n5_0)
329.37/291.57	filter(gen_0':mark:zprimes:ok3_0(+(1, n916_0)), gen_0':mark:zprimes:ok3_0(b), gen_0':mark:zprimes:ok3_0(c)) -> *4_0, rt in Omega(n916_0)
329.37/291.57	sieve(gen_0':mark:zprimes:ok3_0(+(1, n3572_0))) -> *4_0, rt in Omega(n3572_0)
329.37/291.57	s(gen_0':mark:zprimes:ok3_0(+(1, n4290_0))) -> *4_0, rt in Omega(n4290_0)
329.37/291.57	nats(gen_0':mark:zprimes:ok3_0(+(1, n5109_0))) -> *4_0, rt in Omega(n5109_0)
329.37/291.57	
329.37/291.57	
329.37/291.57	Generator Equations:
329.37/291.57	gen_0':mark:zprimes:ok3_0(0) <=> 0'
329.37/291.57	gen_0':mark:zprimes:ok3_0(+(x, 1)) <=> mark(gen_0':mark:zprimes:ok3_0(x))
329.37/291.57	
329.37/291.57	
329.37/291.57	The following defined symbols remain to be analysed:
329.37/291.57	active, proper, top
329.37/291.57	
329.37/291.57	They will be analysed ascendingly in the following order:
329.37/291.57	active < top
329.37/291.57	proper < top
329.37/291.62	EOF