12.61/5.07	YES
12.61/5.08	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
12.61/5.08	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.61/5.08	
12.61/5.08	
12.61/5.08	Termination w.r.t. Q of the given QTRS could be proven:
12.61/5.08	
12.61/5.08	(0) QTRS
12.61/5.08	(1) DependencyPairsProof [EQUIVALENT, 3 ms]
12.61/5.08	(2) QDP
12.61/5.08	(3) DependencyGraphProof [EQUIVALENT, 1 ms]
12.61/5.08	(4) AND
12.61/5.08	    (5) QDP
12.61/5.08	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (7) QDP
12.61/5.08	        (8) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (9) QDP
12.61/5.08	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (11) YES
12.61/5.08	    (12) QDP
12.61/5.08	        (13) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (14) QDP
12.61/5.08	        (15) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (16) QDP
12.61/5.08	        (17) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (18) YES
12.61/5.08	    (19) QDP
12.61/5.08	        (20) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (21) QDP
12.61/5.08	        (22) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (23) QDP
12.61/5.08	        (24) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (25) YES
12.61/5.08	    (26) QDP
12.61/5.08	        (27) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (28) QDP
12.61/5.08	        (29) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (30) QDP
12.61/5.08	        (31) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (32) YES
12.61/5.08	    (33) QDP
12.61/5.08	        (34) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (35) QDP
12.61/5.08	        (36) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (37) QDP
12.61/5.08	        (38) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (39) YES
12.61/5.08	    (40) QDP
12.61/5.08	        (41) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (42) QDP
12.61/5.08	        (43) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (44) QDP
12.61/5.08	        (45) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (46) YES
12.61/5.08	    (47) QDP
12.61/5.08	        (48) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (49) QDP
12.61/5.08	        (50) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (51) QDP
12.61/5.08	        (52) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (53) YES
12.61/5.08	    (54) QDP
12.61/5.08	        (55) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (56) QDP
12.61/5.08	        (57) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (58) QDP
12.61/5.08	        (59) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (60) YES
12.61/5.08	    (61) QDP
12.61/5.08	        (62) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (63) QDP
12.61/5.08	        (64) QDPOrderProof [EQUIVALENT, 80 ms]
12.61/5.08	        (65) QDP
12.61/5.08	        (66) QDPOrderProof [EQUIVALENT, 39 ms]
12.61/5.08	        (67) QDP
12.61/5.08	        (68) QDPQMonotonicMRRProof [EQUIVALENT, 90 ms]
12.61/5.08	        (69) QDP
12.61/5.08	        (70) QDPOrderProof [EQUIVALENT, 63 ms]
12.61/5.08	        (71) QDP
12.61/5.08	        (72) DependencyGraphProof [EQUIVALENT, 0 ms]
12.61/5.08	        (73) QDP
12.61/5.08	        (74) UsableRulesProof [EQUIVALENT, 0 ms]
12.61/5.08	        (75) QDP
12.61/5.08	        (76) QReductionProof [EQUIVALENT, 0 ms]
12.61/5.08	        (77) QDP
12.61/5.08	        (78) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.61/5.08	        (79) YES
12.61/5.08	
12.61/5.08	
12.61/5.08	----------------------------------------
12.61/5.08	
12.61/5.08	(0)
12.61/5.08	Obligation:
12.61/5.08	Q restricted rewrite system:
12.61/5.08	The TRS R consists of the following rules:
12.61/5.08	
12.61/5.08	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.61/5.08	   active(sqr(0)) -> mark(0)
12.61/5.08	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.61/5.08	   active(dbl(0)) -> mark(0)
12.61/5.08	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.61/5.08	   active(add(0, X)) -> mark(X)
12.61/5.08	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.61/5.08	   active(first(0, X)) -> mark(nil)
12.61/5.08	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.61/5.08	   mark(terms(X)) -> active(terms(mark(X)))
12.61/5.08	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.61/5.08	   mark(recip(X)) -> active(recip(mark(X)))
12.61/5.08	   mark(sqr(X)) -> active(sqr(mark(X)))
12.61/5.08	   mark(s(X)) -> active(s(X))
12.61/5.08	   mark(0) -> active(0)
12.61/5.08	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.61/5.08	   mark(dbl(X)) -> active(dbl(mark(X)))
12.61/5.08	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.61/5.08	   mark(nil) -> active(nil)
12.61/5.08	   terms(mark(X)) -> terms(X)
12.61/5.08	   terms(active(X)) -> terms(X)
12.61/5.08	   cons(mark(X1), X2) -> cons(X1, X2)
12.61/5.08	   cons(X1, mark(X2)) -> cons(X1, X2)
12.61/5.08	   cons(active(X1), X2) -> cons(X1, X2)
12.61/5.08	   cons(X1, active(X2)) -> cons(X1, X2)
12.61/5.08	   recip(mark(X)) -> recip(X)
12.61/5.08	   recip(active(X)) -> recip(X)
12.61/5.08	   sqr(mark(X)) -> sqr(X)
12.61/5.08	   sqr(active(X)) -> sqr(X)
12.61/5.08	   s(mark(X)) -> s(X)
12.61/5.08	   s(active(X)) -> s(X)
12.61/5.08	   add(mark(X1), X2) -> add(X1, X2)
12.61/5.08	   add(X1, mark(X2)) -> add(X1, X2)
12.61/5.08	   add(active(X1), X2) -> add(X1, X2)
12.61/5.08	   add(X1, active(X2)) -> add(X1, X2)
12.61/5.08	   dbl(mark(X)) -> dbl(X)
12.61/5.08	   dbl(active(X)) -> dbl(X)
12.61/5.08	   first(mark(X1), X2) -> first(X1, X2)
12.61/5.08	   first(X1, mark(X2)) -> first(X1, X2)
12.61/5.08	   first(active(X1), X2) -> first(X1, X2)
12.61/5.08	   first(X1, active(X2)) -> first(X1, X2)
12.61/5.08	
12.61/5.08	The set Q consists of the following terms:
12.61/5.08	
12.61/5.08	   active(terms(x0))
12.61/5.08	   active(sqr(0))
12.61/5.08	   active(sqr(s(x0)))
12.61/5.08	   active(dbl(0))
12.61/5.08	   active(dbl(s(x0)))
12.61/5.08	   active(add(0, x0))
12.61/5.08	   active(add(s(x0), x1))
12.61/5.08	   active(first(0, x0))
12.61/5.08	   active(first(s(x0), cons(x1, x2)))
12.61/5.08	   mark(terms(x0))
12.61/5.08	   mark(cons(x0, x1))
12.61/5.08	   mark(recip(x0))
12.61/5.08	   mark(sqr(x0))
12.61/5.08	   mark(s(x0))
12.61/5.08	   mark(0)
12.61/5.08	   mark(add(x0, x1))
12.61/5.08	   mark(dbl(x0))
12.61/5.08	   mark(first(x0, x1))
12.61/5.08	   mark(nil)
12.61/5.08	   terms(mark(x0))
12.61/5.08	   terms(active(x0))
12.61/5.08	   cons(mark(x0), x1)
12.61/5.08	   cons(x0, mark(x1))
12.61/5.08	   cons(active(x0), x1)
12.61/5.08	   cons(x0, active(x1))
12.61/5.08	   recip(mark(x0))
12.61/5.08	   recip(active(x0))
12.61/5.08	   sqr(mark(x0))
12.61/5.08	   sqr(active(x0))
12.61/5.08	   s(mark(x0))
12.61/5.08	   s(active(x0))
12.61/5.08	   add(mark(x0), x1)
12.61/5.08	   add(x0, mark(x1))
12.61/5.08	   add(active(x0), x1)
12.61/5.08	   add(x0, active(x1))
12.61/5.08	   dbl(mark(x0))
12.61/5.08	   dbl(active(x0))
12.61/5.08	   first(mark(x0), x1)
12.61/5.08	   first(x0, mark(x1))
12.61/5.08	   first(active(x0), x1)
12.61/5.08	   first(x0, active(x1))
12.61/5.08	
12.61/5.08	
12.61/5.08	----------------------------------------
12.61/5.08	
12.61/5.08	(1) DependencyPairsProof (EQUIVALENT)
12.61/5.08	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
12.61/5.08	----------------------------------------
12.61/5.08	
12.61/5.08	(2)
12.61/5.08	Obligation:
12.61/5.08	Q DP problem:
12.61/5.08	The TRS P consists of the following rules:
12.61/5.08	
12.61/5.08	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.61/5.08	   ACTIVE(terms(N)) -> CONS(recip(sqr(N)), terms(s(N)))
12.61/5.08	   ACTIVE(terms(N)) -> RECIP(sqr(N))
12.61/5.08	   ACTIVE(terms(N)) -> SQR(N)
12.61/5.08	   ACTIVE(terms(N)) -> TERMS(s(N))
12.61/5.08	   ACTIVE(terms(N)) -> S(N)
12.61/5.08	   ACTIVE(sqr(0)) -> MARK(0)
12.61/5.08	   ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X))))
12.61/5.08	   ACTIVE(sqr(s(X))) -> S(add(sqr(X), dbl(X)))
12.61/5.08	   ACTIVE(sqr(s(X))) -> ADD(sqr(X), dbl(X))
12.61/5.08	   ACTIVE(sqr(s(X))) -> SQR(X)
12.61/5.08	   ACTIVE(sqr(s(X))) -> DBL(X)
12.61/5.08	   ACTIVE(dbl(0)) -> MARK(0)
12.61/5.08	   ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X))))
12.61/5.08	   ACTIVE(dbl(s(X))) -> S(s(dbl(X)))
12.61/5.08	   ACTIVE(dbl(s(X))) -> S(dbl(X))
12.61/5.08	   ACTIVE(dbl(s(X))) -> DBL(X)
12.61/5.09	   ACTIVE(add(0, X)) -> MARK(X)
12.61/5.09	   ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y)))
12.61/5.09	   ACTIVE(add(s(X), Y)) -> S(add(X, Y))
12.61/5.09	   ACTIVE(add(s(X), Y)) -> ADD(X, Y)
12.61/5.09	   ACTIVE(first(0, X)) -> MARK(nil)
12.61/5.09	   ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z)))
12.61/5.09	   ACTIVE(first(s(X), cons(Y, Z))) -> CONS(Y, first(X, Z))
12.61/5.09	   ACTIVE(first(s(X), cons(Y, Z))) -> FIRST(X, Z)
12.61/5.09	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.61/5.09	   MARK(terms(X)) -> TERMS(mark(X))
12.61/5.09	   MARK(terms(X)) -> MARK(X)
12.61/5.09	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.61/5.09	   MARK(cons(X1, X2)) -> CONS(mark(X1), X2)
12.61/5.09	   MARK(cons(X1, X2)) -> MARK(X1)
12.61/5.09	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.61/5.09	   MARK(recip(X)) -> RECIP(mark(X))
12.61/5.09	   MARK(recip(X)) -> MARK(X)
12.61/5.09	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.61/5.09	   MARK(sqr(X)) -> SQR(mark(X))
12.61/5.09	   MARK(sqr(X)) -> MARK(X)
12.61/5.09	   MARK(s(X)) -> ACTIVE(s(X))
12.61/5.09	   MARK(0) -> ACTIVE(0)
12.61/5.09	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.61/5.09	   MARK(add(X1, X2)) -> ADD(mark(X1), mark(X2))
12.61/5.09	   MARK(add(X1, X2)) -> MARK(X1)
12.61/5.09	   MARK(add(X1, X2)) -> MARK(X2)
12.61/5.09	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.61/5.09	   MARK(dbl(X)) -> DBL(mark(X))
12.61/5.09	   MARK(dbl(X)) -> MARK(X)
12.61/5.09	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.61/5.09	   MARK(first(X1, X2)) -> FIRST(mark(X1), mark(X2))
12.61/5.09	   MARK(first(X1, X2)) -> MARK(X1)
12.61/5.09	   MARK(first(X1, X2)) -> MARK(X2)
12.61/5.09	   MARK(nil) -> ACTIVE(nil)
12.61/5.09	   TERMS(mark(X)) -> TERMS(X)
12.61/5.09	   TERMS(active(X)) -> TERMS(X)
12.61/5.09	   CONS(mark(X1), X2) -> CONS(X1, X2)
12.61/5.09	   CONS(X1, mark(X2)) -> CONS(X1, X2)
12.61/5.09	   CONS(active(X1), X2) -> CONS(X1, X2)
12.61/5.09	   CONS(X1, active(X2)) -> CONS(X1, X2)
12.61/5.09	   RECIP(mark(X)) -> RECIP(X)
12.61/5.09	   RECIP(active(X)) -> RECIP(X)
12.61/5.09	   SQR(mark(X)) -> SQR(X)
12.61/5.09	   SQR(active(X)) -> SQR(X)
12.61/5.09	   S(mark(X)) -> S(X)
12.61/5.09	   S(active(X)) -> S(X)
12.61/5.09	   ADD(mark(X1), X2) -> ADD(X1, X2)
12.61/5.09	   ADD(X1, mark(X2)) -> ADD(X1, X2)
12.61/5.09	   ADD(active(X1), X2) -> ADD(X1, X2)
12.61/5.09	   ADD(X1, active(X2)) -> ADD(X1, X2)
12.61/5.09	   DBL(mark(X)) -> DBL(X)
12.61/5.09	   DBL(active(X)) -> DBL(X)
12.61/5.09	   FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.61/5.09	   FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.61/5.09	   FIRST(active(X1), X2) -> FIRST(X1, X2)
12.61/5.09	   FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.61/5.09	
12.61/5.09	The TRS R consists of the following rules:
12.61/5.09	
12.61/5.09	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.61/5.09	   active(sqr(0)) -> mark(0)
12.61/5.09	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.61/5.09	   active(dbl(0)) -> mark(0)
12.61/5.09	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.61/5.09	   active(add(0, X)) -> mark(X)
12.61/5.09	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.61/5.09	   active(first(0, X)) -> mark(nil)
12.61/5.09	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.61/5.09	   mark(terms(X)) -> active(terms(mark(X)))
12.61/5.09	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.61/5.09	   mark(recip(X)) -> active(recip(mark(X)))
12.61/5.09	   mark(sqr(X)) -> active(sqr(mark(X)))
12.61/5.09	   mark(s(X)) -> active(s(X))
12.61/5.09	   mark(0) -> active(0)
12.61/5.09	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.61/5.09	   mark(dbl(X)) -> active(dbl(mark(X)))
12.61/5.09	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.61/5.09	   mark(nil) -> active(nil)
12.61/5.09	   terms(mark(X)) -> terms(X)
12.61/5.09	   terms(active(X)) -> terms(X)
12.61/5.09	   cons(mark(X1), X2) -> cons(X1, X2)
12.61/5.09	   cons(X1, mark(X2)) -> cons(X1, X2)
12.61/5.09	   cons(active(X1), X2) -> cons(X1, X2)
12.61/5.09	   cons(X1, active(X2)) -> cons(X1, X2)
12.61/5.09	   recip(mark(X)) -> recip(X)
12.61/5.09	   recip(active(X)) -> recip(X)
12.61/5.09	   sqr(mark(X)) -> sqr(X)
12.61/5.09	   sqr(active(X)) -> sqr(X)
12.61/5.09	   s(mark(X)) -> s(X)
12.61/5.09	   s(active(X)) -> s(X)
12.61/5.09	   add(mark(X1), X2) -> add(X1, X2)
12.61/5.09	   add(X1, mark(X2)) -> add(X1, X2)
12.61/5.09	   add(active(X1), X2) -> add(X1, X2)
12.61/5.09	   add(X1, active(X2)) -> add(X1, X2)
12.61/5.09	   dbl(mark(X)) -> dbl(X)
12.61/5.09	   dbl(active(X)) -> dbl(X)
12.61/5.09	   first(mark(X1), X2) -> first(X1, X2)
12.61/5.09	   first(X1, mark(X2)) -> first(X1, X2)
12.61/5.09	   first(active(X1), X2) -> first(X1, X2)
12.61/5.09	   first(X1, active(X2)) -> first(X1, X2)
12.61/5.09	
12.61/5.09	The set Q consists of the following terms:
12.61/5.09	
12.61/5.09	   active(terms(x0))
12.61/5.09	   active(sqr(0))
12.61/5.09	   active(sqr(s(x0)))
12.61/5.09	   active(dbl(0))
12.61/5.09	   active(dbl(s(x0)))
12.61/5.09	   active(add(0, x0))
12.61/5.09	   active(add(s(x0), x1))
12.61/5.09	   active(first(0, x0))
12.61/5.09	   active(first(s(x0), cons(x1, x2)))
12.61/5.09	   mark(terms(x0))
12.61/5.09	   mark(cons(x0, x1))
12.61/5.09	   mark(recip(x0))
12.61/5.09	   mark(sqr(x0))
12.61/5.09	   mark(s(x0))
12.61/5.09	   mark(0)
12.61/5.09	   mark(add(x0, x1))
12.61/5.09	   mark(dbl(x0))
12.61/5.09	   mark(first(x0, x1))
12.61/5.09	   mark(nil)
12.61/5.09	   terms(mark(x0))
12.61/5.09	   terms(active(x0))
12.61/5.09	   cons(mark(x0), x1)
12.61/5.09	   cons(x0, mark(x1))
12.61/5.09	   cons(active(x0), x1)
12.61/5.09	   cons(x0, active(x1))
12.61/5.09	   recip(mark(x0))
12.61/5.09	   recip(active(x0))
12.61/5.09	   sqr(mark(x0))
12.61/5.09	   sqr(active(x0))
12.61/5.09	   s(mark(x0))
12.61/5.09	   s(active(x0))
12.61/5.09	   add(mark(x0), x1)
12.61/5.09	   add(x0, mark(x1))
12.61/5.09	   add(active(x0), x1)
12.61/5.09	   add(x0, active(x1))
12.61/5.09	   dbl(mark(x0))
12.61/5.09	   dbl(active(x0))
12.61/5.09	   first(mark(x0), x1)
12.61/5.09	   first(x0, mark(x1))
12.61/5.09	   first(active(x0), x1)
12.61/5.09	   first(x0, active(x1))
12.61/5.09	
12.61/5.09	We have to consider all minimal (P,Q,R)-chains.
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(3) DependencyGraphProof (EQUIVALENT)
12.61/5.09	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 9 SCCs with 32 less nodes.
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(4)
12.61/5.09	Complex Obligation (AND)
12.61/5.09	
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(5)
12.61/5.09	Obligation:
12.61/5.09	Q DP problem:
12.61/5.09	The TRS P consists of the following rules:
12.61/5.09	
12.61/5.09	   FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.61/5.09	   FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.61/5.09	   FIRST(active(X1), X2) -> FIRST(X1, X2)
12.61/5.09	   FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.61/5.09	
12.61/5.09	The TRS R consists of the following rules:
12.61/5.09	
12.61/5.09	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.61/5.09	   active(sqr(0)) -> mark(0)
12.61/5.09	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.61/5.09	   active(dbl(0)) -> mark(0)
12.61/5.09	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.61/5.09	   active(add(0, X)) -> mark(X)
12.61/5.09	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.61/5.09	   active(first(0, X)) -> mark(nil)
12.61/5.09	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.61/5.09	   mark(terms(X)) -> active(terms(mark(X)))
12.61/5.09	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.61/5.09	   mark(recip(X)) -> active(recip(mark(X)))
12.61/5.09	   mark(sqr(X)) -> active(sqr(mark(X)))
12.61/5.09	   mark(s(X)) -> active(s(X))
12.61/5.09	   mark(0) -> active(0)
12.61/5.09	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.61/5.09	   mark(dbl(X)) -> active(dbl(mark(X)))
12.61/5.09	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.61/5.09	   mark(nil) -> active(nil)
12.61/5.09	   terms(mark(X)) -> terms(X)
12.61/5.09	   terms(active(X)) -> terms(X)
12.61/5.09	   cons(mark(X1), X2) -> cons(X1, X2)
12.61/5.09	   cons(X1, mark(X2)) -> cons(X1, X2)
12.61/5.09	   cons(active(X1), X2) -> cons(X1, X2)
12.61/5.09	   cons(X1, active(X2)) -> cons(X1, X2)
12.61/5.09	   recip(mark(X)) -> recip(X)
12.61/5.09	   recip(active(X)) -> recip(X)
12.61/5.09	   sqr(mark(X)) -> sqr(X)
12.61/5.09	   sqr(active(X)) -> sqr(X)
12.61/5.09	   s(mark(X)) -> s(X)
12.61/5.09	   s(active(X)) -> s(X)
12.61/5.09	   add(mark(X1), X2) -> add(X1, X2)
12.61/5.09	   add(X1, mark(X2)) -> add(X1, X2)
12.61/5.09	   add(active(X1), X2) -> add(X1, X2)
12.61/5.09	   add(X1, active(X2)) -> add(X1, X2)
12.61/5.09	   dbl(mark(X)) -> dbl(X)
12.61/5.09	   dbl(active(X)) -> dbl(X)
12.61/5.09	   first(mark(X1), X2) -> first(X1, X2)
12.61/5.09	   first(X1, mark(X2)) -> first(X1, X2)
12.61/5.09	   first(active(X1), X2) -> first(X1, X2)
12.61/5.09	   first(X1, active(X2)) -> first(X1, X2)
12.61/5.09	
12.61/5.09	The set Q consists of the following terms:
12.61/5.09	
12.61/5.09	   active(terms(x0))
12.61/5.09	   active(sqr(0))
12.61/5.09	   active(sqr(s(x0)))
12.61/5.09	   active(dbl(0))
12.61/5.09	   active(dbl(s(x0)))
12.61/5.09	   active(add(0, x0))
12.61/5.09	   active(add(s(x0), x1))
12.61/5.09	   active(first(0, x0))
12.61/5.09	   active(first(s(x0), cons(x1, x2)))
12.61/5.09	   mark(terms(x0))
12.61/5.09	   mark(cons(x0, x1))
12.61/5.09	   mark(recip(x0))
12.61/5.09	   mark(sqr(x0))
12.61/5.09	   mark(s(x0))
12.61/5.09	   mark(0)
12.61/5.09	   mark(add(x0, x1))
12.61/5.09	   mark(dbl(x0))
12.61/5.09	   mark(first(x0, x1))
12.61/5.09	   mark(nil)
12.61/5.09	   terms(mark(x0))
12.61/5.09	   terms(active(x0))
12.61/5.09	   cons(mark(x0), x1)
12.61/5.09	   cons(x0, mark(x1))
12.61/5.09	   cons(active(x0), x1)
12.61/5.09	   cons(x0, active(x1))
12.61/5.09	   recip(mark(x0))
12.61/5.09	   recip(active(x0))
12.61/5.09	   sqr(mark(x0))
12.61/5.09	   sqr(active(x0))
12.61/5.09	   s(mark(x0))
12.61/5.09	   s(active(x0))
12.61/5.09	   add(mark(x0), x1)
12.61/5.09	   add(x0, mark(x1))
12.61/5.09	   add(active(x0), x1)
12.61/5.09	   add(x0, active(x1))
12.61/5.09	   dbl(mark(x0))
12.61/5.09	   dbl(active(x0))
12.61/5.09	   first(mark(x0), x1)
12.61/5.09	   first(x0, mark(x1))
12.61/5.09	   first(active(x0), x1)
12.61/5.09	   first(x0, active(x1))
12.61/5.09	
12.61/5.09	We have to consider all minimal (P,Q,R)-chains.
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(6) UsableRulesProof (EQUIVALENT)
12.61/5.09	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.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(7)
12.61/5.09	Obligation:
12.61/5.09	Q DP problem:
12.61/5.09	The TRS P consists of the following rules:
12.61/5.09	
12.61/5.09	   FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.61/5.09	   FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.61/5.09	   FIRST(active(X1), X2) -> FIRST(X1, X2)
12.61/5.09	   FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.61/5.09	
12.61/5.09	R is empty.
12.61/5.09	The set Q consists of the following terms:
12.61/5.09	
12.61/5.09	   active(terms(x0))
12.61/5.09	   active(sqr(0))
12.61/5.09	   active(sqr(s(x0)))
12.61/5.09	   active(dbl(0))
12.61/5.09	   active(dbl(s(x0)))
12.61/5.09	   active(add(0, x0))
12.61/5.09	   active(add(s(x0), x1))
12.61/5.09	   active(first(0, x0))
12.61/5.09	   active(first(s(x0), cons(x1, x2)))
12.61/5.09	   mark(terms(x0))
12.61/5.09	   mark(cons(x0, x1))
12.61/5.09	   mark(recip(x0))
12.61/5.09	   mark(sqr(x0))
12.61/5.09	   mark(s(x0))
12.61/5.09	   mark(0)
12.61/5.09	   mark(add(x0, x1))
12.61/5.09	   mark(dbl(x0))
12.61/5.09	   mark(first(x0, x1))
12.61/5.09	   mark(nil)
12.61/5.09	   terms(mark(x0))
12.61/5.09	   terms(active(x0))
12.61/5.09	   cons(mark(x0), x1)
12.61/5.09	   cons(x0, mark(x1))
12.61/5.09	   cons(active(x0), x1)
12.61/5.09	   cons(x0, active(x1))
12.61/5.09	   recip(mark(x0))
12.61/5.09	   recip(active(x0))
12.61/5.09	   sqr(mark(x0))
12.61/5.09	   sqr(active(x0))
12.61/5.09	   s(mark(x0))
12.61/5.09	   s(active(x0))
12.61/5.09	   add(mark(x0), x1)
12.61/5.09	   add(x0, mark(x1))
12.61/5.09	   add(active(x0), x1)
12.61/5.09	   add(x0, active(x1))
12.61/5.09	   dbl(mark(x0))
12.61/5.09	   dbl(active(x0))
12.61/5.09	   first(mark(x0), x1)
12.61/5.09	   first(x0, mark(x1))
12.61/5.09	   first(active(x0), x1)
12.61/5.09	   first(x0, active(x1))
12.61/5.09	
12.61/5.09	We have to consider all minimal (P,Q,R)-chains.
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(8) QReductionProof (EQUIVALENT)
12.61/5.09	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.61/5.09	
12.61/5.09	   terms(mark(x0))
12.61/5.09	   terms(active(x0))
12.61/5.09	   cons(mark(x0), x1)
12.61/5.09	   cons(x0, mark(x1))
12.61/5.09	   cons(active(x0), x1)
12.61/5.09	   cons(x0, active(x1))
12.61/5.09	   recip(mark(x0))
12.61/5.09	   recip(active(x0))
12.61/5.09	   sqr(mark(x0))
12.61/5.09	   sqr(active(x0))
12.61/5.09	   s(mark(x0))
12.61/5.09	   s(active(x0))
12.61/5.09	   add(mark(x0), x1)
12.61/5.09	   add(x0, mark(x1))
12.61/5.09	   add(active(x0), x1)
12.61/5.09	   add(x0, active(x1))
12.61/5.09	   dbl(mark(x0))
12.61/5.09	   dbl(active(x0))
12.61/5.09	   first(mark(x0), x1)
12.61/5.09	   first(x0, mark(x1))
12.61/5.09	   first(active(x0), x1)
12.61/5.09	   first(x0, active(x1))
12.61/5.09	
12.61/5.09	
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(9)
12.61/5.09	Obligation:
12.61/5.09	Q DP problem:
12.61/5.09	The TRS P consists of the following rules:
12.61/5.09	
12.61/5.09	   FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.61/5.09	   FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.61/5.09	   FIRST(active(X1), X2) -> FIRST(X1, X2)
12.61/5.09	   FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.61/5.09	
12.61/5.09	R is empty.
12.61/5.09	The set Q consists of the following terms:
12.61/5.09	
12.61/5.09	   active(terms(x0))
12.61/5.09	   active(sqr(0))
12.61/5.09	   active(sqr(s(x0)))
12.61/5.09	   active(dbl(0))
12.61/5.09	   active(dbl(s(x0)))
12.61/5.09	   active(add(0, x0))
12.61/5.09	   active(add(s(x0), x1))
12.61/5.09	   active(first(0, x0))
12.61/5.09	   active(first(s(x0), cons(x1, x2)))
12.61/5.09	   mark(terms(x0))
12.61/5.09	   mark(cons(x0, x1))
12.61/5.09	   mark(recip(x0))
12.61/5.09	   mark(sqr(x0))
12.61/5.09	   mark(s(x0))
12.61/5.09	   mark(0)
12.61/5.09	   mark(add(x0, x1))
12.61/5.09	   mark(dbl(x0))
12.61/5.09	   mark(first(x0, x1))
12.61/5.09	   mark(nil)
12.61/5.09	
12.61/5.09	We have to consider all minimal (P,Q,R)-chains.
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(10) QDPSizeChangeProof (EQUIVALENT)
12.61/5.09	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.61/5.09	
12.61/5.09	From the DPs we obtained the following set of size-change graphs:
12.61/5.09	*FIRST(X1, mark(X2)) -> FIRST(X1, X2)
12.61/5.09	The graph contains the following edges 1 >= 1, 2 > 2
12.61/5.09	
12.61/5.09	
12.61/5.09	*FIRST(mark(X1), X2) -> FIRST(X1, X2)
12.61/5.09	The graph contains the following edges 1 > 1, 2 >= 2
12.61/5.09	
12.61/5.09	
12.61/5.09	*FIRST(active(X1), X2) -> FIRST(X1, X2)
12.61/5.09	The graph contains the following edges 1 > 1, 2 >= 2
12.61/5.09	
12.61/5.09	
12.61/5.09	*FIRST(X1, active(X2)) -> FIRST(X1, X2)
12.61/5.09	The graph contains the following edges 1 >= 1, 2 > 2
12.61/5.09	
12.61/5.09	
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(11)
12.61/5.09	YES
12.61/5.09	
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(12)
12.61/5.09	Obligation:
12.61/5.09	Q DP problem:
12.61/5.09	The TRS P consists of the following rules:
12.61/5.09	
12.61/5.09	   DBL(active(X)) -> DBL(X)
12.61/5.09	   DBL(mark(X)) -> DBL(X)
12.61/5.09	
12.61/5.09	The TRS R consists of the following rules:
12.61/5.09	
12.61/5.09	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.61/5.09	   active(sqr(0)) -> mark(0)
12.61/5.09	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.61/5.09	   active(dbl(0)) -> mark(0)
12.61/5.09	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.61/5.09	   active(add(0, X)) -> mark(X)
12.61/5.09	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.61/5.09	   active(first(0, X)) -> mark(nil)
12.61/5.09	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.61/5.09	   mark(terms(X)) -> active(terms(mark(X)))
12.61/5.09	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.61/5.09	   mark(recip(X)) -> active(recip(mark(X)))
12.61/5.09	   mark(sqr(X)) -> active(sqr(mark(X)))
12.61/5.09	   mark(s(X)) -> active(s(X))
12.61/5.09	   mark(0) -> active(0)
12.61/5.09	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.61/5.09	   mark(dbl(X)) -> active(dbl(mark(X)))
12.61/5.09	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.61/5.09	   mark(nil) -> active(nil)
12.61/5.09	   terms(mark(X)) -> terms(X)
12.61/5.09	   terms(active(X)) -> terms(X)
12.61/5.09	   cons(mark(X1), X2) -> cons(X1, X2)
12.61/5.09	   cons(X1, mark(X2)) -> cons(X1, X2)
12.61/5.09	   cons(active(X1), X2) -> cons(X1, X2)
12.61/5.09	   cons(X1, active(X2)) -> cons(X1, X2)
12.61/5.09	   recip(mark(X)) -> recip(X)
12.61/5.09	   recip(active(X)) -> recip(X)
12.61/5.09	   sqr(mark(X)) -> sqr(X)
12.61/5.09	   sqr(active(X)) -> sqr(X)
12.61/5.09	   s(mark(X)) -> s(X)
12.61/5.09	   s(active(X)) -> s(X)
12.61/5.09	   add(mark(X1), X2) -> add(X1, X2)
12.61/5.09	   add(X1, mark(X2)) -> add(X1, X2)
12.61/5.09	   add(active(X1), X2) -> add(X1, X2)
12.61/5.09	   add(X1, active(X2)) -> add(X1, X2)
12.61/5.09	   dbl(mark(X)) -> dbl(X)
12.61/5.09	   dbl(active(X)) -> dbl(X)
12.61/5.09	   first(mark(X1), X2) -> first(X1, X2)
12.61/5.09	   first(X1, mark(X2)) -> first(X1, X2)
12.61/5.09	   first(active(X1), X2) -> first(X1, X2)
12.61/5.09	   first(X1, active(X2)) -> first(X1, X2)
12.61/5.09	
12.61/5.09	The set Q consists of the following terms:
12.61/5.09	
12.61/5.09	   active(terms(x0))
12.61/5.09	   active(sqr(0))
12.61/5.09	   active(sqr(s(x0)))
12.61/5.09	   active(dbl(0))
12.61/5.09	   active(dbl(s(x0)))
12.61/5.09	   active(add(0, x0))
12.61/5.09	   active(add(s(x0), x1))
12.61/5.09	   active(first(0, x0))
12.61/5.09	   active(first(s(x0), cons(x1, x2)))
12.61/5.09	   mark(terms(x0))
12.61/5.09	   mark(cons(x0, x1))
12.61/5.09	   mark(recip(x0))
12.61/5.09	   mark(sqr(x0))
12.61/5.09	   mark(s(x0))
12.61/5.09	   mark(0)
12.61/5.09	   mark(add(x0, x1))
12.61/5.09	   mark(dbl(x0))
12.61/5.09	   mark(first(x0, x1))
12.61/5.09	   mark(nil)
12.61/5.09	   terms(mark(x0))
12.61/5.09	   terms(active(x0))
12.61/5.09	   cons(mark(x0), x1)
12.61/5.09	   cons(x0, mark(x1))
12.61/5.09	   cons(active(x0), x1)
12.61/5.09	   cons(x0, active(x1))
12.61/5.09	   recip(mark(x0))
12.61/5.09	   recip(active(x0))
12.61/5.09	   sqr(mark(x0))
12.61/5.09	   sqr(active(x0))
12.61/5.09	   s(mark(x0))
12.61/5.09	   s(active(x0))
12.61/5.09	   add(mark(x0), x1)
12.61/5.09	   add(x0, mark(x1))
12.61/5.09	   add(active(x0), x1)
12.61/5.09	   add(x0, active(x1))
12.61/5.09	   dbl(mark(x0))
12.61/5.09	   dbl(active(x0))
12.61/5.09	   first(mark(x0), x1)
12.61/5.09	   first(x0, mark(x1))
12.61/5.09	   first(active(x0), x1)
12.61/5.09	   first(x0, active(x1))
12.61/5.09	
12.61/5.09	We have to consider all minimal (P,Q,R)-chains.
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(13) UsableRulesProof (EQUIVALENT)
12.61/5.09	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.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(14)
12.61/5.09	Obligation:
12.61/5.09	Q DP problem:
12.61/5.09	The TRS P consists of the following rules:
12.61/5.09	
12.61/5.09	   DBL(active(X)) -> DBL(X)
12.61/5.09	   DBL(mark(X)) -> DBL(X)
12.61/5.09	
12.61/5.09	R is empty.
12.61/5.09	The set Q consists of the following terms:
12.61/5.09	
12.61/5.09	   active(terms(x0))
12.61/5.09	   active(sqr(0))
12.61/5.09	   active(sqr(s(x0)))
12.61/5.09	   active(dbl(0))
12.61/5.09	   active(dbl(s(x0)))
12.61/5.09	   active(add(0, x0))
12.61/5.09	   active(add(s(x0), x1))
12.61/5.09	   active(first(0, x0))
12.61/5.09	   active(first(s(x0), cons(x1, x2)))
12.61/5.09	   mark(terms(x0))
12.61/5.09	   mark(cons(x0, x1))
12.61/5.09	   mark(recip(x0))
12.61/5.09	   mark(sqr(x0))
12.61/5.09	   mark(s(x0))
12.61/5.09	   mark(0)
12.61/5.09	   mark(add(x0, x1))
12.61/5.09	   mark(dbl(x0))
12.61/5.09	   mark(first(x0, x1))
12.61/5.09	   mark(nil)
12.61/5.09	   terms(mark(x0))
12.61/5.09	   terms(active(x0))
12.61/5.09	   cons(mark(x0), x1)
12.61/5.09	   cons(x0, mark(x1))
12.61/5.09	   cons(active(x0), x1)
12.61/5.09	   cons(x0, active(x1))
12.61/5.09	   recip(mark(x0))
12.61/5.09	   recip(active(x0))
12.61/5.09	   sqr(mark(x0))
12.61/5.09	   sqr(active(x0))
12.61/5.09	   s(mark(x0))
12.61/5.09	   s(active(x0))
12.61/5.09	   add(mark(x0), x1)
12.61/5.09	   add(x0, mark(x1))
12.61/5.09	   add(active(x0), x1)
12.61/5.09	   add(x0, active(x1))
12.61/5.09	   dbl(mark(x0))
12.61/5.09	   dbl(active(x0))
12.61/5.09	   first(mark(x0), x1)
12.61/5.09	   first(x0, mark(x1))
12.61/5.09	   first(active(x0), x1)
12.61/5.09	   first(x0, active(x1))
12.61/5.09	
12.61/5.09	We have to consider all minimal (P,Q,R)-chains.
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(15) QReductionProof (EQUIVALENT)
12.61/5.09	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.61/5.09	
12.61/5.09	   terms(mark(x0))
12.61/5.09	   terms(active(x0))
12.61/5.09	   cons(mark(x0), x1)
12.61/5.09	   cons(x0, mark(x1))
12.61/5.09	   cons(active(x0), x1)
12.61/5.09	   cons(x0, active(x1))
12.61/5.09	   recip(mark(x0))
12.61/5.09	   recip(active(x0))
12.61/5.09	   sqr(mark(x0))
12.61/5.09	   sqr(active(x0))
12.61/5.09	   s(mark(x0))
12.61/5.09	   s(active(x0))
12.61/5.09	   add(mark(x0), x1)
12.61/5.09	   add(x0, mark(x1))
12.61/5.09	   add(active(x0), x1)
12.61/5.09	   add(x0, active(x1))
12.61/5.09	   dbl(mark(x0))
12.61/5.09	   dbl(active(x0))
12.61/5.09	   first(mark(x0), x1)
12.61/5.09	   first(x0, mark(x1))
12.61/5.09	   first(active(x0), x1)
12.61/5.09	   first(x0, active(x1))
12.61/5.09	
12.61/5.09	
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(16)
12.61/5.09	Obligation:
12.61/5.09	Q DP problem:
12.61/5.09	The TRS P consists of the following rules:
12.61/5.09	
12.61/5.09	   DBL(active(X)) -> DBL(X)
12.61/5.09	   DBL(mark(X)) -> DBL(X)
12.61/5.09	
12.61/5.09	R is empty.
12.61/5.09	The set Q consists of the following terms:
12.61/5.09	
12.61/5.09	   active(terms(x0))
12.61/5.09	   active(sqr(0))
12.61/5.09	   active(sqr(s(x0)))
12.61/5.09	   active(dbl(0))
12.61/5.09	   active(dbl(s(x0)))
12.61/5.09	   active(add(0, x0))
12.61/5.09	   active(add(s(x0), x1))
12.61/5.09	   active(first(0, x0))
12.61/5.09	   active(first(s(x0), cons(x1, x2)))
12.61/5.09	   mark(terms(x0))
12.61/5.09	   mark(cons(x0, x1))
12.61/5.09	   mark(recip(x0))
12.61/5.09	   mark(sqr(x0))
12.61/5.09	   mark(s(x0))
12.61/5.09	   mark(0)
12.61/5.09	   mark(add(x0, x1))
12.61/5.09	   mark(dbl(x0))
12.61/5.09	   mark(first(x0, x1))
12.61/5.09	   mark(nil)
12.61/5.09	
12.61/5.09	We have to consider all minimal (P,Q,R)-chains.
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(17) QDPSizeChangeProof (EQUIVALENT)
12.61/5.09	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.61/5.09	
12.61/5.09	From the DPs we obtained the following set of size-change graphs:
12.61/5.09	*DBL(active(X)) -> DBL(X)
12.61/5.09	The graph contains the following edges 1 > 1
12.61/5.09	
12.61/5.09	
12.61/5.09	*DBL(mark(X)) -> DBL(X)
12.61/5.09	The graph contains the following edges 1 > 1
12.61/5.09	
12.61/5.09	
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(18)
12.61/5.09	YES
12.61/5.09	
12.61/5.09	----------------------------------------
12.61/5.09	
12.61/5.09	(19)
12.61/5.09	Obligation:
12.61/5.09	Q DP problem:
12.61/5.09	The TRS P consists of the following rules:
12.61/5.09	
12.61/5.09	   ADD(X1, mark(X2)) -> ADD(X1, X2)
12.61/5.09	   ADD(mark(X1), X2) -> ADD(X1, X2)
12.61/5.09	   ADD(active(X1), X2) -> ADD(X1, X2)
12.61/5.09	   ADD(X1, active(X2)) -> ADD(X1, X2)
12.61/5.09	
12.61/5.09	The TRS R consists of the following rules:
12.61/5.09	
12.61/5.09	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.61/5.09	   active(sqr(0)) -> mark(0)
12.61/5.09	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.61/5.09	   active(dbl(0)) -> mark(0)
12.61/5.09	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.61/5.09	   active(add(0, X)) -> mark(X)
12.61/5.09	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.61/5.09	   active(first(0, X)) -> mark(nil)
12.61/5.09	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.61/5.09	   mark(terms(X)) -> active(terms(mark(X)))
12.61/5.09	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.61/5.09	   mark(recip(X)) -> active(recip(mark(X)))
12.61/5.09	   mark(sqr(X)) -> active(sqr(mark(X)))
12.61/5.09	   mark(s(X)) -> active(s(X))
12.61/5.09	   mark(0) -> active(0)
12.61/5.09	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.61/5.09	   mark(dbl(X)) -> active(dbl(mark(X)))
12.61/5.09	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.61/5.09	   mark(nil) -> active(nil)
12.94/5.10	   terms(mark(X)) -> terms(X)
12.94/5.10	   terms(active(X)) -> terms(X)
12.94/5.10	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.10	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.10	   recip(mark(X)) -> recip(X)
12.94/5.10	   recip(active(X)) -> recip(X)
12.94/5.10	   sqr(mark(X)) -> sqr(X)
12.94/5.10	   sqr(active(X)) -> sqr(X)
12.94/5.10	   s(mark(X)) -> s(X)
12.94/5.10	   s(active(X)) -> s(X)
12.94/5.10	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.10	   add(active(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.10	   dbl(mark(X)) -> dbl(X)
12.94/5.10	   dbl(active(X)) -> dbl(X)
12.94/5.10	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.10	   first(active(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.10	
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(20) UsableRulesProof (EQUIVALENT)
12.94/5.10	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.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(21)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   ADD(X1, mark(X2)) -> ADD(X1, X2)
12.94/5.10	   ADD(mark(X1), X2) -> ADD(X1, X2)
12.94/5.10	   ADD(active(X1), X2) -> ADD(X1, X2)
12.94/5.10	   ADD(X1, active(X2)) -> ADD(X1, X2)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(22) QReductionProof (EQUIVALENT)
12.94/5.10	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.94/5.10	
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(23)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   ADD(X1, mark(X2)) -> ADD(X1, X2)
12.94/5.10	   ADD(mark(X1), X2) -> ADD(X1, X2)
12.94/5.10	   ADD(active(X1), X2) -> ADD(X1, X2)
12.94/5.10	   ADD(X1, active(X2)) -> ADD(X1, X2)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(24) QDPSizeChangeProof (EQUIVALENT)
12.94/5.10	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.94/5.10	
12.94/5.10	From the DPs we obtained the following set of size-change graphs:
12.94/5.10	*ADD(X1, mark(X2)) -> ADD(X1, X2)
12.94/5.10	The graph contains the following edges 1 >= 1, 2 > 2
12.94/5.10	
12.94/5.10	
12.94/5.10	*ADD(mark(X1), X2) -> ADD(X1, X2)
12.94/5.10	The graph contains the following edges 1 > 1, 2 >= 2
12.94/5.10	
12.94/5.10	
12.94/5.10	*ADD(active(X1), X2) -> ADD(X1, X2)
12.94/5.10	The graph contains the following edges 1 > 1, 2 >= 2
12.94/5.10	
12.94/5.10	
12.94/5.10	*ADD(X1, active(X2)) -> ADD(X1, X2)
12.94/5.10	The graph contains the following edges 1 >= 1, 2 > 2
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(25)
12.94/5.10	YES
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(26)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   S(active(X)) -> S(X)
12.94/5.10	   S(mark(X)) -> S(X)
12.94/5.10	
12.94/5.10	The TRS R consists of the following rules:
12.94/5.10	
12.94/5.10	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.10	   active(sqr(0)) -> mark(0)
12.94/5.10	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.10	   active(dbl(0)) -> mark(0)
12.94/5.10	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.10	   active(add(0, X)) -> mark(X)
12.94/5.10	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.10	   active(first(0, X)) -> mark(nil)
12.94/5.10	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.10	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.10	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.10	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.10	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.10	   mark(s(X)) -> active(s(X))
12.94/5.10	   mark(0) -> active(0)
12.94/5.10	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.10	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.10	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.10	   mark(nil) -> active(nil)
12.94/5.10	   terms(mark(X)) -> terms(X)
12.94/5.10	   terms(active(X)) -> terms(X)
12.94/5.10	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.10	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.10	   recip(mark(X)) -> recip(X)
12.94/5.10	   recip(active(X)) -> recip(X)
12.94/5.10	   sqr(mark(X)) -> sqr(X)
12.94/5.10	   sqr(active(X)) -> sqr(X)
12.94/5.10	   s(mark(X)) -> s(X)
12.94/5.10	   s(active(X)) -> s(X)
12.94/5.10	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.10	   add(active(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.10	   dbl(mark(X)) -> dbl(X)
12.94/5.10	   dbl(active(X)) -> dbl(X)
12.94/5.10	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.10	   first(active(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.10	
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(27) UsableRulesProof (EQUIVALENT)
12.94/5.10	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.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(28)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   S(active(X)) -> S(X)
12.94/5.10	   S(mark(X)) -> S(X)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(29) QReductionProof (EQUIVALENT)
12.94/5.10	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.94/5.10	
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(30)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   S(active(X)) -> S(X)
12.94/5.10	   S(mark(X)) -> S(X)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(31) QDPSizeChangeProof (EQUIVALENT)
12.94/5.10	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.94/5.10	
12.94/5.10	From the DPs we obtained the following set of size-change graphs:
12.94/5.10	*S(active(X)) -> S(X)
12.94/5.10	The graph contains the following edges 1 > 1
12.94/5.10	
12.94/5.10	
12.94/5.10	*S(mark(X)) -> S(X)
12.94/5.10	The graph contains the following edges 1 > 1
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(32)
12.94/5.10	YES
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(33)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   SQR(active(X)) -> SQR(X)
12.94/5.10	   SQR(mark(X)) -> SQR(X)
12.94/5.10	
12.94/5.10	The TRS R consists of the following rules:
12.94/5.10	
12.94/5.10	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.10	   active(sqr(0)) -> mark(0)
12.94/5.10	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.10	   active(dbl(0)) -> mark(0)
12.94/5.10	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.10	   active(add(0, X)) -> mark(X)
12.94/5.10	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.10	   active(first(0, X)) -> mark(nil)
12.94/5.10	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.10	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.10	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.10	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.10	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.10	   mark(s(X)) -> active(s(X))
12.94/5.10	   mark(0) -> active(0)
12.94/5.10	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.10	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.10	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.10	   mark(nil) -> active(nil)
12.94/5.10	   terms(mark(X)) -> terms(X)
12.94/5.10	   terms(active(X)) -> terms(X)
12.94/5.10	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.10	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.10	   recip(mark(X)) -> recip(X)
12.94/5.10	   recip(active(X)) -> recip(X)
12.94/5.10	   sqr(mark(X)) -> sqr(X)
12.94/5.10	   sqr(active(X)) -> sqr(X)
12.94/5.10	   s(mark(X)) -> s(X)
12.94/5.10	   s(active(X)) -> s(X)
12.94/5.10	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.10	   add(active(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.10	   dbl(mark(X)) -> dbl(X)
12.94/5.10	   dbl(active(X)) -> dbl(X)
12.94/5.10	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.10	   first(active(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.10	
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(34) UsableRulesProof (EQUIVALENT)
12.94/5.10	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.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(35)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   SQR(active(X)) -> SQR(X)
12.94/5.10	   SQR(mark(X)) -> SQR(X)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(36) QReductionProof (EQUIVALENT)
12.94/5.10	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.94/5.10	
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(37)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   SQR(active(X)) -> SQR(X)
12.94/5.10	   SQR(mark(X)) -> SQR(X)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(38) QDPSizeChangeProof (EQUIVALENT)
12.94/5.10	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.94/5.10	
12.94/5.10	From the DPs we obtained the following set of size-change graphs:
12.94/5.10	*SQR(active(X)) -> SQR(X)
12.94/5.10	The graph contains the following edges 1 > 1
12.94/5.10	
12.94/5.10	
12.94/5.10	*SQR(mark(X)) -> SQR(X)
12.94/5.10	The graph contains the following edges 1 > 1
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(39)
12.94/5.10	YES
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(40)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   RECIP(active(X)) -> RECIP(X)
12.94/5.10	   RECIP(mark(X)) -> RECIP(X)
12.94/5.10	
12.94/5.10	The TRS R consists of the following rules:
12.94/5.10	
12.94/5.10	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.10	   active(sqr(0)) -> mark(0)
12.94/5.10	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.10	   active(dbl(0)) -> mark(0)
12.94/5.10	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.10	   active(add(0, X)) -> mark(X)
12.94/5.10	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.10	   active(first(0, X)) -> mark(nil)
12.94/5.10	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.10	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.10	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.10	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.10	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.10	   mark(s(X)) -> active(s(X))
12.94/5.10	   mark(0) -> active(0)
12.94/5.10	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.10	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.10	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.10	   mark(nil) -> active(nil)
12.94/5.10	   terms(mark(X)) -> terms(X)
12.94/5.10	   terms(active(X)) -> terms(X)
12.94/5.10	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.10	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.10	   recip(mark(X)) -> recip(X)
12.94/5.10	   recip(active(X)) -> recip(X)
12.94/5.10	   sqr(mark(X)) -> sqr(X)
12.94/5.10	   sqr(active(X)) -> sqr(X)
12.94/5.10	   s(mark(X)) -> s(X)
12.94/5.10	   s(active(X)) -> s(X)
12.94/5.10	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.10	   add(active(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.10	   dbl(mark(X)) -> dbl(X)
12.94/5.10	   dbl(active(X)) -> dbl(X)
12.94/5.10	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.10	   first(active(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.10	
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(41) UsableRulesProof (EQUIVALENT)
12.94/5.10	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.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(42)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   RECIP(active(X)) -> RECIP(X)
12.94/5.10	   RECIP(mark(X)) -> RECIP(X)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(43) QReductionProof (EQUIVALENT)
12.94/5.10	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.94/5.10	
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(44)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   RECIP(active(X)) -> RECIP(X)
12.94/5.10	   RECIP(mark(X)) -> RECIP(X)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(45) QDPSizeChangeProof (EQUIVALENT)
12.94/5.10	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.94/5.10	
12.94/5.10	From the DPs we obtained the following set of size-change graphs:
12.94/5.10	*RECIP(active(X)) -> RECIP(X)
12.94/5.10	The graph contains the following edges 1 > 1
12.94/5.10	
12.94/5.10	
12.94/5.10	*RECIP(mark(X)) -> RECIP(X)
12.94/5.10	The graph contains the following edges 1 > 1
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(46)
12.94/5.10	YES
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(47)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   CONS(X1, mark(X2)) -> CONS(X1, X2)
12.94/5.10	   CONS(mark(X1), X2) -> CONS(X1, X2)
12.94/5.10	   CONS(active(X1), X2) -> CONS(X1, X2)
12.94/5.10	   CONS(X1, active(X2)) -> CONS(X1, X2)
12.94/5.10	
12.94/5.10	The TRS R consists of the following rules:
12.94/5.10	
12.94/5.10	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.10	   active(sqr(0)) -> mark(0)
12.94/5.10	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.10	   active(dbl(0)) -> mark(0)
12.94/5.10	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.10	   active(add(0, X)) -> mark(X)
12.94/5.10	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.10	   active(first(0, X)) -> mark(nil)
12.94/5.10	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.10	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.10	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.10	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.10	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.10	   mark(s(X)) -> active(s(X))
12.94/5.10	   mark(0) -> active(0)
12.94/5.10	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.10	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.10	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.10	   mark(nil) -> active(nil)
12.94/5.10	   terms(mark(X)) -> terms(X)
12.94/5.10	   terms(active(X)) -> terms(X)
12.94/5.10	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.10	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.10	   recip(mark(X)) -> recip(X)
12.94/5.10	   recip(active(X)) -> recip(X)
12.94/5.10	   sqr(mark(X)) -> sqr(X)
12.94/5.10	   sqr(active(X)) -> sqr(X)
12.94/5.10	   s(mark(X)) -> s(X)
12.94/5.10	   s(active(X)) -> s(X)
12.94/5.10	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.10	   add(active(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.10	   dbl(mark(X)) -> dbl(X)
12.94/5.10	   dbl(active(X)) -> dbl(X)
12.94/5.10	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.10	   first(active(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.10	
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(48) UsableRulesProof (EQUIVALENT)
12.94/5.10	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.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(49)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   CONS(X1, mark(X2)) -> CONS(X1, X2)
12.94/5.10	   CONS(mark(X1), X2) -> CONS(X1, X2)
12.94/5.10	   CONS(active(X1), X2) -> CONS(X1, X2)
12.94/5.10	   CONS(X1, active(X2)) -> CONS(X1, X2)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(50) QReductionProof (EQUIVALENT)
12.94/5.10	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.94/5.10	
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(51)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   CONS(X1, mark(X2)) -> CONS(X1, X2)
12.94/5.10	   CONS(mark(X1), X2) -> CONS(X1, X2)
12.94/5.10	   CONS(active(X1), X2) -> CONS(X1, X2)
12.94/5.10	   CONS(X1, active(X2)) -> CONS(X1, X2)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(52) QDPSizeChangeProof (EQUIVALENT)
12.94/5.10	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.94/5.10	
12.94/5.10	From the DPs we obtained the following set of size-change graphs:
12.94/5.10	*CONS(X1, mark(X2)) -> CONS(X1, X2)
12.94/5.10	The graph contains the following edges 1 >= 1, 2 > 2
12.94/5.10	
12.94/5.10	
12.94/5.10	*CONS(mark(X1), X2) -> CONS(X1, X2)
12.94/5.10	The graph contains the following edges 1 > 1, 2 >= 2
12.94/5.10	
12.94/5.10	
12.94/5.10	*CONS(active(X1), X2) -> CONS(X1, X2)
12.94/5.10	The graph contains the following edges 1 > 1, 2 >= 2
12.94/5.10	
12.94/5.10	
12.94/5.10	*CONS(X1, active(X2)) -> CONS(X1, X2)
12.94/5.10	The graph contains the following edges 1 >= 1, 2 > 2
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(53)
12.94/5.10	YES
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(54)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   TERMS(active(X)) -> TERMS(X)
12.94/5.10	   TERMS(mark(X)) -> TERMS(X)
12.94/5.10	
12.94/5.10	The TRS R consists of the following rules:
12.94/5.10	
12.94/5.10	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.10	   active(sqr(0)) -> mark(0)
12.94/5.10	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.10	   active(dbl(0)) -> mark(0)
12.94/5.10	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.10	   active(add(0, X)) -> mark(X)
12.94/5.10	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.10	   active(first(0, X)) -> mark(nil)
12.94/5.10	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.10	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.10	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.10	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.10	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.10	   mark(s(X)) -> active(s(X))
12.94/5.10	   mark(0) -> active(0)
12.94/5.10	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.10	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.10	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.10	   mark(nil) -> active(nil)
12.94/5.10	   terms(mark(X)) -> terms(X)
12.94/5.10	   terms(active(X)) -> terms(X)
12.94/5.10	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.10	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.10	   recip(mark(X)) -> recip(X)
12.94/5.10	   recip(active(X)) -> recip(X)
12.94/5.10	   sqr(mark(X)) -> sqr(X)
12.94/5.10	   sqr(active(X)) -> sqr(X)
12.94/5.10	   s(mark(X)) -> s(X)
12.94/5.10	   s(active(X)) -> s(X)
12.94/5.10	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.10	   add(active(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.10	   dbl(mark(X)) -> dbl(X)
12.94/5.10	   dbl(active(X)) -> dbl(X)
12.94/5.10	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.10	   first(active(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.10	
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(55) UsableRulesProof (EQUIVALENT)
12.94/5.10	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.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(56)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   TERMS(active(X)) -> TERMS(X)
12.94/5.10	   TERMS(mark(X)) -> TERMS(X)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(57) QReductionProof (EQUIVALENT)
12.94/5.10	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.94/5.10	
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(58)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   TERMS(active(X)) -> TERMS(X)
12.94/5.10	   TERMS(mark(X)) -> TERMS(X)
12.94/5.10	
12.94/5.10	R is empty.
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(59) QDPSizeChangeProof (EQUIVALENT)
12.94/5.10	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.94/5.10	
12.94/5.10	From the DPs we obtained the following set of size-change graphs:
12.94/5.10	*TERMS(active(X)) -> TERMS(X)
12.94/5.10	The graph contains the following edges 1 > 1
12.94/5.10	
12.94/5.10	
12.94/5.10	*TERMS(mark(X)) -> TERMS(X)
12.94/5.10	The graph contains the following edges 1 > 1
12.94/5.10	
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(60)
12.94/5.10	YES
12.94/5.10	
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(61)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.94/5.10	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.94/5.10	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.10	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.94/5.10	   ACTIVE(add(0, X)) -> MARK(X)
12.94/5.10	   MARK(terms(X)) -> MARK(X)
12.94/5.10	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.94/5.10	   ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z)))
12.94/5.10	   MARK(recip(X)) -> MARK(X)
12.94/5.10	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.94/5.10	   MARK(sqr(X)) -> MARK(X)
12.94/5.10	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.94/5.10	   MARK(add(X1, X2)) -> MARK(X1)
12.94/5.10	   MARK(add(X1, X2)) -> MARK(X2)
12.94/5.10	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.94/5.10	   MARK(dbl(X)) -> MARK(X)
12.94/5.10	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.94/5.10	   MARK(first(X1, X2)) -> MARK(X1)
12.94/5.10	   MARK(first(X1, X2)) -> MARK(X2)
12.94/5.10	
12.94/5.10	The TRS R consists of the following rules:
12.94/5.10	
12.94/5.10	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.10	   active(sqr(0)) -> mark(0)
12.94/5.10	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.10	   active(dbl(0)) -> mark(0)
12.94/5.10	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.10	   active(add(0, X)) -> mark(X)
12.94/5.10	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.10	   active(first(0, X)) -> mark(nil)
12.94/5.10	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.10	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.10	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.10	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.10	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.10	   mark(s(X)) -> active(s(X))
12.94/5.10	   mark(0) -> active(0)
12.94/5.10	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.10	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.10	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.10	   mark(nil) -> active(nil)
12.94/5.10	   terms(mark(X)) -> terms(X)
12.94/5.10	   terms(active(X)) -> terms(X)
12.94/5.10	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.10	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.10	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.10	   recip(mark(X)) -> recip(X)
12.94/5.10	   recip(active(X)) -> recip(X)
12.94/5.10	   sqr(mark(X)) -> sqr(X)
12.94/5.10	   sqr(active(X)) -> sqr(X)
12.94/5.10	   s(mark(X)) -> s(X)
12.94/5.10	   s(active(X)) -> s(X)
12.94/5.10	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.10	   add(active(X1), X2) -> add(X1, X2)
12.94/5.10	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.10	   dbl(mark(X)) -> dbl(X)
12.94/5.10	   dbl(active(X)) -> dbl(X)
12.94/5.10	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.10	   first(active(X1), X2) -> first(X1, X2)
12.94/5.10	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.10	
12.94/5.10	The set Q consists of the following terms:
12.94/5.10	
12.94/5.10	   active(terms(x0))
12.94/5.10	   active(sqr(0))
12.94/5.10	   active(sqr(s(x0)))
12.94/5.10	   active(dbl(0))
12.94/5.10	   active(dbl(s(x0)))
12.94/5.10	   active(add(0, x0))
12.94/5.10	   active(add(s(x0), x1))
12.94/5.10	   active(first(0, x0))
12.94/5.10	   active(first(s(x0), cons(x1, x2)))
12.94/5.10	   mark(terms(x0))
12.94/5.10	   mark(cons(x0, x1))
12.94/5.10	   mark(recip(x0))
12.94/5.10	   mark(sqr(x0))
12.94/5.10	   mark(s(x0))
12.94/5.10	   mark(0)
12.94/5.10	   mark(add(x0, x1))
12.94/5.10	   mark(dbl(x0))
12.94/5.10	   mark(first(x0, x1))
12.94/5.10	   mark(nil)
12.94/5.10	   terms(mark(x0))
12.94/5.10	   terms(active(x0))
12.94/5.10	   cons(mark(x0), x1)
12.94/5.10	   cons(x0, mark(x1))
12.94/5.10	   cons(active(x0), x1)
12.94/5.10	   cons(x0, active(x1))
12.94/5.10	   recip(mark(x0))
12.94/5.10	   recip(active(x0))
12.94/5.10	   sqr(mark(x0))
12.94/5.10	   sqr(active(x0))
12.94/5.10	   s(mark(x0))
12.94/5.10	   s(active(x0))
12.94/5.10	   add(mark(x0), x1)
12.94/5.10	   add(x0, mark(x1))
12.94/5.10	   add(active(x0), x1)
12.94/5.10	   add(x0, active(x1))
12.94/5.10	   dbl(mark(x0))
12.94/5.10	   dbl(active(x0))
12.94/5.10	   first(mark(x0), x1)
12.94/5.10	   first(x0, mark(x1))
12.94/5.10	   first(active(x0), x1)
12.94/5.10	   first(x0, active(x1))
12.94/5.10	
12.94/5.10	We have to consider all minimal (P,Q,R)-chains.
12.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(62) UsableRulesProof (EQUIVALENT)
12.94/5.10	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.94/5.10	----------------------------------------
12.94/5.10	
12.94/5.10	(63)
12.94/5.10	Obligation:
12.94/5.10	Q DP problem:
12.94/5.10	The TRS P consists of the following rules:
12.94/5.10	
12.94/5.10	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.94/5.10	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.94/5.10	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.10	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.94/5.10	   ACTIVE(add(0, X)) -> MARK(X)
12.94/5.10	   MARK(terms(X)) -> MARK(X)
12.94/5.10	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.94/5.10	   ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z)))
12.94/5.10	   MARK(recip(X)) -> MARK(X)
12.94/5.10	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.94/5.10	   MARK(sqr(X)) -> MARK(X)
12.94/5.10	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.94/5.10	   MARK(add(X1, X2)) -> MARK(X1)
12.94/5.10	   MARK(add(X1, X2)) -> MARK(X2)
12.94/5.10	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.94/5.10	   MARK(dbl(X)) -> MARK(X)
12.94/5.11	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.94/5.11	   MARK(first(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(first(X1, X2)) -> MARK(X2)
12.94/5.11	
12.94/5.11	The TRS R consists of the following rules:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	
12.94/5.11	The set Q consists of the following terms:
12.94/5.11	
12.94/5.11	   active(terms(x0))
12.94/5.11	   active(sqr(0))
12.94/5.11	   active(sqr(s(x0)))
12.94/5.11	   active(dbl(0))
12.94/5.11	   active(dbl(s(x0)))
12.94/5.11	   active(add(0, x0))
12.94/5.11	   active(add(s(x0), x1))
12.94/5.11	   active(first(0, x0))
12.94/5.11	   active(first(s(x0), cons(x1, x2)))
12.94/5.11	   mark(terms(x0))
12.94/5.11	   mark(cons(x0, x1))
12.94/5.11	   mark(recip(x0))
12.94/5.11	   mark(sqr(x0))
12.94/5.11	   mark(s(x0))
12.94/5.11	   mark(0)
12.94/5.11	   mark(add(x0, x1))
12.94/5.11	   mark(dbl(x0))
12.94/5.11	   mark(first(x0, x1))
12.94/5.11	   mark(nil)
12.94/5.11	   terms(mark(x0))
12.94/5.11	   terms(active(x0))
12.94/5.11	   cons(mark(x0), x1)
12.94/5.11	   cons(x0, mark(x1))
12.94/5.11	   cons(active(x0), x1)
12.94/5.11	   cons(x0, active(x1))
12.94/5.11	   recip(mark(x0))
12.94/5.11	   recip(active(x0))
12.94/5.11	   sqr(mark(x0))
12.94/5.11	   sqr(active(x0))
12.94/5.11	   s(mark(x0))
12.94/5.11	   s(active(x0))
12.94/5.11	   add(mark(x0), x1)
12.94/5.11	   add(x0, mark(x1))
12.94/5.11	   add(active(x0), x1)
12.94/5.11	   add(x0, active(x1))
12.94/5.11	   dbl(mark(x0))
12.94/5.11	   dbl(active(x0))
12.94/5.11	   first(mark(x0), x1)
12.94/5.11	   first(x0, mark(x1))
12.94/5.11	   first(active(x0), x1)
12.94/5.11	   first(x0, active(x1))
12.94/5.11	
12.94/5.11	We have to consider all minimal (P,Q,R)-chains.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(64) QDPOrderProof (EQUIVALENT)
12.94/5.11	We use the reduction pair processor [LPAR04,JAR06].
12.94/5.11	
12.94/5.11	
12.94/5.11	The following pairs can be oriented strictly and are deleted.
12.94/5.11	
12.94/5.11	   ACTIVE(add(0, X)) -> MARK(X)
12.94/5.11	   ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z)))
12.94/5.11	   MARK(add(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(add(X1, X2)) -> MARK(X2)
12.94/5.11	   MARK(first(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(first(X1, X2)) -> MARK(X2)
12.94/5.11	The remaining pairs can at least be oriented weakly.
12.94/5.11	Used ordering:  Combined order from the following AFS and order.
12.94/5.11	MARK(x1)  =  x1
12.94/5.11	
12.94/5.11	cons(x1, x2)  =  x1
12.94/5.11	
12.94/5.11	ACTIVE(x1)  =  x1
12.94/5.11	
12.94/5.11	mark(x1)  =  x1
12.94/5.11	
12.94/5.11	terms(x1)  =  x1
12.94/5.11	
12.94/5.11	recip(x1)  =  x1
12.94/5.11	
12.94/5.11	sqr(x1)  =  x1
12.94/5.11	
12.94/5.11	add(x1, x2)  =  add(x1, x2)
12.94/5.11	
12.94/5.11	0  =  0
12.94/5.11	
12.94/5.11	first(x1, x2)  =  first(x1, x2)
12.94/5.11	
12.94/5.11	s(x1)  =  s
12.94/5.11	
12.94/5.11	dbl(x1)  =  x1
12.94/5.11	
12.94/5.11	active(x1)  =  x1
12.94/5.11	
12.94/5.11	nil  =  nil
12.94/5.11	
12.94/5.11	
12.94/5.11	Knuth-Bendix order [KBO] with precedence:trivial
12.94/5.11	
12.94/5.11	and weight map:
12.94/5.11	
12.94/5.11	   s=2
12.94/5.11	   0=4
12.94/5.11	   first_2=2
12.94/5.11	   add_2=1
12.94/5.11	   nil=5
12.94/5.11	
12.94/5.11	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	
12.94/5.11	
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(65)
12.94/5.11	Obligation:
12.94/5.11	Q DP problem:
12.94/5.11	The TRS P consists of the following rules:
12.94/5.11	
12.94/5.11	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.94/5.11	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.94/5.11	   MARK(terms(X)) -> MARK(X)
12.94/5.11	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.94/5.11	   MARK(recip(X)) -> MARK(X)
12.94/5.11	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.94/5.11	   MARK(sqr(X)) -> MARK(X)
12.94/5.11	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.94/5.11	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.94/5.11	   MARK(dbl(X)) -> MARK(X)
12.94/5.11	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.94/5.11	
12.94/5.11	The TRS R consists of the following rules:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	
12.94/5.11	The set Q consists of the following terms:
12.94/5.11	
12.94/5.11	   active(terms(x0))
12.94/5.11	   active(sqr(0))
12.94/5.11	   active(sqr(s(x0)))
12.94/5.11	   active(dbl(0))
12.94/5.11	   active(dbl(s(x0)))
12.94/5.11	   active(add(0, x0))
12.94/5.11	   active(add(s(x0), x1))
12.94/5.11	   active(first(0, x0))
12.94/5.11	   active(first(s(x0), cons(x1, x2)))
12.94/5.11	   mark(terms(x0))
12.94/5.11	   mark(cons(x0, x1))
12.94/5.11	   mark(recip(x0))
12.94/5.11	   mark(sqr(x0))
12.94/5.11	   mark(s(x0))
12.94/5.11	   mark(0)
12.94/5.11	   mark(add(x0, x1))
12.94/5.11	   mark(dbl(x0))
12.94/5.11	   mark(first(x0, x1))
12.94/5.11	   mark(nil)
12.94/5.11	   terms(mark(x0))
12.94/5.11	   terms(active(x0))
12.94/5.11	   cons(mark(x0), x1)
12.94/5.11	   cons(x0, mark(x1))
12.94/5.11	   cons(active(x0), x1)
12.94/5.11	   cons(x0, active(x1))
12.94/5.11	   recip(mark(x0))
12.94/5.11	   recip(active(x0))
12.94/5.11	   sqr(mark(x0))
12.94/5.11	   sqr(active(x0))
12.94/5.11	   s(mark(x0))
12.94/5.11	   s(active(x0))
12.94/5.11	   add(mark(x0), x1)
12.94/5.11	   add(x0, mark(x1))
12.94/5.11	   add(active(x0), x1)
12.94/5.11	   add(x0, active(x1))
12.94/5.11	   dbl(mark(x0))
12.94/5.11	   dbl(active(x0))
12.94/5.11	   first(mark(x0), x1)
12.94/5.11	   first(x0, mark(x1))
12.94/5.11	   first(active(x0), x1)
12.94/5.11	   first(x0, active(x1))
12.94/5.11	
12.94/5.11	We have to consider all minimal (P,Q,R)-chains.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(66) QDPOrderProof (EQUIVALENT)
12.94/5.11	We use the reduction pair processor [LPAR04,JAR06].
12.94/5.11	
12.94/5.11	
12.94/5.11	The following pairs can be oriented strictly and are deleted.
12.94/5.11	
12.94/5.11	   MARK(dbl(X)) -> MARK(X)
12.94/5.11	The remaining pairs can at least be oriented weakly.
12.94/5.11	Used ordering:  Combined order from the following AFS and order.
12.94/5.11	MARK(x1)  =  x1
12.94/5.11	
12.94/5.11	cons(x1, x2)  =  x1
12.94/5.11	
12.94/5.11	ACTIVE(x1)  =  x1
12.94/5.11	
12.94/5.11	mark(x1)  =  x1
12.94/5.11	
12.94/5.11	terms(x1)  =  x1
12.94/5.11	
12.94/5.11	recip(x1)  =  x1
12.94/5.11	
12.94/5.11	sqr(x1)  =  x1
12.94/5.11	
12.94/5.11	add(x1, x2)  =  x2
12.94/5.11	
12.94/5.11	dbl(x1)  =  dbl(x1)
12.94/5.11	
12.94/5.11	first(x1, x2)  =  first(x2)
12.94/5.11	
12.94/5.11	active(x1)  =  x1
12.94/5.11	
12.94/5.11	s(x1)  =  s
12.94/5.11	
12.94/5.11	0  =  0
12.94/5.11	
12.94/5.11	nil  =  nil
12.94/5.11	
12.94/5.11	
12.94/5.11	Knuth-Bendix order [KBO] with precedence:trivial
12.94/5.11	
12.94/5.11	and weight map:
12.94/5.11	
12.94/5.11	   s=1
12.94/5.11	   0=2
12.94/5.11	   first_1=2
12.94/5.11	   dbl_1=1
12.94/5.11	   nil=2
12.94/5.11	
12.94/5.11	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	
12.94/5.11	
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(67)
12.94/5.11	Obligation:
12.94/5.11	Q DP problem:
12.94/5.11	The TRS P consists of the following rules:
12.94/5.11	
12.94/5.11	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.94/5.11	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.94/5.11	   MARK(terms(X)) -> MARK(X)
12.94/5.11	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.94/5.11	   MARK(recip(X)) -> MARK(X)
12.94/5.11	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.94/5.11	   MARK(sqr(X)) -> MARK(X)
12.94/5.11	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.94/5.11	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.94/5.11	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.94/5.11	
12.94/5.11	The TRS R consists of the following rules:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	
12.94/5.11	The set Q consists of the following terms:
12.94/5.11	
12.94/5.11	   active(terms(x0))
12.94/5.11	   active(sqr(0))
12.94/5.11	   active(sqr(s(x0)))
12.94/5.11	   active(dbl(0))
12.94/5.11	   active(dbl(s(x0)))
12.94/5.11	   active(add(0, x0))
12.94/5.11	   active(add(s(x0), x1))
12.94/5.11	   active(first(0, x0))
12.94/5.11	   active(first(s(x0), cons(x1, x2)))
12.94/5.11	   mark(terms(x0))
12.94/5.11	   mark(cons(x0, x1))
12.94/5.11	   mark(recip(x0))
12.94/5.11	   mark(sqr(x0))
12.94/5.11	   mark(s(x0))
12.94/5.11	   mark(0)
12.94/5.11	   mark(add(x0, x1))
12.94/5.11	   mark(dbl(x0))
12.94/5.11	   mark(first(x0, x1))
12.94/5.11	   mark(nil)
12.94/5.11	   terms(mark(x0))
12.94/5.11	   terms(active(x0))
12.94/5.11	   cons(mark(x0), x1)
12.94/5.11	   cons(x0, mark(x1))
12.94/5.11	   cons(active(x0), x1)
12.94/5.11	   cons(x0, active(x1))
12.94/5.11	   recip(mark(x0))
12.94/5.11	   recip(active(x0))
12.94/5.11	   sqr(mark(x0))
12.94/5.11	   sqr(active(x0))
12.94/5.11	   s(mark(x0))
12.94/5.11	   s(active(x0))
12.94/5.11	   add(mark(x0), x1)
12.94/5.11	   add(x0, mark(x1))
12.94/5.11	   add(active(x0), x1)
12.94/5.11	   add(x0, active(x1))
12.94/5.11	   dbl(mark(x0))
12.94/5.11	   dbl(active(x0))
12.94/5.11	   first(mark(x0), x1)
12.94/5.11	   first(x0, mark(x1))
12.94/5.11	   first(active(x0), x1)
12.94/5.11	   first(x0, active(x1))
12.94/5.11	
12.94/5.11	We have to consider all minimal (P,Q,R)-chains.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(68) QDPQMonotonicMRRProof (EQUIVALENT)
12.94/5.11	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.94/5.11	
12.94/5.11	Strictly oriented dependency pairs:
12.94/5.11	
12.94/5.11	   MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2)))
12.94/5.11	
12.94/5.11	
12.94/5.11	Used ordering: Polynomial interpretation [POLO]:
12.94/5.11	
12.94/5.11	   POL(0) = 0
12.94/5.11	   POL(ACTIVE(x_1)) = x_1
12.94/5.11	   POL(MARK(x_1)) = 1
12.94/5.11	   POL(active(x_1)) = 0
12.94/5.11	   POL(add(x_1, x_2)) = 0
12.94/5.11	   POL(cons(x_1, x_2)) = 1
12.94/5.11	   POL(dbl(x_1)) = 1
12.94/5.11	   POL(first(x_1, x_2)) = 1
12.94/5.11	   POL(mark(x_1)) = 0
12.94/5.11	   POL(nil) = 0
12.94/5.11	   POL(recip(x_1)) = 1
12.94/5.11	   POL(s(x_1)) = 0
12.94/5.11	   POL(sqr(x_1)) = 1
12.94/5.11	   POL(terms(x_1)) = 1
12.94/5.11	
12.94/5.11	
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(69)
12.94/5.11	Obligation:
12.94/5.11	Q DP problem:
12.94/5.11	The TRS P consists of the following rules:
12.94/5.11	
12.94/5.11	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.94/5.11	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.94/5.11	   MARK(terms(X)) -> MARK(X)
12.94/5.11	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.94/5.11	   MARK(recip(X)) -> MARK(X)
12.94/5.11	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.94/5.11	   MARK(sqr(X)) -> MARK(X)
12.94/5.11	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.94/5.11	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.94/5.11	
12.94/5.11	The TRS R consists of the following rules:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	
12.94/5.11	The set Q consists of the following terms:
12.94/5.11	
12.94/5.11	   active(terms(x0))
12.94/5.11	   active(sqr(0))
12.94/5.11	   active(sqr(s(x0)))
12.94/5.11	   active(dbl(0))
12.94/5.11	   active(dbl(s(x0)))
12.94/5.11	   active(add(0, x0))
12.94/5.11	   active(add(s(x0), x1))
12.94/5.11	   active(first(0, x0))
12.94/5.11	   active(first(s(x0), cons(x1, x2)))
12.94/5.11	   mark(terms(x0))
12.94/5.11	   mark(cons(x0, x1))
12.94/5.11	   mark(recip(x0))
12.94/5.11	   mark(sqr(x0))
12.94/5.11	   mark(s(x0))
12.94/5.11	   mark(0)
12.94/5.11	   mark(add(x0, x1))
12.94/5.11	   mark(dbl(x0))
12.94/5.11	   mark(first(x0, x1))
12.94/5.11	   mark(nil)
12.94/5.11	   terms(mark(x0))
12.94/5.11	   terms(active(x0))
12.94/5.11	   cons(mark(x0), x1)
12.94/5.11	   cons(x0, mark(x1))
12.94/5.11	   cons(active(x0), x1)
12.94/5.11	   cons(x0, active(x1))
12.94/5.11	   recip(mark(x0))
12.94/5.11	   recip(active(x0))
12.94/5.11	   sqr(mark(x0))
12.94/5.11	   sqr(active(x0))
12.94/5.11	   s(mark(x0))
12.94/5.11	   s(active(x0))
12.94/5.11	   add(mark(x0), x1)
12.94/5.11	   add(x0, mark(x1))
12.94/5.11	   add(active(x0), x1)
12.94/5.11	   add(x0, active(x1))
12.94/5.11	   dbl(mark(x0))
12.94/5.11	   dbl(active(x0))
12.94/5.11	   first(mark(x0), x1)
12.94/5.11	   first(x0, mark(x1))
12.94/5.11	   first(active(x0), x1)
12.94/5.11	   first(x0, active(x1))
12.94/5.11	
12.94/5.11	We have to consider all minimal (P,Q,R)-chains.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(70) QDPOrderProof (EQUIVALENT)
12.94/5.11	We use the reduction pair processor [LPAR04,JAR06].
12.94/5.11	
12.94/5.11	
12.94/5.11	The following pairs can be oriented strictly and are deleted.
12.94/5.11	
12.94/5.11	   ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   MARK(terms(X)) -> MARK(X)
12.94/5.11	The remaining pairs can at least be oriented weakly.
12.94/5.11	Used ordering:  Combined order from the following AFS and order.
12.94/5.11	MARK(x1)  =  x1
12.94/5.11	
12.94/5.11	cons(x1, x2)  =  x1
12.94/5.11	
12.94/5.11	ACTIVE(x1)  =  x1
12.94/5.11	
12.94/5.11	mark(x1)  =  x1
12.94/5.11	
12.94/5.11	terms(x1)  =  terms(x1)
12.94/5.11	
12.94/5.11	recip(x1)  =  x1
12.94/5.11	
12.94/5.11	sqr(x1)  =  x1
12.94/5.11	
12.94/5.11	dbl(x1)  =  dbl
12.94/5.11	
12.94/5.11	first(x1, x2)  =  x2
12.94/5.11	
12.94/5.11	active(x1)  =  x1
12.94/5.11	
12.94/5.11	add(x1, x2)  =  add(x2)
12.94/5.11	
12.94/5.11	s(x1)  =  s
12.94/5.11	
12.94/5.11	0  =  0
12.94/5.11	
12.94/5.11	nil  =  nil
12.94/5.11	
12.94/5.11	
12.94/5.11	Knuth-Bendix order [KBO] with precedence:trivial
12.94/5.11	
12.94/5.11	and weight map:
12.94/5.11	
12.94/5.11	   s=3
12.94/5.11	   0=3
12.94/5.11	   terms_1=1
12.94/5.11	   add_1=3
12.94/5.11	   dbl=5
12.94/5.11	   nil=1
12.94/5.11	
12.94/5.11	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	
12.94/5.11	
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(71)
12.94/5.11	Obligation:
12.94/5.11	Q DP problem:
12.94/5.11	The TRS P consists of the following rules:
12.94/5.11	
12.94/5.11	   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
12.94/5.11	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(terms(X)) -> ACTIVE(terms(mark(X)))
12.94/5.11	   MARK(recip(X)) -> ACTIVE(recip(mark(X)))
12.94/5.11	   MARK(recip(X)) -> MARK(X)
12.94/5.11	   MARK(sqr(X)) -> ACTIVE(sqr(mark(X)))
12.94/5.11	   MARK(sqr(X)) -> MARK(X)
12.94/5.11	   MARK(dbl(X)) -> ACTIVE(dbl(mark(X)))
12.94/5.11	   MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2)))
12.94/5.11	
12.94/5.11	The TRS R consists of the following rules:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	
12.94/5.11	The set Q consists of the following terms:
12.94/5.11	
12.94/5.11	   active(terms(x0))
12.94/5.11	   active(sqr(0))
12.94/5.11	   active(sqr(s(x0)))
12.94/5.11	   active(dbl(0))
12.94/5.11	   active(dbl(s(x0)))
12.94/5.11	   active(add(0, x0))
12.94/5.11	   active(add(s(x0), x1))
12.94/5.11	   active(first(0, x0))
12.94/5.11	   active(first(s(x0), cons(x1, x2)))
12.94/5.11	   mark(terms(x0))
12.94/5.11	   mark(cons(x0, x1))
12.94/5.11	   mark(recip(x0))
12.94/5.11	   mark(sqr(x0))
12.94/5.11	   mark(s(x0))
12.94/5.11	   mark(0)
12.94/5.11	   mark(add(x0, x1))
12.94/5.11	   mark(dbl(x0))
12.94/5.11	   mark(first(x0, x1))
12.94/5.11	   mark(nil)
12.94/5.11	   terms(mark(x0))
12.94/5.11	   terms(active(x0))
12.94/5.11	   cons(mark(x0), x1)
12.94/5.11	   cons(x0, mark(x1))
12.94/5.11	   cons(active(x0), x1)
12.94/5.11	   cons(x0, active(x1))
12.94/5.11	   recip(mark(x0))
12.94/5.11	   recip(active(x0))
12.94/5.11	   sqr(mark(x0))
12.94/5.11	   sqr(active(x0))
12.94/5.11	   s(mark(x0))
12.94/5.11	   s(active(x0))
12.94/5.11	   add(mark(x0), x1)
12.94/5.11	   add(x0, mark(x1))
12.94/5.11	   add(active(x0), x1)
12.94/5.11	   add(x0, active(x1))
12.94/5.11	   dbl(mark(x0))
12.94/5.11	   dbl(active(x0))
12.94/5.11	   first(mark(x0), x1)
12.94/5.11	   first(x0, mark(x1))
12.94/5.11	   first(active(x0), x1)
12.94/5.11	   first(x0, active(x1))
12.94/5.11	
12.94/5.11	We have to consider all minimal (P,Q,R)-chains.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(72) DependencyGraphProof (EQUIVALENT)
12.94/5.11	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(73)
12.94/5.11	Obligation:
12.94/5.11	Q DP problem:
12.94/5.11	The TRS P consists of the following rules:
12.94/5.11	
12.94/5.11	   MARK(recip(X)) -> MARK(X)
12.94/5.11	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(sqr(X)) -> MARK(X)
12.94/5.11	
12.94/5.11	The TRS R consists of the following rules:
12.94/5.11	
12.94/5.11	   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
12.94/5.11	   active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N))))
12.94/5.11	   active(add(0, X)) -> mark(X)
12.94/5.11	   mark(terms(X)) -> active(terms(mark(X)))
12.94/5.11	   active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z)))
12.94/5.11	   mark(recip(X)) -> active(recip(mark(X)))
12.94/5.11	   mark(sqr(X)) -> active(sqr(mark(X)))
12.94/5.11	   mark(add(X1, X2)) -> active(add(mark(X1), mark(X2)))
12.94/5.11	   mark(dbl(X)) -> active(dbl(mark(X)))
12.94/5.11	   mark(first(X1, X2)) -> active(first(mark(X1), mark(X2)))
12.94/5.11	   mark(s(X)) -> active(s(X))
12.94/5.11	   mark(0) -> active(0)
12.94/5.11	   mark(nil) -> active(nil)
12.94/5.11	   first(X1, mark(X2)) -> first(X1, X2)
12.94/5.11	   first(mark(X1), X2) -> first(X1, X2)
12.94/5.11	   first(active(X1), X2) -> first(X1, X2)
12.94/5.11	   first(X1, active(X2)) -> first(X1, X2)
12.94/5.11	   active(sqr(0)) -> mark(0)
12.94/5.11	   active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X))))
12.94/5.11	   active(dbl(0)) -> mark(0)
12.94/5.11	   active(dbl(s(X))) -> mark(s(s(dbl(X))))
12.94/5.11	   active(add(s(X), Y)) -> mark(s(add(X, Y)))
12.94/5.11	   active(first(0, X)) -> mark(nil)
12.94/5.11	   cons(X1, mark(X2)) -> cons(X1, X2)
12.94/5.11	   cons(mark(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(active(X1), X2) -> cons(X1, X2)
12.94/5.11	   cons(X1, active(X2)) -> cons(X1, X2)
12.94/5.11	   terms(active(X)) -> terms(X)
12.94/5.11	   terms(mark(X)) -> terms(X)
12.94/5.11	   recip(active(X)) -> recip(X)
12.94/5.11	   recip(mark(X)) -> recip(X)
12.94/5.11	   sqr(active(X)) -> sqr(X)
12.94/5.11	   sqr(mark(X)) -> sqr(X)
12.94/5.11	   add(X1, mark(X2)) -> add(X1, X2)
12.94/5.11	   add(mark(X1), X2) -> add(X1, X2)
12.94/5.11	   add(active(X1), X2) -> add(X1, X2)
12.94/5.11	   add(X1, active(X2)) -> add(X1, X2)
12.94/5.11	   dbl(active(X)) -> dbl(X)
12.94/5.11	   dbl(mark(X)) -> dbl(X)
12.94/5.11	
12.94/5.11	The set Q consists of the following terms:
12.94/5.11	
12.94/5.11	   active(terms(x0))
12.94/5.11	   active(sqr(0))
12.94/5.11	   active(sqr(s(x0)))
12.94/5.11	   active(dbl(0))
12.94/5.11	   active(dbl(s(x0)))
12.94/5.11	   active(add(0, x0))
12.94/5.11	   active(add(s(x0), x1))
12.94/5.11	   active(first(0, x0))
12.94/5.11	   active(first(s(x0), cons(x1, x2)))
12.94/5.11	   mark(terms(x0))
12.94/5.11	   mark(cons(x0, x1))
12.94/5.11	   mark(recip(x0))
12.94/5.11	   mark(sqr(x0))
12.94/5.11	   mark(s(x0))
12.94/5.11	   mark(0)
12.94/5.11	   mark(add(x0, x1))
12.94/5.11	   mark(dbl(x0))
12.94/5.11	   mark(first(x0, x1))
12.94/5.11	   mark(nil)
12.94/5.11	   terms(mark(x0))
12.94/5.11	   terms(active(x0))
12.94/5.11	   cons(mark(x0), x1)
12.94/5.11	   cons(x0, mark(x1))
12.94/5.11	   cons(active(x0), x1)
12.94/5.11	   cons(x0, active(x1))
12.94/5.11	   recip(mark(x0))
12.94/5.11	   recip(active(x0))
12.94/5.11	   sqr(mark(x0))
12.94/5.11	   sqr(active(x0))
12.94/5.11	   s(mark(x0))
12.94/5.11	   s(active(x0))
12.94/5.11	   add(mark(x0), x1)
12.94/5.11	   add(x0, mark(x1))
12.94/5.11	   add(active(x0), x1)
12.94/5.11	   add(x0, active(x1))
12.94/5.11	   dbl(mark(x0))
12.94/5.11	   dbl(active(x0))
12.94/5.11	   first(mark(x0), x1)
12.94/5.11	   first(x0, mark(x1))
12.94/5.11	   first(active(x0), x1)
12.94/5.11	   first(x0, active(x1))
12.94/5.11	
12.94/5.11	We have to consider all minimal (P,Q,R)-chains.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(74) UsableRulesProof (EQUIVALENT)
12.94/5.11	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.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(75)
12.94/5.11	Obligation:
12.94/5.11	Q DP problem:
12.94/5.11	The TRS P consists of the following rules:
12.94/5.11	
12.94/5.11	   MARK(recip(X)) -> MARK(X)
12.94/5.11	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(sqr(X)) -> MARK(X)
12.94/5.11	
12.94/5.11	R is empty.
12.94/5.11	The set Q consists of the following terms:
12.94/5.11	
12.94/5.11	   active(terms(x0))
12.94/5.11	   active(sqr(0))
12.94/5.11	   active(sqr(s(x0)))
12.94/5.11	   active(dbl(0))
12.94/5.11	   active(dbl(s(x0)))
12.94/5.11	   active(add(0, x0))
12.94/5.11	   active(add(s(x0), x1))
12.94/5.11	   active(first(0, x0))
12.94/5.11	   active(first(s(x0), cons(x1, x2)))
12.94/5.11	   mark(terms(x0))
12.94/5.11	   mark(cons(x0, x1))
12.94/5.11	   mark(recip(x0))
12.94/5.11	   mark(sqr(x0))
12.94/5.11	   mark(s(x0))
12.94/5.11	   mark(0)
12.94/5.11	   mark(add(x0, x1))
12.94/5.11	   mark(dbl(x0))
12.94/5.11	   mark(first(x0, x1))
12.94/5.11	   mark(nil)
12.94/5.11	   terms(mark(x0))
12.94/5.11	   terms(active(x0))
12.94/5.11	   cons(mark(x0), x1)
12.94/5.11	   cons(x0, mark(x1))
12.94/5.11	   cons(active(x0), x1)
12.94/5.11	   cons(x0, active(x1))
12.94/5.11	   recip(mark(x0))
12.94/5.11	   recip(active(x0))
12.94/5.11	   sqr(mark(x0))
12.94/5.11	   sqr(active(x0))
12.94/5.11	   s(mark(x0))
12.94/5.11	   s(active(x0))
12.94/5.11	   add(mark(x0), x1)
12.94/5.11	   add(x0, mark(x1))
12.94/5.11	   add(active(x0), x1)
12.94/5.11	   add(x0, active(x1))
12.94/5.11	   dbl(mark(x0))
12.94/5.11	   dbl(active(x0))
12.94/5.11	   first(mark(x0), x1)
12.94/5.11	   first(x0, mark(x1))
12.94/5.11	   first(active(x0), x1)
12.94/5.11	   first(x0, active(x1))
12.94/5.11	
12.94/5.11	We have to consider all minimal (P,Q,R)-chains.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(76) QReductionProof (EQUIVALENT)
12.94/5.11	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
12.94/5.11	
12.94/5.11	   active(terms(x0))
12.94/5.11	   active(sqr(0))
12.94/5.11	   active(sqr(s(x0)))
12.94/5.11	   active(dbl(0))
12.94/5.11	   active(dbl(s(x0)))
12.94/5.11	   active(add(0, x0))
12.94/5.11	   active(add(s(x0), x1))
12.94/5.11	   active(first(0, x0))
12.94/5.11	   active(first(s(x0), cons(x1, x2)))
12.94/5.11	   mark(terms(x0))
12.94/5.11	   mark(cons(x0, x1))
12.94/5.11	   mark(recip(x0))
12.94/5.11	   mark(sqr(x0))
12.94/5.11	   mark(s(x0))
12.94/5.11	   mark(0)
12.94/5.11	   mark(add(x0, x1))
12.94/5.11	   mark(dbl(x0))
12.94/5.11	   mark(first(x0, x1))
12.94/5.11	   mark(nil)
12.94/5.11	   terms(mark(x0))
12.94/5.11	   terms(active(x0))
12.94/5.11	   s(mark(x0))
12.94/5.11	   s(active(x0))
12.94/5.11	   add(mark(x0), x1)
12.94/5.11	   add(x0, mark(x1))
12.94/5.11	   add(active(x0), x1)
12.94/5.11	   add(x0, active(x1))
12.94/5.11	   dbl(mark(x0))
12.94/5.11	   dbl(active(x0))
12.94/5.11	   first(mark(x0), x1)
12.94/5.11	   first(x0, mark(x1))
12.94/5.11	   first(active(x0), x1)
12.94/5.11	   first(x0, active(x1))
12.94/5.11	
12.94/5.11	
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(77)
12.94/5.11	Obligation:
12.94/5.11	Q DP problem:
12.94/5.11	The TRS P consists of the following rules:
12.94/5.11	
12.94/5.11	   MARK(recip(X)) -> MARK(X)
12.94/5.11	   MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.11	   MARK(sqr(X)) -> MARK(X)
12.94/5.11	
12.94/5.11	R is empty.
12.94/5.11	The set Q consists of the following terms:
12.94/5.11	
12.94/5.11	   cons(mark(x0), x1)
12.94/5.11	   cons(x0, mark(x1))
12.94/5.11	   cons(active(x0), x1)
12.94/5.11	   cons(x0, active(x1))
12.94/5.11	   recip(mark(x0))
12.94/5.11	   recip(active(x0))
12.94/5.11	   sqr(mark(x0))
12.94/5.11	   sqr(active(x0))
12.94/5.11	
12.94/5.11	We have to consider all minimal (P,Q,R)-chains.
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(78) QDPSizeChangeProof (EQUIVALENT)
12.94/5.11	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.94/5.11	
12.94/5.11	From the DPs we obtained the following set of size-change graphs:
12.94/5.11	*MARK(recip(X)) -> MARK(X)
12.94/5.11	The graph contains the following edges 1 > 1
12.94/5.11	
12.94/5.11	
12.94/5.11	*MARK(cons(X1, X2)) -> MARK(X1)
12.94/5.11	The graph contains the following edges 1 > 1
12.94/5.11	
12.94/5.11	
12.94/5.11	*MARK(sqr(X)) -> MARK(X)
12.94/5.11	The graph contains the following edges 1 > 1
12.94/5.11	
12.94/5.11	
12.94/5.11	----------------------------------------
12.94/5.11	
12.94/5.11	(79)
12.94/5.11	YES
12.94/5.14	EOF