3.44/1.53	YES
3.44/1.54	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
3.44/1.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.44/1.54	
3.44/1.54	
3.44/1.54	Termination of the given CSR could be proven:
3.44/1.54	
3.44/1.54	(0) CSR
3.44/1.54	(1) CSRInnermostProof [EQUIVALENT, 0 ms]
3.44/1.54	(2) CSR
3.44/1.54	(3) CSDependencyPairsProof [EQUIVALENT, 11 ms]
3.44/1.54	(4) QCSDP
3.44/1.54	(5) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
3.44/1.54	(6) AND
3.44/1.54	    (7) QCSDP
3.44/1.54	        (8) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.44/1.54	        (9) QCSDP
3.44/1.54	        (10) PIsEmptyProof [EQUIVALENT, 0 ms]
3.44/1.54	        (11) YES
3.44/1.54	    (12) QCSDP
3.44/1.54	        (13) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.44/1.54	        (14) QCSDP
3.44/1.54	        (15) PIsEmptyProof [EQUIVALENT, 0 ms]
3.44/1.54	        (16) YES
3.44/1.54	    (17) QCSDP
3.44/1.54	        (18) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.44/1.54	        (19) QCSDP
3.44/1.54	        (20) PIsEmptyProof [EQUIVALENT, 0 ms]
3.44/1.54	        (21) YES
3.44/1.54	
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(0)
3.44/1.54	Obligation:
3.44/1.54	Context-sensitive rewrite system:
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The replacement map contains the following entries:
3.44/1.54	
3.44/1.54	terms: {1}
3.44/1.54	cons: {1}
3.44/1.54	recip: {1}
3.44/1.54	sqr: {1}
3.44/1.54	s: {1}
3.44/1.54	0: empty set
3.44/1.54	add: {1, 2}
3.44/1.54	dbl: {1}
3.44/1.54	first: {1, 2}
3.44/1.54	nil: empty set
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(1) CSRInnermostProof (EQUIVALENT)
3.44/1.54	The CSR is orthogonal. By [CS_Inn] we can switch to innermost.
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(2)
3.44/1.54	Obligation:
3.44/1.54	Context-sensitive rewrite system:
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The replacement map contains the following entries:
3.44/1.54	
3.44/1.54	terms: {1}
3.44/1.54	cons: {1}
3.44/1.54	recip: {1}
3.44/1.54	sqr: {1}
3.44/1.54	s: {1}
3.44/1.54	0: empty set
3.44/1.54	add: {1, 2}
3.44/1.54	dbl: {1}
3.44/1.54	first: {1, 2}
3.44/1.54	nil: empty set
3.44/1.54	
3.44/1.54	
3.44/1.54	Innermost Strategy.
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(3) CSDependencyPairsProof (EQUIVALENT)
3.44/1.54	Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(4)
3.44/1.54	Obligation:
3.44/1.54	Q-restricted context-sensitive dependency pair problem:
3.44/1.54	The symbols in {terms_1, recip_1, sqr_1, s_1, add_2, dbl_1, first_2, SQR_1, TERMS_1, ADD_2, DBL_1} are replacing on all positions.
3.44/1.54	For all symbols f in {cons_2} we have mu(f) = {1}.
3.44/1.54	
3.44/1.54	The ordinary context-sensitive dependency pairs DP_o are:
3.44/1.54	   TERMS(N) -> SQR(N)
3.44/1.54	   SQR(s(X)) -> ADD(sqr(X), dbl(X))
3.44/1.54	   SQR(s(X)) -> SQR(X)
3.44/1.54	   SQR(s(X)) -> DBL(X)
3.44/1.54	   DBL(s(X)) -> DBL(X)
3.44/1.54	   ADD(s(X), Y) -> ADD(X, Y)
3.44/1.54	
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The set Q consists of the following terms:
3.44/1.54	
3.44/1.54	   terms(x0)
3.44/1.54	   sqr(0)
3.44/1.54	   sqr(s(x0))
3.44/1.54	   dbl(0)
3.44/1.54	   dbl(s(x0))
3.44/1.54	   add(0, x0)
3.44/1.54	   add(s(x0), x1)
3.44/1.54	   first(0, x0)
3.44/1.54	   first(s(x0), cons(x1, x2))
3.44/1.54	
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(5) QCSDependencyGraphProof (EQUIVALENT)
3.44/1.54	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 3 SCCs with 3 less nodes.
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(6)
3.44/1.54	Complex Obligation (AND)
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(7)
3.44/1.54	Obligation:
3.44/1.54	Q-restricted context-sensitive dependency pair problem:
3.44/1.54	The symbols in {terms_1, recip_1, sqr_1, s_1, add_2, dbl_1, first_2, DBL_1} are replacing on all positions.
3.44/1.54	For all symbols f in {cons_2} we have mu(f) = {1}.
3.44/1.54	
3.44/1.54	The TRS P consists of the following rules:
3.44/1.54	
3.44/1.54	   DBL(s(X)) -> DBL(X)
3.44/1.54	
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The set Q consists of the following terms:
3.44/1.54	
3.44/1.54	   terms(x0)
3.44/1.54	   sqr(0)
3.44/1.54	   sqr(s(x0))
3.44/1.54	   dbl(0)
3.44/1.54	   dbl(s(x0))
3.44/1.54	   add(0, x0)
3.44/1.54	   add(s(x0), x1)
3.44/1.54	   first(0, x0)
3.44/1.54	   first(s(x0), cons(x1, x2))
3.44/1.54	
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(8) QCSDPSubtermProof (EQUIVALENT)
3.44/1.54	We use the subterm processor [DA_EMMES].
3.44/1.54	
3.44/1.54	
3.44/1.54	The following pairs can be oriented strictly and are deleted.
3.44/1.54	
3.44/1.54	   DBL(s(X)) -> DBL(X)
3.44/1.54	The remaining pairs can at least be oriented weakly.
3.44/1.54	none
3.44/1.54	Used ordering:  Combined order from the following AFS and order.
3.44/1.54	DBL(x1)  =  x1
3.44/1.54	
3.44/1.54	
3.44/1.54	Subterm Order
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(9)
3.44/1.54	Obligation:
3.44/1.54	Q-restricted context-sensitive dependency pair problem:
3.44/1.54	The symbols in {terms_1, recip_1, sqr_1, s_1, add_2, dbl_1, first_2} are replacing on all positions.
3.44/1.54	For all symbols f in {cons_2} we have mu(f) = {1}.
3.44/1.54	
3.44/1.54	The TRS P consists of the following rules:
3.44/1.54	none
3.44/1.54	
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The set Q consists of the following terms:
3.44/1.54	
3.44/1.54	   terms(x0)
3.44/1.54	   sqr(0)
3.44/1.54	   sqr(s(x0))
3.44/1.54	   dbl(0)
3.44/1.54	   dbl(s(x0))
3.44/1.54	   add(0, x0)
3.44/1.54	   add(s(x0), x1)
3.44/1.54	   first(0, x0)
3.44/1.54	   first(s(x0), cons(x1, x2))
3.44/1.54	
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(10) PIsEmptyProof (EQUIVALENT)
3.44/1.54	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(11)
3.44/1.54	YES
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(12)
3.44/1.54	Obligation:
3.44/1.54	Q-restricted context-sensitive dependency pair problem:
3.44/1.54	The symbols in {terms_1, recip_1, sqr_1, s_1, add_2, dbl_1, first_2, ADD_2} are replacing on all positions.
3.44/1.54	For all symbols f in {cons_2} we have mu(f) = {1}.
3.44/1.54	
3.44/1.54	The TRS P consists of the following rules:
3.44/1.54	
3.44/1.54	   ADD(s(X), Y) -> ADD(X, Y)
3.44/1.54	
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The set Q consists of the following terms:
3.44/1.54	
3.44/1.54	   terms(x0)
3.44/1.54	   sqr(0)
3.44/1.54	   sqr(s(x0))
3.44/1.54	   dbl(0)
3.44/1.54	   dbl(s(x0))
3.44/1.54	   add(0, x0)
3.44/1.54	   add(s(x0), x1)
3.44/1.54	   first(0, x0)
3.44/1.54	   first(s(x0), cons(x1, x2))
3.44/1.54	
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(13) QCSDPSubtermProof (EQUIVALENT)
3.44/1.54	We use the subterm processor [DA_EMMES].
3.44/1.54	
3.44/1.54	
3.44/1.54	The following pairs can be oriented strictly and are deleted.
3.44/1.54	
3.44/1.54	   ADD(s(X), Y) -> ADD(X, Y)
3.44/1.54	The remaining pairs can at least be oriented weakly.
3.44/1.54	none
3.44/1.54	Used ordering:  Combined order from the following AFS and order.
3.44/1.54	ADD(x1, x2)  =  x1
3.44/1.54	
3.44/1.54	
3.44/1.54	Subterm Order
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(14)
3.44/1.54	Obligation:
3.44/1.54	Q-restricted context-sensitive dependency pair problem:
3.44/1.54	The symbols in {terms_1, recip_1, sqr_1, s_1, add_2, dbl_1, first_2} are replacing on all positions.
3.44/1.54	For all symbols f in {cons_2} we have mu(f) = {1}.
3.44/1.54	
3.44/1.54	The TRS P consists of the following rules:
3.44/1.54	none
3.44/1.54	
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The set Q consists of the following terms:
3.44/1.54	
3.44/1.54	   terms(x0)
3.44/1.54	   sqr(0)
3.44/1.54	   sqr(s(x0))
3.44/1.54	   dbl(0)
3.44/1.54	   dbl(s(x0))
3.44/1.54	   add(0, x0)
3.44/1.54	   add(s(x0), x1)
3.44/1.54	   first(0, x0)
3.44/1.54	   first(s(x0), cons(x1, x2))
3.44/1.54	
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(15) PIsEmptyProof (EQUIVALENT)
3.44/1.54	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(16)
3.44/1.54	YES
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(17)
3.44/1.54	Obligation:
3.44/1.54	Q-restricted context-sensitive dependency pair problem:
3.44/1.54	The symbols in {terms_1, recip_1, sqr_1, s_1, add_2, dbl_1, first_2, SQR_1} are replacing on all positions.
3.44/1.54	For all symbols f in {cons_2} we have mu(f) = {1}.
3.44/1.54	
3.44/1.54	The TRS P consists of the following rules:
3.44/1.54	
3.44/1.54	   SQR(s(X)) -> SQR(X)
3.44/1.54	
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The set Q consists of the following terms:
3.44/1.54	
3.44/1.54	   terms(x0)
3.44/1.54	   sqr(0)
3.44/1.54	   sqr(s(x0))
3.44/1.54	   dbl(0)
3.44/1.54	   dbl(s(x0))
3.44/1.54	   add(0, x0)
3.44/1.54	   add(s(x0), x1)
3.44/1.54	   first(0, x0)
3.44/1.54	   first(s(x0), cons(x1, x2))
3.44/1.54	
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(18) QCSDPSubtermProof (EQUIVALENT)
3.44/1.54	We use the subterm processor [DA_EMMES].
3.44/1.54	
3.44/1.54	
3.44/1.54	The following pairs can be oriented strictly and are deleted.
3.44/1.54	
3.44/1.54	   SQR(s(X)) -> SQR(X)
3.44/1.54	The remaining pairs can at least be oriented weakly.
3.44/1.54	none
3.44/1.54	Used ordering:  Combined order from the following AFS and order.
3.44/1.54	SQR(x1)  =  x1
3.44/1.54	
3.44/1.54	
3.44/1.54	Subterm Order
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(19)
3.44/1.54	Obligation:
3.44/1.54	Q-restricted context-sensitive dependency pair problem:
3.44/1.54	The symbols in {terms_1, recip_1, sqr_1, s_1, add_2, dbl_1, first_2} are replacing on all positions.
3.44/1.54	For all symbols f in {cons_2} we have mu(f) = {1}.
3.44/1.54	
3.44/1.54	The TRS P consists of the following rules:
3.44/1.54	none
3.44/1.54	
3.44/1.54	The TRS R consists of the following rules:
3.44/1.54	
3.44/1.54	   terms(N) -> cons(recip(sqr(N)), terms(s(N)))
3.44/1.54	   sqr(0) -> 0
3.44/1.54	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
3.44/1.54	   dbl(0) -> 0
3.44/1.54	   dbl(s(X)) -> s(s(dbl(X)))
3.44/1.54	   add(0, X) -> X
3.44/1.54	   add(s(X), Y) -> s(add(X, Y))
3.44/1.54	   first(0, X) -> nil
3.44/1.54	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.44/1.54	
3.44/1.54	The set Q consists of the following terms:
3.44/1.54	
3.44/1.54	   terms(x0)
3.44/1.54	   sqr(0)
3.44/1.54	   sqr(s(x0))
3.44/1.54	   dbl(0)
3.44/1.54	   dbl(s(x0))
3.44/1.54	   add(0, x0)
3.44/1.54	   add(s(x0), x1)
3.44/1.54	   first(0, x0)
3.44/1.54	   first(s(x0), cons(x1, x2))
3.44/1.54	
3.44/1.54	
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(20) PIsEmptyProof (EQUIVALENT)
3.44/1.54	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
3.44/1.54	----------------------------------------
3.44/1.54	
3.44/1.54	(21)
3.44/1.54	YES
3.44/1.57	EOF