5.59/2.43	YES
5.72/2.43	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
5.72/2.43	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.72/2.43	
5.72/2.43	
5.72/2.43	Termination w.r.t. Q of the given QTRS could be proven:
5.72/2.43	
5.72/2.43	(0) QTRS
5.72/2.43	(1) DependencyPairsProof [EQUIVALENT, 25 ms]
5.72/2.43	(2) QDP
5.72/2.43	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
5.72/2.43	(4) QDP
5.72/2.43	(5) QDPOrderProof [EQUIVALENT, 93 ms]
5.72/2.43	(6) QDP
5.72/2.43	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
5.72/2.43	(8) QDP
5.72/2.43	(9) UsableRulesProof [EQUIVALENT, 0 ms]
5.72/2.43	(10) QDP
5.72/2.43	(11) QReductionProof [EQUIVALENT, 0 ms]
5.72/2.43	(12) QDP
5.72/2.43	(13) QDPSizeChangeProof [EQUIVALENT, 0 ms]
5.72/2.43	(14) YES
5.72/2.43	
5.72/2.43	
5.72/2.43	----------------------------------------
5.72/2.43	
5.72/2.43	(0)
5.72/2.43	Obligation:
5.72/2.43	Q restricted rewrite system:
5.72/2.43	The TRS R consists of the following rules:
5.72/2.43	
5.72/2.43	   a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N)))
5.72/2.43	   a__sqr(0) -> 0
5.72/2.43	   a__sqr(s(X)) -> s(add(sqr(X), dbl(X)))
5.72/2.43	   a__dbl(0) -> 0
5.72/2.43	   a__dbl(s(X)) -> s(s(dbl(X)))
5.72/2.43	   a__add(0, X) -> mark(X)
5.72/2.43	   a__add(s(X), Y) -> s(add(X, Y))
5.72/2.43	   a__first(0, X) -> nil
5.72/2.43	   a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
5.72/2.43	   mark(terms(X)) -> a__terms(mark(X))
5.72/2.43	   mark(sqr(X)) -> a__sqr(mark(X))
5.72/2.43	   mark(add(X1, X2)) -> a__add(mark(X1), mark(X2))
5.72/2.43	   mark(dbl(X)) -> a__dbl(mark(X))
5.72/2.43	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
5.72/2.43	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
5.72/2.43	   mark(recip(X)) -> recip(mark(X))
5.72/2.43	   mark(s(X)) -> s(X)
5.72/2.43	   mark(0) -> 0
5.72/2.43	   mark(nil) -> nil
5.72/2.43	   a__terms(X) -> terms(X)
5.72/2.43	   a__sqr(X) -> sqr(X)
5.72/2.43	   a__add(X1, X2) -> add(X1, X2)
5.72/2.43	   a__dbl(X) -> dbl(X)
5.72/2.43	   a__first(X1, X2) -> first(X1, X2)
5.72/2.43	
5.72/2.43	The set Q consists of the following terms:
5.72/2.43	
5.72/2.43	   a__terms(x0)
5.72/2.43	   mark(terms(x0))
5.72/2.43	   mark(sqr(x0))
5.72/2.43	   mark(add(x0, x1))
5.72/2.43	   mark(dbl(x0))
5.72/2.43	   mark(first(x0, x1))
5.72/2.43	   mark(cons(x0, x1))
5.72/2.43	   mark(recip(x0))
5.72/2.43	   mark(s(x0))
5.72/2.43	   mark(0)
5.72/2.43	   mark(nil)
5.72/2.43	   a__sqr(x0)
5.72/2.43	   a__add(x0, x1)
5.72/2.43	   a__dbl(x0)
5.72/2.43	   a__first(x0, x1)
5.72/2.43	
5.72/2.43	
5.72/2.43	----------------------------------------
5.72/2.43	
5.72/2.43	(1) DependencyPairsProof (EQUIVALENT)
5.72/2.43	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
5.72/2.43	----------------------------------------
5.72/2.43	
5.72/2.43	(2)
5.72/2.43	Obligation:
5.72/2.43	Q DP problem:
5.72/2.43	The TRS P consists of the following rules:
5.72/2.43	
5.72/2.43	   A__TERMS(N) -> A__SQR(mark(N))
5.72/2.43	   A__TERMS(N) -> MARK(N)
5.72/2.43	   A__ADD(0, X) -> MARK(X)
5.72/2.43	   A__FIRST(s(X), cons(Y, Z)) -> MARK(Y)
5.72/2.43	   MARK(terms(X)) -> A__TERMS(mark(X))
5.72/2.43	   MARK(terms(X)) -> MARK(X)
5.72/2.43	   MARK(sqr(X)) -> A__SQR(mark(X))
5.72/2.43	   MARK(sqr(X)) -> MARK(X)
5.72/2.43	   MARK(add(X1, X2)) -> A__ADD(mark(X1), mark(X2))
5.72/2.43	   MARK(add(X1, X2)) -> MARK(X1)
5.72/2.43	   MARK(add(X1, X2)) -> MARK(X2)
5.72/2.43	   MARK(dbl(X)) -> A__DBL(mark(X))
5.72/2.43	   MARK(dbl(X)) -> MARK(X)
5.72/2.43	   MARK(first(X1, X2)) -> A__FIRST(mark(X1), mark(X2))
5.72/2.43	   MARK(first(X1, X2)) -> MARK(X1)
5.72/2.43	   MARK(first(X1, X2)) -> MARK(X2)
5.72/2.43	   MARK(cons(X1, X2)) -> MARK(X1)
5.72/2.43	   MARK(recip(X)) -> MARK(X)
5.72/2.43	
5.72/2.43	The TRS R consists of the following rules:
5.72/2.43	
5.72/2.43	   a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N)))
5.72/2.43	   a__sqr(0) -> 0
5.72/2.43	   a__sqr(s(X)) -> s(add(sqr(X), dbl(X)))
5.72/2.43	   a__dbl(0) -> 0
5.72/2.43	   a__dbl(s(X)) -> s(s(dbl(X)))
5.72/2.43	   a__add(0, X) -> mark(X)
5.72/2.43	   a__add(s(X), Y) -> s(add(X, Y))
5.72/2.43	   a__first(0, X) -> nil
5.72/2.43	   a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
5.72/2.43	   mark(terms(X)) -> a__terms(mark(X))
5.72/2.43	   mark(sqr(X)) -> a__sqr(mark(X))
5.72/2.43	   mark(add(X1, X2)) -> a__add(mark(X1), mark(X2))
5.72/2.43	   mark(dbl(X)) -> a__dbl(mark(X))
5.72/2.43	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
5.72/2.43	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
5.72/2.43	   mark(recip(X)) -> recip(mark(X))
5.72/2.43	   mark(s(X)) -> s(X)
5.72/2.43	   mark(0) -> 0
5.72/2.43	   mark(nil) -> nil
5.72/2.43	   a__terms(X) -> terms(X)
5.72/2.43	   a__sqr(X) -> sqr(X)
5.72/2.43	   a__add(X1, X2) -> add(X1, X2)
5.72/2.43	   a__dbl(X) -> dbl(X)
5.72/2.43	   a__first(X1, X2) -> first(X1, X2)
5.72/2.43	
5.72/2.43	The set Q consists of the following terms:
5.72/2.43	
5.72/2.43	   a__terms(x0)
5.72/2.43	   mark(terms(x0))
5.72/2.43	   mark(sqr(x0))
5.72/2.43	   mark(add(x0, x1))
5.72/2.43	   mark(dbl(x0))
5.72/2.43	   mark(first(x0, x1))
5.72/2.43	   mark(cons(x0, x1))
5.72/2.43	   mark(recip(x0))
5.72/2.43	   mark(s(x0))
5.72/2.43	   mark(0)
5.72/2.43	   mark(nil)
5.72/2.43	   a__sqr(x0)
5.72/2.43	   a__add(x0, x1)
5.72/2.43	   a__dbl(x0)
5.72/2.43	   a__first(x0, x1)
5.72/2.43	
5.72/2.43	We have to consider all minimal (P,Q,R)-chains.
5.72/2.43	----------------------------------------
5.72/2.43	
5.72/2.43	(3) DependencyGraphProof (EQUIVALENT)
5.72/2.43	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
5.72/2.43	----------------------------------------
5.72/2.43	
5.72/2.43	(4)
5.72/2.43	Obligation:
5.72/2.43	Q DP problem:
5.72/2.43	The TRS P consists of the following rules:
5.72/2.43	
5.72/2.43	   A__TERMS(N) -> MARK(N)
5.72/2.43	   MARK(terms(X)) -> A__TERMS(mark(X))
5.72/2.43	   MARK(terms(X)) -> MARK(X)
5.72/2.43	   MARK(sqr(X)) -> MARK(X)
5.72/2.43	   MARK(add(X1, X2)) -> A__ADD(mark(X1), mark(X2))
5.72/2.43	   A__ADD(0, X) -> MARK(X)
5.72/2.43	   MARK(add(X1, X2)) -> MARK(X1)
5.72/2.43	   MARK(add(X1, X2)) -> MARK(X2)
5.72/2.43	   MARK(dbl(X)) -> MARK(X)
5.72/2.43	   MARK(first(X1, X2)) -> A__FIRST(mark(X1), mark(X2))
5.72/2.43	   A__FIRST(s(X), cons(Y, Z)) -> MARK(Y)
5.72/2.43	   MARK(first(X1, X2)) -> MARK(X1)
5.72/2.43	   MARK(first(X1, X2)) -> MARK(X2)
5.72/2.43	   MARK(cons(X1, X2)) -> MARK(X1)
5.72/2.43	   MARK(recip(X)) -> MARK(X)
5.72/2.43	
5.72/2.43	The TRS R consists of the following rules:
5.72/2.43	
5.72/2.43	   a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N)))
5.72/2.43	   a__sqr(0) -> 0
5.72/2.43	   a__sqr(s(X)) -> s(add(sqr(X), dbl(X)))
5.72/2.43	   a__dbl(0) -> 0
5.72/2.43	   a__dbl(s(X)) -> s(s(dbl(X)))
5.72/2.43	   a__add(0, X) -> mark(X)
5.72/2.43	   a__add(s(X), Y) -> s(add(X, Y))
5.72/2.43	   a__first(0, X) -> nil
5.72/2.43	   a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
5.72/2.43	   mark(terms(X)) -> a__terms(mark(X))
5.72/2.43	   mark(sqr(X)) -> a__sqr(mark(X))
5.72/2.43	   mark(add(X1, X2)) -> a__add(mark(X1), mark(X2))
5.72/2.43	   mark(dbl(X)) -> a__dbl(mark(X))
5.72/2.43	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
5.72/2.43	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
5.72/2.43	   mark(recip(X)) -> recip(mark(X))
5.72/2.43	   mark(s(X)) -> s(X)
5.72/2.43	   mark(0) -> 0
5.72/2.43	   mark(nil) -> nil
5.72/2.43	   a__terms(X) -> terms(X)
5.72/2.43	   a__sqr(X) -> sqr(X)
5.72/2.43	   a__add(X1, X2) -> add(X1, X2)
5.72/2.43	   a__dbl(X) -> dbl(X)
5.72/2.43	   a__first(X1, X2) -> first(X1, X2)
5.72/2.43	
5.72/2.43	The set Q consists of the following terms:
5.72/2.43	
5.72/2.43	   a__terms(x0)
5.72/2.43	   mark(terms(x0))
5.72/2.43	   mark(sqr(x0))
5.72/2.43	   mark(add(x0, x1))
5.72/2.43	   mark(dbl(x0))
5.72/2.43	   mark(first(x0, x1))
5.72/2.43	   mark(cons(x0, x1))
5.72/2.43	   mark(recip(x0))
5.72/2.43	   mark(s(x0))
5.72/2.43	   mark(0)
5.72/2.43	   mark(nil)
5.72/2.43	   a__sqr(x0)
5.72/2.43	   a__add(x0, x1)
5.72/2.43	   a__dbl(x0)
5.72/2.43	   a__first(x0, x1)
5.72/2.43	
5.72/2.43	We have to consider all minimal (P,Q,R)-chains.
5.72/2.43	----------------------------------------
5.72/2.43	
5.72/2.43	(5) QDPOrderProof (EQUIVALENT)
5.72/2.43	We use the reduction pair processor [LPAR04,JAR06].
5.72/2.43	
5.72/2.43	
5.72/2.43	The following pairs can be oriented strictly and are deleted.
5.72/2.43	
5.72/2.43	   A__TERMS(N) -> MARK(N)
5.72/2.43	   MARK(terms(X)) -> A__TERMS(mark(X))
5.72/2.43	   MARK(terms(X)) -> MARK(X)
5.72/2.43	   MARK(add(X1, X2)) -> A__ADD(mark(X1), mark(X2))
5.72/2.43	   A__ADD(0, X) -> MARK(X)
5.72/2.43	   MARK(add(X1, X2)) -> MARK(X1)
5.72/2.43	   MARK(add(X1, X2)) -> MARK(X2)
5.72/2.43	   A__FIRST(s(X), cons(Y, Z)) -> MARK(Y)
5.72/2.43	   MARK(first(X1, X2)) -> MARK(X1)
5.72/2.43	   MARK(first(X1, X2)) -> MARK(X2)
5.72/2.43	   MARK(cons(X1, X2)) -> MARK(X1)
5.72/2.43	The remaining pairs can at least be oriented weakly.
5.72/2.43	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
5.72/2.43	
5.72/2.43	POL( A__ADD_2(x_1, x_2) ) = 2x_2 + 1
5.72/2.43	POL( A__FIRST_2(x_1, x_2) ) = x_1 + 2x_2 + 2
5.72/2.43	POL( A__TERMS_1(x_1) ) = 2x_1 + 1
5.72/2.43	POL( mark_1(x_1) ) = x_1
5.72/2.43	POL( terms_1(x_1) ) = 2x_1 + 1
5.72/2.43	POL( a__terms_1(x_1) ) = 2x_1 + 1
5.72/2.43	POL( sqr_1(x_1) ) = x_1
5.72/2.43	POL( a__sqr_1(x_1) ) = x_1
5.72/2.43	POL( add_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1
5.72/2.43	POL( a__add_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1
5.72/2.43	POL( 0 ) = 0
5.72/2.43	POL( dbl_1(x_1) ) = x_1
5.72/2.43	POL( a__dbl_1(x_1) ) = x_1
5.72/2.43	POL( first_2(x_1, x_2) ) = x_1 + x_2 + 1
5.72/2.43	POL( a__first_2(x_1, x_2) ) = x_1 + x_2 + 1
5.72/2.43	POL( cons_2(x_1, x_2) ) = x_1 + 1
5.72/2.44	POL( recip_1(x_1) ) = x_1
5.72/2.44	POL( s_1(x_1) ) = 2
5.72/2.44	POL( nil ) = 0
5.72/2.44	POL( MARK_1(x_1) ) = 2x_1
5.72/2.44	
5.72/2.44	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
5.72/2.44	
5.72/2.44	   mark(terms(X)) -> a__terms(mark(X))
5.72/2.44	   mark(sqr(X)) -> a__sqr(mark(X))
5.72/2.44	   mark(add(X1, X2)) -> a__add(mark(X1), mark(X2))
5.72/2.44	   a__add(0, X) -> mark(X)
5.72/2.44	   mark(dbl(X)) -> a__dbl(mark(X))
5.72/2.44	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
5.72/2.44	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
5.72/2.44	   mark(recip(X)) -> recip(mark(X))
5.72/2.44	   mark(s(X)) -> s(X)
5.72/2.44	   mark(0) -> 0
5.72/2.44	   mark(nil) -> nil
5.72/2.44	   a__terms(X) -> terms(X)
5.72/2.44	   a__sqr(0) -> 0
5.72/2.44	   a__sqr(s(X)) -> s(add(sqr(X), dbl(X)))
5.72/2.44	   a__sqr(X) -> sqr(X)
5.72/2.44	   a__add(s(X), Y) -> s(add(X, Y))
5.72/2.44	   a__add(X1, X2) -> add(X1, X2)
5.72/2.44	   a__dbl(0) -> 0
5.72/2.44	   a__dbl(s(X)) -> s(s(dbl(X)))
5.72/2.44	   a__dbl(X) -> dbl(X)
5.72/2.44	   a__first(0, X) -> nil
5.72/2.44	   a__first(X1, X2) -> first(X1, X2)
5.72/2.44	   a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
5.72/2.44	   a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N)))
5.72/2.44	
5.72/2.44	
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(6)
5.72/2.44	Obligation:
5.72/2.44	Q DP problem:
5.72/2.44	The TRS P consists of the following rules:
5.72/2.44	
5.72/2.44	   MARK(sqr(X)) -> MARK(X)
5.72/2.44	   MARK(dbl(X)) -> MARK(X)
5.72/2.44	   MARK(first(X1, X2)) -> A__FIRST(mark(X1), mark(X2))
5.72/2.44	   MARK(recip(X)) -> MARK(X)
5.72/2.44	
5.72/2.44	The TRS R consists of the following rules:
5.72/2.44	
5.72/2.44	   a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N)))
5.72/2.44	   a__sqr(0) -> 0
5.72/2.44	   a__sqr(s(X)) -> s(add(sqr(X), dbl(X)))
5.72/2.44	   a__dbl(0) -> 0
5.72/2.44	   a__dbl(s(X)) -> s(s(dbl(X)))
5.72/2.44	   a__add(0, X) -> mark(X)
5.72/2.44	   a__add(s(X), Y) -> s(add(X, Y))
5.72/2.44	   a__first(0, X) -> nil
5.72/2.44	   a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
5.72/2.44	   mark(terms(X)) -> a__terms(mark(X))
5.72/2.44	   mark(sqr(X)) -> a__sqr(mark(X))
5.72/2.44	   mark(add(X1, X2)) -> a__add(mark(X1), mark(X2))
5.72/2.44	   mark(dbl(X)) -> a__dbl(mark(X))
5.72/2.44	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
5.72/2.44	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
5.72/2.44	   mark(recip(X)) -> recip(mark(X))
5.72/2.44	   mark(s(X)) -> s(X)
5.72/2.44	   mark(0) -> 0
5.72/2.44	   mark(nil) -> nil
5.72/2.44	   a__terms(X) -> terms(X)
5.72/2.44	   a__sqr(X) -> sqr(X)
5.72/2.44	   a__add(X1, X2) -> add(X1, X2)
5.72/2.44	   a__dbl(X) -> dbl(X)
5.72/2.44	   a__first(X1, X2) -> first(X1, X2)
5.72/2.44	
5.72/2.44	The set Q consists of the following terms:
5.72/2.44	
5.72/2.44	   a__terms(x0)
5.72/2.44	   mark(terms(x0))
5.72/2.44	   mark(sqr(x0))
5.72/2.44	   mark(add(x0, x1))
5.72/2.44	   mark(dbl(x0))
5.72/2.44	   mark(first(x0, x1))
5.72/2.44	   mark(cons(x0, x1))
5.72/2.44	   mark(recip(x0))
5.72/2.44	   mark(s(x0))
5.72/2.44	   mark(0)
5.72/2.44	   mark(nil)
5.72/2.44	   a__sqr(x0)
5.72/2.44	   a__add(x0, x1)
5.72/2.44	   a__dbl(x0)
5.72/2.44	   a__first(x0, x1)
5.72/2.44	
5.72/2.44	We have to consider all minimal (P,Q,R)-chains.
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(7) DependencyGraphProof (EQUIVALENT)
5.72/2.44	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(8)
5.72/2.44	Obligation:
5.72/2.44	Q DP problem:
5.72/2.44	The TRS P consists of the following rules:
5.72/2.44	
5.72/2.44	   MARK(dbl(X)) -> MARK(X)
5.72/2.44	   MARK(sqr(X)) -> MARK(X)
5.72/2.44	   MARK(recip(X)) -> MARK(X)
5.72/2.44	
5.72/2.44	The TRS R consists of the following rules:
5.72/2.44	
5.72/2.44	   a__terms(N) -> cons(recip(a__sqr(mark(N))), terms(s(N)))
5.72/2.44	   a__sqr(0) -> 0
5.72/2.44	   a__sqr(s(X)) -> s(add(sqr(X), dbl(X)))
5.72/2.44	   a__dbl(0) -> 0
5.72/2.44	   a__dbl(s(X)) -> s(s(dbl(X)))
5.72/2.44	   a__add(0, X) -> mark(X)
5.72/2.44	   a__add(s(X), Y) -> s(add(X, Y))
5.72/2.44	   a__first(0, X) -> nil
5.72/2.44	   a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
5.72/2.44	   mark(terms(X)) -> a__terms(mark(X))
5.72/2.44	   mark(sqr(X)) -> a__sqr(mark(X))
5.72/2.44	   mark(add(X1, X2)) -> a__add(mark(X1), mark(X2))
5.72/2.44	   mark(dbl(X)) -> a__dbl(mark(X))
5.72/2.44	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
5.72/2.44	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
5.72/2.44	   mark(recip(X)) -> recip(mark(X))
5.72/2.44	   mark(s(X)) -> s(X)
5.72/2.44	   mark(0) -> 0
5.72/2.44	   mark(nil) -> nil
5.72/2.44	   a__terms(X) -> terms(X)
5.72/2.44	   a__sqr(X) -> sqr(X)
5.72/2.44	   a__add(X1, X2) -> add(X1, X2)
5.72/2.44	   a__dbl(X) -> dbl(X)
5.72/2.44	   a__first(X1, X2) -> first(X1, X2)
5.72/2.44	
5.72/2.44	The set Q consists of the following terms:
5.72/2.44	
5.72/2.44	   a__terms(x0)
5.72/2.44	   mark(terms(x0))
5.72/2.44	   mark(sqr(x0))
5.72/2.44	   mark(add(x0, x1))
5.72/2.44	   mark(dbl(x0))
5.72/2.44	   mark(first(x0, x1))
5.72/2.44	   mark(cons(x0, x1))
5.72/2.44	   mark(recip(x0))
5.72/2.44	   mark(s(x0))
5.72/2.44	   mark(0)
5.72/2.44	   mark(nil)
5.72/2.44	   a__sqr(x0)
5.72/2.44	   a__add(x0, x1)
5.72/2.44	   a__dbl(x0)
5.72/2.44	   a__first(x0, x1)
5.72/2.44	
5.72/2.44	We have to consider all minimal (P,Q,R)-chains.
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(9) UsableRulesProof (EQUIVALENT)
5.72/2.44	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.
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(10)
5.72/2.44	Obligation:
5.72/2.44	Q DP problem:
5.72/2.44	The TRS P consists of the following rules:
5.72/2.44	
5.72/2.44	   MARK(dbl(X)) -> MARK(X)
5.72/2.44	   MARK(sqr(X)) -> MARK(X)
5.72/2.44	   MARK(recip(X)) -> MARK(X)
5.72/2.44	
5.72/2.44	R is empty.
5.72/2.44	The set Q consists of the following terms:
5.72/2.44	
5.72/2.44	   a__terms(x0)
5.72/2.44	   mark(terms(x0))
5.72/2.44	   mark(sqr(x0))
5.72/2.44	   mark(add(x0, x1))
5.72/2.44	   mark(dbl(x0))
5.72/2.44	   mark(first(x0, x1))
5.72/2.44	   mark(cons(x0, x1))
5.72/2.44	   mark(recip(x0))
5.72/2.44	   mark(s(x0))
5.72/2.44	   mark(0)
5.72/2.44	   mark(nil)
5.72/2.44	   a__sqr(x0)
5.72/2.44	   a__add(x0, x1)
5.72/2.44	   a__dbl(x0)
5.72/2.44	   a__first(x0, x1)
5.72/2.44	
5.72/2.44	We have to consider all minimal (P,Q,R)-chains.
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(11) QReductionProof (EQUIVALENT)
5.72/2.44	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
5.72/2.44	
5.72/2.44	   a__terms(x0)
5.72/2.44	   mark(terms(x0))
5.72/2.44	   mark(sqr(x0))
5.72/2.44	   mark(add(x0, x1))
5.72/2.44	   mark(dbl(x0))
5.72/2.44	   mark(first(x0, x1))
5.72/2.44	   mark(cons(x0, x1))
5.72/2.44	   mark(recip(x0))
5.72/2.44	   mark(s(x0))
5.72/2.44	   mark(0)
5.72/2.44	   mark(nil)
5.72/2.44	   a__sqr(x0)
5.72/2.44	   a__add(x0, x1)
5.72/2.44	   a__dbl(x0)
5.72/2.44	   a__first(x0, x1)
5.72/2.44	
5.72/2.44	
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(12)
5.72/2.44	Obligation:
5.72/2.44	Q DP problem:
5.72/2.44	The TRS P consists of the following rules:
5.72/2.44	
5.72/2.44	   MARK(dbl(X)) -> MARK(X)
5.72/2.44	   MARK(sqr(X)) -> MARK(X)
5.72/2.44	   MARK(recip(X)) -> MARK(X)
5.72/2.44	
5.72/2.44	R is empty.
5.72/2.44	Q is empty.
5.72/2.44	We have to consider all minimal (P,Q,R)-chains.
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(13) QDPSizeChangeProof (EQUIVALENT)
5.72/2.44	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. 
5.72/2.44	
5.72/2.44	From the DPs we obtained the following set of size-change graphs:
5.72/2.44	*MARK(dbl(X)) -> MARK(X)
5.72/2.44	The graph contains the following edges 1 > 1
5.72/2.44	
5.72/2.44	
5.72/2.44	*MARK(sqr(X)) -> MARK(X)
5.72/2.44	The graph contains the following edges 1 > 1
5.72/2.44	
5.72/2.44	
5.72/2.44	*MARK(recip(X)) -> MARK(X)
5.72/2.44	The graph contains the following edges 1 > 1
5.72/2.44	
5.72/2.44	
5.72/2.44	----------------------------------------
5.72/2.44	
5.72/2.44	(14)
5.72/2.44	YES
5.76/2.49	EOF