12.69/4.50	YES
12.69/4.52	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
12.69/4.52	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.69/4.52	
12.69/4.52	
12.69/4.52	Termination w.r.t. Q of the given QTRS could be proven:
12.69/4.52	
12.69/4.52	(0) QTRS
12.69/4.52	(1) DependencyPairsProof [EQUIVALENT, 56 ms]
12.69/4.52	(2) QDP
12.69/4.52	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
12.69/4.52	(4) AND
12.69/4.52	    (5) QDP
12.69/4.52	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (7) QDP
12.69/4.52	        (8) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (9) QDP
12.69/4.52	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (11) YES
12.69/4.52	    (12) QDP
12.69/4.52	        (13) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (14) QDP
12.69/4.52	        (15) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (16) QDP
12.69/4.52	        (17) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (18) YES
12.69/4.52	    (19) QDP
12.69/4.52	        (20) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (21) QDP
12.69/4.52	        (22) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (23) QDP
12.69/4.52	        (24) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (25) YES
12.69/4.52	    (26) QDP
12.69/4.52	        (27) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (28) QDP
12.69/4.52	        (29) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (30) QDP
12.69/4.52	        (31) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (32) YES
12.69/4.52	    (33) QDP
12.69/4.52	        (34) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (35) QDP
12.69/4.52	        (36) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (37) QDP
12.69/4.52	        (38) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (39) YES
12.69/4.52	    (40) QDP
12.69/4.52	        (41) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (42) QDP
12.69/4.52	        (43) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (44) QDP
12.69/4.52	        (45) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (46) YES
12.69/4.52	    (47) QDP
12.69/4.52	        (48) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (49) QDP
12.69/4.52	        (50) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (51) QDP
12.69/4.52	        (52) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (53) YES
12.69/4.52	    (54) QDP
12.69/4.52	        (55) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (56) QDP
12.69/4.52	        (57) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (58) QDP
12.69/4.52	        (59) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (60) YES
12.69/4.52	    (61) QDP
12.69/4.52	        (62) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (63) QDP
12.69/4.52	        (64) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (65) QDP
12.69/4.52	        (66) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (67) YES
12.69/4.52	    (68) QDP
12.69/4.52	        (69) QDPQMonotonicMRRProof [EQUIVALENT, 277 ms]
12.69/4.52	        (70) QDP
12.69/4.52	        (71) QDPOrderProof [EQUIVALENT, 373 ms]
12.69/4.52	        (72) QDP
12.69/4.52	        (73) DependencyGraphProof [EQUIVALENT, 0 ms]
12.69/4.52	        (74) QDP
12.69/4.52	        (75) UsableRulesProof [EQUIVALENT, 0 ms]
12.69/4.52	        (76) QDP
12.69/4.52	        (77) QReductionProof [EQUIVALENT, 0 ms]
12.69/4.52	        (78) QDP
12.69/4.52	        (79) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.69/4.52	        (80) YES
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(0)
12.69/4.52	Obligation:
12.69/4.52	Q restricted rewrite system:
12.69/4.52	The TRS R consists of the following rules:
12.69/4.52	
12.69/4.52	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   active(sqr(0)) -> mark(0)
12.69/4.52	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.52	   active(dbl(0)) -> mark(0)
12.69/4.52	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.52	   active(add(0, X)) -> mark(X)
12.69/4.52	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.52	   active(first(0, X)) -> mark(nil)
12.69/4.52	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.52	   active(half(0)) -> mark(0)
12.69/4.52	   active(half(s(0))) -> mark(0)
12.69/4.52	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.52	   active(half(dbl(X))) -> mark(X)
12.69/4.52	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.52	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.52	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.52	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.52	   mark(s(X)) -> active(s(mark(X)))
12.69/4.52	   mark(0) -> active(0)
12.69/4.52	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.52	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.52	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.52	   mark(nil) -> active(nil)
12.69/4.52	   mark(half(X)) -> active(half(mark(X)))
12.69/4.52	   terms(mark(X)) -> terms(X)
12.69/4.52	   terms(active(X)) -> terms(X)
12.69/4.52	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.52	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.52	   recip(mark(X)) -> recip(X)
12.69/4.52	   recip(active(X)) -> recip(X)
12.69/4.52	   sqr(mark(X)) -> sqr(X)
12.69/4.52	   sqr(active(X)) -> sqr(X)
12.69/4.52	   s(mark(X)) -> s(X)
12.69/4.52	   s(active(X)) -> s(X)
12.69/4.52	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.52	   add(active(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.52	   dbl(mark(X)) -> dbl(X)
12.69/4.52	   dbl(active(X)) -> dbl(X)
12.69/4.52	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.52	   first(active(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.52	   half(mark(X)) -> half(X)
12.69/4.52	   half(active(X)) -> half(X)
12.69/4.52	
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(1) DependencyPairsProof (EQUIVALENT)
12.69/4.52	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(2)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   ACTIVE(terms(N)) -> CONS(recip(sqr(N)), terms(s(N)))
12.69/4.52	   ACTIVE(terms(N)) -> RECIP(sqr(N))
12.69/4.52	   ACTIVE(terms(N)) -> SQR(N)
12.69/4.52	   ACTIVE(terms(N)) -> TERMS(s(N))
12.69/4.52	   ACTIVE(terms(N)) -> S(N)
12.69/4.52	   ACTIVE(sqr(0)) -> MARK(0)
12.69/4.52	   ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X))))
12.69/4.52	   ACTIVE(sqr(s(X))) -> S(add(sqr(X), dbl(X)))
12.69/4.52	   ACTIVE(sqr(s(X))) -> ADD(sqr(X), dbl(X))
12.69/4.52	   ACTIVE(sqr(s(X))) -> SQR(X)
12.69/4.52	   ACTIVE(sqr(s(X))) -> DBL(X)
12.69/4.52	   ACTIVE(dbl(0)) -> MARK(0)
12.69/4.52	   ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X))))
12.69/4.52	   ACTIVE(dbl(s(X))) -> S(s(dbl(X)))
12.69/4.52	   ACTIVE(dbl(s(X))) -> S(dbl(X))
12.69/4.52	   ACTIVE(dbl(s(X))) -> DBL(X)
12.69/4.52	   ACTIVE(add(0, X)) -> MARK(X)
12.69/4.52	   ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y)))
12.69/4.52	   ACTIVE(add(s(X), Y)) -> S(add(X, Y))
12.69/4.52	   ACTIVE(add(s(X), Y)) -> ADD(X, Y)
12.69/4.52	   ACTIVE(first(0, X)) -> MARK(nil)
12.69/4.52	   ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z)))
12.69/4.52	   ACTIVE(first(s(X), cons(Y, Z))) -> CONS(Y, first(X, Z))
12.69/4.52	   ACTIVE(first(s(X), cons(Y, Z))) -> FIRST(X, Z)
12.69/4.52	   ACTIVE(half(0)) -> MARK(0)
12.69/4.52	   ACTIVE(half(s(0))) -> MARK(0)
12.69/4.52	   ACTIVE(half(s(s(X)))) -> MARK(s(half(X)))
12.69/4.52	   ACTIVE(half(s(s(X)))) -> S(half(X))
12.69/4.52	   ACTIVE(half(s(s(X)))) -> HALF(X)
12.69/4.52	   ACTIVE(half(dbl(X))) -> MARK(X)
12.69/4.52	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.69/4.52	   MARK(terms(X)) -> TERMS(mark(X))
12.69/4.52	   MARK(terms(X)) -> MARK(X)
12.69/4.52	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.69/4.52	   MARK(cons(X1, X2)) -> CONS(mark(X1), X2)
12.69/4.52	   MARK(cons(X1, X2)) -> MARK(X1)
12.69/4.52	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.69/4.52	   MARK(recip(X)) -> RECIP(mark(X))
12.69/4.52	   MARK(recip(X)) -> MARK(X)
12.69/4.52	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.69/4.52	   MARK(sqr(X)) -> SQR(mark(X))
12.69/4.52	   MARK(sqr(X)) -> MARK(X)
12.69/4.52	   MARK(s(X)) -> ACTIVE(s(mark(X)))
12.69/4.52	   MARK(s(X)) -> S(mark(X))
12.69/4.52	   MARK(s(X)) -> MARK(X)
12.69/4.52	   MARK(0) -> ACTIVE(0)
12.69/4.52	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.69/4.52	   MARK(add(X1, X2)) -> ADD(mark(X1), mark(X2))
12.69/4.52	   MARK(add(X1, X2)) -> MARK(X1)
12.69/4.52	   MARK(add(X1, X2)) -> MARK(X2)
12.69/4.52	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.69/4.52	   MARK(dbl(X)) -> DBL(mark(X))
12.69/4.52	   MARK(dbl(X)) -> MARK(X)
12.69/4.52	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.69/4.52	   MARK(first(X1, X2)) -> FIRST(mark(X1), mark(X2))
12.69/4.52	   MARK(first(X1, X2)) -> MARK(X1)
12.69/4.52	   MARK(first(X1, X2)) -> MARK(X2)
12.69/4.52	   MARK(nil) -> ACTIVE(nil)
12.69/4.52	   MARK(half(X)) -> ACTIVE(half(mark(X)))
12.69/4.52	   MARK(half(X)) -> HALF(mark(X))
12.69/4.52	   MARK(half(X)) -> MARK(X)
12.69/4.52	   TERMS(mark(X)) -> TERMS(X)
12.69/4.52	   TERMS(active(X)) -> TERMS(X)
12.69/4.52	   CONS(mark(X1), X2) -> CONS(X1, X2)
12.69/4.52	   CONS(X1, mark(X2)) -> CONS(X1, X2)
12.69/4.52	   CONS(active(X1), X2) -> CONS(X1, X2)
12.69/4.52	   CONS(X1, active(X2)) -> CONS(X1, X2)
12.69/4.52	   RECIP(mark(X)) -> RECIP(X)
12.69/4.52	   RECIP(active(X)) -> RECIP(X)
12.69/4.52	   SQR(mark(X)) -> SQR(X)
12.69/4.52	   SQR(active(X)) -> SQR(X)
12.69/4.52	   S(mark(X)) -> S(X)
12.69/4.52	   S(active(X)) -> S(X)
12.69/4.52	   ADD(mark(X1), X2) -> ADD(X1, X2)
12.69/4.52	   ADD(X1, mark(X2)) -> ADD(X1, X2)
12.69/4.52	   ADD(active(X1), X2) -> ADD(X1, X2)
12.69/4.52	   ADD(X1, active(X2)) -> ADD(X1, X2)
12.69/4.52	   DBL(mark(X)) -> DBL(X)
12.69/4.52	   DBL(active(X)) -> DBL(X)
12.69/4.52	   FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.69/4.52	   FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.69/4.52	   FIRST(active(X1), X2) -> FIRST(X1, X2)
12.69/4.52	   FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.69/4.52	   HALF(mark(X)) -> HALF(X)
12.69/4.52	   HALF(active(X)) -> HALF(X)
12.69/4.52	
12.69/4.52	The TRS R consists of the following rules:
12.69/4.52	
12.69/4.52	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   active(sqr(0)) -> mark(0)
12.69/4.52	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.52	   active(dbl(0)) -> mark(0)
12.69/4.52	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.52	   active(add(0, X)) -> mark(X)
12.69/4.52	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.52	   active(first(0, X)) -> mark(nil)
12.69/4.52	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.52	   active(half(0)) -> mark(0)
12.69/4.52	   active(half(s(0))) -> mark(0)
12.69/4.52	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.52	   active(half(dbl(X))) -> mark(X)
12.69/4.52	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.52	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.52	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.52	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.52	   mark(s(X)) -> active(s(mark(X)))
12.69/4.52	   mark(0) -> active(0)
12.69/4.52	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.52	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.52	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.52	   mark(nil) -> active(nil)
12.69/4.52	   mark(half(X)) -> active(half(mark(X)))
12.69/4.52	   terms(mark(X)) -> terms(X)
12.69/4.52	   terms(active(X)) -> terms(X)
12.69/4.52	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.52	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.52	   recip(mark(X)) -> recip(X)
12.69/4.52	   recip(active(X)) -> recip(X)
12.69/4.52	   sqr(mark(X)) -> sqr(X)
12.69/4.52	   sqr(active(X)) -> sqr(X)
12.69/4.52	   s(mark(X)) -> s(X)
12.69/4.52	   s(active(X)) -> s(X)
12.69/4.52	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.52	   add(active(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.52	   dbl(mark(X)) -> dbl(X)
12.69/4.52	   dbl(active(X)) -> dbl(X)
12.69/4.52	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.52	   first(active(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.52	   half(mark(X)) -> half(X)
12.69/4.52	   half(active(X)) -> half(X)
12.69/4.52	
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(3) DependencyGraphProof (EQUIVALENT)
12.69/4.52	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 10 SCCs with 34 less nodes.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(4)
12.69/4.52	Complex Obligation (AND)
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(5)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   HALF(active(X)) -> HALF(X)
12.69/4.52	   HALF(mark(X)) -> HALF(X)
12.69/4.52	
12.69/4.52	The TRS R consists of the following rules:
12.69/4.52	
12.69/4.52	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   active(sqr(0)) -> mark(0)
12.69/4.52	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.52	   active(dbl(0)) -> mark(0)
12.69/4.52	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.52	   active(add(0, X)) -> mark(X)
12.69/4.52	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.52	   active(first(0, X)) -> mark(nil)
12.69/4.52	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.52	   active(half(0)) -> mark(0)
12.69/4.52	   active(half(s(0))) -> mark(0)
12.69/4.52	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.52	   active(half(dbl(X))) -> mark(X)
12.69/4.52	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.52	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.52	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.52	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.52	   mark(s(X)) -> active(s(mark(X)))
12.69/4.52	   mark(0) -> active(0)
12.69/4.52	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.52	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.52	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.52	   mark(nil) -> active(nil)
12.69/4.52	   mark(half(X)) -> active(half(mark(X)))
12.69/4.52	   terms(mark(X)) -> terms(X)
12.69/4.52	   terms(active(X)) -> terms(X)
12.69/4.52	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.52	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.52	   recip(mark(X)) -> recip(X)
12.69/4.52	   recip(active(X)) -> recip(X)
12.69/4.52	   sqr(mark(X)) -> sqr(X)
12.69/4.52	   sqr(active(X)) -> sqr(X)
12.69/4.52	   s(mark(X)) -> s(X)
12.69/4.52	   s(active(X)) -> s(X)
12.69/4.52	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.52	   add(active(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.52	   dbl(mark(X)) -> dbl(X)
12.69/4.52	   dbl(active(X)) -> dbl(X)
12.69/4.52	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.52	   first(active(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.52	   half(mark(X)) -> half(X)
12.69/4.52	   half(active(X)) -> half(X)
12.69/4.52	
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(6) UsableRulesProof (EQUIVALENT)
12.69/4.52	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(7)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   HALF(active(X)) -> HALF(X)
12.69/4.52	   HALF(mark(X)) -> HALF(X)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(8) QReductionProof (EQUIVALENT)
12.69/4.52	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.52	
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(9)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   HALF(active(X)) -> HALF(X)
12.69/4.52	   HALF(mark(X)) -> HALF(X)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(10) QDPSizeChangeProof (EQUIVALENT)
12.69/4.52	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.52	
12.69/4.52	From the DPs we obtained the following set of size-change graphs:
12.69/4.52	*HALF(active(X)) -> HALF(X)
12.69/4.52	The graph contains the following edges 1 > 1
12.69/4.52	
12.69/4.52	
12.69/4.52	*HALF(mark(X)) -> HALF(X)
12.69/4.52	The graph contains the following edges 1 > 1
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(11)
12.69/4.52	YES
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(12)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.69/4.52	   FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.69/4.52	   FIRST(active(X1), X2) -> FIRST(X1, X2)
12.69/4.52	   FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.69/4.52	
12.69/4.52	The TRS R consists of the following rules:
12.69/4.52	
12.69/4.52	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   active(sqr(0)) -> mark(0)
12.69/4.52	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.52	   active(dbl(0)) -> mark(0)
12.69/4.52	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.52	   active(add(0, X)) -> mark(X)
12.69/4.52	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.52	   active(first(0, X)) -> mark(nil)
12.69/4.52	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.52	   active(half(0)) -> mark(0)
12.69/4.52	   active(half(s(0))) -> mark(0)
12.69/4.52	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.52	   active(half(dbl(X))) -> mark(X)
12.69/4.52	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.52	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.52	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.52	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.52	   mark(s(X)) -> active(s(mark(X)))
12.69/4.52	   mark(0) -> active(0)
12.69/4.52	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.52	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.52	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.52	   mark(nil) -> active(nil)
12.69/4.52	   mark(half(X)) -> active(half(mark(X)))
12.69/4.52	   terms(mark(X)) -> terms(X)
12.69/4.52	   terms(active(X)) -> terms(X)
12.69/4.52	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.52	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.52	   recip(mark(X)) -> recip(X)
12.69/4.52	   recip(active(X)) -> recip(X)
12.69/4.52	   sqr(mark(X)) -> sqr(X)
12.69/4.52	   sqr(active(X)) -> sqr(X)
12.69/4.52	   s(mark(X)) -> s(X)
12.69/4.52	   s(active(X)) -> s(X)
12.69/4.52	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.52	   add(active(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.52	   dbl(mark(X)) -> dbl(X)
12.69/4.52	   dbl(active(X)) -> dbl(X)
12.69/4.52	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.52	   first(active(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.52	   half(mark(X)) -> half(X)
12.69/4.52	   half(active(X)) -> half(X)
12.69/4.52	
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(13) UsableRulesProof (EQUIVALENT)
12.69/4.52	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(14)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.69/4.52	   FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.69/4.52	   FIRST(active(X1), X2) -> FIRST(X1, X2)
12.69/4.52	   FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(15) QReductionProof (EQUIVALENT)
12.69/4.52	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.52	
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(16)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.69/4.52	   FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.69/4.52	   FIRST(active(X1), X2) -> FIRST(X1, X2)
12.69/4.52	   FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(17) QDPSizeChangeProof (EQUIVALENT)
12.69/4.52	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.52	
12.69/4.52	From the DPs we obtained the following set of size-change graphs:
12.69/4.52	*FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.69/4.52	The graph contains the following edges 1 >= 1, 2 > 2
12.69/4.52	
12.69/4.52	
12.69/4.52	*FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.69/4.52	The graph contains the following edges 1 > 1, 2 >= 2
12.69/4.52	
12.69/4.52	
12.69/4.52	*FIRST(active(X1), X2) -> FIRST(X1, X2)
12.69/4.52	The graph contains the following edges 1 > 1, 2 >= 2
12.69/4.52	
12.69/4.52	
12.69/4.52	*FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.69/4.52	The graph contains the following edges 1 >= 1, 2 > 2
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(18)
12.69/4.52	YES
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(19)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   DBL(active(X)) -> DBL(X)
12.69/4.52	   DBL(mark(X)) -> DBL(X)
12.69/4.52	
12.69/4.52	The TRS R consists of the following rules:
12.69/4.52	
12.69/4.52	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   active(sqr(0)) -> mark(0)
12.69/4.52	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.52	   active(dbl(0)) -> mark(0)
12.69/4.52	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.52	   active(add(0, X)) -> mark(X)
12.69/4.52	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.52	   active(first(0, X)) -> mark(nil)
12.69/4.52	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.52	   active(half(0)) -> mark(0)
12.69/4.52	   active(half(s(0))) -> mark(0)
12.69/4.52	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.52	   active(half(dbl(X))) -> mark(X)
12.69/4.52	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.52	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.52	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.52	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.52	   mark(s(X)) -> active(s(mark(X)))
12.69/4.52	   mark(0) -> active(0)
12.69/4.52	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.52	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.52	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.52	   mark(nil) -> active(nil)
12.69/4.52	   mark(half(X)) -> active(half(mark(X)))
12.69/4.52	   terms(mark(X)) -> terms(X)
12.69/4.52	   terms(active(X)) -> terms(X)
12.69/4.52	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.52	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.52	   recip(mark(X)) -> recip(X)
12.69/4.52	   recip(active(X)) -> recip(X)
12.69/4.52	   sqr(mark(X)) -> sqr(X)
12.69/4.52	   sqr(active(X)) -> sqr(X)
12.69/4.52	   s(mark(X)) -> s(X)
12.69/4.52	   s(active(X)) -> s(X)
12.69/4.52	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.52	   add(active(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.52	   dbl(mark(X)) -> dbl(X)
12.69/4.52	   dbl(active(X)) -> dbl(X)
12.69/4.52	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.52	   first(active(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.52	   half(mark(X)) -> half(X)
12.69/4.52	   half(active(X)) -> half(X)
12.69/4.52	
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(20) UsableRulesProof (EQUIVALENT)
12.69/4.52	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(21)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   DBL(active(X)) -> DBL(X)
12.69/4.52	   DBL(mark(X)) -> DBL(X)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(22) QReductionProof (EQUIVALENT)
12.69/4.52	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.52	
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(23)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   DBL(active(X)) -> DBL(X)
12.69/4.52	   DBL(mark(X)) -> DBL(X)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(24) QDPSizeChangeProof (EQUIVALENT)
12.69/4.52	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.52	
12.69/4.52	From the DPs we obtained the following set of size-change graphs:
12.69/4.52	*DBL(active(X)) -> DBL(X)
12.69/4.52	The graph contains the following edges 1 > 1
12.69/4.52	
12.69/4.52	
12.69/4.52	*DBL(mark(X)) -> DBL(X)
12.69/4.52	The graph contains the following edges 1 > 1
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(25)
12.69/4.52	YES
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(26)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   ADD(X1, mark(X2)) -> ADD(X1, X2)
12.69/4.52	   ADD(mark(X1), X2) -> ADD(X1, X2)
12.69/4.52	   ADD(active(X1), X2) -> ADD(X1, X2)
12.69/4.52	   ADD(X1, active(X2)) -> ADD(X1, X2)
12.69/4.52	
12.69/4.52	The TRS R consists of the following rules:
12.69/4.52	
12.69/4.52	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   active(sqr(0)) -> mark(0)
12.69/4.52	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.52	   active(dbl(0)) -> mark(0)
12.69/4.52	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.52	   active(add(0, X)) -> mark(X)
12.69/4.52	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.52	   active(first(0, X)) -> mark(nil)
12.69/4.52	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.52	   active(half(0)) -> mark(0)
12.69/4.52	   active(half(s(0))) -> mark(0)
12.69/4.52	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.52	   active(half(dbl(X))) -> mark(X)
12.69/4.52	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.52	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.52	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.52	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.52	   mark(s(X)) -> active(s(mark(X)))
12.69/4.52	   mark(0) -> active(0)
12.69/4.52	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.52	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.52	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.52	   mark(nil) -> active(nil)
12.69/4.52	   mark(half(X)) -> active(half(mark(X)))
12.69/4.52	   terms(mark(X)) -> terms(X)
12.69/4.52	   terms(active(X)) -> terms(X)
12.69/4.52	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.52	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.52	   recip(mark(X)) -> recip(X)
12.69/4.52	   recip(active(X)) -> recip(X)
12.69/4.52	   sqr(mark(X)) -> sqr(X)
12.69/4.52	   sqr(active(X)) -> sqr(X)
12.69/4.52	   s(mark(X)) -> s(X)
12.69/4.52	   s(active(X)) -> s(X)
12.69/4.52	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.52	   add(active(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.52	   dbl(mark(X)) -> dbl(X)
12.69/4.52	   dbl(active(X)) -> dbl(X)
12.69/4.52	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.52	   first(active(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.52	   half(mark(X)) -> half(X)
12.69/4.52	   half(active(X)) -> half(X)
12.69/4.52	
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(27) UsableRulesProof (EQUIVALENT)
12.69/4.52	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(28)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   ADD(X1, mark(X2)) -> ADD(X1, X2)
12.69/4.52	   ADD(mark(X1), X2) -> ADD(X1, X2)
12.69/4.52	   ADD(active(X1), X2) -> ADD(X1, X2)
12.69/4.52	   ADD(X1, active(X2)) -> ADD(X1, X2)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(29) QReductionProof (EQUIVALENT)
12.69/4.52	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.52	
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(30)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   ADD(X1, mark(X2)) -> ADD(X1, X2)
12.69/4.52	   ADD(mark(X1), X2) -> ADD(X1, X2)
12.69/4.52	   ADD(active(X1), X2) -> ADD(X1, X2)
12.69/4.52	   ADD(X1, active(X2)) -> ADD(X1, X2)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(31) QDPSizeChangeProof (EQUIVALENT)
12.69/4.52	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.52	
12.69/4.52	From the DPs we obtained the following set of size-change graphs:
12.69/4.52	*ADD(X1, mark(X2)) -> ADD(X1, X2)
12.69/4.52	The graph contains the following edges 1 >= 1, 2 > 2
12.69/4.52	
12.69/4.52	
12.69/4.52	*ADD(mark(X1), X2) -> ADD(X1, X2)
12.69/4.52	The graph contains the following edges 1 > 1, 2 >= 2
12.69/4.52	
12.69/4.52	
12.69/4.52	*ADD(active(X1), X2) -> ADD(X1, X2)
12.69/4.52	The graph contains the following edges 1 > 1, 2 >= 2
12.69/4.52	
12.69/4.52	
12.69/4.52	*ADD(X1, active(X2)) -> ADD(X1, X2)
12.69/4.52	The graph contains the following edges 1 >= 1, 2 > 2
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(32)
12.69/4.52	YES
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(33)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   S(active(X)) -> S(X)
12.69/4.52	   S(mark(X)) -> S(X)
12.69/4.52	
12.69/4.52	The TRS R consists of the following rules:
12.69/4.52	
12.69/4.52	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   active(sqr(0)) -> mark(0)
12.69/4.52	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.52	   active(dbl(0)) -> mark(0)
12.69/4.52	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.52	   active(add(0, X)) -> mark(X)
12.69/4.52	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.52	   active(first(0, X)) -> mark(nil)
12.69/4.52	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.52	   active(half(0)) -> mark(0)
12.69/4.52	   active(half(s(0))) -> mark(0)
12.69/4.52	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.52	   active(half(dbl(X))) -> mark(X)
12.69/4.52	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.52	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.52	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.52	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.52	   mark(s(X)) -> active(s(mark(X)))
12.69/4.52	   mark(0) -> active(0)
12.69/4.52	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.52	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.52	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.52	   mark(nil) -> active(nil)
12.69/4.52	   mark(half(X)) -> active(half(mark(X)))
12.69/4.52	   terms(mark(X)) -> terms(X)
12.69/4.52	   terms(active(X)) -> terms(X)
12.69/4.52	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.52	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.52	   recip(mark(X)) -> recip(X)
12.69/4.52	   recip(active(X)) -> recip(X)
12.69/4.52	   sqr(mark(X)) -> sqr(X)
12.69/4.52	   sqr(active(X)) -> sqr(X)
12.69/4.52	   s(mark(X)) -> s(X)
12.69/4.52	   s(active(X)) -> s(X)
12.69/4.52	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.52	   add(active(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.52	   dbl(mark(X)) -> dbl(X)
12.69/4.52	   dbl(active(X)) -> dbl(X)
12.69/4.52	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.52	   first(active(X1), X2) -> first(X1, X2)
12.69/4.52	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.52	   half(mark(X)) -> half(X)
12.69/4.52	   half(active(X)) -> half(X)
12.69/4.52	
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(34) UsableRulesProof (EQUIVALENT)
12.69/4.52	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(35)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   S(active(X)) -> S(X)
12.69/4.52	   S(mark(X)) -> S(X)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(36) QReductionProof (EQUIVALENT)
12.69/4.52	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.52	
12.69/4.52	   terms(mark(x0))
12.69/4.52	   terms(active(x0))
12.69/4.52	   cons(mark(x0), x1)
12.69/4.52	   cons(x0, mark(x1))
12.69/4.52	   cons(active(x0), x1)
12.69/4.52	   cons(x0, active(x1))
12.69/4.52	   recip(mark(x0))
12.69/4.52	   recip(active(x0))
12.69/4.52	   sqr(mark(x0))
12.69/4.52	   sqr(active(x0))
12.69/4.52	   s(mark(x0))
12.69/4.52	   s(active(x0))
12.69/4.52	   add(mark(x0), x1)
12.69/4.52	   add(x0, mark(x1))
12.69/4.52	   add(active(x0), x1)
12.69/4.52	   add(x0, active(x1))
12.69/4.52	   dbl(mark(x0))
12.69/4.52	   dbl(active(x0))
12.69/4.52	   first(mark(x0), x1)
12.69/4.52	   first(x0, mark(x1))
12.69/4.52	   first(active(x0), x1)
12.69/4.52	   first(x0, active(x1))
12.69/4.52	   half(mark(x0))
12.69/4.52	   half(active(x0))
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(37)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   S(active(X)) -> S(X)
12.69/4.52	   S(mark(X)) -> S(X)
12.69/4.52	
12.69/4.52	R is empty.
12.69/4.52	The set Q consists of the following terms:
12.69/4.52	
12.69/4.52	   active(terms(x0))
12.69/4.52	   active(sqr(0))
12.69/4.52	   active(sqr(s(x0)))
12.69/4.52	   active(dbl(0))
12.69/4.52	   active(dbl(s(x0)))
12.69/4.52	   active(add(0, x0))
12.69/4.52	   active(add(s(x0), x1))
12.69/4.52	   active(first(0, x0))
12.69/4.52	   active(first(s(x0), cons(x1, x2)))
12.69/4.52	   active(half(0))
12.69/4.52	   active(half(s(0)))
12.69/4.52	   active(half(s(s(x0))))
12.69/4.52	   active(half(dbl(x0)))
12.69/4.52	   mark(terms(x0))
12.69/4.52	   mark(cons(x0, x1))
12.69/4.52	   mark(recip(x0))
12.69/4.52	   mark(sqr(x0))
12.69/4.52	   mark(s(x0))
12.69/4.52	   mark(0)
12.69/4.52	   mark(add(x0, x1))
12.69/4.52	   mark(dbl(x0))
12.69/4.52	   mark(first(x0, x1))
12.69/4.52	   mark(nil)
12.69/4.52	   mark(half(x0))
12.69/4.52	
12.69/4.52	We have to consider all minimal (P,Q,R)-chains.
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(38) QDPSizeChangeProof (EQUIVALENT)
12.69/4.52	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.52	
12.69/4.52	From the DPs we obtained the following set of size-change graphs:
12.69/4.52	*S(active(X)) -> S(X)
12.69/4.52	The graph contains the following edges 1 > 1
12.69/4.52	
12.69/4.52	
12.69/4.52	*S(mark(X)) -> S(X)
12.69/4.52	The graph contains the following edges 1 > 1
12.69/4.52	
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(39)
12.69/4.52	YES
12.69/4.52	
12.69/4.52	----------------------------------------
12.69/4.52	
12.69/4.52	(40)
12.69/4.52	Obligation:
12.69/4.52	Q DP problem:
12.69/4.52	The TRS P consists of the following rules:
12.69/4.52	
12.69/4.52	   SQR(active(X)) -> SQR(X)
12.69/4.52	   SQR(mark(X)) -> SQR(X)
12.69/4.52	
12.69/4.52	The TRS R consists of the following rules:
12.69/4.52	
12.69/4.52	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.52	   active(sqr(0)) -> mark(0)
12.69/4.52	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.52	   active(dbl(0)) -> mark(0)
12.69/4.52	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.52	   active(add(0, X)) -> mark(X)
12.69/4.52	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.52	   active(first(0, X)) -> mark(nil)
12.69/4.52	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.52	   active(half(0)) -> mark(0)
12.69/4.52	   active(half(s(0))) -> mark(0)
12.69/4.52	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.52	   active(half(dbl(X))) -> mark(X)
12.69/4.52	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.52	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.52	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.52	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.52	   mark(s(X)) -> active(s(mark(X)))
12.69/4.52	   mark(0) -> active(0)
12.69/4.52	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.52	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.52	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.52	   mark(nil) -> active(nil)
12.69/4.52	   mark(half(X)) -> active(half(mark(X)))
12.69/4.52	   terms(mark(X)) -> terms(X)
12.69/4.52	   terms(active(X)) -> terms(X)
12.69/4.52	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.52	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.52	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.52	   recip(mark(X)) -> recip(X)
12.69/4.52	   recip(active(X)) -> recip(X)
12.69/4.52	   sqr(mark(X)) -> sqr(X)
12.69/4.52	   sqr(active(X)) -> sqr(X)
12.69/4.52	   s(mark(X)) -> s(X)
12.69/4.52	   s(active(X)) -> s(X)
12.69/4.52	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.52	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.52	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(41) UsableRulesProof (EQUIVALENT)
12.69/4.53	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(42)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   SQR(active(X)) -> SQR(X)
12.69/4.53	   SQR(mark(X)) -> SQR(X)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(43) QReductionProof (EQUIVALENT)
12.69/4.53	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.53	
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(44)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   SQR(active(X)) -> SQR(X)
12.69/4.53	   SQR(mark(X)) -> SQR(X)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(45) QDPSizeChangeProof (EQUIVALENT)
12.69/4.53	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.53	
12.69/4.53	From the DPs we obtained the following set of size-change graphs:
12.69/4.53	*SQR(active(X)) -> SQR(X)
12.69/4.53	The graph contains the following edges 1 > 1
12.69/4.53	
12.69/4.53	
12.69/4.53	*SQR(mark(X)) -> SQR(X)
12.69/4.53	The graph contains the following edges 1 > 1
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(46)
12.69/4.53	YES
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(47)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   RECIP(active(X)) -> RECIP(X)
12.69/4.53	   RECIP(mark(X)) -> RECIP(X)
12.69/4.53	
12.69/4.53	The TRS R consists of the following rules:
12.69/4.53	
12.69/4.53	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   active(sqr(0)) -> mark(0)
12.69/4.53	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.53	   active(dbl(0)) -> mark(0)
12.69/4.53	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.53	   active(add(0, X)) -> mark(X)
12.69/4.53	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.53	   active(first(0, X)) -> mark(nil)
12.69/4.53	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.53	   active(half(0)) -> mark(0)
12.69/4.53	   active(half(s(0))) -> mark(0)
12.69/4.53	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.53	   active(half(dbl(X))) -> mark(X)
12.69/4.53	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.53	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.53	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.53	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.53	   mark(s(X)) -> active(s(mark(X)))
12.69/4.53	   mark(0) -> active(0)
12.69/4.53	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.53	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.53	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.53	   mark(nil) -> active(nil)
12.69/4.53	   mark(half(X)) -> active(half(mark(X)))
12.69/4.53	   terms(mark(X)) -> terms(X)
12.69/4.53	   terms(active(X)) -> terms(X)
12.69/4.53	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.53	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.53	   recip(mark(X)) -> recip(X)
12.69/4.53	   recip(active(X)) -> recip(X)
12.69/4.53	   sqr(mark(X)) -> sqr(X)
12.69/4.53	   sqr(active(X)) -> sqr(X)
12.69/4.53	   s(mark(X)) -> s(X)
12.69/4.53	   s(active(X)) -> s(X)
12.69/4.53	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.53	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(48) UsableRulesProof (EQUIVALENT)
12.69/4.53	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(49)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   RECIP(active(X)) -> RECIP(X)
12.69/4.53	   RECIP(mark(X)) -> RECIP(X)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(50) QReductionProof (EQUIVALENT)
12.69/4.53	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.53	
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(51)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   RECIP(active(X)) -> RECIP(X)
12.69/4.53	   RECIP(mark(X)) -> RECIP(X)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(52) QDPSizeChangeProof (EQUIVALENT)
12.69/4.53	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.53	
12.69/4.53	From the DPs we obtained the following set of size-change graphs:
12.69/4.53	*RECIP(active(X)) -> RECIP(X)
12.69/4.53	The graph contains the following edges 1 > 1
12.69/4.53	
12.69/4.53	
12.69/4.53	*RECIP(mark(X)) -> RECIP(X)
12.69/4.53	The graph contains the following edges 1 > 1
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(53)
12.69/4.53	YES
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(54)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   CONS(X1, mark(X2)) -> CONS(X1, X2)
12.69/4.53	   CONS(mark(X1), X2) -> CONS(X1, X2)
12.69/4.53	   CONS(active(X1), X2) -> CONS(X1, X2)
12.69/4.53	   CONS(X1, active(X2)) -> CONS(X1, X2)
12.69/4.53	
12.69/4.53	The TRS R consists of the following rules:
12.69/4.53	
12.69/4.53	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   active(sqr(0)) -> mark(0)
12.69/4.53	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.53	   active(dbl(0)) -> mark(0)
12.69/4.53	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.53	   active(add(0, X)) -> mark(X)
12.69/4.53	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.53	   active(first(0, X)) -> mark(nil)
12.69/4.53	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.53	   active(half(0)) -> mark(0)
12.69/4.53	   active(half(s(0))) -> mark(0)
12.69/4.53	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.53	   active(half(dbl(X))) -> mark(X)
12.69/4.53	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.53	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.53	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.53	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.53	   mark(s(X)) -> active(s(mark(X)))
12.69/4.53	   mark(0) -> active(0)
12.69/4.53	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.53	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.53	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.53	   mark(nil) -> active(nil)
12.69/4.53	   mark(half(X)) -> active(half(mark(X)))
12.69/4.53	   terms(mark(X)) -> terms(X)
12.69/4.53	   terms(active(X)) -> terms(X)
12.69/4.53	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.53	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.53	   recip(mark(X)) -> recip(X)
12.69/4.53	   recip(active(X)) -> recip(X)
12.69/4.53	   sqr(mark(X)) -> sqr(X)
12.69/4.53	   sqr(active(X)) -> sqr(X)
12.69/4.53	   s(mark(X)) -> s(X)
12.69/4.53	   s(active(X)) -> s(X)
12.69/4.53	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.53	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(55) UsableRulesProof (EQUIVALENT)
12.69/4.53	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(56)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   CONS(X1, mark(X2)) -> CONS(X1, X2)
12.69/4.53	   CONS(mark(X1), X2) -> CONS(X1, X2)
12.69/4.53	   CONS(active(X1), X2) -> CONS(X1, X2)
12.69/4.53	   CONS(X1, active(X2)) -> CONS(X1, X2)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(57) QReductionProof (EQUIVALENT)
12.69/4.53	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.53	
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(58)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   CONS(X1, mark(X2)) -> CONS(X1, X2)
12.69/4.53	   CONS(mark(X1), X2) -> CONS(X1, X2)
12.69/4.53	   CONS(active(X1), X2) -> CONS(X1, X2)
12.69/4.53	   CONS(X1, active(X2)) -> CONS(X1, X2)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(59) QDPSizeChangeProof (EQUIVALENT)
12.69/4.53	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.53	
12.69/4.53	From the DPs we obtained the following set of size-change graphs:
12.69/4.53	*CONS(X1, mark(X2)) -> CONS(X1, X2)
12.69/4.53	The graph contains the following edges 1 >= 1, 2 > 2
12.69/4.53	
12.69/4.53	
12.69/4.53	*CONS(mark(X1), X2) -> CONS(X1, X2)
12.69/4.53	The graph contains the following edges 1 > 1, 2 >= 2
12.69/4.53	
12.69/4.53	
12.69/4.53	*CONS(active(X1), X2) -> CONS(X1, X2)
12.69/4.53	The graph contains the following edges 1 > 1, 2 >= 2
12.69/4.53	
12.69/4.53	
12.69/4.53	*CONS(X1, active(X2)) -> CONS(X1, X2)
12.69/4.53	The graph contains the following edges 1 >= 1, 2 > 2
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(60)
12.69/4.53	YES
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(61)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   TERMS(active(X)) -> TERMS(X)
12.69/4.53	   TERMS(mark(X)) -> TERMS(X)
12.69/4.53	
12.69/4.53	The TRS R consists of the following rules:
12.69/4.53	
12.69/4.53	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   active(sqr(0)) -> mark(0)
12.69/4.53	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.53	   active(dbl(0)) -> mark(0)
12.69/4.53	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.53	   active(add(0, X)) -> mark(X)
12.69/4.53	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.53	   active(first(0, X)) -> mark(nil)
12.69/4.53	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.53	   active(half(0)) -> mark(0)
12.69/4.53	   active(half(s(0))) -> mark(0)
12.69/4.53	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.53	   active(half(dbl(X))) -> mark(X)
12.69/4.53	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.53	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.53	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.53	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.53	   mark(s(X)) -> active(s(mark(X)))
12.69/4.53	   mark(0) -> active(0)
12.69/4.53	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.53	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.53	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.53	   mark(nil) -> active(nil)
12.69/4.53	   mark(half(X)) -> active(half(mark(X)))
12.69/4.53	   terms(mark(X)) -> terms(X)
12.69/4.53	   terms(active(X)) -> terms(X)
12.69/4.53	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.53	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.53	   recip(mark(X)) -> recip(X)
12.69/4.53	   recip(active(X)) -> recip(X)
12.69/4.53	   sqr(mark(X)) -> sqr(X)
12.69/4.53	   sqr(active(X)) -> sqr(X)
12.69/4.53	   s(mark(X)) -> s(X)
12.69/4.53	   s(active(X)) -> s(X)
12.69/4.53	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.53	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(62) UsableRulesProof (EQUIVALENT)
12.69/4.53	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(63)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   TERMS(active(X)) -> TERMS(X)
12.69/4.53	   TERMS(mark(X)) -> TERMS(X)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(64) QReductionProof (EQUIVALENT)
12.69/4.53	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.53	
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(65)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   TERMS(active(X)) -> TERMS(X)
12.69/4.53	   TERMS(mark(X)) -> TERMS(X)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(66) QDPSizeChangeProof (EQUIVALENT)
12.69/4.53	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.53	
12.69/4.53	From the DPs we obtained the following set of size-change graphs:
12.69/4.53	*TERMS(active(X)) -> TERMS(X)
12.69/4.53	The graph contains the following edges 1 > 1
12.69/4.53	
12.69/4.53	
12.69/4.53	*TERMS(mark(X)) -> TERMS(X)
12.69/4.53	The graph contains the following edges 1 > 1
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(67)
12.69/4.53	YES
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(68)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.69/4.53	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   MARK(cons(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.69/4.53	   ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X))))
12.69/4.53	   MARK(s(X)) -> ACTIVE(s(mark(X)))
12.69/4.53	   ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X))))
12.69/4.53	   MARK(s(X)) -> MARK(X)
12.69/4.53	   MARK(terms(X)) -> MARK(X)
12.69/4.53	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.69/4.53	   ACTIVE(add(0, X)) -> MARK(X)
12.69/4.53	   MARK(recip(X)) -> MARK(X)
12.69/4.53	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.69/4.53	   ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y)))
12.69/4.53	   ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z)))
12.69/4.53	   ACTIVE(half(s(s(X)))) -> MARK(s(half(X)))
12.69/4.53	   ACTIVE(half(dbl(X))) -> MARK(X)
12.69/4.53	   MARK(sqr(X)) -> MARK(X)
12.69/4.53	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.69/4.53	   MARK(add(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(add(X1, X2)) -> MARK(X2)
12.69/4.53	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.69/4.53	   MARK(dbl(X)) -> MARK(X)
12.69/4.53	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.69/4.53	   MARK(first(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(first(X1, X2)) -> MARK(X2)
12.69/4.53	   MARK(half(X)) -> ACTIVE(half(mark(X)))
12.69/4.53	   MARK(half(X)) -> MARK(X)
12.69/4.53	
12.69/4.53	The TRS R consists of the following rules:
12.69/4.53	
12.69/4.53	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   active(sqr(0)) -> mark(0)
12.69/4.53	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.53	   active(dbl(0)) -> mark(0)
12.69/4.53	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.53	   active(add(0, X)) -> mark(X)
12.69/4.53	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.53	   active(first(0, X)) -> mark(nil)
12.69/4.53	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.53	   active(half(0)) -> mark(0)
12.69/4.53	   active(half(s(0))) -> mark(0)
12.69/4.53	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.53	   active(half(dbl(X))) -> mark(X)
12.69/4.53	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.53	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.53	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.53	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.53	   mark(s(X)) -> active(s(mark(X)))
12.69/4.53	   mark(0) -> active(0)
12.69/4.53	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.53	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.53	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.53	   mark(nil) -> active(nil)
12.69/4.53	   mark(half(X)) -> active(half(mark(X)))
12.69/4.53	   terms(mark(X)) -> terms(X)
12.69/4.53	   terms(active(X)) -> terms(X)
12.69/4.53	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.53	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.53	   recip(mark(X)) -> recip(X)
12.69/4.53	   recip(active(X)) -> recip(X)
12.69/4.53	   sqr(mark(X)) -> sqr(X)
12.69/4.53	   sqr(active(X)) -> sqr(X)
12.69/4.53	   s(mark(X)) -> s(X)
12.69/4.53	   s(active(X)) -> s(X)
12.69/4.53	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.53	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(69) QDPQMonotonicMRRProof (EQUIVALENT)
12.69/4.53	By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain.
12.69/4.53	
12.69/4.53	Strictly oriented dependency pairs:
12.69/4.53	
12.69/4.53	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.69/4.53	   MARK(s(X)) -> ACTIVE(s(mark(X)))
12.69/4.53	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.69/4.53	
12.69/4.53	
12.69/4.53	Used ordering: Polynomial interpretation [POLO]:
12.69/4.53	
12.69/4.53	   POL(0) = 0
12.69/4.53	   POL(ACTIVE(x_1)) = 2*x_1
12.69/4.53	   POL(MARK(x_1)) = 2
12.69/4.53	   POL(active(x_1)) = 0
12.69/4.53	   POL(add(x_1, x_2)) = 1
12.69/4.53	   POL(cons(x_1, x_2)) = 0
12.69/4.53	   POL(dbl(x_1)) = 1
12.69/4.53	   POL(first(x_1, x_2)) = 1
12.69/4.53	   POL(half(x_1)) = 1
12.69/4.53	   POL(mark(x_1)) = 0
12.69/4.53	   POL(nil) = 0
12.69/4.53	   POL(recip(x_1)) = 0
12.69/4.53	   POL(s(x_1)) = 0
12.69/4.53	   POL(sqr(x_1)) = 1
12.69/4.53	   POL(terms(x_1)) = 1
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(70)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   MARK(cons(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.69/4.53	   ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X))))
12.69/4.53	   ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X))))
12.69/4.53	   MARK(s(X)) -> MARK(X)
12.69/4.53	   MARK(terms(X)) -> MARK(X)
12.69/4.53	   ACTIVE(add(0, X)) -> MARK(X)
12.69/4.53	   MARK(recip(X)) -> MARK(X)
12.69/4.53	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.69/4.53	   ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y)))
12.69/4.53	   ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z)))
12.69/4.53	   ACTIVE(half(s(s(X)))) -> MARK(s(half(X)))
12.69/4.53	   ACTIVE(half(dbl(X))) -> MARK(X)
12.69/4.53	   MARK(sqr(X)) -> MARK(X)
12.69/4.53	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.69/4.53	   MARK(add(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(add(X1, X2)) -> MARK(X2)
12.69/4.53	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.69/4.53	   MARK(dbl(X)) -> MARK(X)
12.69/4.53	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.69/4.53	   MARK(first(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(first(X1, X2)) -> MARK(X2)
12.69/4.53	   MARK(half(X)) -> ACTIVE(half(mark(X)))
12.69/4.53	   MARK(half(X)) -> MARK(X)
12.69/4.53	
12.69/4.53	The TRS R consists of the following rules:
12.69/4.53	
12.69/4.53	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   active(sqr(0)) -> mark(0)
12.69/4.53	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.53	   active(dbl(0)) -> mark(0)
12.69/4.53	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.53	   active(add(0, X)) -> mark(X)
12.69/4.53	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.53	   active(first(0, X)) -> mark(nil)
12.69/4.53	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.53	   active(half(0)) -> mark(0)
12.69/4.53	   active(half(s(0))) -> mark(0)
12.69/4.53	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.53	   active(half(dbl(X))) -> mark(X)
12.69/4.53	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.53	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.53	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.53	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.53	   mark(s(X)) -> active(s(mark(X)))
12.69/4.53	   mark(0) -> active(0)
12.69/4.53	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.53	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.53	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.53	   mark(nil) -> active(nil)
12.69/4.53	   mark(half(X)) -> active(half(mark(X)))
12.69/4.53	   terms(mark(X)) -> terms(X)
12.69/4.53	   terms(active(X)) -> terms(X)
12.69/4.53	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.53	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.53	   recip(mark(X)) -> recip(X)
12.69/4.53	   recip(active(X)) -> recip(X)
12.69/4.53	   sqr(mark(X)) -> sqr(X)
12.69/4.53	   sqr(active(X)) -> sqr(X)
12.69/4.53	   s(mark(X)) -> s(X)
12.69/4.53	   s(active(X)) -> s(X)
12.69/4.53	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.53	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(71) QDPOrderProof (EQUIVALENT)
12.69/4.53	We use the reduction pair processor [LPAR04,JAR06].
12.69/4.53	
12.69/4.53	
12.69/4.53	The following pairs can be oriented strictly and are deleted.
12.69/4.53	
12.69/4.53	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X))))
12.69/4.53	   ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X))))
12.69/4.53	   MARK(s(X)) -> MARK(X)
12.69/4.53	   MARK(terms(X)) -> MARK(X)
12.69/4.53	   ACTIVE(add(0, X)) -> MARK(X)
12.69/4.53	   ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y)))
12.69/4.53	   ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z)))
12.69/4.53	   ACTIVE(half(s(s(X)))) -> MARK(s(half(X)))
12.69/4.53	   ACTIVE(half(dbl(X))) -> MARK(X)
12.69/4.53	   MARK(sqr(X)) -> MARK(X)
12.69/4.53	   MARK(add(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(add(X1, X2)) -> MARK(X2)
12.69/4.53	   MARK(dbl(X)) -> MARK(X)
12.69/4.53	   MARK(first(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(first(X1, X2)) -> MARK(X2)
12.69/4.53	   MARK(half(X)) -> MARK(X)
12.69/4.53	The remaining pairs can at least be oriented weakly.
12.69/4.53	Used ordering:  Combined order from the following AFS and order.
12.69/4.53	ACTIVE(x1)  =  ACTIVE(x1)
12.69/4.53	
12.69/4.53	terms(x1)  =  terms(x1)
12.69/4.53	
12.69/4.53	MARK(x1)  =  MARK(x1)
12.69/4.53	
12.69/4.53	cons(x1, x2)  =  x1
12.69/4.53	
12.69/4.53	recip(x1)  =  x1
12.69/4.53	
12.69/4.53	sqr(x1)  =  sqr(x1)
12.69/4.53	
12.69/4.53	s(x1)  =  s(x1)
12.69/4.53	
12.69/4.53	mark(x1)  =  x1
12.69/4.53	
12.69/4.53	add(x1, x2)  =  add(x1, x2)
12.69/4.53	
12.69/4.53	dbl(x1)  =  dbl(x1)
12.69/4.53	
12.69/4.53	0  =  0
12.69/4.53	
12.69/4.53	first(x1, x2)  =  first(x1, x2)
12.69/4.53	
12.69/4.53	half(x1)  =  half(x1)
12.69/4.53	
12.69/4.53	active(x1)  =  x1
12.69/4.53	
12.69/4.53	nil  =  nil
12.69/4.53	
12.69/4.53	
12.69/4.53	Recursive path order with status [RPO].
12.69/4.53	Quasi-Precedence: [ACTIVE_1, terms_1, MARK_1, 0, first_2] > sqr_1 > add_2 > s_1
12.69/4.53	[ACTIVE_1, terms_1, MARK_1, 0, first_2] > sqr_1 > dbl_1 > s_1
12.69/4.53	[ACTIVE_1, terms_1, MARK_1, 0, first_2] > half_1 > s_1
12.69/4.53	[ACTIVE_1, terms_1, MARK_1, 0, first_2] > nil
12.69/4.53	
12.69/4.53	Status: ACTIVE_1: multiset status
12.69/4.53	terms_1: multiset status
12.69/4.53	MARK_1: multiset status
12.69/4.53	sqr_1: [1]
12.69/4.53	s_1: multiset status
12.69/4.53	add_2: [2,1]
12.69/4.53	dbl_1: [1]
12.69/4.53	0: multiset status
12.69/4.53	first_2: [1,2]
12.69/4.53	half_1: [1]
12.69/4.53	nil: multiset status
12.69/4.53	
12.69/4.53	
12.69/4.53	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
12.69/4.53	
12.69/4.53	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.53	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.53	   mark(s(X)) -> active(s(mark(X)))
12.69/4.53	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.53	   active(add(0, X)) -> mark(X)
12.69/4.53	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.53	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.53	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.53	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.53	   active(half(dbl(X))) -> mark(X)
12.69/4.53	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.53	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.53	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.53	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.53	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.53	   mark(half(X)) -> active(half(mark(X)))
12.69/4.53	   mark(0) -> active(0)
12.69/4.53	   mark(nil) -> active(nil)
12.69/4.53	   terms(active(X)) -> terms(X)
12.69/4.53	   terms(mark(X)) -> terms(X)
12.69/4.53	   sqr(active(X)) -> sqr(X)
12.69/4.53	   sqr(mark(X)) -> sqr(X)
12.69/4.53	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.53	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.53	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   active(sqr(0)) -> mark(0)
12.69/4.53	   active(dbl(0)) -> mark(0)
12.69/4.53	   active(first(0, X)) -> mark(nil)
12.69/4.53	   active(half(0)) -> mark(0)
12.69/4.53	   active(half(s(0))) -> mark(0)
12.69/4.53	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.53	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.53	   s(active(X)) -> s(X)
12.69/4.53	   s(mark(X)) -> s(X)
12.69/4.53	   recip(active(X)) -> recip(X)
12.69/4.53	   recip(mark(X)) -> recip(X)
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(72)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   MARK(cons(X1, X2)) -> MARK(X1)
12.69/4.53	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.69/4.53	   MARK(recip(X)) -> MARK(X)
12.69/4.53	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.69/4.53	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.69/4.53	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.69/4.53	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.69/4.53	   MARK(half(X)) -> ACTIVE(half(mark(X)))
12.69/4.53	
12.69/4.53	The TRS R consists of the following rules:
12.69/4.53	
12.69/4.53	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   active(sqr(0)) -> mark(0)
12.69/4.53	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.53	   active(dbl(0)) -> mark(0)
12.69/4.53	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.53	   active(add(0, X)) -> mark(X)
12.69/4.53	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.53	   active(first(0, X)) -> mark(nil)
12.69/4.53	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.53	   active(half(0)) -> mark(0)
12.69/4.53	   active(half(s(0))) -> mark(0)
12.69/4.53	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.53	   active(half(dbl(X))) -> mark(X)
12.69/4.53	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.53	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.53	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.53	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.53	   mark(s(X)) -> active(s(mark(X)))
12.69/4.53	   mark(0) -> active(0)
12.69/4.53	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.53	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.53	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.53	   mark(nil) -> active(nil)
12.69/4.53	   mark(half(X)) -> active(half(mark(X)))
12.69/4.53	   terms(mark(X)) -> terms(X)
12.69/4.53	   terms(active(X)) -> terms(X)
12.69/4.53	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.53	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.53	   recip(mark(X)) -> recip(X)
12.69/4.53	   recip(active(X)) -> recip(X)
12.69/4.53	   sqr(mark(X)) -> sqr(X)
12.69/4.53	   sqr(active(X)) -> sqr(X)
12.69/4.53	   s(mark(X)) -> s(X)
12.69/4.53	   s(active(X)) -> s(X)
12.69/4.53	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.53	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(73) DependencyGraphProof (EQUIVALENT)
12.69/4.53	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(74)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   MARK(recip(X)) -> MARK(X)
12.69/4.53	   MARK(cons(X1, X2)) -> MARK(X1)
12.69/4.53	
12.69/4.53	The TRS R consists of the following rules:
12.69/4.53	
12.69/4.53	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.69/4.53	   active(sqr(0)) -> mark(0)
12.69/4.53	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.69/4.53	   active(dbl(0)) -> mark(0)
12.69/4.53	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.69/4.53	   active(add(0, X)) -> mark(X)
12.69/4.53	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.69/4.53	   active(first(0, X)) -> mark(nil)
12.69/4.53	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.69/4.53	   active(half(0)) -> mark(0)
12.69/4.53	   active(half(s(0))) -> mark(0)
12.69/4.53	   active(half(s(s(X)))) -> mark(s(half(X)))
12.69/4.53	   active(half(dbl(X))) -> mark(X)
12.69/4.53	   mark(terms(X)) -> active(terms(mark(X)))
12.69/4.53	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.69/4.53	   mark(recip(X)) -> active(recip(mark(X)))
12.69/4.53	   mark(sqr(X)) -> active(sqr(mark(X)))
12.69/4.53	   mark(s(X)) -> active(s(mark(X)))
12.69/4.53	   mark(0) -> active(0)
12.69/4.53	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.69/4.53	   mark(dbl(X)) -> active(dbl(mark(X)))
12.69/4.53	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.69/4.53	   mark(nil) -> active(nil)
12.69/4.53	   mark(half(X)) -> active(half(mark(X)))
12.69/4.53	   terms(mark(X)) -> terms(X)
12.69/4.53	   terms(active(X)) -> terms(X)
12.69/4.53	   cons(mark(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, mark(X2)) -> cons(X1, X2)
12.69/4.53	   cons(active(X1), X2) -> cons(X1, X2)
12.69/4.53	   cons(X1, active(X2)) -> cons(X1, X2)
12.69/4.53	   recip(mark(X)) -> recip(X)
12.69/4.53	   recip(active(X)) -> recip(X)
12.69/4.53	   sqr(mark(X)) -> sqr(X)
12.69/4.53	   sqr(active(X)) -> sqr(X)
12.69/4.53	   s(mark(X)) -> s(X)
12.69/4.53	   s(active(X)) -> s(X)
12.69/4.53	   add(mark(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, mark(X2)) -> add(X1, X2)
12.69/4.53	   add(active(X1), X2) -> add(X1, X2)
12.69/4.53	   add(X1, active(X2)) -> add(X1, X2)
12.69/4.53	   dbl(mark(X)) -> dbl(X)
12.69/4.53	   dbl(active(X)) -> dbl(X)
12.69/4.53	   first(mark(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, mark(X2)) -> first(X1, X2)
12.69/4.53	   first(active(X1), X2) -> first(X1, X2)
12.69/4.53	   first(X1, active(X2)) -> first(X1, X2)
12.69/4.53	   half(mark(X)) -> half(X)
12.69/4.53	   half(active(X)) -> half(X)
12.69/4.53	
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(75) UsableRulesProof (EQUIVALENT)
12.69/4.53	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(76)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   MARK(recip(X)) -> MARK(X)
12.69/4.53	   MARK(cons(X1, X2)) -> MARK(X1)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(77) QReductionProof (EQUIVALENT)
12.69/4.53	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.69/4.53	
12.69/4.53	   active(terms(x0))
12.69/4.53	   active(sqr(0))
12.69/4.53	   active(sqr(s(x0)))
12.69/4.53	   active(dbl(0))
12.69/4.53	   active(dbl(s(x0)))
12.69/4.53	   active(add(0, x0))
12.69/4.53	   active(add(s(x0), x1))
12.69/4.53	   active(first(0, x0))
12.69/4.53	   active(first(s(x0), cons(x1, x2)))
12.69/4.53	   active(half(0))
12.69/4.53	   active(half(s(0)))
12.69/4.53	   active(half(s(s(x0))))
12.69/4.53	   active(half(dbl(x0)))
12.69/4.53	   mark(terms(x0))
12.69/4.53	   mark(cons(x0, x1))
12.69/4.53	   mark(recip(x0))
12.69/4.53	   mark(sqr(x0))
12.69/4.53	   mark(s(x0))
12.69/4.53	   mark(0)
12.69/4.53	   mark(add(x0, x1))
12.69/4.53	   mark(dbl(x0))
12.69/4.53	   mark(first(x0, x1))
12.69/4.53	   mark(nil)
12.69/4.53	   mark(half(x0))
12.69/4.53	   terms(mark(x0))
12.69/4.53	   terms(active(x0))
12.69/4.53	   sqr(mark(x0))
12.69/4.53	   sqr(active(x0))
12.69/4.53	   s(mark(x0))
12.69/4.53	   s(active(x0))
12.69/4.53	   add(mark(x0), x1)
12.69/4.53	   add(x0, mark(x1))
12.69/4.53	   add(active(x0), x1)
12.69/4.53	   add(x0, active(x1))
12.69/4.53	   dbl(mark(x0))
12.69/4.53	   dbl(active(x0))
12.69/4.53	   first(mark(x0), x1)
12.69/4.53	   first(x0, mark(x1))
12.69/4.53	   first(active(x0), x1)
12.69/4.53	   first(x0, active(x1))
12.69/4.53	   half(mark(x0))
12.69/4.53	   half(active(x0))
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(78)
12.69/4.53	Obligation:
12.69/4.53	Q DP problem:
12.69/4.53	The TRS P consists of the following rules:
12.69/4.53	
12.69/4.53	   MARK(recip(X)) -> MARK(X)
12.69/4.53	   MARK(cons(X1, X2)) -> MARK(X1)
12.69/4.53	
12.69/4.53	R is empty.
12.69/4.53	The set Q consists of the following terms:
12.69/4.53	
12.69/4.53	   cons(mark(x0), x1)
12.69/4.53	   cons(x0, mark(x1))
12.69/4.53	   cons(active(x0), x1)
12.69/4.53	   cons(x0, active(x1))
12.69/4.53	   recip(mark(x0))
12.69/4.53	   recip(active(x0))
12.69/4.53	
12.69/4.53	We have to consider all minimal (P,Q,R)-chains.
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(79) QDPSizeChangeProof (EQUIVALENT)
12.69/4.53	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
12.69/4.53	
12.69/4.53	From the DPs we obtained the following set of size-change graphs:
12.69/4.53	*MARK(recip(X)) -> MARK(X)
12.69/4.53	The graph contains the following edges 1 > 1
12.69/4.53	
12.69/4.53	
12.69/4.53	*MARK(cons(X1, X2)) -> MARK(X1)
12.69/4.53	The graph contains the following edges 1 > 1
12.69/4.53	
12.69/4.53	
12.69/4.53	----------------------------------------
12.69/4.53	
12.69/4.53	(80)
12.69/4.53	YES
13.52/4.55	EOF