42.49/12.43	WORST_CASE(Omega(n^1), O(n^1))
42.49/12.44	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
42.49/12.44	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
42.49/12.44	
42.49/12.44	
42.49/12.44	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
42.49/12.44	
42.49/12.44	(0) CpxTRS
42.49/12.44	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 6 ms]
42.49/12.44	(2) CpxTRS
42.49/12.44	    (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
42.49/12.44	    (4) CpxTRS
42.49/12.44	    (5) CpxTrsMatchBoundsTAProof [FINISHED, 258 ms]
42.49/12.44	    (6) BOUNDS(1, n^1)
42.49/12.44	(7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
42.49/12.44	(8) CpxTRS
42.49/12.44	    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
42.49/12.44	    (10) typed CpxTrs
42.49/12.44	    (11) OrderProof [LOWER BOUND(ID), 0 ms]
42.49/12.44	    (12) typed CpxTrs
42.49/12.44	    (13) RewriteLemmaProof [LOWER BOUND(ID), 469 ms]
42.49/12.44	    (14) BEST
42.49/12.44	        (15) proven lower bound
42.49/12.44	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
42.49/12.44	            (17) BOUNDS(n^1, INF)
42.49/12.44	        (18) typed CpxTrs
42.49/12.44	            (19) RewriteLemmaProof [LOWER BOUND(ID), 128 ms]
42.49/12.44	            (20) typed CpxTrs
42.49/12.44	            (21) RewriteLemmaProof [LOWER BOUND(ID), 104 ms]
42.49/12.44	            (22) typed CpxTrs
42.49/12.44	            (23) RewriteLemmaProof [LOWER BOUND(ID), 90 ms]
42.49/12.44	            (24) typed CpxTrs
42.49/12.44	            (25) RewriteLemmaProof [LOWER BOUND(ID), 66 ms]
42.49/12.44	            (26) typed CpxTrs
42.49/12.44	            (27) RewriteLemmaProof [LOWER BOUND(ID), 104 ms]
42.49/12.44	            (28) typed CpxTrs
42.49/12.44	            (29) RewriteLemmaProof [LOWER BOUND(ID), 103 ms]
42.49/12.44	            (30) typed CpxTrs
42.49/12.44	            (31) RewriteLemmaProof [LOWER BOUND(ID), 136 ms]
42.49/12.44	            (32) typed CpxTrs
42.49/12.44	            (33) RewriteLemmaProof [LOWER BOUND(ID), 70 ms]
42.49/12.44	            (34) typed CpxTrs
42.49/12.44	            (35) RewriteLemmaProof [LOWER BOUND(ID), 111 ms]
42.49/12.44	            (36) typed CpxTrs
42.49/12.44	            (37) RewriteLemmaProof [LOWER BOUND(ID), 82 ms]
42.49/12.44	            (38) typed CpxTrs
42.49/12.44	            (39) RewriteLemmaProof [LOWER BOUND(ID), 59 ms]
42.49/12.44	            (40) typed CpxTrs
42.49/12.44	            (41) RewriteLemmaProof [LOWER BOUND(ID), 116 ms]
42.49/12.44	            (42) typed CpxTrs
42.49/12.44	
42.49/12.44	
42.49/12.44	----------------------------------------
42.49/12.44	
42.49/12.44	(0)
42.49/12.44	Obligation:
42.49/12.44	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
42.49/12.44	
42.49/12.44	
42.49/12.44	The TRS R consists of the following rules:
42.49/12.44	
42.49/12.44	   active(from(X)) -> mark(cons(X, from(s(X))))
42.49/12.44	   active(2ndspos(0, Z)) -> mark(rnil)
42.49/12.44	   active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.49/12.44	   active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.49/12.44	   active(2ndsneg(0, Z)) -> mark(rnil)
42.49/12.44	   active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.49/12.44	   active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.49/12.44	   active(pi(X)) -> mark(2ndspos(X, from(0)))
42.49/12.44	   active(plus(0, Y)) -> mark(Y)
42.49/12.44	   active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.49/12.44	   active(times(0, Y)) -> mark(0)
42.49/12.44	   active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.49/12.44	   active(square(X)) -> mark(times(X, X))
42.49/12.44	   active(s(X)) -> s(active(X))
42.49/12.44	   active(posrecip(X)) -> posrecip(active(X))
42.49/12.44	   active(negrecip(X)) -> negrecip(active(X))
42.49/12.44	   active(cons(X1, X2)) -> cons(active(X1), X2)
42.49/12.44	   active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.49/12.44	   active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.49/12.44	   active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.49/12.44	   active(from(X)) -> from(active(X))
42.49/12.44	   active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.49/12.44	   active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.49/12.44	   active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.49/12.44	   active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.49/12.44	   active(pi(X)) -> pi(active(X))
42.49/12.44	   active(plus(X1, X2)) -> plus(active(X1), X2)
42.49/12.44	   active(plus(X1, X2)) -> plus(X1, active(X2))
42.49/12.44	   active(times(X1, X2)) -> times(active(X1), X2)
42.49/12.44	   active(times(X1, X2)) -> times(X1, active(X2))
42.49/12.44	   active(square(X)) -> square(active(X))
42.49/12.44	   s(mark(X)) -> mark(s(X))
42.49/12.44	   posrecip(mark(X)) -> mark(posrecip(X))
42.49/12.44	   negrecip(mark(X)) -> mark(negrecip(X))
42.49/12.44	   cons(mark(X1), X2) -> mark(cons(X1, X2))
42.49/12.44	   cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.49/12.44	   rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.49/12.44	   rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.49/12.44	   from(mark(X)) -> mark(from(X))
42.49/12.44	   2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.49/12.44	   2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.49/12.44	   2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.49/12.44	   2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.49/12.44	   pi(mark(X)) -> mark(pi(X))
42.49/12.44	   plus(mark(X1), X2) -> mark(plus(X1, X2))
42.49/12.44	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.49/12.44	   times(mark(X1), X2) -> mark(times(X1, X2))
42.49/12.44	   times(X1, mark(X2)) -> mark(times(X1, X2))
42.49/12.44	   square(mark(X)) -> mark(square(X))
42.49/12.44	   proper(0) -> ok(0)
42.49/12.44	   proper(s(X)) -> s(proper(X))
42.49/12.44	   proper(posrecip(X)) -> posrecip(proper(X))
42.49/12.44	   proper(negrecip(X)) -> negrecip(proper(X))
42.49/12.44	   proper(nil) -> ok(nil)
42.49/12.44	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.49/12.44	   proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.49/12.44	   proper(rnil) -> ok(rnil)
42.49/12.44	   proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.49/12.44	   proper(from(X)) -> from(proper(X))
42.49/12.44	   proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.49/12.44	   proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.49/12.44	   proper(pi(X)) -> pi(proper(X))
42.49/12.44	   proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.49/12.44	   proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.49/12.44	   proper(square(X)) -> square(proper(X))
42.49/12.44	   s(ok(X)) -> ok(s(X))
42.49/12.44	   posrecip(ok(X)) -> ok(posrecip(X))
42.49/12.44	   negrecip(ok(X)) -> ok(negrecip(X))
42.49/12.44	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.49/12.44	   cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.49/12.44	   rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.49/12.44	   from(ok(X)) -> ok(from(X))
42.49/12.44	   2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.49/12.44	   2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.49/12.44	   pi(ok(X)) -> ok(pi(X))
42.49/12.44	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.49/12.44	   times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.49/12.44	   square(ok(X)) -> ok(square(X))
42.49/12.44	   top(mark(X)) -> top(proper(X))
42.49/12.44	   top(ok(X)) -> top(active(X))
42.49/12.44	
42.49/12.44	S is empty.
42.49/12.44	Rewrite Strategy: FULL
42.49/12.44	----------------------------------------
42.49/12.44	
42.49/12.44	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
42.49/12.44	The following defined symbols can occur below the 0th argument of top: proper, active
42.49/12.44	The following defined symbols can occur below the 0th argument of proper: proper, active
42.49/12.44	The following defined symbols can occur below the 0th argument of active: proper, active
42.49/12.44	
42.49/12.44	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
42.49/12.44	active(from(X)) -> mark(cons(X, from(s(X))))
42.49/12.44	active(2ndspos(0, Z)) -> mark(rnil)
42.49/12.44	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.49/12.44	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.49/12.44	active(2ndsneg(0, Z)) -> mark(rnil)
42.49/12.44	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.49/12.44	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.49/12.44	active(pi(X)) -> mark(2ndspos(X, from(0)))
42.49/12.44	active(plus(0, Y)) -> mark(Y)
42.49/12.44	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.49/12.44	active(times(0, Y)) -> mark(0)
42.49/12.44	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.49/12.44	active(square(X)) -> mark(times(X, X))
42.49/12.44	active(s(X)) -> s(active(X))
42.49/12.44	active(posrecip(X)) -> posrecip(active(X))
42.49/12.44	active(negrecip(X)) -> negrecip(active(X))
42.49/12.44	active(cons(X1, X2)) -> cons(active(X1), X2)
42.49/12.44	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.49/12.44	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.49/12.44	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.49/12.44	active(from(X)) -> from(active(X))
42.49/12.44	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.49/12.44	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.49/12.44	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.49/12.44	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.49/12.44	active(pi(X)) -> pi(active(X))
42.49/12.44	active(plus(X1, X2)) -> plus(active(X1), X2)
42.49/12.44	active(plus(X1, X2)) -> plus(X1, active(X2))
42.49/12.44	active(times(X1, X2)) -> times(active(X1), X2)
42.49/12.44	active(times(X1, X2)) -> times(X1, active(X2))
42.49/12.44	active(square(X)) -> square(active(X))
42.49/12.44	proper(s(X)) -> s(proper(X))
42.49/12.44	proper(posrecip(X)) -> posrecip(proper(X))
42.49/12.44	proper(negrecip(X)) -> negrecip(proper(X))
42.49/12.44	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.49/12.44	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.49/12.44	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.49/12.44	proper(from(X)) -> from(proper(X))
42.49/12.44	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.49/12.44	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.49/12.44	proper(pi(X)) -> pi(proper(X))
42.71/12.45	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.45	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.45	proper(square(X)) -> square(proper(X))
42.71/12.45	
42.71/12.45	----------------------------------------
42.71/12.45	
42.71/12.45	(2)
42.71/12.45	Obligation:
42.71/12.45	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
42.71/12.45	
42.71/12.45	
42.71/12.45	The TRS R consists of the following rules:
42.71/12.45	
42.71/12.45	   s(mark(X)) -> mark(s(X))
42.71/12.45	   posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.45	   negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.45	   cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.45	   cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.45	   rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.45	   rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.45	   from(mark(X)) -> mark(from(X))
42.71/12.45	   2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.45	   2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.45	   2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.45	   2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.45	   pi(mark(X)) -> mark(pi(X))
42.71/12.45	   plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.45	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.45	   times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.45	   times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.45	   square(mark(X)) -> mark(square(X))
42.71/12.45	   proper(0) -> ok(0)
42.71/12.45	   proper(nil) -> ok(nil)
42.71/12.45	   proper(rnil) -> ok(rnil)
42.71/12.45	   s(ok(X)) -> ok(s(X))
42.71/12.45	   posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.45	   negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.45	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.45	   cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.45	   rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.45	   from(ok(X)) -> ok(from(X))
42.71/12.45	   2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.45	   2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.45	   pi(ok(X)) -> ok(pi(X))
42.71/12.45	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.45	   times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.45	   square(ok(X)) -> ok(square(X))
42.71/12.45	   top(mark(X)) -> top(proper(X))
42.71/12.45	   top(ok(X)) -> top(active(X))
42.71/12.45	
42.71/12.45	S is empty.
42.71/12.45	Rewrite Strategy: FULL
42.71/12.45	----------------------------------------
42.71/12.45	
42.71/12.45	(3) RelTrsToTrsProof (UPPER BOUND(ID))
42.71/12.45	transformed relative TRS to TRS
42.71/12.45	----------------------------------------
42.71/12.45	
42.71/12.45	(4)
42.71/12.45	Obligation:
42.71/12.45	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
42.71/12.45	
42.71/12.45	
42.71/12.45	The TRS R consists of the following rules:
42.71/12.45	
42.71/12.45	   s(mark(X)) -> mark(s(X))
42.71/12.45	   posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.45	   negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.45	   cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.45	   cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.45	   rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.45	   rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.45	   from(mark(X)) -> mark(from(X))
42.71/12.45	   2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.45	   2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.45	   2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.45	   2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.45	   pi(mark(X)) -> mark(pi(X))
42.71/12.45	   plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.45	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.45	   times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.45	   times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.45	   square(mark(X)) -> mark(square(X))
42.71/12.45	   proper(0) -> ok(0)
42.71/12.45	   proper(nil) -> ok(nil)
42.71/12.45	   proper(rnil) -> ok(rnil)
42.71/12.45	   s(ok(X)) -> ok(s(X))
42.71/12.45	   posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.45	   negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.45	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.45	   cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.45	   rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.45	   from(ok(X)) -> ok(from(X))
42.71/12.45	   2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.45	   2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.45	   pi(ok(X)) -> ok(pi(X))
42.71/12.45	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.45	   times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.45	   square(ok(X)) -> ok(square(X))
42.71/12.45	   top(mark(X)) -> top(proper(X))
42.71/12.45	   top(ok(X)) -> top(active(X))
42.71/12.45	
42.71/12.45	S is empty.
42.71/12.45	Rewrite Strategy: FULL
42.71/12.45	----------------------------------------
42.71/12.45	
42.71/12.45	(5) CpxTrsMatchBoundsTAProof (FINISHED)
42.71/12.45	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2. 
42.71/12.45	
42.71/12.45	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
42.71/12.45	final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
42.71/12.45	transitions: 
42.71/12.45	mark0(0) -> 0
42.71/12.45	00() -> 0
42.71/12.45	ok0(0) -> 0
42.71/12.45	nil0() -> 0
42.71/12.45	rnil0() -> 0
42.71/12.45	active0(0) -> 0
42.71/12.45	s0(0) -> 1
42.71/12.45	posrecip0(0) -> 2
42.71/12.45	negrecip0(0) -> 3
42.71/12.45	cons0(0, 0) -> 4
42.71/12.45	cons20(0, 0) -> 5
42.71/12.45	rcons0(0, 0) -> 6
42.71/12.45	from0(0) -> 7
42.71/12.45	2ndspos0(0, 0) -> 8
42.71/12.45	2ndsneg0(0, 0) -> 9
42.71/12.45	pi0(0) -> 10
42.71/12.45	plus0(0, 0) -> 11
42.71/12.45	times0(0, 0) -> 12
42.71/12.45	square0(0) -> 13
42.71/12.45	proper0(0) -> 14
42.71/12.45	top0(0) -> 15
42.71/12.45	s1(0) -> 16
42.71/12.45	mark1(16) -> 1
42.71/12.45	posrecip1(0) -> 17
42.71/12.45	mark1(17) -> 2
42.71/12.45	negrecip1(0) -> 18
42.71/12.45	mark1(18) -> 3
42.71/12.45	cons1(0, 0) -> 19
42.71/12.45	mark1(19) -> 4
42.71/12.45	cons21(0, 0) -> 20
42.71/12.45	mark1(20) -> 5
42.71/12.45	rcons1(0, 0) -> 21
42.71/12.45	mark1(21) -> 6
42.71/12.45	from1(0) -> 22
42.71/12.45	mark1(22) -> 7
42.71/12.45	2ndspos1(0, 0) -> 23
42.71/12.45	mark1(23) -> 8
42.71/12.45	2ndsneg1(0, 0) -> 24
42.71/12.45	mark1(24) -> 9
42.71/12.45	pi1(0) -> 25
42.71/12.45	mark1(25) -> 10
42.71/12.45	plus1(0, 0) -> 26
42.71/12.45	mark1(26) -> 11
42.71/12.45	times1(0, 0) -> 27
42.71/12.45	mark1(27) -> 12
42.71/12.45	square1(0) -> 28
42.71/12.45	mark1(28) -> 13
42.71/12.45	01() -> 29
42.71/12.45	ok1(29) -> 14
42.71/12.45	nil1() -> 30
42.71/12.45	ok1(30) -> 14
42.71/12.45	rnil1() -> 31
42.71/12.45	ok1(31) -> 14
42.71/12.45	s1(0) -> 32
42.71/12.45	ok1(32) -> 1
42.71/12.45	posrecip1(0) -> 33
42.71/12.45	ok1(33) -> 2
42.71/12.45	negrecip1(0) -> 34
42.71/12.45	ok1(34) -> 3
42.71/12.45	cons1(0, 0) -> 35
42.71/12.45	ok1(35) -> 4
42.71/12.45	cons21(0, 0) -> 36
42.71/12.45	ok1(36) -> 5
42.71/12.45	rcons1(0, 0) -> 37
42.71/12.45	ok1(37) -> 6
42.71/12.45	from1(0) -> 38
42.71/12.45	ok1(38) -> 7
42.71/12.45	2ndspos1(0, 0) -> 39
42.71/12.45	ok1(39) -> 8
42.71/12.45	2ndsneg1(0, 0) -> 40
42.71/12.45	ok1(40) -> 9
42.71/12.45	pi1(0) -> 41
42.71/12.45	ok1(41) -> 10
42.71/12.45	plus1(0, 0) -> 42
42.71/12.45	ok1(42) -> 11
42.71/12.45	times1(0, 0) -> 43
42.71/12.45	ok1(43) -> 12
42.71/12.45	square1(0) -> 44
42.71/12.45	ok1(44) -> 13
42.71/12.45	proper1(0) -> 45
42.71/12.45	top1(45) -> 15
42.71/12.45	active1(0) -> 46
42.71/12.45	top1(46) -> 15
42.71/12.45	mark1(16) -> 16
42.71/12.45	mark1(16) -> 32
42.71/12.45	mark1(17) -> 17
42.71/12.45	mark1(17) -> 33
42.71/12.45	mark1(18) -> 18
42.71/12.45	mark1(18) -> 34
42.71/12.45	mark1(19) -> 19
42.71/12.45	mark1(19) -> 35
42.71/12.45	mark1(20) -> 20
42.71/12.45	mark1(20) -> 36
42.71/12.45	mark1(21) -> 21
42.71/12.45	mark1(21) -> 37
42.71/12.45	mark1(22) -> 22
42.71/12.45	mark1(22) -> 38
42.71/12.45	mark1(23) -> 23
42.71/12.45	mark1(23) -> 39
42.71/12.45	mark1(24) -> 24
42.71/12.45	mark1(24) -> 40
42.71/12.45	mark1(25) -> 25
42.71/12.45	mark1(25) -> 41
42.71/12.45	mark1(26) -> 26
42.71/12.45	mark1(26) -> 42
42.71/12.45	mark1(27) -> 27
42.71/12.45	mark1(27) -> 43
42.71/12.45	mark1(28) -> 28
42.71/12.45	mark1(28) -> 44
42.71/12.45	ok1(29) -> 45
42.71/12.45	ok1(30) -> 45
42.71/12.45	ok1(31) -> 45
42.71/12.45	ok1(32) -> 16
42.71/12.45	ok1(32) -> 32
42.71/12.45	ok1(33) -> 17
42.71/12.45	ok1(33) -> 33
42.71/12.45	ok1(34) -> 18
42.71/12.45	ok1(34) -> 34
42.71/12.45	ok1(35) -> 19
42.71/12.45	ok1(35) -> 35
42.71/12.45	ok1(36) -> 20
42.71/12.45	ok1(36) -> 36
42.71/12.45	ok1(37) -> 21
42.71/12.45	ok1(37) -> 37
42.71/12.45	ok1(38) -> 22
42.71/12.45	ok1(38) -> 38
42.71/12.45	ok1(39) -> 23
42.71/12.45	ok1(39) -> 39
42.71/12.45	ok1(40) -> 24
42.71/12.45	ok1(40) -> 40
42.71/12.45	ok1(41) -> 25
42.71/12.45	ok1(41) -> 41
42.71/12.45	ok1(42) -> 26
42.71/12.45	ok1(42) -> 42
42.71/12.45	ok1(43) -> 27
42.71/12.45	ok1(43) -> 43
42.71/12.45	ok1(44) -> 28
42.71/12.45	ok1(44) -> 44
42.71/12.45	active2(29) -> 47
42.71/12.45	top2(47) -> 15
42.71/12.45	active2(30) -> 47
42.71/12.45	active2(31) -> 47
42.71/12.45	
42.71/12.45	----------------------------------------
42.71/12.45	
42.71/12.45	(6)
42.71/12.45	BOUNDS(1, n^1)
42.71/12.45	
42.71/12.45	----------------------------------------
42.71/12.45	
42.71/12.45	(7) RenamingProof (BOTH BOUNDS(ID, ID))
42.71/12.45	Renamed function symbols to avoid clashes with predefined symbol.
42.71/12.45	----------------------------------------
42.71/12.45	
42.71/12.45	(8)
42.71/12.45	Obligation:
42.71/12.45	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
42.71/12.45	
42.71/12.45	
42.71/12.45	The TRS R consists of the following rules:
42.71/12.45	
42.71/12.45	   active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.45	   active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.45	   active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.45	   active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.45	   active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.45	   active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.45	   active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.45	   active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.45	   active(plus(0', Y)) -> mark(Y)
42.71/12.45	   active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.45	   active(times(0', Y)) -> mark(0')
42.71/12.45	   active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.45	   active(square(X)) -> mark(times(X, X))
42.71/12.45	   active(s(X)) -> s(active(X))
42.71/12.45	   active(posrecip(X)) -> posrecip(active(X))
42.71/12.45	   active(negrecip(X)) -> negrecip(active(X))
42.71/12.45	   active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.45	   active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.45	   active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.45	   active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.45	   active(from(X)) -> from(active(X))
42.71/12.45	   active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.45	   active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.45	   active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.45	   active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.45	   active(pi(X)) -> pi(active(X))
42.71/12.45	   active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.45	   active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.45	   active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.45	   active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.45	   active(square(X)) -> square(active(X))
42.71/12.46	   s(mark(X)) -> mark(s(X))
42.71/12.46	   posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.46	   negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.46	   cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.46	   cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.46	   rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.46	   rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.46	   from(mark(X)) -> mark(from(X))
42.71/12.46	   2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.46	   2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.46	   2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.46	   2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.46	   pi(mark(X)) -> mark(pi(X))
42.71/12.46	   plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.46	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.46	   times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.46	   times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.46	   square(mark(X)) -> mark(square(X))
42.71/12.46	   proper(0') -> ok(0')
42.71/12.46	   proper(s(X)) -> s(proper(X))
42.71/12.46	   proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.46	   proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.46	   proper(nil) -> ok(nil)
42.71/12.46	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.46	   proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.46	   proper(rnil) -> ok(rnil)
42.71/12.46	   proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.46	   proper(from(X)) -> from(proper(X))
42.71/12.46	   proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.46	   proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.46	   proper(pi(X)) -> pi(proper(X))
42.71/12.46	   proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.46	   proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.46	   proper(square(X)) -> square(proper(X))
42.71/12.46	   s(ok(X)) -> ok(s(X))
42.71/12.46	   posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.46	   negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.46	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.46	   cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.46	   rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.46	   from(ok(X)) -> ok(from(X))
42.71/12.46	   2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.46	   2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.46	   pi(ok(X)) -> ok(pi(X))
42.71/12.46	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.46	   times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.46	   square(ok(X)) -> ok(square(X))
42.71/12.46	   top(mark(X)) -> top(proper(X))
42.71/12.46	   top(ok(X)) -> top(active(X))
42.71/12.46	
42.71/12.46	S is empty.
42.71/12.46	Rewrite Strategy: FULL
42.71/12.46	----------------------------------------
42.71/12.46	
42.71/12.46	(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
42.71/12.46	Infered types.
42.71/12.46	----------------------------------------
42.71/12.46	
42.71/12.46	(10)
42.71/12.46	Obligation:
42.71/12.46	TRS:
42.71/12.46	Rules:
42.71/12.46	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.46	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.46	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.46	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.46	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.46	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.46	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.46	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.46	active(plus(0', Y)) -> mark(Y)
42.71/12.46	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.46	active(times(0', Y)) -> mark(0')
42.71/12.46	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.46	active(square(X)) -> mark(times(X, X))
42.71/12.46	active(s(X)) -> s(active(X))
42.71/12.46	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(11) OrderProof (LOWER BOUND(ID))
42.71/12.47	Heuristically decided to analyse the following defined symbols:
42.71/12.47	active, cons, from, s, 2ndspos, cons2, rcons, posrecip, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	cons < active
42.71/12.47	from < active
42.71/12.47	s < active
42.71/12.47	2ndspos < active
42.71/12.47	cons2 < active
42.71/12.47	rcons < active
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	cons < proper
42.71/12.47	from < proper
42.71/12.47	s < proper
42.71/12.47	2ndspos < proper
42.71/12.47	cons2 < proper
42.71/12.47	rcons < proper
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(12)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	cons, active, from, s, 2ndspos, cons2, rcons, posrecip, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	cons < active
42.71/12.47	from < active
42.71/12.47	s < active
42.71/12.47	2ndspos < active
42.71/12.47	cons2 < active
42.71/12.47	rcons < active
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	cons < proper
42.71/12.47	from < proper
42.71/12.47	s < proper
42.71/12.47	2ndspos < proper
42.71/12.47	cons2 < proper
42.71/12.47	rcons < proper
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(13) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, 0)), gen_mark:0':rnil:ok:nil3_0(b))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, +(n5_0, 1))), gen_mark:0':rnil:ok:nil3_0(b)) ->_R^Omega(1)
42.71/12.47	mark(cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(14)
42.71/12.47	Complex Obligation (BEST)
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(15)
42.71/12.47	Obligation:
42.71/12.47	Proved the lower bound n^1 for the following obligation:
42.71/12.47	
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	cons, active, from, s, 2ndspos, cons2, rcons, posrecip, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	cons < active
42.71/12.47	from < active
42.71/12.47	s < active
42.71/12.47	2ndspos < active
42.71/12.47	cons2 < active
42.71/12.47	rcons < active
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	cons < proper
42.71/12.47	from < proper
42.71/12.47	s < proper
42.71/12.47	2ndspos < proper
42.71/12.47	cons2 < proper
42.71/12.47	rcons < proper
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(16) LowerBoundPropagationProof (FINISHED)
42.71/12.47	Propagated lower bound.
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(17)
42.71/12.47	BOUNDS(n^1, INF)
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(18)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	from, active, s, 2ndspos, cons2, rcons, posrecip, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	from < active
42.71/12.47	s < active
42.71/12.47	2ndspos < active
42.71/12.47	cons2 < active
42.71/12.47	rcons < active
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	from < proper
42.71/12.47	s < proper
42.71/12.47	2ndspos < proper
42.71/12.47	cons2 < proper
42.71/12.47	rcons < proper
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(19) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, 0)))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, +(n1560_0, 1)))) ->_R^Omega(1)
42.71/12.47	mark(from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0)))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(20)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	s, active, 2ndspos, cons2, rcons, posrecip, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	s < active
42.71/12.47	2ndspos < active
42.71/12.47	cons2 < active
42.71/12.47	rcons < active
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	s < proper
42.71/12.47	2ndspos < proper
42.71/12.47	cons2 < proper
42.71/12.47	rcons < proper
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(21) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, 0)))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, +(n2217_0, 1)))) ->_R^Omega(1)
42.71/12.47	mark(s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0)))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(22)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	2ndspos, active, cons2, rcons, posrecip, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	2ndspos < active
42.71/12.47	cons2 < active
42.71/12.47	rcons < active
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	2ndspos < proper
42.71/12.47	cons2 < proper
42.71/12.47	rcons < proper
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(23) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, 0)), gen_mark:0':rnil:ok:nil3_0(b))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, +(n2975_0, 1))), gen_mark:0':rnil:ok:nil3_0(b)) ->_R^Omega(1)
42.71/12.47	mark(2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(24)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	cons2, active, rcons, posrecip, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	cons2 < active
42.71/12.47	rcons < active
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	cons2 < proper
42.71/12.47	rcons < proper
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(25) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, 0)))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, +(n5451_0, 1)))) ->_R^Omega(1)
42.71/12.47	mark(cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0)))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(26)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.47	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	rcons, active, posrecip, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	rcons < active
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	rcons < proper
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(27) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, 0)), gen_mark:0':rnil:ok:nil3_0(b))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, +(n8034_0, 1))), gen_mark:0':rnil:ok:nil3_0(b)) ->_R^Omega(1)
42.71/12.47	mark(rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(28)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.47	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.71/12.47	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	posrecip, active, 2ndsneg, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	posrecip < active
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	posrecip < proper
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(29) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0))) -> *4_0, rt in Omega(n11122_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, 0)))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, +(n11122_0, 1)))) ->_R^Omega(1)
42.71/12.47	mark(posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0)))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(30)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.47	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.71/12.47	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.71/12.47	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0))) -> *4_0, rt in Omega(n11122_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	2ndsneg, active, negrecip, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	2ndsneg < active
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	2ndsneg < proper
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(31) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, n12431_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n12431_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, 0)), gen_mark:0':rnil:ok:nil3_0(b))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, +(n12431_0, 1))), gen_mark:0':rnil:ok:nil3_0(b)) ->_R^Omega(1)
42.71/12.47	mark(2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, n12431_0)), gen_mark:0':rnil:ok:nil3_0(b))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(32)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.47	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.71/12.47	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.71/12.47	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0))) -> *4_0, rt in Omega(n11122_0)
42.71/12.47	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, n12431_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n12431_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	negrecip, active, plus, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	negrecip < active
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	negrecip < proper
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(33) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n16033_0))) -> *4_0, rt in Omega(n16033_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, 0)))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, +(n16033_0, 1)))) ->_R^Omega(1)
42.71/12.47	mark(negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n16033_0)))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(34)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.47	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.47	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.47	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.47	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.47	active(plus(0', Y)) -> mark(Y)
42.71/12.47	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.47	active(times(0', Y)) -> mark(0')
42.71/12.47	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.47	active(square(X)) -> mark(times(X, X))
42.71/12.47	active(s(X)) -> s(active(X))
42.71/12.47	active(posrecip(X)) -> posrecip(active(X))
42.71/12.47	active(negrecip(X)) -> negrecip(active(X))
42.71/12.47	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.47	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.47	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.47	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.47	active(from(X)) -> from(active(X))
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.47	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.47	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.47	active(pi(X)) -> pi(active(X))
42.71/12.47	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.47	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.47	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.47	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.47	active(square(X)) -> square(active(X))
42.71/12.47	s(mark(X)) -> mark(s(X))
42.71/12.47	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.47	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.47	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.47	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.47	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.47	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.47	from(mark(X)) -> mark(from(X))
42.71/12.47	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.47	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.47	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.47	pi(mark(X)) -> mark(pi(X))
42.71/12.47	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.47	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.47	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.47	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.47	square(mark(X)) -> mark(square(X))
42.71/12.47	proper(0') -> ok(0')
42.71/12.47	proper(s(X)) -> s(proper(X))
42.71/12.47	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.47	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.47	proper(nil) -> ok(nil)
42.71/12.47	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.47	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.47	proper(rnil) -> ok(rnil)
42.71/12.47	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.47	proper(from(X)) -> from(proper(X))
42.71/12.47	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.47	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.47	proper(pi(X)) -> pi(proper(X))
42.71/12.47	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.47	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.47	proper(square(X)) -> square(proper(X))
42.71/12.47	s(ok(X)) -> ok(s(X))
42.71/12.47	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.47	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.47	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.47	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.47	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.47	from(ok(X)) -> ok(from(X))
42.71/12.47	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.47	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.47	pi(ok(X)) -> ok(pi(X))
42.71/12.47	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.47	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.47	square(ok(X)) -> ok(square(X))
42.71/12.47	top(mark(X)) -> top(proper(X))
42.71/12.47	top(ok(X)) -> top(active(X))
42.71/12.47	
42.71/12.47	Types:
42.71/12.47	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	0' :: mark:0':rnil:ok:nil
42.71/12.47	rnil :: mark:0':rnil:ok:nil
42.71/12.47	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.47	nil :: mark:0':rnil:ok:nil
42.71/12.47	top :: mark:0':rnil:ok:nil -> top
42.71/12.47	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.47	hole_top2_0 :: top
42.71/12.47	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.47	
42.71/12.47	
42.71/12.47	Lemmas:
42.71/12.47	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.47	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.47	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.47	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.47	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.71/12.47	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.71/12.47	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0))) -> *4_0, rt in Omega(n11122_0)
42.71/12.47	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, n12431_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n12431_0)
42.71/12.47	negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n16033_0))) -> *4_0, rt in Omega(n16033_0)
42.71/12.47	
42.71/12.47	
42.71/12.47	Generator Equations:
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.47	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.47	
42.71/12.47	
42.71/12.47	The following defined symbols remain to be analysed:
42.71/12.47	plus, active, times, pi, square, proper, top
42.71/12.47	
42.71/12.47	They will be analysed ascendingly in the following order:
42.71/12.47	plus < active
42.71/12.47	times < active
42.71/12.47	pi < active
42.71/12.47	square < active
42.71/12.47	active < top
42.71/12.47	plus < proper
42.71/12.47	times < proper
42.71/12.47	pi < proper
42.71/12.47	square < proper
42.71/12.47	proper < top
42.71/12.47	
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(35) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.47	Proved the following rewrite lemma:
42.71/12.47	plus(gen_mark:0':rnil:ok:nil3_0(+(1, n17593_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n17593_0)
42.71/12.47	
42.71/12.47	Induction Base:
42.71/12.47	plus(gen_mark:0':rnil:ok:nil3_0(+(1, 0)), gen_mark:0':rnil:ok:nil3_0(b))
42.71/12.47	
42.71/12.47	Induction Step:
42.71/12.47	plus(gen_mark:0':rnil:ok:nil3_0(+(1, +(n17593_0, 1))), gen_mark:0':rnil:ok:nil3_0(b)) ->_R^Omega(1)
42.71/12.47	mark(plus(gen_mark:0':rnil:ok:nil3_0(+(1, n17593_0)), gen_mark:0':rnil:ok:nil3_0(b))) ->_IH
42.71/12.47	mark(*4_0)
42.71/12.47	
42.71/12.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.47	----------------------------------------
42.71/12.47	
42.71/12.47	(36)
42.71/12.47	Obligation:
42.71/12.47	TRS:
42.71/12.47	Rules:
42.71/12.47	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.47	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.47	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.48	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.48	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.48	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.48	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.48	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.48	active(plus(0', Y)) -> mark(Y)
42.71/12.48	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.48	active(times(0', Y)) -> mark(0')
42.71/12.48	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.48	active(square(X)) -> mark(times(X, X))
42.71/12.48	active(s(X)) -> s(active(X))
42.71/12.48	active(posrecip(X)) -> posrecip(active(X))
42.71/12.48	active(negrecip(X)) -> negrecip(active(X))
42.71/12.48	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.48	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.48	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.48	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.48	active(from(X)) -> from(active(X))
42.71/12.48	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.48	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.48	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.48	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.48	active(pi(X)) -> pi(active(X))
42.71/12.48	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.48	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.48	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.48	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.48	active(square(X)) -> square(active(X))
42.71/12.48	s(mark(X)) -> mark(s(X))
42.71/12.48	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.48	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.48	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.48	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.48	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.48	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.48	from(mark(X)) -> mark(from(X))
42.71/12.48	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.48	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.48	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.48	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.48	pi(mark(X)) -> mark(pi(X))
42.71/12.48	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.48	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.48	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.48	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.48	square(mark(X)) -> mark(square(X))
42.71/12.48	proper(0') -> ok(0')
42.71/12.48	proper(s(X)) -> s(proper(X))
42.71/12.48	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.48	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.48	proper(nil) -> ok(nil)
42.71/12.48	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.48	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.48	proper(rnil) -> ok(rnil)
42.71/12.48	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.48	proper(from(X)) -> from(proper(X))
42.71/12.48	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.48	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.48	proper(pi(X)) -> pi(proper(X))
42.71/12.48	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.48	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.48	proper(square(X)) -> square(proper(X))
42.71/12.48	s(ok(X)) -> ok(s(X))
42.71/12.48	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.48	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.48	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.48	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.48	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.48	from(ok(X)) -> ok(from(X))
42.71/12.48	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.48	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.48	pi(ok(X)) -> ok(pi(X))
42.71/12.48	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.48	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.48	square(ok(X)) -> ok(square(X))
42.71/12.48	top(mark(X)) -> top(proper(X))
42.71/12.48	top(ok(X)) -> top(active(X))
42.71/12.48	
42.71/12.48	Types:
42.71/12.48	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	0' :: mark:0':rnil:ok:nil
42.71/12.48	rnil :: mark:0':rnil:ok:nil
42.71/12.48	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	nil :: mark:0':rnil:ok:nil
42.71/12.48	top :: mark:0':rnil:ok:nil -> top
42.71/12.48	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.48	hole_top2_0 :: top
42.71/12.48	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.48	
42.71/12.48	
42.71/12.48	Lemmas:
42.71/12.48	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.48	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.48	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.48	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.48	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.71/12.48	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.71/12.48	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0))) -> *4_0, rt in Omega(n11122_0)
42.71/12.48	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, n12431_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n12431_0)
42.71/12.48	negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n16033_0))) -> *4_0, rt in Omega(n16033_0)
42.71/12.48	plus(gen_mark:0':rnil:ok:nil3_0(+(1, n17593_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n17593_0)
42.71/12.48	
42.71/12.48	
42.71/12.48	Generator Equations:
42.71/12.48	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.48	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.48	
42.71/12.48	
42.71/12.48	The following defined symbols remain to be analysed:
42.71/12.48	times, active, pi, square, proper, top
42.71/12.48	
42.71/12.48	They will be analysed ascendingly in the following order:
42.71/12.48	times < active
42.71/12.48	pi < active
42.71/12.48	square < active
42.71/12.48	active < top
42.71/12.48	times < proper
42.71/12.48	pi < proper
42.71/12.48	square < proper
42.71/12.48	proper < top
42.71/12.48	
42.71/12.48	----------------------------------------
42.71/12.48	
42.71/12.48	(37) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.48	Proved the following rewrite lemma:
42.71/12.48	times(gen_mark:0':rnil:ok:nil3_0(+(1, n21709_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n21709_0)
42.71/12.48	
42.71/12.48	Induction Base:
42.71/12.48	times(gen_mark:0':rnil:ok:nil3_0(+(1, 0)), gen_mark:0':rnil:ok:nil3_0(b))
42.71/12.48	
42.71/12.48	Induction Step:
42.71/12.48	times(gen_mark:0':rnil:ok:nil3_0(+(1, +(n21709_0, 1))), gen_mark:0':rnil:ok:nil3_0(b)) ->_R^Omega(1)
42.71/12.48	mark(times(gen_mark:0':rnil:ok:nil3_0(+(1, n21709_0)), gen_mark:0':rnil:ok:nil3_0(b))) ->_IH
42.71/12.48	mark(*4_0)
42.71/12.48	
42.71/12.48	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.48	----------------------------------------
42.71/12.48	
42.71/12.48	(38)
42.71/12.48	Obligation:
42.71/12.48	TRS:
42.71/12.48	Rules:
42.71/12.48	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.48	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.48	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.48	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.48	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.48	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.48	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.48	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.48	active(plus(0', Y)) -> mark(Y)
42.71/12.48	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.48	active(times(0', Y)) -> mark(0')
42.71/12.48	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.48	active(square(X)) -> mark(times(X, X))
42.71/12.48	active(s(X)) -> s(active(X))
42.71/12.48	active(posrecip(X)) -> posrecip(active(X))
42.71/12.48	active(negrecip(X)) -> negrecip(active(X))
42.71/12.48	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.48	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.48	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.48	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.48	active(from(X)) -> from(active(X))
42.71/12.48	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.48	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.48	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.48	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.48	active(pi(X)) -> pi(active(X))
42.71/12.48	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.48	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.48	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.48	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.48	active(square(X)) -> square(active(X))
42.71/12.48	s(mark(X)) -> mark(s(X))
42.71/12.48	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.48	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.48	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.48	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.48	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.48	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.48	from(mark(X)) -> mark(from(X))
42.71/12.48	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.48	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.48	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.48	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.48	pi(mark(X)) -> mark(pi(X))
42.71/12.48	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.48	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.48	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.48	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.48	square(mark(X)) -> mark(square(X))
42.71/12.48	proper(0') -> ok(0')
42.71/12.48	proper(s(X)) -> s(proper(X))
42.71/12.48	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.48	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.48	proper(nil) -> ok(nil)
42.71/12.48	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.48	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.48	proper(rnil) -> ok(rnil)
42.71/12.48	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.48	proper(from(X)) -> from(proper(X))
42.71/12.48	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.48	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.48	proper(pi(X)) -> pi(proper(X))
42.71/12.48	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.48	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.48	proper(square(X)) -> square(proper(X))
42.71/12.48	s(ok(X)) -> ok(s(X))
42.71/12.48	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.48	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.48	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.48	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.48	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.48	from(ok(X)) -> ok(from(X))
42.71/12.48	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.48	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.48	pi(ok(X)) -> ok(pi(X))
42.71/12.48	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.48	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.48	square(ok(X)) -> ok(square(X))
42.71/12.48	top(mark(X)) -> top(proper(X))
42.71/12.48	top(ok(X)) -> top(active(X))
42.71/12.48	
42.71/12.48	Types:
42.71/12.48	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	0' :: mark:0':rnil:ok:nil
42.71/12.48	rnil :: mark:0':rnil:ok:nil
42.71/12.48	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	nil :: mark:0':rnil:ok:nil
42.71/12.48	top :: mark:0':rnil:ok:nil -> top
42.71/12.48	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.48	hole_top2_0 :: top
42.71/12.48	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.48	
42.71/12.48	
42.71/12.48	Lemmas:
42.71/12.48	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.48	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.48	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.48	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.71/12.48	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.71/12.48	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.71/12.48	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0))) -> *4_0, rt in Omega(n11122_0)
42.71/12.48	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, n12431_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n12431_0)
42.71/12.48	negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n16033_0))) -> *4_0, rt in Omega(n16033_0)
42.71/12.48	plus(gen_mark:0':rnil:ok:nil3_0(+(1, n17593_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n17593_0)
42.71/12.48	times(gen_mark:0':rnil:ok:nil3_0(+(1, n21709_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n21709_0)
42.71/12.48	
42.71/12.48	
42.71/12.48	Generator Equations:
42.71/12.48	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.71/12.48	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.71/12.48	
42.71/12.48	
42.71/12.48	The following defined symbols remain to be analysed:
42.71/12.48	pi, active, square, proper, top
42.71/12.48	
42.71/12.48	They will be analysed ascendingly in the following order:
42.71/12.48	pi < active
42.71/12.48	square < active
42.71/12.48	active < top
42.71/12.48	pi < proper
42.71/12.48	square < proper
42.71/12.48	proper < top
42.71/12.48	
42.71/12.48	----------------------------------------
42.71/12.48	
42.71/12.48	(39) RewriteLemmaProof (LOWER BOUND(ID))
42.71/12.48	Proved the following rewrite lemma:
42.71/12.48	pi(gen_mark:0':rnil:ok:nil3_0(+(1, n26131_0))) -> *4_0, rt in Omega(n26131_0)
42.71/12.48	
42.71/12.48	Induction Base:
42.71/12.48	pi(gen_mark:0':rnil:ok:nil3_0(+(1, 0)))
42.71/12.48	
42.71/12.48	Induction Step:
42.71/12.48	pi(gen_mark:0':rnil:ok:nil3_0(+(1, +(n26131_0, 1)))) ->_R^Omega(1)
42.71/12.48	mark(pi(gen_mark:0':rnil:ok:nil3_0(+(1, n26131_0)))) ->_IH
42.71/12.48	mark(*4_0)
42.71/12.48	
42.71/12.48	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.71/12.48	----------------------------------------
42.71/12.48	
42.71/12.48	(40)
42.71/12.48	Obligation:
42.71/12.48	TRS:
42.71/12.48	Rules:
42.71/12.48	active(from(X)) -> mark(cons(X, from(s(X))))
42.71/12.48	active(2ndspos(0', Z)) -> mark(rnil)
42.71/12.48	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.71/12.48	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.71/12.48	active(2ndsneg(0', Z)) -> mark(rnil)
42.71/12.48	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.71/12.48	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.71/12.48	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.71/12.48	active(plus(0', Y)) -> mark(Y)
42.71/12.48	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.71/12.48	active(times(0', Y)) -> mark(0')
42.71/12.48	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.71/12.48	active(square(X)) -> mark(times(X, X))
42.71/12.48	active(s(X)) -> s(active(X))
42.71/12.48	active(posrecip(X)) -> posrecip(active(X))
42.71/12.48	active(negrecip(X)) -> negrecip(active(X))
42.71/12.48	active(cons(X1, X2)) -> cons(active(X1), X2)
42.71/12.48	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.71/12.48	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.71/12.48	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.71/12.48	active(from(X)) -> from(active(X))
42.71/12.48	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.71/12.48	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.71/12.48	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.71/12.48	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.71/12.48	active(pi(X)) -> pi(active(X))
42.71/12.48	active(plus(X1, X2)) -> plus(active(X1), X2)
42.71/12.48	active(plus(X1, X2)) -> plus(X1, active(X2))
42.71/12.48	active(times(X1, X2)) -> times(active(X1), X2)
42.71/12.48	active(times(X1, X2)) -> times(X1, active(X2))
42.71/12.48	active(square(X)) -> square(active(X))
42.71/12.48	s(mark(X)) -> mark(s(X))
42.71/12.48	posrecip(mark(X)) -> mark(posrecip(X))
42.71/12.48	negrecip(mark(X)) -> mark(negrecip(X))
42.71/12.48	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.71/12.48	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.71/12.48	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.71/12.48	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.71/12.48	from(mark(X)) -> mark(from(X))
42.71/12.48	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.71/12.48	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.71/12.48	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.71/12.48	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.71/12.48	pi(mark(X)) -> mark(pi(X))
42.71/12.48	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.71/12.48	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.71/12.48	times(mark(X1), X2) -> mark(times(X1, X2))
42.71/12.48	times(X1, mark(X2)) -> mark(times(X1, X2))
42.71/12.48	square(mark(X)) -> mark(square(X))
42.71/12.48	proper(0') -> ok(0')
42.71/12.48	proper(s(X)) -> s(proper(X))
42.71/12.48	proper(posrecip(X)) -> posrecip(proper(X))
42.71/12.48	proper(negrecip(X)) -> negrecip(proper(X))
42.71/12.48	proper(nil) -> ok(nil)
42.71/12.48	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.71/12.48	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.71/12.48	proper(rnil) -> ok(rnil)
42.71/12.48	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.71/12.48	proper(from(X)) -> from(proper(X))
42.71/12.48	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.71/12.48	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.71/12.48	proper(pi(X)) -> pi(proper(X))
42.71/12.48	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.71/12.48	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.71/12.48	proper(square(X)) -> square(proper(X))
42.71/12.48	s(ok(X)) -> ok(s(X))
42.71/12.48	posrecip(ok(X)) -> ok(posrecip(X))
42.71/12.48	negrecip(ok(X)) -> ok(negrecip(X))
42.71/12.48	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.71/12.48	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.71/12.48	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.71/12.48	from(ok(X)) -> ok(from(X))
42.71/12.48	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.71/12.48	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.71/12.48	pi(ok(X)) -> ok(pi(X))
42.71/12.48	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.71/12.48	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.71/12.48	square(ok(X)) -> ok(square(X))
42.71/12.48	top(mark(X)) -> top(proper(X))
42.71/12.48	top(ok(X)) -> top(active(X))
42.71/12.48	
42.71/12.48	Types:
42.71/12.48	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	0' :: mark:0':rnil:ok:nil
42.71/12.48	rnil :: mark:0':rnil:ok:nil
42.71/12.48	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.71/12.48	nil :: mark:0':rnil:ok:nil
42.71/12.48	top :: mark:0':rnil:ok:nil -> top
42.71/12.48	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.71/12.48	hole_top2_0 :: top
42.71/12.48	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.71/12.48	
42.71/12.48	
42.71/12.48	Lemmas:
42.71/12.48	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.71/12.48	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.71/12.48	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.71/12.48	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.80/12.48	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.80/12.48	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.80/12.48	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0))) -> *4_0, rt in Omega(n11122_0)
42.80/12.48	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, n12431_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n12431_0)
42.80/12.48	negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n16033_0))) -> *4_0, rt in Omega(n16033_0)
42.80/12.48	plus(gen_mark:0':rnil:ok:nil3_0(+(1, n17593_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n17593_0)
42.80/12.48	times(gen_mark:0':rnil:ok:nil3_0(+(1, n21709_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n21709_0)
42.80/12.48	pi(gen_mark:0':rnil:ok:nil3_0(+(1, n26131_0))) -> *4_0, rt in Omega(n26131_0)
42.80/12.48	
42.80/12.48	
42.80/12.48	Generator Equations:
42.80/12.48	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.80/12.48	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.80/12.48	
42.80/12.48	
42.80/12.48	The following defined symbols remain to be analysed:
42.80/12.48	square, active, proper, top
42.80/12.48	
42.80/12.48	They will be analysed ascendingly in the following order:
42.80/12.48	square < active
42.80/12.48	active < top
42.80/12.48	square < proper
42.80/12.48	proper < top
42.80/12.48	
42.80/12.48	----------------------------------------
42.80/12.48	
42.80/12.48	(41) RewriteLemmaProof (LOWER BOUND(ID))
42.80/12.48	Proved the following rewrite lemma:
42.80/12.48	square(gen_mark:0':rnil:ok:nil3_0(+(1, n28092_0))) -> *4_0, rt in Omega(n28092_0)
42.80/12.48	
42.80/12.48	Induction Base:
42.80/12.48	square(gen_mark:0':rnil:ok:nil3_0(+(1, 0)))
42.80/12.48	
42.80/12.48	Induction Step:
42.80/12.48	square(gen_mark:0':rnil:ok:nil3_0(+(1, +(n28092_0, 1)))) ->_R^Omega(1)
42.80/12.48	mark(square(gen_mark:0':rnil:ok:nil3_0(+(1, n28092_0)))) ->_IH
42.80/12.48	mark(*4_0)
42.80/12.48	
42.80/12.48	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
42.80/12.48	----------------------------------------
42.80/12.48	
42.80/12.48	(42)
42.80/12.48	Obligation:
42.80/12.48	TRS:
42.80/12.48	Rules:
42.80/12.48	active(from(X)) -> mark(cons(X, from(s(X))))
42.80/12.48	active(2ndspos(0', Z)) -> mark(rnil)
42.80/12.48	active(2ndspos(s(N), cons(X, Z))) -> mark(2ndspos(s(N), cons2(X, Z)))
42.80/12.48	active(2ndspos(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
42.80/12.48	active(2ndsneg(0', Z)) -> mark(rnil)
42.80/12.48	active(2ndsneg(s(N), cons(X, Z))) -> mark(2ndsneg(s(N), cons2(X, Z)))
42.80/12.48	active(2ndsneg(s(N), cons2(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
42.80/12.48	active(pi(X)) -> mark(2ndspos(X, from(0')))
42.80/12.48	active(plus(0', Y)) -> mark(Y)
42.80/12.48	active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
42.80/12.48	active(times(0', Y)) -> mark(0')
42.80/12.48	active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
42.80/12.48	active(square(X)) -> mark(times(X, X))
42.80/12.48	active(s(X)) -> s(active(X))
42.80/12.48	active(posrecip(X)) -> posrecip(active(X))
42.80/12.48	active(negrecip(X)) -> negrecip(active(X))
42.80/12.48	active(cons(X1, X2)) -> cons(active(X1), X2)
42.80/12.48	active(cons2(X1, X2)) -> cons2(X1, active(X2))
42.80/12.48	active(rcons(X1, X2)) -> rcons(active(X1), X2)
42.80/12.48	active(rcons(X1, X2)) -> rcons(X1, active(X2))
42.80/12.48	active(from(X)) -> from(active(X))
42.80/12.48	active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
42.80/12.48	active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
42.80/12.48	active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
42.80/12.48	active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
42.80/12.48	active(pi(X)) -> pi(active(X))
42.80/12.48	active(plus(X1, X2)) -> plus(active(X1), X2)
42.80/12.48	active(plus(X1, X2)) -> plus(X1, active(X2))
42.80/12.48	active(times(X1, X2)) -> times(active(X1), X2)
42.80/12.48	active(times(X1, X2)) -> times(X1, active(X2))
42.80/12.48	active(square(X)) -> square(active(X))
42.80/12.48	s(mark(X)) -> mark(s(X))
42.80/12.48	posrecip(mark(X)) -> mark(posrecip(X))
42.80/12.48	negrecip(mark(X)) -> mark(negrecip(X))
42.80/12.48	cons(mark(X1), X2) -> mark(cons(X1, X2))
42.80/12.48	cons2(X1, mark(X2)) -> mark(cons2(X1, X2))
42.80/12.48	rcons(mark(X1), X2) -> mark(rcons(X1, X2))
42.80/12.48	rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
42.80/12.48	from(mark(X)) -> mark(from(X))
42.80/12.48	2ndspos(mark(X1), X2) -> mark(2ndspos(X1, X2))
42.80/12.48	2ndspos(X1, mark(X2)) -> mark(2ndspos(X1, X2))
42.80/12.48	2ndsneg(mark(X1), X2) -> mark(2ndsneg(X1, X2))
42.80/12.48	2ndsneg(X1, mark(X2)) -> mark(2ndsneg(X1, X2))
42.80/12.48	pi(mark(X)) -> mark(pi(X))
42.80/12.48	plus(mark(X1), X2) -> mark(plus(X1, X2))
42.80/12.48	plus(X1, mark(X2)) -> mark(plus(X1, X2))
42.80/12.48	times(mark(X1), X2) -> mark(times(X1, X2))
42.80/12.48	times(X1, mark(X2)) -> mark(times(X1, X2))
42.80/12.48	square(mark(X)) -> mark(square(X))
42.80/12.48	proper(0') -> ok(0')
42.80/12.48	proper(s(X)) -> s(proper(X))
42.80/12.48	proper(posrecip(X)) -> posrecip(proper(X))
42.80/12.48	proper(negrecip(X)) -> negrecip(proper(X))
42.80/12.48	proper(nil) -> ok(nil)
42.80/12.48	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
42.80/12.48	proper(cons2(X1, X2)) -> cons2(proper(X1), proper(X2))
42.80/12.48	proper(rnil) -> ok(rnil)
42.80/12.48	proper(rcons(X1, X2)) -> rcons(proper(X1), proper(X2))
42.80/12.48	proper(from(X)) -> from(proper(X))
42.80/12.48	proper(2ndspos(X1, X2)) -> 2ndspos(proper(X1), proper(X2))
42.80/12.48	proper(2ndsneg(X1, X2)) -> 2ndsneg(proper(X1), proper(X2))
42.80/12.48	proper(pi(X)) -> pi(proper(X))
42.80/12.48	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
42.80/12.48	proper(times(X1, X2)) -> times(proper(X1), proper(X2))
42.80/12.48	proper(square(X)) -> square(proper(X))
42.80/12.48	s(ok(X)) -> ok(s(X))
42.80/12.48	posrecip(ok(X)) -> ok(posrecip(X))
42.80/12.48	negrecip(ok(X)) -> ok(negrecip(X))
42.80/12.48	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
42.80/12.48	cons2(ok(X1), ok(X2)) -> ok(cons2(X1, X2))
42.80/12.48	rcons(ok(X1), ok(X2)) -> ok(rcons(X1, X2))
42.80/12.48	from(ok(X)) -> ok(from(X))
42.80/12.48	2ndspos(ok(X1), ok(X2)) -> ok(2ndspos(X1, X2))
42.80/12.48	2ndsneg(ok(X1), ok(X2)) -> ok(2ndsneg(X1, X2))
42.80/12.48	pi(ok(X)) -> ok(pi(X))
42.80/12.48	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
42.80/12.48	times(ok(X1), ok(X2)) -> ok(times(X1, X2))
42.80/12.48	square(ok(X)) -> ok(square(X))
42.80/12.48	top(mark(X)) -> top(proper(X))
42.80/12.48	top(ok(X)) -> top(active(X))
42.80/12.48	
42.80/12.48	Types:
42.80/12.48	active :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	from :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	mark :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	cons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	s :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	2ndspos :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	0' :: mark:0':rnil:ok:nil
42.80/12.48	rnil :: mark:0':rnil:ok:nil
42.80/12.48	cons2 :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	rcons :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	posrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	2ndsneg :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	negrecip :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	pi :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	plus :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	times :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	square :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	proper :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	ok :: mark:0':rnil:ok:nil -> mark:0':rnil:ok:nil
42.80/12.48	nil :: mark:0':rnil:ok:nil
42.80/12.48	top :: mark:0':rnil:ok:nil -> top
42.80/12.48	hole_mark:0':rnil:ok:nil1_0 :: mark:0':rnil:ok:nil
42.80/12.48	hole_top2_0 :: top
42.80/12.48	gen_mark:0':rnil:ok:nil3_0 :: Nat -> mark:0':rnil:ok:nil
42.80/12.48	
42.80/12.48	
42.80/12.48	Lemmas:
42.80/12.48	cons(gen_mark:0':rnil:ok:nil3_0(+(1, n5_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n5_0)
42.80/12.48	from(gen_mark:0':rnil:ok:nil3_0(+(1, n1560_0))) -> *4_0, rt in Omega(n1560_0)
42.80/12.48	s(gen_mark:0':rnil:ok:nil3_0(+(1, n2217_0))) -> *4_0, rt in Omega(n2217_0)
42.80/12.48	2ndspos(gen_mark:0':rnil:ok:nil3_0(+(1, n2975_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n2975_0)
42.80/12.48	cons2(gen_mark:0':rnil:ok:nil3_0(a), gen_mark:0':rnil:ok:nil3_0(+(1, n5451_0))) -> *4_0, rt in Omega(n5451_0)
42.80/12.48	rcons(gen_mark:0':rnil:ok:nil3_0(+(1, n8034_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n8034_0)
42.80/12.48	posrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n11122_0))) -> *4_0, rt in Omega(n11122_0)
42.80/12.48	2ndsneg(gen_mark:0':rnil:ok:nil3_0(+(1, n12431_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n12431_0)
42.80/12.48	negrecip(gen_mark:0':rnil:ok:nil3_0(+(1, n16033_0))) -> *4_0, rt in Omega(n16033_0)
42.80/12.48	plus(gen_mark:0':rnil:ok:nil3_0(+(1, n17593_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n17593_0)
42.80/12.48	times(gen_mark:0':rnil:ok:nil3_0(+(1, n21709_0)), gen_mark:0':rnil:ok:nil3_0(b)) -> *4_0, rt in Omega(n21709_0)
42.80/12.48	pi(gen_mark:0':rnil:ok:nil3_0(+(1, n26131_0))) -> *4_0, rt in Omega(n26131_0)
42.80/12.48	square(gen_mark:0':rnil:ok:nil3_0(+(1, n28092_0))) -> *4_0, rt in Omega(n28092_0)
42.80/12.48	
42.80/12.48	
42.80/12.48	Generator Equations:
42.80/12.48	gen_mark:0':rnil:ok:nil3_0(0) <=> 0'
42.80/12.48	gen_mark:0':rnil:ok:nil3_0(+(x, 1)) <=> mark(gen_mark:0':rnil:ok:nil3_0(x))
42.80/12.48	
42.80/12.48	
42.80/12.48	The following defined symbols remain to be analysed:
42.80/12.48	active, proper, top
42.80/12.48	
42.80/12.48	They will be analysed ascendingly in the following order:
42.80/12.48	active < top
42.80/12.48	proper < top
42.80/12.52	EOF