31.89/10.29	WORST_CASE(Omega(n^1), O(n^1))
31.89/10.31	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
31.89/10.31	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
31.89/10.31	
31.89/10.31	
31.89/10.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
31.89/10.31	
31.89/10.31	(0) CpxTRS
31.89/10.31	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
31.89/10.31	(2) CpxTRS
31.89/10.31	    (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
31.89/10.31	    (4) CpxTRS
31.89/10.31	    (5) CpxTrsMatchBoundsTAProof [FINISHED, 155 ms]
31.89/10.31	    (6) BOUNDS(1, n^1)
31.89/10.31	(7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
31.89/10.31	(8) CpxTRS
31.89/10.31	    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
31.89/10.31	    (10) typed CpxTrs
31.89/10.31	    (11) OrderProof [LOWER BOUND(ID), 0 ms]
31.89/10.31	    (12) typed CpxTrs
31.89/10.31	    (13) RewriteLemmaProof [LOWER BOUND(ID), 456 ms]
31.89/10.31	    (14) BEST
31.89/10.31	        (15) proven lower bound
31.89/10.31	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
31.89/10.31	            (17) BOUNDS(n^1, INF)
31.89/10.31	        (18) typed CpxTrs
31.89/10.31	            (19) RewriteLemmaProof [LOWER BOUND(ID), 149 ms]
31.89/10.31	            (20) typed CpxTrs
31.89/10.31	            (21) RewriteLemmaProof [LOWER BOUND(ID), 148 ms]
31.89/10.31	            (22) typed CpxTrs
31.89/10.31	            (23) RewriteLemmaProof [LOWER BOUND(ID), 111 ms]
31.89/10.31	            (24) typed CpxTrs
31.89/10.31	            (25) RewriteLemmaProof [LOWER BOUND(ID), 101 ms]
31.89/10.31	            (26) typed CpxTrs
31.89/10.31	            (27) RewriteLemmaProof [LOWER BOUND(ID), 144 ms]
31.89/10.31	            (28) typed CpxTrs
31.89/10.31	            (29) RewriteLemmaProof [LOWER BOUND(ID), 80 ms]
31.89/10.31	            (30) typed CpxTrs
31.89/10.31	            (31) RewriteLemmaProof [LOWER BOUND(ID), 139 ms]
31.89/10.31	            (32) typed CpxTrs
31.89/10.31	
31.89/10.31	
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(0)
31.89/10.31	Obligation:
31.89/10.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
31.89/10.31	
31.89/10.31	
31.89/10.31	The TRS R consists of the following rules:
31.89/10.31	
31.89/10.31	   active(U11(tt, N)) -> mark(N)
31.89/10.31	   active(U21(tt, M, N)) -> mark(s(plus(N, M)))
31.89/10.31	   active(U31(tt)) -> mark(0)
31.89/10.31	   active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
31.89/10.31	   active(and(tt, X)) -> mark(X)
31.89/10.31	   active(isNat(0)) -> mark(tt)
31.89/10.31	   active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
31.89/10.31	   active(isNat(s(V1))) -> mark(isNat(V1))
31.89/10.31	   active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
31.89/10.31	   active(plus(N, 0)) -> mark(U11(isNat(N), N))
31.89/10.31	   active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
31.89/10.31	   active(x(N, 0)) -> mark(U31(isNat(N)))
31.89/10.31	   active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
31.89/10.31	   active(U11(X1, X2)) -> U11(active(X1), X2)
31.89/10.31	   active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
31.89/10.31	   active(s(X)) -> s(active(X))
31.89/10.31	   active(plus(X1, X2)) -> plus(active(X1), X2)
31.89/10.31	   active(plus(X1, X2)) -> plus(X1, active(X2))
31.89/10.31	   active(U31(X)) -> U31(active(X))
31.89/10.31	   active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
31.89/10.31	   active(x(X1, X2)) -> x(active(X1), X2)
31.89/10.31	   active(x(X1, X2)) -> x(X1, active(X2))
31.89/10.31	   active(and(X1, X2)) -> and(active(X1), X2)
31.89/10.31	   U11(mark(X1), X2) -> mark(U11(X1, X2))
31.89/10.31	   U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
31.89/10.31	   s(mark(X)) -> mark(s(X))
31.89/10.31	   plus(mark(X1), X2) -> mark(plus(X1, X2))
31.89/10.31	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
31.89/10.31	   U31(mark(X)) -> mark(U31(X))
31.89/10.31	   U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
31.89/10.31	   x(mark(X1), X2) -> mark(x(X1, X2))
31.89/10.31	   x(X1, mark(X2)) -> mark(x(X1, X2))
31.89/10.31	   and(mark(X1), X2) -> mark(and(X1, X2))
31.89/10.31	   proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
31.89/10.31	   proper(tt) -> ok(tt)
31.89/10.31	   proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
31.89/10.31	   proper(s(X)) -> s(proper(X))
31.89/10.31	   proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
31.89/10.31	   proper(U31(X)) -> U31(proper(X))
31.89/10.31	   proper(0) -> ok(0)
31.89/10.31	   proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
31.89/10.31	   proper(x(X1, X2)) -> x(proper(X1), proper(X2))
31.89/10.31	   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
31.89/10.31	   proper(isNat(X)) -> isNat(proper(X))
31.89/10.31	   U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
31.89/10.31	   U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
31.89/10.31	   s(ok(X)) -> ok(s(X))
31.89/10.31	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
31.89/10.31	   U31(ok(X)) -> ok(U31(X))
31.89/10.31	   U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
31.89/10.31	   x(ok(X1), ok(X2)) -> ok(x(X1, X2))
31.89/10.31	   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
31.89/10.31	   isNat(ok(X)) -> ok(isNat(X))
31.89/10.31	   top(mark(X)) -> top(proper(X))
31.89/10.31	   top(ok(X)) -> top(active(X))
31.89/10.31	
31.89/10.31	S is empty.
31.89/10.31	Rewrite Strategy: FULL
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
31.89/10.31	The following defined symbols can occur below the 0th argument of top: proper, active
31.89/10.31	The following defined symbols can occur below the 0th argument of proper: proper, active
31.89/10.31	The following defined symbols can occur below the 0th argument of active: proper, active
31.89/10.31	
31.89/10.31	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
31.89/10.31	active(U11(tt, N)) -> mark(N)
31.89/10.31	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
31.89/10.31	active(U31(tt)) -> mark(0)
31.89/10.31	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
31.89/10.31	active(and(tt, X)) -> mark(X)
31.89/10.31	active(isNat(0)) -> mark(tt)
31.89/10.31	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
31.89/10.31	active(isNat(s(V1))) -> mark(isNat(V1))
31.89/10.31	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
31.89/10.31	active(plus(N, 0)) -> mark(U11(isNat(N), N))
31.89/10.31	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
31.89/10.31	active(x(N, 0)) -> mark(U31(isNat(N)))
31.89/10.31	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
31.89/10.31	active(U11(X1, X2)) -> U11(active(X1), X2)
31.89/10.31	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
31.89/10.31	active(s(X)) -> s(active(X))
31.89/10.31	active(plus(X1, X2)) -> plus(active(X1), X2)
31.89/10.31	active(plus(X1, X2)) -> plus(X1, active(X2))
31.89/10.31	active(U31(X)) -> U31(active(X))
31.89/10.31	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
31.89/10.31	active(x(X1, X2)) -> x(active(X1), X2)
31.89/10.31	active(x(X1, X2)) -> x(X1, active(X2))
31.89/10.31	active(and(X1, X2)) -> and(active(X1), X2)
31.89/10.31	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
31.89/10.31	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
31.89/10.31	proper(s(X)) -> s(proper(X))
31.89/10.31	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
31.89/10.31	proper(U31(X)) -> U31(proper(X))
31.89/10.31	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
31.89/10.31	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
31.89/10.31	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
31.89/10.31	proper(isNat(X)) -> isNat(proper(X))
31.89/10.31	
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(2)
31.89/10.31	Obligation:
31.89/10.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
31.89/10.31	
31.89/10.31	
31.89/10.31	The TRS R consists of the following rules:
31.89/10.31	
31.89/10.31	   U11(mark(X1), X2) -> mark(U11(X1, X2))
31.89/10.31	   U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
31.89/10.31	   s(mark(X)) -> mark(s(X))
31.89/10.31	   plus(mark(X1), X2) -> mark(plus(X1, X2))
31.89/10.31	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
31.89/10.31	   U31(mark(X)) -> mark(U31(X))
31.89/10.31	   U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
31.89/10.31	   x(mark(X1), X2) -> mark(x(X1, X2))
31.89/10.31	   x(X1, mark(X2)) -> mark(x(X1, X2))
31.89/10.31	   and(mark(X1), X2) -> mark(and(X1, X2))
31.89/10.31	   proper(tt) -> ok(tt)
31.89/10.31	   proper(0) -> ok(0)
31.89/10.31	   U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
31.89/10.31	   U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
31.89/10.31	   s(ok(X)) -> ok(s(X))
31.89/10.31	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
31.89/10.31	   U31(ok(X)) -> ok(U31(X))
31.89/10.31	   U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
31.89/10.31	   x(ok(X1), ok(X2)) -> ok(x(X1, X2))
31.89/10.31	   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
31.89/10.31	   isNat(ok(X)) -> ok(isNat(X))
31.89/10.31	   top(mark(X)) -> top(proper(X))
31.89/10.31	   top(ok(X)) -> top(active(X))
31.89/10.31	
31.89/10.31	S is empty.
31.89/10.31	Rewrite Strategy: FULL
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(3) RelTrsToTrsProof (UPPER BOUND(ID))
31.89/10.31	transformed relative TRS to TRS
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(4)
31.89/10.31	Obligation:
31.89/10.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
31.89/10.31	
31.89/10.31	
31.89/10.31	The TRS R consists of the following rules:
31.89/10.31	
31.89/10.31	   U11(mark(X1), X2) -> mark(U11(X1, X2))
31.89/10.31	   U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
31.89/10.31	   s(mark(X)) -> mark(s(X))
31.89/10.31	   plus(mark(X1), X2) -> mark(plus(X1, X2))
31.89/10.31	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
31.89/10.31	   U31(mark(X)) -> mark(U31(X))
31.89/10.31	   U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
31.89/10.31	   x(mark(X1), X2) -> mark(x(X1, X2))
31.89/10.31	   x(X1, mark(X2)) -> mark(x(X1, X2))
31.89/10.31	   and(mark(X1), X2) -> mark(and(X1, X2))
31.89/10.31	   proper(tt) -> ok(tt)
31.89/10.31	   proper(0) -> ok(0)
31.89/10.31	   U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
31.89/10.31	   U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
31.89/10.31	   s(ok(X)) -> ok(s(X))
31.89/10.31	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
31.89/10.31	   U31(ok(X)) -> ok(U31(X))
31.89/10.31	   U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
31.89/10.31	   x(ok(X1), ok(X2)) -> ok(x(X1, X2))
31.89/10.31	   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
31.89/10.31	   isNat(ok(X)) -> ok(isNat(X))
31.89/10.31	   top(mark(X)) -> top(proper(X))
31.89/10.31	   top(ok(X)) -> top(active(X))
31.89/10.31	
31.89/10.31	S is empty.
31.89/10.31	Rewrite Strategy: FULL
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(5) CpxTrsMatchBoundsTAProof (FINISHED)
31.89/10.31	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. 
31.89/10.31	
31.89/10.31	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
31.89/10.31	final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
31.89/10.31	transitions: 
31.89/10.31	mark0(0) -> 0
31.89/10.31	tt0() -> 0
31.89/10.31	ok0(0) -> 0
31.89/10.31	00() -> 0
31.89/10.31	active0(0) -> 0
31.89/10.31	U110(0, 0) -> 1
31.89/10.31	U210(0, 0, 0) -> 2
31.89/10.31	s0(0) -> 3
31.89/10.31	plus0(0, 0) -> 4
31.89/10.31	U310(0) -> 5
31.89/10.31	U410(0, 0, 0) -> 6
31.89/10.31	x0(0, 0) -> 7
31.89/10.31	and0(0, 0) -> 8
31.89/10.31	proper0(0) -> 9
31.89/10.31	isNat0(0) -> 10
31.89/10.31	top0(0) -> 11
31.89/10.31	U111(0, 0) -> 12
31.89/10.31	mark1(12) -> 1
31.89/10.31	U211(0, 0, 0) -> 13
31.89/10.31	mark1(13) -> 2
31.89/10.31	s1(0) -> 14
31.89/10.31	mark1(14) -> 3
31.89/10.31	plus1(0, 0) -> 15
31.89/10.31	mark1(15) -> 4
31.89/10.31	U311(0) -> 16
31.89/10.31	mark1(16) -> 5
31.89/10.31	U411(0, 0, 0) -> 17
31.89/10.31	mark1(17) -> 6
31.89/10.31	x1(0, 0) -> 18
31.89/10.31	mark1(18) -> 7
31.89/10.31	and1(0, 0) -> 19
31.89/10.31	mark1(19) -> 8
31.89/10.31	tt1() -> 20
31.89/10.31	ok1(20) -> 9
31.89/10.31	01() -> 21
31.89/10.31	ok1(21) -> 9
31.89/10.31	U111(0, 0) -> 22
31.89/10.31	ok1(22) -> 1
31.89/10.31	U211(0, 0, 0) -> 23
31.89/10.31	ok1(23) -> 2
31.89/10.31	s1(0) -> 24
31.89/10.31	ok1(24) -> 3
31.89/10.31	plus1(0, 0) -> 25
31.89/10.31	ok1(25) -> 4
31.89/10.31	U311(0) -> 26
31.89/10.31	ok1(26) -> 5
31.89/10.31	U411(0, 0, 0) -> 27
31.89/10.31	ok1(27) -> 6
31.89/10.31	x1(0, 0) -> 28
31.89/10.31	ok1(28) -> 7
31.89/10.31	and1(0, 0) -> 29
31.89/10.31	ok1(29) -> 8
31.89/10.31	isNat1(0) -> 30
31.89/10.31	ok1(30) -> 10
31.89/10.31	proper1(0) -> 31
31.89/10.31	top1(31) -> 11
31.89/10.31	active1(0) -> 32
31.89/10.31	top1(32) -> 11
31.89/10.31	mark1(12) -> 12
31.89/10.31	mark1(12) -> 22
31.89/10.31	mark1(13) -> 13
31.89/10.31	mark1(13) -> 23
31.89/10.31	mark1(14) -> 14
31.89/10.31	mark1(14) -> 24
31.89/10.31	mark1(15) -> 15
31.89/10.31	mark1(15) -> 25
31.89/10.31	mark1(16) -> 16
31.89/10.31	mark1(16) -> 26
31.89/10.31	mark1(17) -> 17
31.89/10.31	mark1(17) -> 27
31.89/10.31	mark1(18) -> 18
31.89/10.31	mark1(18) -> 28
31.89/10.31	mark1(19) -> 19
31.89/10.31	mark1(19) -> 29
31.89/10.31	ok1(20) -> 31
31.89/10.31	ok1(21) -> 31
31.89/10.31	ok1(22) -> 12
31.89/10.31	ok1(22) -> 22
31.89/10.31	ok1(23) -> 13
31.89/10.31	ok1(23) -> 23
31.89/10.31	ok1(24) -> 14
31.89/10.31	ok1(24) -> 24
31.89/10.31	ok1(25) -> 15
31.89/10.31	ok1(25) -> 25
31.89/10.31	ok1(26) -> 16
31.89/10.31	ok1(26) -> 26
31.89/10.31	ok1(27) -> 17
31.89/10.31	ok1(27) -> 27
31.89/10.31	ok1(28) -> 18
31.89/10.31	ok1(28) -> 28
31.89/10.31	ok1(29) -> 19
31.89/10.31	ok1(29) -> 29
31.89/10.31	ok1(30) -> 30
31.89/10.31	active2(20) -> 33
31.89/10.31	top2(33) -> 11
31.89/10.31	active2(21) -> 33
31.89/10.31	
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(6)
31.89/10.31	BOUNDS(1, n^1)
31.89/10.31	
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(7) RenamingProof (BOTH BOUNDS(ID, ID))
31.89/10.31	Renamed function symbols to avoid clashes with predefined symbol.
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(8)
31.89/10.31	Obligation:
31.89/10.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
31.89/10.31	
31.89/10.31	
31.89/10.31	The TRS R consists of the following rules:
31.89/10.31	
31.89/10.31	   active(U11(tt, N)) -> mark(N)
31.89/10.31	   active(U21(tt, M, N)) -> mark(s(plus(N, M)))
31.89/10.31	   active(U31(tt)) -> mark(0')
31.89/10.31	   active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
31.89/10.31	   active(and(tt, X)) -> mark(X)
31.89/10.31	   active(isNat(0')) -> mark(tt)
31.89/10.31	   active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
31.89/10.31	   active(isNat(s(V1))) -> mark(isNat(V1))
31.89/10.31	   active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
31.89/10.31	   active(plus(N, 0')) -> mark(U11(isNat(N), N))
31.89/10.31	   active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
31.89/10.31	   active(x(N, 0')) -> mark(U31(isNat(N)))
31.89/10.31	   active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
31.89/10.31	   active(U11(X1, X2)) -> U11(active(X1), X2)
31.89/10.31	   active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
31.89/10.31	   active(s(X)) -> s(active(X))
31.89/10.31	   active(plus(X1, X2)) -> plus(active(X1), X2)
31.89/10.31	   active(plus(X1, X2)) -> plus(X1, active(X2))
31.89/10.31	   active(U31(X)) -> U31(active(X))
31.89/10.31	   active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
31.89/10.31	   active(x(X1, X2)) -> x(active(X1), X2)
31.89/10.31	   active(x(X1, X2)) -> x(X1, active(X2))
31.89/10.31	   active(and(X1, X2)) -> and(active(X1), X2)
31.89/10.31	   U11(mark(X1), X2) -> mark(U11(X1, X2))
31.89/10.31	   U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
31.89/10.31	   s(mark(X)) -> mark(s(X))
31.89/10.31	   plus(mark(X1), X2) -> mark(plus(X1, X2))
31.89/10.31	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
31.89/10.31	   U31(mark(X)) -> mark(U31(X))
31.89/10.31	   U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
31.89/10.31	   x(mark(X1), X2) -> mark(x(X1, X2))
31.89/10.31	   x(X1, mark(X2)) -> mark(x(X1, X2))
31.89/10.31	   and(mark(X1), X2) -> mark(and(X1, X2))
31.89/10.31	   proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
31.89/10.31	   proper(tt) -> ok(tt)
31.89/10.31	   proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
31.89/10.31	   proper(s(X)) -> s(proper(X))
31.89/10.31	   proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
31.89/10.31	   proper(U31(X)) -> U31(proper(X))
31.89/10.31	   proper(0') -> ok(0')
31.89/10.31	   proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
31.89/10.31	   proper(x(X1, X2)) -> x(proper(X1), proper(X2))
31.89/10.31	   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
31.89/10.31	   proper(isNat(X)) -> isNat(proper(X))
31.89/10.31	   U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
31.89/10.31	   U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
31.89/10.31	   s(ok(X)) -> ok(s(X))
31.89/10.31	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
31.89/10.31	   U31(ok(X)) -> ok(U31(X))
31.89/10.31	   U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
31.89/10.31	   x(ok(X1), ok(X2)) -> ok(x(X1, X2))
31.89/10.31	   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
31.89/10.31	   isNat(ok(X)) -> ok(isNat(X))
31.89/10.31	   top(mark(X)) -> top(proper(X))
31.89/10.31	   top(ok(X)) -> top(active(X))
31.89/10.31	
31.89/10.31	S is empty.
31.89/10.31	Rewrite Strategy: FULL
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
31.89/10.31	Infered types.
31.89/10.31	----------------------------------------
31.89/10.31	
31.89/10.31	(10)
31.89/10.31	Obligation:
31.89/10.31	TRS:
31.89/10.31	Rules:
31.89/10.31	active(U11(tt, N)) -> mark(N)
31.89/10.31	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
31.89/10.31	active(U31(tt)) -> mark(0')
31.89/10.31	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
31.89/10.31	active(and(tt, X)) -> mark(X)
31.89/10.31	active(isNat(0')) -> mark(tt)
31.89/10.31	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
31.89/10.31	active(isNat(s(V1))) -> mark(isNat(V1))
31.89/10.31	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
31.89/10.31	active(plus(N, 0')) -> mark(U11(isNat(N), N))
31.89/10.31	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
31.89/10.31	active(x(N, 0')) -> mark(U31(isNat(N)))
31.89/10.31	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
31.89/10.31	active(U11(X1, X2)) -> U11(active(X1), X2)
31.89/10.31	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
31.89/10.31	active(s(X)) -> s(active(X))
31.89/10.31	active(plus(X1, X2)) -> plus(active(X1), X2)
31.89/10.31	active(plus(X1, X2)) -> plus(X1, active(X2))
31.89/10.31	active(U31(X)) -> U31(active(X))
31.89/10.31	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
31.89/10.31	active(x(X1, X2)) -> x(active(X1), X2)
31.89/10.31	active(x(X1, X2)) -> x(X1, active(X2))
31.89/10.31	active(and(X1, X2)) -> and(active(X1), X2)
31.89/10.31	U11(mark(X1), X2) -> mark(U11(X1, X2))
31.89/10.31	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
31.89/10.31	s(mark(X)) -> mark(s(X))
31.89/10.31	plus(mark(X1), X2) -> mark(plus(X1, X2))
31.89/10.31	plus(X1, mark(X2)) -> mark(plus(X1, X2))
31.89/10.31	U31(mark(X)) -> mark(U31(X))
31.89/10.31	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
31.89/10.31	x(mark(X1), X2) -> mark(x(X1, X2))
31.89/10.31	x(X1, mark(X2)) -> mark(x(X1, X2))
31.89/10.31	and(mark(X1), X2) -> mark(and(X1, X2))
31.89/10.31	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
31.89/10.31	proper(tt) -> ok(tt)
31.89/10.31	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
31.89/10.31	proper(s(X)) -> s(proper(X))
31.89/10.31	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
31.89/10.31	proper(U31(X)) -> U31(proper(X))
31.89/10.31	proper(0') -> ok(0')
31.89/10.31	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
31.89/10.31	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
31.89/10.31	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
31.89/10.31	proper(isNat(X)) -> isNat(proper(X))
31.89/10.31	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
31.89/10.31	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
31.89/10.31	s(ok(X)) -> ok(s(X))
31.89/10.31	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
31.89/10.31	U31(ok(X)) -> ok(U31(X))
31.89/10.31	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
31.89/10.31	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
31.89/10.31	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
31.89/10.31	isNat(ok(X)) -> ok(isNat(X))
31.89/10.31	top(mark(X)) -> top(proper(X))
31.89/10.31	top(ok(X)) -> top(active(X))
31.89/10.31	
31.89/10.31	Types:
31.89/10.31	active :: tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	tt :: tt:mark:0':ok
31.89/10.31	mark :: tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	s :: tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	U31 :: tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	0' :: tt:mark:0':ok
31.89/10.31	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	isNat :: tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	proper :: tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	ok :: tt:mark:0':ok -> tt:mark:0':ok
31.89/10.31	top :: tt:mark:0':ok -> top
31.89/10.31	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
31.89/10.31	hole_top2_0 :: top
31.89/10.31	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
31.89/10.31	
31.89/10.31	----------------------------------------
32.09/10.32	
32.09/10.32	(11) OrderProof (LOWER BOUND(ID))
32.09/10.32	Heuristically decided to analyse the following defined symbols:
32.09/10.32	active, s, plus, x, and, isNat, U11, U21, U31, U41, proper, top
32.09/10.32	
32.09/10.32	They will be analysed ascendingly in the following order:
32.09/10.32	s < active
32.09/10.32	plus < active
32.09/10.32	x < active
32.09/10.32	and < active
32.09/10.32	isNat < active
32.09/10.32	U11 < active
32.09/10.32	U21 < active
32.09/10.32	U31 < active
32.09/10.32	U41 < active
32.09/10.32	active < top
32.09/10.32	s < proper
32.09/10.32	plus < proper
32.09/10.32	x < proper
32.09/10.32	and < proper
32.09/10.32	isNat < proper
32.09/10.32	U11 < proper
32.09/10.32	U21 < proper
32.09/10.32	U31 < proper
32.09/10.32	U41 < proper
32.09/10.32	proper < top
32.09/10.32	
32.09/10.32	----------------------------------------
32.09/10.32	
32.09/10.32	(12)
32.09/10.32	Obligation:
32.09/10.32	TRS:
32.09/10.32	Rules:
32.09/10.32	active(U11(tt, N)) -> mark(N)
32.09/10.32	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.32	active(U31(tt)) -> mark(0')
32.09/10.32	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.32	active(and(tt, X)) -> mark(X)
32.09/10.32	active(isNat(0')) -> mark(tt)
32.09/10.32	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.32	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.32	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.32	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.32	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.32	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.32	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.32	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.32	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.32	active(s(X)) -> s(active(X))
32.09/10.32	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.32	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.32	active(U31(X)) -> U31(active(X))
32.09/10.32	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.32	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.32	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.32	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.32	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.32	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.32	s(mark(X)) -> mark(s(X))
32.09/10.32	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.32	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.32	U31(mark(X)) -> mark(U31(X))
32.09/10.32	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.32	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.32	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.32	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.32	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.32	proper(tt) -> ok(tt)
32.09/10.32	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.32	proper(s(X)) -> s(proper(X))
32.09/10.32	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.32	proper(U31(X)) -> U31(proper(X))
32.09/10.32	proper(0') -> ok(0')
32.09/10.32	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.32	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.32	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.32	proper(isNat(X)) -> isNat(proper(X))
32.09/10.32	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.32	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.32	s(ok(X)) -> ok(s(X))
32.09/10.32	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.32	U31(ok(X)) -> ok(U31(X))
32.09/10.32	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.32	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.32	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.32	isNat(ok(X)) -> ok(isNat(X))
32.09/10.32	top(mark(X)) -> top(proper(X))
32.09/10.32	top(ok(X)) -> top(active(X))
32.09/10.32	
32.09/10.32	Types:
32.09/10.32	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	tt :: tt:mark:0':ok
32.09/10.32	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	0' :: tt:mark:0':ok
32.09/10.32	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.32	top :: tt:mark:0':ok -> top
32.09/10.32	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.32	hole_top2_0 :: top
32.09/10.32	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.32	
32.09/10.32	
32.09/10.32	Generator Equations:
32.09/10.32	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.32	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.32	
32.09/10.32	
32.09/10.32	The following defined symbols remain to be analysed:
32.09/10.32	s, active, plus, x, and, isNat, U11, U21, U31, U41, proper, top
32.09/10.32	
32.09/10.32	They will be analysed ascendingly in the following order:
32.09/10.32	s < active
32.09/10.32	plus < active
32.09/10.32	x < active
32.09/10.32	and < active
32.09/10.32	isNat < active
32.09/10.32	U11 < active
32.09/10.32	U21 < active
32.09/10.32	U31 < active
32.09/10.32	U41 < active
32.09/10.32	active < top
32.09/10.32	s < proper
32.09/10.32	plus < proper
32.09/10.32	x < proper
32.09/10.32	and < proper
32.09/10.32	isNat < proper
32.09/10.32	U11 < proper
32.09/10.32	U21 < proper
32.09/10.32	U31 < proper
32.09/10.32	U41 < proper
32.09/10.32	proper < top
32.09/10.32	
32.09/10.32	----------------------------------------
32.09/10.32	
32.09/10.32	(13) RewriteLemmaProof (LOWER BOUND(ID))
32.09/10.32	Proved the following rewrite lemma:
32.09/10.32	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.32	
32.09/10.32	Induction Base:
32.09/10.32	s(gen_tt:mark:0':ok3_0(+(1, 0)))
32.09/10.32	
32.09/10.32	Induction Step:
32.09/10.32	s(gen_tt:mark:0':ok3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1)
32.09/10.32	mark(s(gen_tt:mark:0':ok3_0(+(1, n5_0)))) ->_IH
32.09/10.32	mark(*4_0)
32.09/10.32	
32.09/10.32	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
32.09/10.32	----------------------------------------
32.09/10.32	
32.09/10.32	(14)
32.09/10.32	Complex Obligation (BEST)
32.09/10.32	
32.09/10.32	----------------------------------------
32.09/10.32	
32.09/10.32	(15)
32.09/10.32	Obligation:
32.09/10.32	Proved the lower bound n^1 for the following obligation:
32.09/10.32	
32.09/10.32	TRS:
32.09/10.32	Rules:
32.09/10.32	active(U11(tt, N)) -> mark(N)
32.09/10.32	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.32	active(U31(tt)) -> mark(0')
32.09/10.32	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.32	active(and(tt, X)) -> mark(X)
32.09/10.32	active(isNat(0')) -> mark(tt)
32.09/10.32	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.32	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.32	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.32	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.32	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.32	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.32	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.32	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.32	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.32	active(s(X)) -> s(active(X))
32.09/10.32	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.32	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.32	active(U31(X)) -> U31(active(X))
32.09/10.32	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.32	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.32	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.32	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.32	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.32	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.32	s(mark(X)) -> mark(s(X))
32.09/10.32	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.32	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.32	U31(mark(X)) -> mark(U31(X))
32.09/10.32	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.32	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.32	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	s, active, plus, x, and, isNat, U11, U21, U31, U41, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	s < active
32.09/10.33	plus < active
32.09/10.33	x < active
32.09/10.33	and < active
32.09/10.33	isNat < active
32.09/10.33	U11 < active
32.09/10.33	U21 < active
32.09/10.33	U31 < active
32.09/10.33	U41 < active
32.09/10.33	active < top
32.09/10.33	s < proper
32.09/10.33	plus < proper
32.09/10.33	x < proper
32.09/10.33	and < proper
32.09/10.33	isNat < proper
32.09/10.33	U11 < proper
32.09/10.33	U21 < proper
32.09/10.33	U31 < proper
32.09/10.33	U41 < proper
32.09/10.33	proper < top
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(16) LowerBoundPropagationProof (FINISHED)
32.09/10.33	Propagated lower bound.
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(17)
32.09/10.33	BOUNDS(n^1, INF)
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(18)
32.09/10.33	Obligation:
32.09/10.33	TRS:
32.09/10.33	Rules:
32.09/10.33	active(U11(tt, N)) -> mark(N)
32.09/10.33	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.33	active(U31(tt)) -> mark(0')
32.09/10.33	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.33	active(and(tt, X)) -> mark(X)
32.09/10.33	active(isNat(0')) -> mark(tt)
32.09/10.33	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.33	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.33	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.33	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.33	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.33	active(s(X)) -> s(active(X))
32.09/10.33	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.33	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.33	active(U31(X)) -> U31(active(X))
32.09/10.33	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.33	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.33	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.33	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.33	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.33	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.33	s(mark(X)) -> mark(s(X))
32.09/10.33	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.33	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.33	U31(mark(X)) -> mark(U31(X))
32.09/10.33	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.33	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.33	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Lemmas:
32.09/10.33	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	plus, active, x, and, isNat, U11, U21, U31, U41, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	plus < active
32.09/10.33	x < active
32.09/10.33	and < active
32.09/10.33	isNat < active
32.09/10.33	U11 < active
32.09/10.33	U21 < active
32.09/10.33	U31 < active
32.09/10.33	U41 < active
32.09/10.33	active < top
32.09/10.33	plus < proper
32.09/10.33	x < proper
32.09/10.33	and < proper
32.09/10.33	isNat < proper
32.09/10.33	U11 < proper
32.09/10.33	U21 < proper
32.09/10.33	U31 < proper
32.09/10.33	U41 < proper
32.09/10.33	proper < top
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(19) RewriteLemmaProof (LOWER BOUND(ID))
32.09/10.33	Proved the following rewrite lemma:
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n437_0)
32.09/10.33	
32.09/10.33	Induction Base:
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, 0)), gen_tt:mark:0':ok3_0(b))
32.09/10.33	
32.09/10.33	Induction Step:
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, +(n437_0, 1))), gen_tt:mark:0':ok3_0(b)) ->_R^Omega(1)
32.09/10.33	mark(plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b))) ->_IH
32.09/10.33	mark(*4_0)
32.09/10.33	
32.09/10.33	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(20)
32.09/10.33	Obligation:
32.09/10.33	TRS:
32.09/10.33	Rules:
32.09/10.33	active(U11(tt, N)) -> mark(N)
32.09/10.33	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.33	active(U31(tt)) -> mark(0')
32.09/10.33	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.33	active(and(tt, X)) -> mark(X)
32.09/10.33	active(isNat(0')) -> mark(tt)
32.09/10.33	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.33	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.33	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.33	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.33	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.33	active(s(X)) -> s(active(X))
32.09/10.33	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.33	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.33	active(U31(X)) -> U31(active(X))
32.09/10.33	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.33	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.33	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.33	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.33	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.33	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.33	s(mark(X)) -> mark(s(X))
32.09/10.33	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.33	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.33	U31(mark(X)) -> mark(U31(X))
32.09/10.33	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.33	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.33	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Lemmas:
32.09/10.33	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n437_0)
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	x, active, and, isNat, U11, U21, U31, U41, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	x < active
32.09/10.33	and < active
32.09/10.33	isNat < active
32.09/10.33	U11 < active
32.09/10.33	U21 < active
32.09/10.33	U31 < active
32.09/10.33	U41 < active
32.09/10.33	active < top
32.09/10.33	x < proper
32.09/10.33	and < proper
32.09/10.33	isNat < proper
32.09/10.33	U11 < proper
32.09/10.33	U21 < proper
32.09/10.33	U31 < proper
32.09/10.33	U41 < proper
32.09/10.33	proper < top
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(21) RewriteLemmaProof (LOWER BOUND(ID))
32.09/10.33	Proved the following rewrite lemma:
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, n2049_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n2049_0)
32.09/10.33	
32.09/10.33	Induction Base:
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, 0)), gen_tt:mark:0':ok3_0(b))
32.09/10.33	
32.09/10.33	Induction Step:
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, +(n2049_0, 1))), gen_tt:mark:0':ok3_0(b)) ->_R^Omega(1)
32.09/10.33	mark(x(gen_tt:mark:0':ok3_0(+(1, n2049_0)), gen_tt:mark:0':ok3_0(b))) ->_IH
32.09/10.33	mark(*4_0)
32.09/10.33	
32.09/10.33	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(22)
32.09/10.33	Obligation:
32.09/10.33	TRS:
32.09/10.33	Rules:
32.09/10.33	active(U11(tt, N)) -> mark(N)
32.09/10.33	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.33	active(U31(tt)) -> mark(0')
32.09/10.33	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.33	active(and(tt, X)) -> mark(X)
32.09/10.33	active(isNat(0')) -> mark(tt)
32.09/10.33	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.33	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.33	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.33	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.33	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.33	active(s(X)) -> s(active(X))
32.09/10.33	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.33	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.33	active(U31(X)) -> U31(active(X))
32.09/10.33	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.33	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.33	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.33	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.33	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.33	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.33	s(mark(X)) -> mark(s(X))
32.09/10.33	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.33	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.33	U31(mark(X)) -> mark(U31(X))
32.09/10.33	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.33	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.33	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Lemmas:
32.09/10.33	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n437_0)
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, n2049_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n2049_0)
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	and, active, isNat, U11, U21, U31, U41, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	and < active
32.09/10.33	isNat < active
32.09/10.33	U11 < active
32.09/10.33	U21 < active
32.09/10.33	U31 < active
32.09/10.33	U41 < active
32.09/10.33	active < top
32.09/10.33	and < proper
32.09/10.33	isNat < proper
32.09/10.33	U11 < proper
32.09/10.33	U21 < proper
32.09/10.33	U31 < proper
32.09/10.33	U41 < proper
32.09/10.33	proper < top
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(23) RewriteLemmaProof (LOWER BOUND(ID))
32.09/10.33	Proved the following rewrite lemma:
32.09/10.33	and(gen_tt:mark:0':ok3_0(+(1, n3967_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n3967_0)
32.09/10.33	
32.09/10.33	Induction Base:
32.09/10.33	and(gen_tt:mark:0':ok3_0(+(1, 0)), gen_tt:mark:0':ok3_0(b))
32.09/10.33	
32.09/10.33	Induction Step:
32.09/10.33	and(gen_tt:mark:0':ok3_0(+(1, +(n3967_0, 1))), gen_tt:mark:0':ok3_0(b)) ->_R^Omega(1)
32.09/10.33	mark(and(gen_tt:mark:0':ok3_0(+(1, n3967_0)), gen_tt:mark:0':ok3_0(b))) ->_IH
32.09/10.33	mark(*4_0)
32.09/10.33	
32.09/10.33	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(24)
32.09/10.33	Obligation:
32.09/10.33	TRS:
32.09/10.33	Rules:
32.09/10.33	active(U11(tt, N)) -> mark(N)
32.09/10.33	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.33	active(U31(tt)) -> mark(0')
32.09/10.33	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.33	active(and(tt, X)) -> mark(X)
32.09/10.33	active(isNat(0')) -> mark(tt)
32.09/10.33	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.33	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.33	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.33	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.33	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.33	active(s(X)) -> s(active(X))
32.09/10.33	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.33	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.33	active(U31(X)) -> U31(active(X))
32.09/10.33	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.33	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.33	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.33	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.33	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.33	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.33	s(mark(X)) -> mark(s(X))
32.09/10.33	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.33	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.33	U31(mark(X)) -> mark(U31(X))
32.09/10.33	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.33	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.33	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Lemmas:
32.09/10.33	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n437_0)
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, n2049_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n2049_0)
32.09/10.33	and(gen_tt:mark:0':ok3_0(+(1, n3967_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n3967_0)
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	isNat, active, U11, U21, U31, U41, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	isNat < active
32.09/10.33	U11 < active
32.09/10.33	U21 < active
32.09/10.33	U31 < active
32.09/10.33	U41 < active
32.09/10.33	active < top
32.09/10.33	isNat < proper
32.09/10.33	U11 < proper
32.09/10.33	U21 < proper
32.09/10.33	U31 < proper
32.09/10.33	U41 < proper
32.09/10.33	proper < top
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(25) RewriteLemmaProof (LOWER BOUND(ID))
32.09/10.33	Proved the following rewrite lemma:
32.09/10.33	U11(gen_tt:mark:0':ok3_0(+(1, n6014_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n6014_0)
32.09/10.33	
32.09/10.33	Induction Base:
32.09/10.33	U11(gen_tt:mark:0':ok3_0(+(1, 0)), gen_tt:mark:0':ok3_0(b))
32.09/10.33	
32.09/10.33	Induction Step:
32.09/10.33	U11(gen_tt:mark:0':ok3_0(+(1, +(n6014_0, 1))), gen_tt:mark:0':ok3_0(b)) ->_R^Omega(1)
32.09/10.33	mark(U11(gen_tt:mark:0':ok3_0(+(1, n6014_0)), gen_tt:mark:0':ok3_0(b))) ->_IH
32.09/10.33	mark(*4_0)
32.09/10.33	
32.09/10.33	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(26)
32.09/10.33	Obligation:
32.09/10.33	TRS:
32.09/10.33	Rules:
32.09/10.33	active(U11(tt, N)) -> mark(N)
32.09/10.33	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.33	active(U31(tt)) -> mark(0')
32.09/10.33	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.33	active(and(tt, X)) -> mark(X)
32.09/10.33	active(isNat(0')) -> mark(tt)
32.09/10.33	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.33	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.33	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.33	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.33	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.33	active(s(X)) -> s(active(X))
32.09/10.33	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.33	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.33	active(U31(X)) -> U31(active(X))
32.09/10.33	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.33	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.33	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.33	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.33	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.33	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.33	s(mark(X)) -> mark(s(X))
32.09/10.33	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.33	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.33	U31(mark(X)) -> mark(U31(X))
32.09/10.33	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.33	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.33	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Lemmas:
32.09/10.33	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n437_0)
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, n2049_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n2049_0)
32.09/10.33	and(gen_tt:mark:0':ok3_0(+(1, n3967_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n3967_0)
32.09/10.33	U11(gen_tt:mark:0':ok3_0(+(1, n6014_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n6014_0)
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	U21, active, U31, U41, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	U21 < active
32.09/10.33	U31 < active
32.09/10.33	U41 < active
32.09/10.33	active < top
32.09/10.33	U21 < proper
32.09/10.33	U31 < proper
32.09/10.33	U41 < proper
32.09/10.33	proper < top
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(27) RewriteLemmaProof (LOWER BOUND(ID))
32.09/10.33	Proved the following rewrite lemma:
32.09/10.33	U21(gen_tt:mark:0':ok3_0(+(1, n8345_0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c)) -> *4_0, rt in Omega(n8345_0)
32.09/10.33	
32.09/10.33	Induction Base:
32.09/10.33	U21(gen_tt:mark:0':ok3_0(+(1, 0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c))
32.09/10.33	
32.09/10.33	Induction Step:
32.09/10.33	U21(gen_tt:mark:0':ok3_0(+(1, +(n8345_0, 1))), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c)) ->_R^Omega(1)
32.09/10.33	mark(U21(gen_tt:mark:0':ok3_0(+(1, n8345_0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c))) ->_IH
32.09/10.33	mark(*4_0)
32.09/10.33	
32.09/10.33	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(28)
32.09/10.33	Obligation:
32.09/10.33	TRS:
32.09/10.33	Rules:
32.09/10.33	active(U11(tt, N)) -> mark(N)
32.09/10.33	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.33	active(U31(tt)) -> mark(0')
32.09/10.33	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.33	active(and(tt, X)) -> mark(X)
32.09/10.33	active(isNat(0')) -> mark(tt)
32.09/10.33	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.33	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.33	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.33	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.33	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.33	active(s(X)) -> s(active(X))
32.09/10.33	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.33	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.33	active(U31(X)) -> U31(active(X))
32.09/10.33	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.33	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.33	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.33	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.33	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.33	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.33	s(mark(X)) -> mark(s(X))
32.09/10.33	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.33	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.33	U31(mark(X)) -> mark(U31(X))
32.09/10.33	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.33	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.33	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Lemmas:
32.09/10.33	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n437_0)
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, n2049_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n2049_0)
32.09/10.33	and(gen_tt:mark:0':ok3_0(+(1, n3967_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n3967_0)
32.09/10.33	U11(gen_tt:mark:0':ok3_0(+(1, n6014_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n6014_0)
32.09/10.33	U21(gen_tt:mark:0':ok3_0(+(1, n8345_0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c)) -> *4_0, rt in Omega(n8345_0)
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	U31, active, U41, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	U31 < active
32.09/10.33	U41 < active
32.09/10.33	active < top
32.09/10.33	U31 < proper
32.09/10.33	U41 < proper
32.09/10.33	proper < top
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(29) RewriteLemmaProof (LOWER BOUND(ID))
32.09/10.33	Proved the following rewrite lemma:
32.09/10.33	U31(gen_tt:mark:0':ok3_0(+(1, n12486_0))) -> *4_0, rt in Omega(n12486_0)
32.09/10.33	
32.09/10.33	Induction Base:
32.09/10.33	U31(gen_tt:mark:0':ok3_0(+(1, 0)))
32.09/10.33	
32.09/10.33	Induction Step:
32.09/10.33	U31(gen_tt:mark:0':ok3_0(+(1, +(n12486_0, 1)))) ->_R^Omega(1)
32.09/10.33	mark(U31(gen_tt:mark:0':ok3_0(+(1, n12486_0)))) ->_IH
32.09/10.33	mark(*4_0)
32.09/10.33	
32.09/10.33	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(30)
32.09/10.33	Obligation:
32.09/10.33	TRS:
32.09/10.33	Rules:
32.09/10.33	active(U11(tt, N)) -> mark(N)
32.09/10.33	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.33	active(U31(tt)) -> mark(0')
32.09/10.33	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.33	active(and(tt, X)) -> mark(X)
32.09/10.33	active(isNat(0')) -> mark(tt)
32.09/10.33	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.33	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.33	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.33	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.33	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.33	active(s(X)) -> s(active(X))
32.09/10.33	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.33	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.33	active(U31(X)) -> U31(active(X))
32.09/10.33	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.33	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.33	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.33	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.33	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.33	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.33	s(mark(X)) -> mark(s(X))
32.09/10.33	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.33	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.33	U31(mark(X)) -> mark(U31(X))
32.09/10.33	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.33	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.33	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Lemmas:
32.09/10.33	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n437_0)
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, n2049_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n2049_0)
32.09/10.33	and(gen_tt:mark:0':ok3_0(+(1, n3967_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n3967_0)
32.09/10.33	U11(gen_tt:mark:0':ok3_0(+(1, n6014_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n6014_0)
32.09/10.33	U21(gen_tt:mark:0':ok3_0(+(1, n8345_0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c)) -> *4_0, rt in Omega(n8345_0)
32.09/10.33	U31(gen_tt:mark:0':ok3_0(+(1, n12486_0))) -> *4_0, rt in Omega(n12486_0)
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	U41, active, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	U41 < active
32.09/10.33	active < top
32.09/10.33	U41 < proper
32.09/10.33	proper < top
32.09/10.33	
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(31) RewriteLemmaProof (LOWER BOUND(ID))
32.09/10.33	Proved the following rewrite lemma:
32.09/10.33	U41(gen_tt:mark:0':ok3_0(+(1, n13818_0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c)) -> *4_0, rt in Omega(n13818_0)
32.09/10.33	
32.09/10.33	Induction Base:
32.09/10.33	U41(gen_tt:mark:0':ok3_0(+(1, 0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c))
32.09/10.33	
32.09/10.33	Induction Step:
32.09/10.33	U41(gen_tt:mark:0':ok3_0(+(1, +(n13818_0, 1))), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c)) ->_R^Omega(1)
32.09/10.33	mark(U41(gen_tt:mark:0':ok3_0(+(1, n13818_0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c))) ->_IH
32.09/10.33	mark(*4_0)
32.09/10.33	
32.09/10.33	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
32.09/10.33	----------------------------------------
32.09/10.33	
32.09/10.33	(32)
32.09/10.33	Obligation:
32.09/10.33	TRS:
32.09/10.33	Rules:
32.09/10.33	active(U11(tt, N)) -> mark(N)
32.09/10.33	active(U21(tt, M, N)) -> mark(s(plus(N, M)))
32.09/10.33	active(U31(tt)) -> mark(0')
32.09/10.33	active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
32.09/10.33	active(and(tt, X)) -> mark(X)
32.09/10.33	active(isNat(0')) -> mark(tt)
32.09/10.33	active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(isNat(s(V1))) -> mark(isNat(V1))
32.09/10.33	active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
32.09/10.33	active(plus(N, 0')) -> mark(U11(isNat(N), N))
32.09/10.33	active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(x(N, 0')) -> mark(U31(isNat(N)))
32.09/10.33	active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
32.09/10.33	active(U11(X1, X2)) -> U11(active(X1), X2)
32.09/10.33	active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
32.09/10.33	active(s(X)) -> s(active(X))
32.09/10.33	active(plus(X1, X2)) -> plus(active(X1), X2)
32.09/10.33	active(plus(X1, X2)) -> plus(X1, active(X2))
32.09/10.33	active(U31(X)) -> U31(active(X))
32.09/10.33	active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
32.09/10.33	active(x(X1, X2)) -> x(active(X1), X2)
32.09/10.33	active(x(X1, X2)) -> x(X1, active(X2))
32.09/10.33	active(and(X1, X2)) -> and(active(X1), X2)
32.09/10.33	U11(mark(X1), X2) -> mark(U11(X1, X2))
32.09/10.33	U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
32.09/10.33	s(mark(X)) -> mark(s(X))
32.09/10.33	plus(mark(X1), X2) -> mark(plus(X1, X2))
32.09/10.33	plus(X1, mark(X2)) -> mark(plus(X1, X2))
32.09/10.33	U31(mark(X)) -> mark(U31(X))
32.09/10.33	U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
32.09/10.33	x(mark(X1), X2) -> mark(x(X1, X2))
32.09/10.33	x(X1, mark(X2)) -> mark(x(X1, X2))
32.09/10.33	and(mark(X1), X2) -> mark(and(X1, X2))
32.09/10.33	proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
32.09/10.33	proper(tt) -> ok(tt)
32.09/10.33	proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(s(X)) -> s(proper(X))
32.09/10.33	proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
32.09/10.33	proper(U31(X)) -> U31(proper(X))
32.09/10.33	proper(0') -> ok(0')
32.09/10.33	proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
32.09/10.33	proper(x(X1, X2)) -> x(proper(X1), proper(X2))
32.09/10.33	proper(and(X1, X2)) -> and(proper(X1), proper(X2))
32.09/10.33	proper(isNat(X)) -> isNat(proper(X))
32.09/10.33	U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
32.09/10.33	U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
32.09/10.33	s(ok(X)) -> ok(s(X))
32.09/10.33	plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
32.09/10.33	U31(ok(X)) -> ok(U31(X))
32.09/10.33	U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
32.09/10.33	x(ok(X1), ok(X2)) -> ok(x(X1, X2))
32.09/10.33	and(ok(X1), ok(X2)) -> ok(and(X1, X2))
32.09/10.33	isNat(ok(X)) -> ok(isNat(X))
32.09/10.33	top(mark(X)) -> top(proper(X))
32.09/10.33	top(ok(X)) -> top(active(X))
32.09/10.33	
32.09/10.33	Types:
32.09/10.33	active :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U11 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	tt :: tt:mark:0':ok
32.09/10.33	mark :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U21 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	s :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	plus :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	U31 :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	0' :: tt:mark:0':ok
32.09/10.33	U41 :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	x :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	and :: tt:mark:0':ok -> tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	isNat :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	proper :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	ok :: tt:mark:0':ok -> tt:mark:0':ok
32.09/10.33	top :: tt:mark:0':ok -> top
32.09/10.33	hole_tt:mark:0':ok1_0 :: tt:mark:0':ok
32.09/10.33	hole_top2_0 :: top
32.09/10.33	gen_tt:mark:0':ok3_0 :: Nat -> tt:mark:0':ok
32.09/10.33	
32.09/10.33	
32.09/10.33	Lemmas:
32.09/10.33	s(gen_tt:mark:0':ok3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
32.09/10.33	plus(gen_tt:mark:0':ok3_0(+(1, n437_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n437_0)
32.09/10.33	x(gen_tt:mark:0':ok3_0(+(1, n2049_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n2049_0)
32.09/10.33	and(gen_tt:mark:0':ok3_0(+(1, n3967_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n3967_0)
32.09/10.33	U11(gen_tt:mark:0':ok3_0(+(1, n6014_0)), gen_tt:mark:0':ok3_0(b)) -> *4_0, rt in Omega(n6014_0)
32.09/10.33	U21(gen_tt:mark:0':ok3_0(+(1, n8345_0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c)) -> *4_0, rt in Omega(n8345_0)
32.09/10.33	U31(gen_tt:mark:0':ok3_0(+(1, n12486_0))) -> *4_0, rt in Omega(n12486_0)
32.09/10.33	U41(gen_tt:mark:0':ok3_0(+(1, n13818_0)), gen_tt:mark:0':ok3_0(b), gen_tt:mark:0':ok3_0(c)) -> *4_0, rt in Omega(n13818_0)
32.09/10.33	
32.09/10.33	
32.09/10.33	Generator Equations:
32.09/10.33	gen_tt:mark:0':ok3_0(0) <=> tt
32.09/10.33	gen_tt:mark:0':ok3_0(+(x, 1)) <=> mark(gen_tt:mark:0':ok3_0(x))
32.09/10.33	
32.09/10.33	
32.09/10.33	The following defined symbols remain to be analysed:
32.09/10.33	active, proper, top
32.09/10.33	
32.09/10.33	They will be analysed ascendingly in the following order:
32.09/10.33	active < top
32.09/10.33	proper < top
32.16/10.37	EOF