44.21/13.27	WORST_CASE(Omega(n^1), O(n^1))
44.21/13.29	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
44.21/13.29	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
44.21/13.29	
44.21/13.29	
44.21/13.29	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
44.21/13.29	
44.21/13.29	(0) CpxTRS
44.21/13.29	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
44.21/13.29	(2) CpxTRS
44.21/13.29	    (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
44.21/13.29	    (4) CpxTRS
44.21/13.29	    (5) CpxTrsMatchBoundsTAProof [FINISHED, 167 ms]
44.21/13.29	    (6) BOUNDS(1, n^1)
44.21/13.29	(7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
44.21/13.29	(8) CpxTRS
44.21/13.29	    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
44.21/13.29	    (10) typed CpxTrs
44.21/13.29	    (11) OrderProof [LOWER BOUND(ID), 0 ms]
44.21/13.29	    (12) typed CpxTrs
44.21/13.29	    (13) RewriteLemmaProof [LOWER BOUND(ID), 558 ms]
44.21/13.29	    (14) BEST
44.21/13.29	        (15) proven lower bound
44.21/13.29	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
44.21/13.29	            (17) BOUNDS(n^1, INF)
44.21/13.29	        (18) typed CpxTrs
44.21/13.29	            (19) RewriteLemmaProof [LOWER BOUND(ID), 148 ms]
44.21/13.29	            (20) typed CpxTrs
44.21/13.29	            (21) RewriteLemmaProof [LOWER BOUND(ID), 99 ms]
44.21/13.29	            (22) typed CpxTrs
44.21/13.29	            (23) RewriteLemmaProof [LOWER BOUND(ID), 103 ms]
44.21/13.29	            (24) typed CpxTrs
44.21/13.29	            (25) RewriteLemmaProof [LOWER BOUND(ID), 83 ms]
44.21/13.29	            (26) typed CpxTrs
44.21/13.29	            (27) RewriteLemmaProof [LOWER BOUND(ID), 37 ms]
44.21/13.29	            (28) typed CpxTrs
44.21/13.29	            (29) RewriteLemmaProof [LOWER BOUND(ID), 75 ms]
44.21/13.29	            (30) typed CpxTrs
44.21/13.29	            (31) RewriteLemmaProof [LOWER BOUND(ID), 58 ms]
44.21/13.29	            (32) typed CpxTrs
44.21/13.29	
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(0)
44.21/13.29	Obligation:
44.21/13.29	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
44.21/13.29	
44.21/13.29	
44.21/13.29	The TRS R consists of the following rules:
44.21/13.29	
44.21/13.29	   active(dbl(0)) -> mark(0)
44.21/13.29	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	   active(dbls(nil)) -> mark(nil)
44.21/13.29	   active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	   active(sel(0, cons(X, Y))) -> mark(X)
44.21/13.29	   active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	   active(indx(nil, X)) -> mark(nil)
44.21/13.29	   active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	   active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	   active(dbl1(0)) -> mark(01)
44.21/13.29	   active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	   active(sel1(0, cons(X, Y))) -> mark(X)
44.21/13.29	   active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	   active(quote(0)) -> mark(01)
44.21/13.29	   active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	   active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	   active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	   active(dbl(X)) -> dbl(active(X))
44.21/13.29	   active(dbls(X)) -> dbls(active(X))
44.21/13.29	   active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	   active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	   active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	   active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	   active(s1(X)) -> s1(active(X))
44.21/13.29	   active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	   active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	   active(quote(X)) -> quote(active(X))
44.21/13.29	   dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	   dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	   sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	   sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	   indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	   dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	   s1(mark(X)) -> mark(s1(X))
44.21/13.29	   sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	   sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	   quote(mark(X)) -> mark(quote(X))
44.21/13.29	   proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	   proper(0) -> ok(0)
44.21/13.29	   proper(s(X)) -> s(proper(X))
44.21/13.29	   proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	   proper(nil) -> ok(nil)
44.21/13.29	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	   proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	   proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	   proper(from(X)) -> from(proper(X))
44.21/13.29	   proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	   proper(01) -> ok(01)
44.21/13.29	   proper(s1(X)) -> s1(proper(X))
44.21/13.29	   proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	   proper(quote(X)) -> quote(proper(X))
44.21/13.29	   dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	   s(ok(X)) -> ok(s(X))
44.21/13.29	   dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	   sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	   indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	   from(ok(X)) -> ok(from(X))
44.21/13.29	   dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	   s1(ok(X)) -> ok(s1(X))
44.21/13.29	   sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	   quote(ok(X)) -> ok(quote(X))
44.21/13.29	   top(mark(X)) -> top(proper(X))
44.21/13.29	   top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	S is empty.
44.21/13.29	Rewrite Strategy: FULL
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
44.21/13.29	The following defined symbols can occur below the 0th argument of top: proper, active
44.21/13.29	The following defined symbols can occur below the 0th argument of proper: proper, active
44.21/13.29	The following defined symbols can occur below the 0th argument of active: proper, active
44.21/13.29	
44.21/13.29	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
44.21/13.29	active(dbl(0)) -> mark(0)
44.21/13.29	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	active(dbls(nil)) -> mark(nil)
44.21/13.29	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	active(sel(0, cons(X, Y))) -> mark(X)
44.21/13.29	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	active(indx(nil, X)) -> mark(nil)
44.21/13.29	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	active(dbl1(0)) -> mark(01)
44.21/13.29	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	active(sel1(0, cons(X, Y))) -> mark(X)
44.21/13.29	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	active(quote(0)) -> mark(01)
44.21/13.29	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	active(dbl(X)) -> dbl(active(X))
44.21/13.29	active(dbls(X)) -> dbls(active(X))
44.21/13.29	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	active(s1(X)) -> s1(active(X))
44.21/13.29	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	active(quote(X)) -> quote(active(X))
44.21/13.29	proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	proper(s(X)) -> s(proper(X))
44.21/13.29	proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	proper(from(X)) -> from(proper(X))
44.21/13.29	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	proper(s1(X)) -> s1(proper(X))
44.21/13.29	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	proper(quote(X)) -> quote(proper(X))
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(2)
44.21/13.29	Obligation:
44.21/13.29	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
44.21/13.29	
44.21/13.29	
44.21/13.29	The TRS R consists of the following rules:
44.21/13.29	
44.21/13.29	   dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	   dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	   sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	   sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	   indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	   dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	   s1(mark(X)) -> mark(s1(X))
44.21/13.29	   sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	   sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	   quote(mark(X)) -> mark(quote(X))
44.21/13.29	   proper(0) -> ok(0)
44.21/13.29	   proper(nil) -> ok(nil)
44.21/13.29	   proper(01) -> ok(01)
44.21/13.29	   dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	   s(ok(X)) -> ok(s(X))
44.21/13.29	   dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	   sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	   indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	   from(ok(X)) -> ok(from(X))
44.21/13.29	   dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	   s1(ok(X)) -> ok(s1(X))
44.21/13.29	   sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	   quote(ok(X)) -> ok(quote(X))
44.21/13.29	   top(mark(X)) -> top(proper(X))
44.21/13.29	   top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	S is empty.
44.21/13.29	Rewrite Strategy: FULL
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(3) RelTrsToTrsProof (UPPER BOUND(ID))
44.21/13.29	transformed relative TRS to TRS
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(4)
44.21/13.29	Obligation:
44.21/13.29	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
44.21/13.29	
44.21/13.29	
44.21/13.29	The TRS R consists of the following rules:
44.21/13.29	
44.21/13.29	   dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	   dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	   sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	   sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	   indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	   dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	   s1(mark(X)) -> mark(s1(X))
44.21/13.29	   sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	   sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	   quote(mark(X)) -> mark(quote(X))
44.21/13.29	   proper(0) -> ok(0)
44.21/13.29	   proper(nil) -> ok(nil)
44.21/13.29	   proper(01) -> ok(01)
44.21/13.29	   dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	   s(ok(X)) -> ok(s(X))
44.21/13.29	   dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	   sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	   indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	   from(ok(X)) -> ok(from(X))
44.21/13.29	   dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	   s1(ok(X)) -> ok(s1(X))
44.21/13.29	   sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	   quote(ok(X)) -> ok(quote(X))
44.21/13.29	   top(mark(X)) -> top(proper(X))
44.21/13.29	   top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	S is empty.
44.21/13.29	Rewrite Strategy: FULL
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(5) CpxTrsMatchBoundsTAProof (FINISHED)
44.21/13.29	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. 
44.21/13.29	
44.21/13.29	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
44.21/13.29	final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
44.21/13.29	transitions: 
44.21/13.29	mark0(0) -> 0
44.21/13.29	00() -> 0
44.21/13.29	ok0(0) -> 0
44.21/13.29	nil0() -> 0
44.21/13.29	010() -> 0
44.21/13.29	active0(0) -> 0
44.21/13.29	dbl0(0) -> 1
44.21/13.29	dbls0(0) -> 2
44.21/13.29	sel0(0, 0) -> 3
44.21/13.29	indx0(0, 0) -> 4
44.21/13.29	dbl10(0) -> 5
44.21/13.29	s10(0) -> 6
44.21/13.29	sel10(0, 0) -> 7
44.21/13.29	quote0(0) -> 8
44.21/13.29	proper0(0) -> 9
44.21/13.29	s0(0) -> 10
44.21/13.29	cons0(0, 0) -> 11
44.21/13.29	from0(0) -> 12
44.21/13.29	top0(0) -> 13
44.21/13.29	dbl1(0) -> 14
44.21/13.29	mark1(14) -> 1
44.21/13.29	dbls1(0) -> 15
44.21/13.29	mark1(15) -> 2
44.21/13.29	sel1(0, 0) -> 16
44.21/13.29	mark1(16) -> 3
44.21/13.29	indx1(0, 0) -> 17
44.21/13.29	mark1(17) -> 4
44.21/13.29	dbl11(0) -> 18
44.21/13.29	mark1(18) -> 5
44.21/13.29	s11(0) -> 19
44.21/13.29	mark1(19) -> 6
44.21/13.29	sel11(0, 0) -> 20
44.21/13.29	mark1(20) -> 7
44.21/13.29	quote1(0) -> 21
44.21/13.29	mark1(21) -> 8
44.21/13.29	01() -> 22
44.21/13.29	ok1(22) -> 9
44.21/13.29	nil1() -> 23
44.21/13.29	ok1(23) -> 9
44.21/13.29	011() -> 24
44.21/13.29	ok1(24) -> 9
44.21/13.29	dbl1(0) -> 25
44.21/13.29	ok1(25) -> 1
44.21/13.29	s1(0) -> 26
44.21/13.29	ok1(26) -> 10
44.21/13.29	dbls1(0) -> 27
44.21/13.29	ok1(27) -> 2
44.21/13.29	cons1(0, 0) -> 28
44.21/13.29	ok1(28) -> 11
44.21/13.29	sel1(0, 0) -> 29
44.21/13.29	ok1(29) -> 3
44.21/13.29	indx1(0, 0) -> 30
44.21/13.29	ok1(30) -> 4
44.21/13.29	from1(0) -> 31
44.21/13.29	ok1(31) -> 12
44.21/13.29	dbl11(0) -> 32
44.21/13.29	ok1(32) -> 5
44.21/13.29	s11(0) -> 33
44.21/13.29	ok1(33) -> 6
44.21/13.29	sel11(0, 0) -> 34
44.21/13.29	ok1(34) -> 7
44.21/13.29	quote1(0) -> 35
44.21/13.29	ok1(35) -> 8
44.21/13.29	proper1(0) -> 36
44.21/13.29	top1(36) -> 13
44.21/13.29	active1(0) -> 37
44.21/13.29	top1(37) -> 13
44.21/13.29	mark1(14) -> 14
44.21/13.29	mark1(14) -> 25
44.21/13.29	mark1(15) -> 15
44.21/13.29	mark1(15) -> 27
44.21/13.29	mark1(16) -> 16
44.21/13.29	mark1(16) -> 29
44.21/13.29	mark1(17) -> 17
44.21/13.29	mark1(17) -> 30
44.21/13.29	mark1(18) -> 18
44.21/13.29	mark1(18) -> 32
44.21/13.29	mark1(19) -> 19
44.21/13.29	mark1(19) -> 33
44.21/13.29	mark1(20) -> 20
44.21/13.29	mark1(20) -> 34
44.21/13.29	mark1(21) -> 21
44.21/13.29	mark1(21) -> 35
44.21/13.29	ok1(22) -> 36
44.21/13.29	ok1(23) -> 36
44.21/13.29	ok1(24) -> 36
44.21/13.29	ok1(25) -> 14
44.21/13.29	ok1(25) -> 25
44.21/13.29	ok1(26) -> 26
44.21/13.29	ok1(27) -> 15
44.21/13.29	ok1(27) -> 27
44.21/13.29	ok1(28) -> 28
44.21/13.29	ok1(29) -> 16
44.21/13.29	ok1(29) -> 29
44.21/13.29	ok1(30) -> 17
44.21/13.29	ok1(30) -> 30
44.21/13.29	ok1(31) -> 31
44.21/13.29	ok1(32) -> 18
44.21/13.29	ok1(32) -> 32
44.21/13.29	ok1(33) -> 19
44.21/13.29	ok1(33) -> 33
44.21/13.29	ok1(34) -> 20
44.21/13.29	ok1(34) -> 34
44.21/13.29	ok1(35) -> 21
44.21/13.29	ok1(35) -> 35
44.21/13.29	active2(22) -> 38
44.21/13.29	top2(38) -> 13
44.21/13.29	active2(23) -> 38
44.21/13.29	active2(24) -> 38
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(6)
44.21/13.29	BOUNDS(1, n^1)
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(7) RenamingProof (BOTH BOUNDS(ID, ID))
44.21/13.29	Renamed function symbols to avoid clashes with predefined symbol.
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(8)
44.21/13.29	Obligation:
44.21/13.29	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
44.21/13.29	
44.21/13.29	
44.21/13.29	The TRS R consists of the following rules:
44.21/13.29	
44.21/13.29	   active(dbl(0')) -> mark(0')
44.21/13.29	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	   active(dbls(nil)) -> mark(nil)
44.21/13.29	   active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	   active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.29	   active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	   active(indx(nil, X)) -> mark(nil)
44.21/13.29	   active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	   active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	   active(dbl1(0')) -> mark(01')
44.21/13.29	   active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	   active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.29	   active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	   active(quote(0')) -> mark(01')
44.21/13.29	   active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	   active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	   active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	   active(dbl(X)) -> dbl(active(X))
44.21/13.29	   active(dbls(X)) -> dbls(active(X))
44.21/13.29	   active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	   active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	   active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	   active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	   active(s1(X)) -> s1(active(X))
44.21/13.29	   active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	   active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	   active(quote(X)) -> quote(active(X))
44.21/13.29	   dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	   dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	   sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	   sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	   indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	   dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	   s1(mark(X)) -> mark(s1(X))
44.21/13.29	   sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	   sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	   quote(mark(X)) -> mark(quote(X))
44.21/13.29	   proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	   proper(0') -> ok(0')
44.21/13.29	   proper(s(X)) -> s(proper(X))
44.21/13.29	   proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	   proper(nil) -> ok(nil)
44.21/13.29	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	   proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	   proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	   proper(from(X)) -> from(proper(X))
44.21/13.29	   proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	   proper(01') -> ok(01')
44.21/13.29	   proper(s1(X)) -> s1(proper(X))
44.21/13.29	   proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	   proper(quote(X)) -> quote(proper(X))
44.21/13.29	   dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	   s(ok(X)) -> ok(s(X))
44.21/13.29	   dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	   sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	   indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	   from(ok(X)) -> ok(from(X))
44.21/13.29	   dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	   s1(ok(X)) -> ok(s1(X))
44.21/13.29	   sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	   quote(ok(X)) -> ok(quote(X))
44.21/13.29	   top(mark(X)) -> top(proper(X))
44.21/13.29	   top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	S is empty.
44.21/13.29	Rewrite Strategy: FULL
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
44.21/13.29	Infered types.
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(10)
44.21/13.29	Obligation:
44.21/13.29	TRS:
44.21/13.29	Rules:
44.21/13.29	active(dbl(0')) -> mark(0')
44.21/13.29	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	active(dbls(nil)) -> mark(nil)
44.21/13.29	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	active(indx(nil, X)) -> mark(nil)
44.21/13.29	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	active(dbl1(0')) -> mark(01')
44.21/13.29	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	active(quote(0')) -> mark(01')
44.21/13.29	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	active(dbl(X)) -> dbl(active(X))
44.21/13.29	active(dbls(X)) -> dbls(active(X))
44.21/13.29	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	active(s1(X)) -> s1(active(X))
44.21/13.29	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	active(quote(X)) -> quote(active(X))
44.21/13.29	dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	s1(mark(X)) -> mark(s1(X))
44.21/13.29	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	quote(mark(X)) -> mark(quote(X))
44.21/13.29	proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	proper(0') -> ok(0')
44.21/13.29	proper(s(X)) -> s(proper(X))
44.21/13.29	proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	proper(nil) -> ok(nil)
44.21/13.29	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	proper(from(X)) -> from(proper(X))
44.21/13.29	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	proper(01') -> ok(01')
44.21/13.29	proper(s1(X)) -> s1(proper(X))
44.21/13.29	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	proper(quote(X)) -> quote(proper(X))
44.21/13.29	dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	s(ok(X)) -> ok(s(X))
44.21/13.29	dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	from(ok(X)) -> ok(from(X))
44.21/13.29	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	s1(ok(X)) -> ok(s1(X))
44.21/13.29	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	quote(ok(X)) -> ok(quote(X))
44.21/13.29	top(mark(X)) -> top(proper(X))
44.21/13.29	top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	Types:
44.21/13.29	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	0' :: 0':mark:nil:01':ok
44.21/13.29	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	nil :: 0':mark:nil:01':ok
44.21/13.29	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	01' :: 0':mark:nil:01':ok
44.21/13.29	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	top :: 0':mark:nil:01':ok -> top
44.21/13.29	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.29	hole_top2_0 :: top
44.21/13.29	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(11) OrderProof (LOWER BOUND(ID))
44.21/13.29	Heuristically decided to analyse the following defined symbols:
44.21/13.29	active, s, dbl, cons, dbls, sel, indx, from, s1, dbl1, sel1, quote, proper, top
44.21/13.29	
44.21/13.29	They will be analysed ascendingly in the following order:
44.21/13.29	s < active
44.21/13.29	dbl < active
44.21/13.29	cons < active
44.21/13.29	dbls < active
44.21/13.29	sel < active
44.21/13.29	indx < active
44.21/13.29	from < active
44.21/13.29	s1 < active
44.21/13.29	dbl1 < active
44.21/13.29	sel1 < active
44.21/13.29	quote < active
44.21/13.29	active < top
44.21/13.29	s < proper
44.21/13.29	dbl < proper
44.21/13.29	cons < proper
44.21/13.29	dbls < proper
44.21/13.29	sel < proper
44.21/13.29	indx < proper
44.21/13.29	from < proper
44.21/13.29	s1 < proper
44.21/13.29	dbl1 < proper
44.21/13.29	sel1 < proper
44.21/13.29	quote < proper
44.21/13.29	proper < top
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(12)
44.21/13.29	Obligation:
44.21/13.29	TRS:
44.21/13.29	Rules:
44.21/13.29	active(dbl(0')) -> mark(0')
44.21/13.29	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	active(dbls(nil)) -> mark(nil)
44.21/13.29	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	active(indx(nil, X)) -> mark(nil)
44.21/13.29	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	active(dbl1(0')) -> mark(01')
44.21/13.29	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	active(quote(0')) -> mark(01')
44.21/13.29	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	active(dbl(X)) -> dbl(active(X))
44.21/13.29	active(dbls(X)) -> dbls(active(X))
44.21/13.29	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	active(s1(X)) -> s1(active(X))
44.21/13.29	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	active(quote(X)) -> quote(active(X))
44.21/13.29	dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	s1(mark(X)) -> mark(s1(X))
44.21/13.29	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	quote(mark(X)) -> mark(quote(X))
44.21/13.29	proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	proper(0') -> ok(0')
44.21/13.29	proper(s(X)) -> s(proper(X))
44.21/13.29	proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	proper(nil) -> ok(nil)
44.21/13.29	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	proper(from(X)) -> from(proper(X))
44.21/13.29	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	proper(01') -> ok(01')
44.21/13.29	proper(s1(X)) -> s1(proper(X))
44.21/13.29	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	proper(quote(X)) -> quote(proper(X))
44.21/13.29	dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	s(ok(X)) -> ok(s(X))
44.21/13.29	dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	from(ok(X)) -> ok(from(X))
44.21/13.29	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	s1(ok(X)) -> ok(s1(X))
44.21/13.29	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	quote(ok(X)) -> ok(quote(X))
44.21/13.29	top(mark(X)) -> top(proper(X))
44.21/13.29	top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	Types:
44.21/13.29	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	0' :: 0':mark:nil:01':ok
44.21/13.29	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	nil :: 0':mark:nil:01':ok
44.21/13.29	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	01' :: 0':mark:nil:01':ok
44.21/13.29	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	top :: 0':mark:nil:01':ok -> top
44.21/13.29	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.29	hole_top2_0 :: top
44.21/13.29	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.29	
44.21/13.29	
44.21/13.29	Generator Equations:
44.21/13.29	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.29	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.29	
44.21/13.29	
44.21/13.29	The following defined symbols remain to be analysed:
44.21/13.29	s, active, dbl, cons, dbls, sel, indx, from, s1, dbl1, sel1, quote, proper, top
44.21/13.29	
44.21/13.29	They will be analysed ascendingly in the following order:
44.21/13.29	s < active
44.21/13.29	dbl < active
44.21/13.29	cons < active
44.21/13.29	dbls < active
44.21/13.29	sel < active
44.21/13.29	indx < active
44.21/13.29	from < active
44.21/13.29	s1 < active
44.21/13.29	dbl1 < active
44.21/13.29	sel1 < active
44.21/13.29	quote < active
44.21/13.29	active < top
44.21/13.29	s < proper
44.21/13.29	dbl < proper
44.21/13.29	cons < proper
44.21/13.29	dbls < proper
44.21/13.29	sel < proper
44.21/13.29	indx < proper
44.21/13.29	from < proper
44.21/13.29	s1 < proper
44.21/13.29	dbl1 < proper
44.21/13.29	sel1 < proper
44.21/13.29	quote < proper
44.21/13.29	proper < top
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(13) RewriteLemmaProof (LOWER BOUND(ID))
44.21/13.29	Proved the following rewrite lemma:
44.21/13.29	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.29	
44.21/13.29	Induction Base:
44.21/13.29	dbl(gen_0':mark:nil:01':ok3_0(+(1, 0)))
44.21/13.29	
44.21/13.29	Induction Step:
44.21/13.29	dbl(gen_0':mark:nil:01':ok3_0(+(1, +(n9_0, 1)))) ->_R^Omega(1)
44.21/13.29	mark(dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0)))) ->_IH
44.21/13.29	mark(*4_0)
44.21/13.29	
44.21/13.29	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(14)
44.21/13.29	Complex Obligation (BEST)
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(15)
44.21/13.29	Obligation:
44.21/13.29	Proved the lower bound n^1 for the following obligation:
44.21/13.29	
44.21/13.29	TRS:
44.21/13.29	Rules:
44.21/13.29	active(dbl(0')) -> mark(0')
44.21/13.29	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	active(dbls(nil)) -> mark(nil)
44.21/13.29	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	active(indx(nil, X)) -> mark(nil)
44.21/13.29	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	active(dbl1(0')) -> mark(01')
44.21/13.29	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	active(quote(0')) -> mark(01')
44.21/13.29	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	active(dbl(X)) -> dbl(active(X))
44.21/13.29	active(dbls(X)) -> dbls(active(X))
44.21/13.29	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	active(s1(X)) -> s1(active(X))
44.21/13.29	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	active(quote(X)) -> quote(active(X))
44.21/13.29	dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	s1(mark(X)) -> mark(s1(X))
44.21/13.29	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	quote(mark(X)) -> mark(quote(X))
44.21/13.29	proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	proper(0') -> ok(0')
44.21/13.29	proper(s(X)) -> s(proper(X))
44.21/13.29	proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	proper(nil) -> ok(nil)
44.21/13.29	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	proper(from(X)) -> from(proper(X))
44.21/13.29	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	proper(01') -> ok(01')
44.21/13.29	proper(s1(X)) -> s1(proper(X))
44.21/13.29	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	proper(quote(X)) -> quote(proper(X))
44.21/13.29	dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	s(ok(X)) -> ok(s(X))
44.21/13.29	dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	from(ok(X)) -> ok(from(X))
44.21/13.29	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	s1(ok(X)) -> ok(s1(X))
44.21/13.29	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	quote(ok(X)) -> ok(quote(X))
44.21/13.29	top(mark(X)) -> top(proper(X))
44.21/13.29	top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	Types:
44.21/13.29	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	0' :: 0':mark:nil:01':ok
44.21/13.29	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	nil :: 0':mark:nil:01':ok
44.21/13.29	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	01' :: 0':mark:nil:01':ok
44.21/13.29	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	top :: 0':mark:nil:01':ok -> top
44.21/13.29	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.29	hole_top2_0 :: top
44.21/13.29	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.29	
44.21/13.29	
44.21/13.29	Generator Equations:
44.21/13.29	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.29	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.29	
44.21/13.29	
44.21/13.29	The following defined symbols remain to be analysed:
44.21/13.29	dbl, active, cons, dbls, sel, indx, from, s1, dbl1, sel1, quote, proper, top
44.21/13.29	
44.21/13.29	They will be analysed ascendingly in the following order:
44.21/13.29	dbl < active
44.21/13.29	cons < active
44.21/13.29	dbls < active
44.21/13.29	sel < active
44.21/13.29	indx < active
44.21/13.29	from < active
44.21/13.29	s1 < active
44.21/13.29	dbl1 < active
44.21/13.29	sel1 < active
44.21/13.29	quote < active
44.21/13.29	active < top
44.21/13.29	dbl < proper
44.21/13.29	cons < proper
44.21/13.29	dbls < proper
44.21/13.29	sel < proper
44.21/13.29	indx < proper
44.21/13.29	from < proper
44.21/13.29	s1 < proper
44.21/13.29	dbl1 < proper
44.21/13.29	sel1 < proper
44.21/13.29	quote < proper
44.21/13.29	proper < top
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(16) LowerBoundPropagationProof (FINISHED)
44.21/13.29	Propagated lower bound.
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(17)
44.21/13.29	BOUNDS(n^1, INF)
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(18)
44.21/13.29	Obligation:
44.21/13.29	TRS:
44.21/13.29	Rules:
44.21/13.29	active(dbl(0')) -> mark(0')
44.21/13.29	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	active(dbls(nil)) -> mark(nil)
44.21/13.29	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	active(indx(nil, X)) -> mark(nil)
44.21/13.29	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	active(dbl1(0')) -> mark(01')
44.21/13.29	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	active(quote(0')) -> mark(01')
44.21/13.29	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	active(dbl(X)) -> dbl(active(X))
44.21/13.29	active(dbls(X)) -> dbls(active(X))
44.21/13.29	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	active(s1(X)) -> s1(active(X))
44.21/13.29	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	active(quote(X)) -> quote(active(X))
44.21/13.29	dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	s1(mark(X)) -> mark(s1(X))
44.21/13.29	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	quote(mark(X)) -> mark(quote(X))
44.21/13.29	proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	proper(0') -> ok(0')
44.21/13.29	proper(s(X)) -> s(proper(X))
44.21/13.29	proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	proper(nil) -> ok(nil)
44.21/13.29	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	proper(from(X)) -> from(proper(X))
44.21/13.29	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	proper(01') -> ok(01')
44.21/13.29	proper(s1(X)) -> s1(proper(X))
44.21/13.29	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	proper(quote(X)) -> quote(proper(X))
44.21/13.29	dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	s(ok(X)) -> ok(s(X))
44.21/13.29	dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	from(ok(X)) -> ok(from(X))
44.21/13.29	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	s1(ok(X)) -> ok(s1(X))
44.21/13.29	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	quote(ok(X)) -> ok(quote(X))
44.21/13.29	top(mark(X)) -> top(proper(X))
44.21/13.29	top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	Types:
44.21/13.29	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	0' :: 0':mark:nil:01':ok
44.21/13.29	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	nil :: 0':mark:nil:01':ok
44.21/13.29	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	01' :: 0':mark:nil:01':ok
44.21/13.29	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	top :: 0':mark:nil:01':ok -> top
44.21/13.29	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.29	hole_top2_0 :: top
44.21/13.29	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.29	
44.21/13.29	
44.21/13.29	Lemmas:
44.21/13.29	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.29	
44.21/13.29	
44.21/13.29	Generator Equations:
44.21/13.29	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.29	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.29	
44.21/13.29	
44.21/13.29	The following defined symbols remain to be analysed:
44.21/13.29	cons, active, dbls, sel, indx, from, s1, dbl1, sel1, quote, proper, top
44.21/13.29	
44.21/13.29	They will be analysed ascendingly in the following order:
44.21/13.29	cons < active
44.21/13.29	dbls < active
44.21/13.29	sel < active
44.21/13.29	indx < active
44.21/13.29	from < active
44.21/13.29	s1 < active
44.21/13.29	dbl1 < active
44.21/13.29	sel1 < active
44.21/13.29	quote < active
44.21/13.29	active < top
44.21/13.29	cons < proper
44.21/13.29	dbls < proper
44.21/13.29	sel < proper
44.21/13.29	indx < proper
44.21/13.29	from < proper
44.21/13.29	s1 < proper
44.21/13.29	dbl1 < proper
44.21/13.29	sel1 < proper
44.21/13.29	quote < proper
44.21/13.29	proper < top
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(19) RewriteLemmaProof (LOWER BOUND(ID))
44.21/13.29	Proved the following rewrite lemma:
44.21/13.29	dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0)
44.21/13.29	
44.21/13.29	Induction Base:
44.21/13.29	dbls(gen_0':mark:nil:01':ok3_0(+(1, 0)))
44.21/13.29	
44.21/13.29	Induction Step:
44.21/13.29	dbls(gen_0':mark:nil:01':ok3_0(+(1, +(n478_0, 1)))) ->_R^Omega(1)
44.21/13.29	mark(dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0)))) ->_IH
44.21/13.29	mark(*4_0)
44.21/13.29	
44.21/13.29	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(20)
44.21/13.29	Obligation:
44.21/13.29	TRS:
44.21/13.29	Rules:
44.21/13.29	active(dbl(0')) -> mark(0')
44.21/13.29	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	active(dbls(nil)) -> mark(nil)
44.21/13.29	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	active(indx(nil, X)) -> mark(nil)
44.21/13.29	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	active(dbl1(0')) -> mark(01')
44.21/13.29	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	active(quote(0')) -> mark(01')
44.21/13.29	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	active(dbl(X)) -> dbl(active(X))
44.21/13.29	active(dbls(X)) -> dbls(active(X))
44.21/13.29	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	active(s1(X)) -> s1(active(X))
44.21/13.29	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	active(quote(X)) -> quote(active(X))
44.21/13.29	dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	s1(mark(X)) -> mark(s1(X))
44.21/13.29	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	quote(mark(X)) -> mark(quote(X))
44.21/13.29	proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	proper(0') -> ok(0')
44.21/13.29	proper(s(X)) -> s(proper(X))
44.21/13.29	proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	proper(nil) -> ok(nil)
44.21/13.29	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	proper(from(X)) -> from(proper(X))
44.21/13.29	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	proper(01') -> ok(01')
44.21/13.29	proper(s1(X)) -> s1(proper(X))
44.21/13.29	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	proper(quote(X)) -> quote(proper(X))
44.21/13.29	dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	s(ok(X)) -> ok(s(X))
44.21/13.29	dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	from(ok(X)) -> ok(from(X))
44.21/13.29	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	s1(ok(X)) -> ok(s1(X))
44.21/13.29	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	quote(ok(X)) -> ok(quote(X))
44.21/13.29	top(mark(X)) -> top(proper(X))
44.21/13.29	top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	Types:
44.21/13.29	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	0' :: 0':mark:nil:01':ok
44.21/13.29	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	nil :: 0':mark:nil:01':ok
44.21/13.29	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	01' :: 0':mark:nil:01':ok
44.21/13.29	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	top :: 0':mark:nil:01':ok -> top
44.21/13.29	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.29	hole_top2_0 :: top
44.21/13.29	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.29	
44.21/13.29	
44.21/13.29	Lemmas:
44.21/13.29	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.29	dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0)
44.21/13.29	
44.21/13.29	
44.21/13.29	Generator Equations:
44.21/13.29	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.29	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.29	
44.21/13.29	
44.21/13.29	The following defined symbols remain to be analysed:
44.21/13.29	sel, active, indx, from, s1, dbl1, sel1, quote, proper, top
44.21/13.29	
44.21/13.29	They will be analysed ascendingly in the following order:
44.21/13.29	sel < active
44.21/13.29	indx < active
44.21/13.29	from < active
44.21/13.29	s1 < active
44.21/13.29	dbl1 < active
44.21/13.29	sel1 < active
44.21/13.29	quote < active
44.21/13.29	active < top
44.21/13.29	sel < proper
44.21/13.29	indx < proper
44.21/13.29	from < proper
44.21/13.29	s1 < proper
44.21/13.29	dbl1 < proper
44.21/13.29	sel1 < proper
44.21/13.29	quote < proper
44.21/13.29	proper < top
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(21) RewriteLemmaProof (LOWER BOUND(ID))
44.21/13.29	Proved the following rewrite lemma:
44.21/13.29	sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0)
44.21/13.29	
44.21/13.29	Induction Base:
44.21/13.29	sel(gen_0':mark:nil:01':ok3_0(+(1, 0)), gen_0':mark:nil:01':ok3_0(b))
44.21/13.29	
44.21/13.29	Induction Step:
44.21/13.29	sel(gen_0':mark:nil:01':ok3_0(+(1, +(n1038_0, 1))), gen_0':mark:nil:01':ok3_0(b)) ->_R^Omega(1)
44.21/13.29	mark(sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b))) ->_IH
44.21/13.29	mark(*4_0)
44.21/13.29	
44.21/13.29	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(22)
44.21/13.29	Obligation:
44.21/13.29	TRS:
44.21/13.29	Rules:
44.21/13.29	active(dbl(0')) -> mark(0')
44.21/13.29	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	active(dbls(nil)) -> mark(nil)
44.21/13.29	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	active(indx(nil, X)) -> mark(nil)
44.21/13.29	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	active(dbl1(0')) -> mark(01')
44.21/13.29	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	active(quote(0')) -> mark(01')
44.21/13.29	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	active(dbl(X)) -> dbl(active(X))
44.21/13.29	active(dbls(X)) -> dbls(active(X))
44.21/13.29	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	active(s1(X)) -> s1(active(X))
44.21/13.29	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	active(quote(X)) -> quote(active(X))
44.21/13.29	dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	s1(mark(X)) -> mark(s1(X))
44.21/13.29	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	quote(mark(X)) -> mark(quote(X))
44.21/13.29	proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	proper(0') -> ok(0')
44.21/13.29	proper(s(X)) -> s(proper(X))
44.21/13.29	proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	proper(nil) -> ok(nil)
44.21/13.29	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.29	proper(from(X)) -> from(proper(X))
44.21/13.29	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.29	proper(01') -> ok(01')
44.21/13.29	proper(s1(X)) -> s1(proper(X))
44.21/13.29	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.29	proper(quote(X)) -> quote(proper(X))
44.21/13.29	dbl(ok(X)) -> ok(dbl(X))
44.21/13.29	s(ok(X)) -> ok(s(X))
44.21/13.29	dbls(ok(X)) -> ok(dbls(X))
44.21/13.29	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.29	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.29	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.29	from(ok(X)) -> ok(from(X))
44.21/13.29	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.29	s1(ok(X)) -> ok(s1(X))
44.21/13.29	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.29	quote(ok(X)) -> ok(quote(X))
44.21/13.29	top(mark(X)) -> top(proper(X))
44.21/13.29	top(ok(X)) -> top(active(X))
44.21/13.29	
44.21/13.29	Types:
44.21/13.29	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	0' :: 0':mark:nil:01':ok
44.21/13.29	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	nil :: 0':mark:nil:01':ok
44.21/13.29	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	01' :: 0':mark:nil:01':ok
44.21/13.29	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.29	top :: 0':mark:nil:01':ok -> top
44.21/13.29	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.29	hole_top2_0 :: top
44.21/13.29	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.29	
44.21/13.29	
44.21/13.29	Lemmas:
44.21/13.29	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.29	dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0)
44.21/13.29	sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0)
44.21/13.29	
44.21/13.29	
44.21/13.29	Generator Equations:
44.21/13.29	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.29	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.29	
44.21/13.29	
44.21/13.29	The following defined symbols remain to be analysed:
44.21/13.29	indx, active, from, s1, dbl1, sel1, quote, proper, top
44.21/13.29	
44.21/13.29	They will be analysed ascendingly in the following order:
44.21/13.29	indx < active
44.21/13.29	from < active
44.21/13.29	s1 < active
44.21/13.29	dbl1 < active
44.21/13.29	sel1 < active
44.21/13.29	quote < active
44.21/13.29	active < top
44.21/13.29	indx < proper
44.21/13.29	from < proper
44.21/13.29	s1 < proper
44.21/13.29	dbl1 < proper
44.21/13.29	sel1 < proper
44.21/13.29	quote < proper
44.21/13.29	proper < top
44.21/13.29	
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(23) RewriteLemmaProof (LOWER BOUND(ID))
44.21/13.29	Proved the following rewrite lemma:
44.21/13.29	indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0)
44.21/13.29	
44.21/13.29	Induction Base:
44.21/13.29	indx(gen_0':mark:nil:01':ok3_0(+(1, 0)), gen_0':mark:nil:01':ok3_0(b))
44.21/13.29	
44.21/13.29	Induction Step:
44.21/13.29	indx(gen_0':mark:nil:01':ok3_0(+(1, +(n2984_0, 1))), gen_0':mark:nil:01':ok3_0(b)) ->_R^Omega(1)
44.21/13.29	mark(indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b))) ->_IH
44.21/13.29	mark(*4_0)
44.21/13.29	
44.21/13.29	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
44.21/13.29	----------------------------------------
44.21/13.29	
44.21/13.29	(24)
44.21/13.29	Obligation:
44.21/13.29	TRS:
44.21/13.29	Rules:
44.21/13.29	active(dbl(0')) -> mark(0')
44.21/13.29	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.29	active(dbls(nil)) -> mark(nil)
44.21/13.29	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.29	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.29	active(indx(nil, X)) -> mark(nil)
44.21/13.29	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.29	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.29	active(dbl1(0')) -> mark(01')
44.21/13.29	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.29	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.29	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.29	active(quote(0')) -> mark(01')
44.21/13.29	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.29	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.29	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.29	active(dbl(X)) -> dbl(active(X))
44.21/13.29	active(dbls(X)) -> dbls(active(X))
44.21/13.29	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.29	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.29	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.29	active(dbl1(X)) -> dbl1(active(X))
44.21/13.29	active(s1(X)) -> s1(active(X))
44.21/13.29	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.29	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.29	active(quote(X)) -> quote(active(X))
44.21/13.29	dbl(mark(X)) -> mark(dbl(X))
44.21/13.29	dbls(mark(X)) -> mark(dbls(X))
44.21/13.29	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.29	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.29	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.29	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.29	s1(mark(X)) -> mark(s1(X))
44.21/13.29	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.29	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.29	quote(mark(X)) -> mark(quote(X))
44.21/13.29	proper(dbl(X)) -> dbl(proper(X))
44.21/13.29	proper(0') -> ok(0')
44.21/13.29	proper(s(X)) -> s(proper(X))
44.21/13.29	proper(dbls(X)) -> dbls(proper(X))
44.21/13.29	proper(nil) -> ok(nil)
44.21/13.29	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.29	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.29	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.30	proper(from(X)) -> from(proper(X))
44.21/13.30	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.30	proper(01') -> ok(01')
44.21/13.30	proper(s1(X)) -> s1(proper(X))
44.21/13.30	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.30	proper(quote(X)) -> quote(proper(X))
44.21/13.30	dbl(ok(X)) -> ok(dbl(X))
44.21/13.30	s(ok(X)) -> ok(s(X))
44.21/13.30	dbls(ok(X)) -> ok(dbls(X))
44.21/13.30	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.30	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.30	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.30	from(ok(X)) -> ok(from(X))
44.21/13.30	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.30	s1(ok(X)) -> ok(s1(X))
44.21/13.30	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.30	quote(ok(X)) -> ok(quote(X))
44.21/13.30	top(mark(X)) -> top(proper(X))
44.21/13.30	top(ok(X)) -> top(active(X))
44.21/13.30	
44.21/13.30	Types:
44.21/13.30	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	0' :: 0':mark:nil:01':ok
44.21/13.30	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	nil :: 0':mark:nil:01':ok
44.21/13.30	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	01' :: 0':mark:nil:01':ok
44.21/13.30	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	top :: 0':mark:nil:01':ok -> top
44.21/13.30	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.30	hole_top2_0 :: top
44.21/13.30	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.30	
44.21/13.30	
44.21/13.30	Lemmas:
44.21/13.30	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.30	dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0)
44.21/13.30	sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0)
44.21/13.30	indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0)
44.21/13.30	
44.21/13.30	
44.21/13.30	Generator Equations:
44.21/13.30	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.30	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.30	
44.21/13.30	
44.21/13.30	The following defined symbols remain to be analysed:
44.21/13.30	from, active, s1, dbl1, sel1, quote, proper, top
44.21/13.30	
44.21/13.30	They will be analysed ascendingly in the following order:
44.21/13.30	from < active
44.21/13.30	s1 < active
44.21/13.30	dbl1 < active
44.21/13.30	sel1 < active
44.21/13.30	quote < active
44.21/13.30	active < top
44.21/13.30	from < proper
44.21/13.30	s1 < proper
44.21/13.30	dbl1 < proper
44.21/13.30	sel1 < proper
44.21/13.30	quote < proper
44.21/13.30	proper < top
44.21/13.30	
44.21/13.30	----------------------------------------
44.21/13.30	
44.21/13.30	(25) RewriteLemmaProof (LOWER BOUND(ID))
44.21/13.30	Proved the following rewrite lemma:
44.21/13.30	s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0)
44.21/13.30	
44.21/13.30	Induction Base:
44.21/13.30	s1(gen_0':mark:nil:01':ok3_0(+(1, 0)))
44.21/13.30	
44.21/13.30	Induction Step:
44.21/13.30	s1(gen_0':mark:nil:01':ok3_0(+(1, +(n5057_0, 1)))) ->_R^Omega(1)
44.21/13.30	mark(s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0)))) ->_IH
44.21/13.30	mark(*4_0)
44.21/13.30	
44.21/13.30	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
44.21/13.30	----------------------------------------
44.21/13.30	
44.21/13.30	(26)
44.21/13.30	Obligation:
44.21/13.30	TRS:
44.21/13.30	Rules:
44.21/13.30	active(dbl(0')) -> mark(0')
44.21/13.30	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.30	active(dbls(nil)) -> mark(nil)
44.21/13.30	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.30	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.30	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.30	active(indx(nil, X)) -> mark(nil)
44.21/13.30	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.30	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.30	active(dbl1(0')) -> mark(01')
44.21/13.30	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.30	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.30	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.30	active(quote(0')) -> mark(01')
44.21/13.30	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.30	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.30	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.30	active(dbl(X)) -> dbl(active(X))
44.21/13.30	active(dbls(X)) -> dbls(active(X))
44.21/13.30	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.30	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.30	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.30	active(dbl1(X)) -> dbl1(active(X))
44.21/13.30	active(s1(X)) -> s1(active(X))
44.21/13.30	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.30	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.30	active(quote(X)) -> quote(active(X))
44.21/13.30	dbl(mark(X)) -> mark(dbl(X))
44.21/13.30	dbls(mark(X)) -> mark(dbls(X))
44.21/13.30	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.30	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.30	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.30	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.30	s1(mark(X)) -> mark(s1(X))
44.21/13.30	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.30	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.30	quote(mark(X)) -> mark(quote(X))
44.21/13.30	proper(dbl(X)) -> dbl(proper(X))
44.21/13.30	proper(0') -> ok(0')
44.21/13.30	proper(s(X)) -> s(proper(X))
44.21/13.30	proper(dbls(X)) -> dbls(proper(X))
44.21/13.30	proper(nil) -> ok(nil)
44.21/13.30	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.30	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.30	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.30	proper(from(X)) -> from(proper(X))
44.21/13.30	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.30	proper(01') -> ok(01')
44.21/13.30	proper(s1(X)) -> s1(proper(X))
44.21/13.30	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.30	proper(quote(X)) -> quote(proper(X))
44.21/13.30	dbl(ok(X)) -> ok(dbl(X))
44.21/13.30	s(ok(X)) -> ok(s(X))
44.21/13.30	dbls(ok(X)) -> ok(dbls(X))
44.21/13.30	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.30	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.30	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.30	from(ok(X)) -> ok(from(X))
44.21/13.30	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.30	s1(ok(X)) -> ok(s1(X))
44.21/13.30	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.30	quote(ok(X)) -> ok(quote(X))
44.21/13.30	top(mark(X)) -> top(proper(X))
44.21/13.30	top(ok(X)) -> top(active(X))
44.21/13.30	
44.21/13.30	Types:
44.21/13.30	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	0' :: 0':mark:nil:01':ok
44.21/13.30	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	nil :: 0':mark:nil:01':ok
44.21/13.30	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	01' :: 0':mark:nil:01':ok
44.21/13.30	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	top :: 0':mark:nil:01':ok -> top
44.21/13.30	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.30	hole_top2_0 :: top
44.21/13.30	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.30	
44.21/13.30	
44.21/13.30	Lemmas:
44.21/13.30	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.30	dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0)
44.21/13.30	sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0)
44.21/13.30	indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0)
44.21/13.30	s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0)
44.21/13.30	
44.21/13.30	
44.21/13.30	Generator Equations:
44.21/13.30	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.30	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.30	
44.21/13.30	
44.21/13.30	The following defined symbols remain to be analysed:
44.21/13.30	dbl1, active, sel1, quote, proper, top
44.21/13.30	
44.21/13.30	They will be analysed ascendingly in the following order:
44.21/13.30	dbl1 < active
44.21/13.30	sel1 < active
44.21/13.30	quote < active
44.21/13.30	active < top
44.21/13.30	dbl1 < proper
44.21/13.30	sel1 < proper
44.21/13.30	quote < proper
44.21/13.30	proper < top
44.21/13.30	
44.21/13.30	----------------------------------------
44.21/13.30	
44.21/13.30	(27) RewriteLemmaProof (LOWER BOUND(ID))
44.21/13.30	Proved the following rewrite lemma:
44.21/13.30	dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0))) -> *4_0, rt in Omega(n6018_0)
44.21/13.30	
44.21/13.30	Induction Base:
44.21/13.30	dbl1(gen_0':mark:nil:01':ok3_0(+(1, 0)))
44.21/13.30	
44.21/13.30	Induction Step:
44.21/13.30	dbl1(gen_0':mark:nil:01':ok3_0(+(1, +(n6018_0, 1)))) ->_R^Omega(1)
44.21/13.30	mark(dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0)))) ->_IH
44.21/13.30	mark(*4_0)
44.21/13.30	
44.21/13.30	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
44.21/13.30	----------------------------------------
44.21/13.30	
44.21/13.30	(28)
44.21/13.30	Obligation:
44.21/13.30	TRS:
44.21/13.30	Rules:
44.21/13.30	active(dbl(0')) -> mark(0')
44.21/13.30	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.30	active(dbls(nil)) -> mark(nil)
44.21/13.30	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.30	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.30	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.30	active(indx(nil, X)) -> mark(nil)
44.21/13.30	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.30	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.30	active(dbl1(0')) -> mark(01')
44.21/13.30	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.30	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.30	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.30	active(quote(0')) -> mark(01')
44.21/13.30	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.30	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.30	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.30	active(dbl(X)) -> dbl(active(X))
44.21/13.30	active(dbls(X)) -> dbls(active(X))
44.21/13.30	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.30	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.30	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.30	active(dbl1(X)) -> dbl1(active(X))
44.21/13.30	active(s1(X)) -> s1(active(X))
44.21/13.30	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.30	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.30	active(quote(X)) -> quote(active(X))
44.21/13.30	dbl(mark(X)) -> mark(dbl(X))
44.21/13.30	dbls(mark(X)) -> mark(dbls(X))
44.21/13.30	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.30	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.30	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.30	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.30	s1(mark(X)) -> mark(s1(X))
44.21/13.30	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.30	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.30	quote(mark(X)) -> mark(quote(X))
44.21/13.30	proper(dbl(X)) -> dbl(proper(X))
44.21/13.30	proper(0') -> ok(0')
44.21/13.30	proper(s(X)) -> s(proper(X))
44.21/13.30	proper(dbls(X)) -> dbls(proper(X))
44.21/13.30	proper(nil) -> ok(nil)
44.21/13.30	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.30	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.30	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.30	proper(from(X)) -> from(proper(X))
44.21/13.30	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.30	proper(01') -> ok(01')
44.21/13.30	proper(s1(X)) -> s1(proper(X))
44.21/13.30	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.30	proper(quote(X)) -> quote(proper(X))
44.21/13.30	dbl(ok(X)) -> ok(dbl(X))
44.21/13.30	s(ok(X)) -> ok(s(X))
44.21/13.30	dbls(ok(X)) -> ok(dbls(X))
44.21/13.30	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.30	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.30	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.30	from(ok(X)) -> ok(from(X))
44.21/13.30	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.30	s1(ok(X)) -> ok(s1(X))
44.21/13.30	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.30	quote(ok(X)) -> ok(quote(X))
44.21/13.30	top(mark(X)) -> top(proper(X))
44.21/13.30	top(ok(X)) -> top(active(X))
44.21/13.30	
44.21/13.30	Types:
44.21/13.30	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	0' :: 0':mark:nil:01':ok
44.21/13.30	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	nil :: 0':mark:nil:01':ok
44.21/13.30	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	01' :: 0':mark:nil:01':ok
44.21/13.30	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	top :: 0':mark:nil:01':ok -> top
44.21/13.30	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.30	hole_top2_0 :: top
44.21/13.30	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.30	
44.21/13.30	
44.21/13.30	Lemmas:
44.21/13.30	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.30	dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0)
44.21/13.30	sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0)
44.21/13.30	indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0)
44.21/13.30	s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0)
44.21/13.30	dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0))) -> *4_0, rt in Omega(n6018_0)
44.21/13.30	
44.21/13.30	
44.21/13.30	Generator Equations:
44.21/13.30	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.30	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.30	
44.21/13.30	
44.21/13.30	The following defined symbols remain to be analysed:
44.21/13.30	sel1, active, quote, proper, top
44.21/13.30	
44.21/13.30	They will be analysed ascendingly in the following order:
44.21/13.30	sel1 < active
44.21/13.30	quote < active
44.21/13.30	active < top
44.21/13.30	sel1 < proper
44.21/13.30	quote < proper
44.21/13.30	proper < top
44.21/13.30	
44.21/13.30	----------------------------------------
44.21/13.30	
44.21/13.30	(29) RewriteLemmaProof (LOWER BOUND(ID))
44.21/13.30	Proved the following rewrite lemma:
44.21/13.30	sel1(gen_0':mark:nil:01':ok3_0(+(1, n7080_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n7080_0)
44.21/13.30	
44.21/13.30	Induction Base:
44.21/13.30	sel1(gen_0':mark:nil:01':ok3_0(+(1, 0)), gen_0':mark:nil:01':ok3_0(b))
44.21/13.30	
44.21/13.30	Induction Step:
44.21/13.30	sel1(gen_0':mark:nil:01':ok3_0(+(1, +(n7080_0, 1))), gen_0':mark:nil:01':ok3_0(b)) ->_R^Omega(1)
44.21/13.30	mark(sel1(gen_0':mark:nil:01':ok3_0(+(1, n7080_0)), gen_0':mark:nil:01':ok3_0(b))) ->_IH
44.21/13.30	mark(*4_0)
44.21/13.30	
44.21/13.30	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
44.21/13.30	----------------------------------------
44.21/13.30	
44.21/13.30	(30)
44.21/13.30	Obligation:
44.21/13.30	TRS:
44.21/13.30	Rules:
44.21/13.30	active(dbl(0')) -> mark(0')
44.21/13.30	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.30	active(dbls(nil)) -> mark(nil)
44.21/13.30	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.30	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.30	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.30	active(indx(nil, X)) -> mark(nil)
44.21/13.30	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.30	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.30	active(dbl1(0')) -> mark(01')
44.21/13.30	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.30	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.30	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.30	active(quote(0')) -> mark(01')
44.21/13.30	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.30	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.30	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.30	active(dbl(X)) -> dbl(active(X))
44.21/13.30	active(dbls(X)) -> dbls(active(X))
44.21/13.30	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.30	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.30	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.30	active(dbl1(X)) -> dbl1(active(X))
44.21/13.30	active(s1(X)) -> s1(active(X))
44.21/13.30	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.30	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.30	active(quote(X)) -> quote(active(X))
44.21/13.30	dbl(mark(X)) -> mark(dbl(X))
44.21/13.30	dbls(mark(X)) -> mark(dbls(X))
44.21/13.30	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.30	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.30	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.30	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.30	s1(mark(X)) -> mark(s1(X))
44.21/13.30	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.30	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.30	quote(mark(X)) -> mark(quote(X))
44.21/13.30	proper(dbl(X)) -> dbl(proper(X))
44.21/13.30	proper(0') -> ok(0')
44.21/13.30	proper(s(X)) -> s(proper(X))
44.21/13.30	proper(dbls(X)) -> dbls(proper(X))
44.21/13.30	proper(nil) -> ok(nil)
44.21/13.30	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.30	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.30	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.30	proper(from(X)) -> from(proper(X))
44.21/13.30	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.30	proper(01') -> ok(01')
44.21/13.30	proper(s1(X)) -> s1(proper(X))
44.21/13.30	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.30	proper(quote(X)) -> quote(proper(X))
44.21/13.30	dbl(ok(X)) -> ok(dbl(X))
44.21/13.30	s(ok(X)) -> ok(s(X))
44.21/13.30	dbls(ok(X)) -> ok(dbls(X))
44.21/13.30	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.30	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.30	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.30	from(ok(X)) -> ok(from(X))
44.21/13.30	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.30	s1(ok(X)) -> ok(s1(X))
44.21/13.30	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.30	quote(ok(X)) -> ok(quote(X))
44.21/13.30	top(mark(X)) -> top(proper(X))
44.21/13.30	top(ok(X)) -> top(active(X))
44.21/13.30	
44.21/13.30	Types:
44.21/13.30	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	0' :: 0':mark:nil:01':ok
44.21/13.30	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	nil :: 0':mark:nil:01':ok
44.21/13.30	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	01' :: 0':mark:nil:01':ok
44.21/13.30	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	top :: 0':mark:nil:01':ok -> top
44.21/13.30	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.30	hole_top2_0 :: top
44.21/13.30	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.30	
44.21/13.30	
44.21/13.30	Lemmas:
44.21/13.30	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.30	dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0)
44.21/13.30	sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0)
44.21/13.30	indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0)
44.21/13.30	s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0)
44.21/13.30	dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0))) -> *4_0, rt in Omega(n6018_0)
44.21/13.30	sel1(gen_0':mark:nil:01':ok3_0(+(1, n7080_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n7080_0)
44.21/13.30	
44.21/13.30	
44.21/13.30	Generator Equations:
44.21/13.30	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.30	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.30	
44.21/13.30	
44.21/13.30	The following defined symbols remain to be analysed:
44.21/13.30	quote, active, proper, top
44.21/13.30	
44.21/13.30	They will be analysed ascendingly in the following order:
44.21/13.30	quote < active
44.21/13.30	active < top
44.21/13.30	quote < proper
44.21/13.30	proper < top
44.21/13.30	
44.21/13.30	----------------------------------------
44.21/13.30	
44.21/13.30	(31) RewriteLemmaProof (LOWER BOUND(ID))
44.21/13.30	Proved the following rewrite lemma:
44.21/13.30	quote(gen_0':mark:nil:01':ok3_0(+(1, n10054_0))) -> *4_0, rt in Omega(n10054_0)
44.21/13.30	
44.21/13.30	Induction Base:
44.21/13.30	quote(gen_0':mark:nil:01':ok3_0(+(1, 0)))
44.21/13.30	
44.21/13.30	Induction Step:
44.21/13.30	quote(gen_0':mark:nil:01':ok3_0(+(1, +(n10054_0, 1)))) ->_R^Omega(1)
44.21/13.30	mark(quote(gen_0':mark:nil:01':ok3_0(+(1, n10054_0)))) ->_IH
44.21/13.30	mark(*4_0)
44.21/13.30	
44.21/13.30	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
44.21/13.30	----------------------------------------
44.21/13.30	
44.21/13.30	(32)
44.21/13.30	Obligation:
44.21/13.30	TRS:
44.21/13.30	Rules:
44.21/13.30	active(dbl(0')) -> mark(0')
44.21/13.30	active(dbl(s(X))) -> mark(s(s(dbl(X))))
44.21/13.30	active(dbls(nil)) -> mark(nil)
44.21/13.30	active(dbls(cons(X, Y))) -> mark(cons(dbl(X), dbls(Y)))
44.21/13.30	active(sel(0', cons(X, Y))) -> mark(X)
44.21/13.30	active(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z))
44.21/13.30	active(indx(nil, X)) -> mark(nil)
44.21/13.30	active(indx(cons(X, Y), Z)) -> mark(cons(sel(X, Z), indx(Y, Z)))
44.21/13.30	active(from(X)) -> mark(cons(X, from(s(X))))
44.21/13.30	active(dbl1(0')) -> mark(01')
44.21/13.30	active(dbl1(s(X))) -> mark(s1(s1(dbl1(X))))
44.21/13.30	active(sel1(0', cons(X, Y))) -> mark(X)
44.21/13.30	active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z))
44.21/13.30	active(quote(0')) -> mark(01')
44.21/13.30	active(quote(s(X))) -> mark(s1(quote(X)))
44.21/13.30	active(quote(dbl(X))) -> mark(dbl1(X))
44.21/13.30	active(quote(sel(X, Y))) -> mark(sel1(X, Y))
44.21/13.30	active(dbl(X)) -> dbl(active(X))
44.21/13.30	active(dbls(X)) -> dbls(active(X))
44.21/13.30	active(sel(X1, X2)) -> sel(active(X1), X2)
44.21/13.30	active(sel(X1, X2)) -> sel(X1, active(X2))
44.21/13.30	active(indx(X1, X2)) -> indx(active(X1), X2)
44.21/13.30	active(dbl1(X)) -> dbl1(active(X))
44.21/13.30	active(s1(X)) -> s1(active(X))
44.21/13.30	active(sel1(X1, X2)) -> sel1(active(X1), X2)
44.21/13.30	active(sel1(X1, X2)) -> sel1(X1, active(X2))
44.21/13.30	active(quote(X)) -> quote(active(X))
44.21/13.30	dbl(mark(X)) -> mark(dbl(X))
44.21/13.30	dbls(mark(X)) -> mark(dbls(X))
44.21/13.30	sel(mark(X1), X2) -> mark(sel(X1, X2))
44.21/13.30	sel(X1, mark(X2)) -> mark(sel(X1, X2))
44.21/13.30	indx(mark(X1), X2) -> mark(indx(X1, X2))
44.21/13.30	dbl1(mark(X)) -> mark(dbl1(X))
44.21/13.30	s1(mark(X)) -> mark(s1(X))
44.21/13.30	sel1(mark(X1), X2) -> mark(sel1(X1, X2))
44.21/13.30	sel1(X1, mark(X2)) -> mark(sel1(X1, X2))
44.21/13.30	quote(mark(X)) -> mark(quote(X))
44.21/13.30	proper(dbl(X)) -> dbl(proper(X))
44.21/13.30	proper(0') -> ok(0')
44.21/13.30	proper(s(X)) -> s(proper(X))
44.21/13.30	proper(dbls(X)) -> dbls(proper(X))
44.21/13.30	proper(nil) -> ok(nil)
44.21/13.30	proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
44.21/13.30	proper(sel(X1, X2)) -> sel(proper(X1), proper(X2))
44.21/13.30	proper(indx(X1, X2)) -> indx(proper(X1), proper(X2))
44.21/13.30	proper(from(X)) -> from(proper(X))
44.21/13.30	proper(dbl1(X)) -> dbl1(proper(X))
44.21/13.30	proper(01') -> ok(01')
44.21/13.30	proper(s1(X)) -> s1(proper(X))
44.21/13.30	proper(sel1(X1, X2)) -> sel1(proper(X1), proper(X2))
44.21/13.30	proper(quote(X)) -> quote(proper(X))
44.21/13.30	dbl(ok(X)) -> ok(dbl(X))
44.21/13.30	s(ok(X)) -> ok(s(X))
44.21/13.30	dbls(ok(X)) -> ok(dbls(X))
44.21/13.30	cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
44.21/13.30	sel(ok(X1), ok(X2)) -> ok(sel(X1, X2))
44.21/13.30	indx(ok(X1), ok(X2)) -> ok(indx(X1, X2))
44.21/13.30	from(ok(X)) -> ok(from(X))
44.21/13.30	dbl1(ok(X)) -> ok(dbl1(X))
44.21/13.30	s1(ok(X)) -> ok(s1(X))
44.21/13.30	sel1(ok(X1), ok(X2)) -> ok(sel1(X1, X2))
44.21/13.30	quote(ok(X)) -> ok(quote(X))
44.21/13.30	top(mark(X)) -> top(proper(X))
44.21/13.30	top(ok(X)) -> top(active(X))
44.21/13.30	
44.21/13.30	Types:
44.21/13.30	active :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	0' :: 0':mark:nil:01':ok
44.21/13.30	mark :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	s :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbls :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	nil :: 0':mark:nil:01':ok
44.21/13.30	cons :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	indx :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	from :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	dbl1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	01' :: 0':mark:nil:01':ok
44.21/13.30	s1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	sel1 :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	quote :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	proper :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	ok :: 0':mark:nil:01':ok -> 0':mark:nil:01':ok
44.21/13.30	top :: 0':mark:nil:01':ok -> top
44.21/13.30	hole_0':mark:nil:01':ok1_0 :: 0':mark:nil:01':ok
44.21/13.30	hole_top2_0 :: top
44.21/13.30	gen_0':mark:nil:01':ok3_0 :: Nat -> 0':mark:nil:01':ok
44.21/13.30	
44.21/13.30	
44.21/13.30	Lemmas:
44.21/13.30	dbl(gen_0':mark:nil:01':ok3_0(+(1, n9_0))) -> *4_0, rt in Omega(n9_0)
44.21/13.30	dbls(gen_0':mark:nil:01':ok3_0(+(1, n478_0))) -> *4_0, rt in Omega(n478_0)
44.21/13.30	sel(gen_0':mark:nil:01':ok3_0(+(1, n1038_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n1038_0)
44.21/13.30	indx(gen_0':mark:nil:01':ok3_0(+(1, n2984_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n2984_0)
44.21/13.30	s1(gen_0':mark:nil:01':ok3_0(+(1, n5057_0))) -> *4_0, rt in Omega(n5057_0)
44.21/13.30	dbl1(gen_0':mark:nil:01':ok3_0(+(1, n6018_0))) -> *4_0, rt in Omega(n6018_0)
44.21/13.30	sel1(gen_0':mark:nil:01':ok3_0(+(1, n7080_0)), gen_0':mark:nil:01':ok3_0(b)) -> *4_0, rt in Omega(n7080_0)
44.21/13.30	quote(gen_0':mark:nil:01':ok3_0(+(1, n10054_0))) -> *4_0, rt in Omega(n10054_0)
44.21/13.30	
44.21/13.30	
44.21/13.30	Generator Equations:
44.21/13.30	gen_0':mark:nil:01':ok3_0(0) <=> 0'
44.21/13.30	gen_0':mark:nil:01':ok3_0(+(x, 1)) <=> mark(gen_0':mark:nil:01':ok3_0(x))
44.21/13.30	
44.21/13.30	
44.21/13.30	The following defined symbols remain to be analysed:
44.21/13.30	active, proper, top
44.21/13.30	
44.21/13.30	They will be analysed ascendingly in the following order:
44.21/13.30	active < top
44.21/13.30	proper < top
44.52/13.34	EOF