2.98/1.43	YES
2.98/1.44	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
2.98/1.44	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
2.98/1.44	
2.98/1.44	
2.98/1.44	Termination of the given CSR could be proven:
2.98/1.44	
2.98/1.44	(0) CSR
2.98/1.44	(1) CSRInnermostProof [EQUIVALENT, 0 ms]
2.98/1.44	(2) CSR
2.98/1.44	(3) CSDependencyPairsProof [EQUIVALENT, 0 ms]
2.98/1.44	(4) QCSDP
2.98/1.44	(5) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
2.98/1.44	(6) AND
2.98/1.44	    (7) QCSDP
2.98/1.44	        (8) QCSDPSubtermProof [EQUIVALENT, 0 ms]
2.98/1.44	        (9) QCSDP
2.98/1.44	        (10) PIsEmptyProof [EQUIVALENT, 0 ms]
2.98/1.44	        (11) YES
2.98/1.44	    (12) QCSDP
2.98/1.44	        (13) QCSDPSubtermProof [EQUIVALENT, 0 ms]
2.98/1.44	        (14) QCSDP
2.98/1.44	        (15) PIsEmptyProof [EQUIVALENT, 0 ms]
2.98/1.44	        (16) YES
2.98/1.44	
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(0)
2.98/1.44	Obligation:
2.98/1.44	Context-sensitive rewrite system:
2.98/1.44	The TRS R consists of the following rules:
2.98/1.44	
2.98/1.44	   from(X) -> cons(X, from(s(X)))
2.98/1.44	   first(0, Z) -> nil
2.98/1.44	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
2.98/1.44	   sel(0, cons(X, Z)) -> X
2.98/1.44	   sel(s(X), cons(Y, Z)) -> sel(X, Z)
2.98/1.44	
2.98/1.44	The replacement map contains the following entries:
2.98/1.44	
2.98/1.44	from: {1}
2.98/1.44	cons: {1}
2.98/1.44	s: {1}
2.98/1.44	first: {1, 2}
2.98/1.44	0: empty set
2.98/1.44	nil: empty set
2.98/1.44	sel: {1, 2}
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(1) CSRInnermostProof (EQUIVALENT)
2.98/1.44	The CSR is orthogonal. By [CS_Inn] we can switch to innermost.
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(2)
2.98/1.44	Obligation:
2.98/1.44	Context-sensitive rewrite system:
2.98/1.44	The TRS R consists of the following rules:
2.98/1.44	
2.98/1.44	   from(X) -> cons(X, from(s(X)))
2.98/1.44	   first(0, Z) -> nil
2.98/1.44	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
2.98/1.44	   sel(0, cons(X, Z)) -> X
2.98/1.44	   sel(s(X), cons(Y, Z)) -> sel(X, Z)
2.98/1.44	
2.98/1.44	The replacement map contains the following entries:
2.98/1.44	
2.98/1.44	from: {1}
2.98/1.44	cons: {1}
2.98/1.44	s: {1}
2.98/1.44	first: {1, 2}
2.98/1.44	0: empty set
2.98/1.44	nil: empty set
2.98/1.44	sel: {1, 2}
2.98/1.44	
2.98/1.44	
2.98/1.44	Innermost Strategy.
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(3) CSDependencyPairsProof (EQUIVALENT)
2.98/1.44	Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(4)
2.98/1.44	Obligation:
2.98/1.44	Q-restricted context-sensitive dependency pair problem:
2.98/1.44	The symbols in {from_1, s_1, first_2, sel_2, SEL_2, FROM_1, FIRST_2} are replacing on all positions.
2.98/1.44	For all symbols f in {cons_2} we have mu(f) = {1}.
2.98/1.44	The symbols in {U_1} are not replacing on any position.
2.98/1.44	
2.98/1.44	The ordinary context-sensitive dependency pairs DP_o are:
2.98/1.44	   SEL(s(X), cons(Y, Z)) -> SEL(X, Z)
2.98/1.44	
2.98/1.44	The collapsing dependency pairs are DP_c:
2.98/1.44	   SEL(s(X), cons(Y, Z)) -> Z
2.98/1.44	
2.98/1.44	
2.98/1.44	The hidden terms of R are:
2.98/1.44	
2.98/1.44	   from(s(x0))
2.98/1.44	   first(x0, x1)
2.98/1.44	
2.98/1.44	Every hiding context is built from:
2.98/1.44	   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@358e7922
2.98/1.44	   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@31d07a7a
2.98/1.44	   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@5968a76c
2.98/1.44	
2.98/1.44	Hence, the new unhiding pairs DP_u are :
2.98/1.44	   SEL(s(X), cons(Y, Z)) -> U(Z)
2.98/1.44	   U(s(x_0)) -> U(x_0)
2.98/1.44	   U(from(x_0)) -> U(x_0)
2.98/1.44	   U(first(x_0, x_1)) -> U(x_0)
2.98/1.44	   U(first(x_0, x_1)) -> U(x_1)
2.98/1.44	   U(from(s(x0))) -> FROM(s(x0))
2.98/1.44	   U(first(x0, x1)) -> FIRST(x0, x1)
2.98/1.44	
2.98/1.44	The TRS R consists of the following rules:
2.98/1.44	
2.98/1.44	   from(X) -> cons(X, from(s(X)))
2.98/1.44	   first(0, Z) -> nil
2.98/1.44	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
2.98/1.44	   sel(0, cons(X, Z)) -> X
2.98/1.44	   sel(s(X), cons(Y, Z)) -> sel(X, Z)
2.98/1.44	
2.98/1.44	The set Q consists of the following terms:
2.98/1.44	
2.98/1.44	   from(x0)
2.98/1.44	   first(0, x0)
2.98/1.44	   first(s(x0), cons(x1, x2))
2.98/1.44	   sel(0, cons(x0, x1))
2.98/1.44	   sel(s(x0), cons(x1, x2))
2.98/1.44	
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(5) QCSDependencyGraphProof (EQUIVALENT)
2.98/1.44	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 2 SCCs with 3 less nodes.
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(6)
2.98/1.44	Complex Obligation (AND)
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(7)
2.98/1.44	Obligation:
2.98/1.44	Q-restricted context-sensitive dependency pair problem:
2.98/1.44	The symbols in {from_1, s_1, first_2, sel_2} are replacing on all positions.
2.98/1.44	For all symbols f in {cons_2} we have mu(f) = {1}.
2.98/1.44	The symbols in {U_1} are not replacing on any position.
2.98/1.44	
2.98/1.44	The TRS P consists of the following rules:
2.98/1.44	
2.98/1.44	   U(s(x_0)) -> U(x_0)
2.98/1.44	   U(from(x_0)) -> U(x_0)
2.98/1.44	   U(first(x_0, x_1)) -> U(x_0)
2.98/1.44	   U(first(x_0, x_1)) -> U(x_1)
2.98/1.44	
2.98/1.44	The TRS R consists of the following rules:
2.98/1.44	
2.98/1.44	   from(X) -> cons(X, from(s(X)))
2.98/1.44	   first(0, Z) -> nil
2.98/1.44	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
2.98/1.44	   sel(0, cons(X, Z)) -> X
2.98/1.44	   sel(s(X), cons(Y, Z)) -> sel(X, Z)
2.98/1.44	
2.98/1.44	The set Q consists of the following terms:
2.98/1.44	
2.98/1.44	   from(x0)
2.98/1.44	   first(0, x0)
2.98/1.44	   first(s(x0), cons(x1, x2))
2.98/1.44	   sel(0, cons(x0, x1))
2.98/1.44	   sel(s(x0), cons(x1, x2))
2.98/1.44	
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(8) QCSDPSubtermProof (EQUIVALENT)
2.98/1.44	We use the subterm processor [DA_EMMES].
2.98/1.44	
2.98/1.44	
2.98/1.44	The following pairs can be oriented strictly and are deleted.
2.98/1.44	
2.98/1.44	   U(s(x_0)) -> U(x_0)
2.98/1.44	   U(from(x_0)) -> U(x_0)
2.98/1.44	   U(first(x_0, x_1)) -> U(x_0)
2.98/1.44	   U(first(x_0, x_1)) -> U(x_1)
2.98/1.44	The remaining pairs can at least be oriented weakly.
2.98/1.44	none
2.98/1.44	Used ordering:  Combined order from the following AFS and order.
2.98/1.44	U(x1)  =  x1
2.98/1.44	
2.98/1.44	
2.98/1.44	Subterm Order
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(9)
2.98/1.44	Obligation:
2.98/1.44	Q-restricted context-sensitive dependency pair problem:
2.98/1.44	The symbols in {from_1, s_1, first_2, sel_2} are replacing on all positions.
2.98/1.44	For all symbols f in {cons_2} we have mu(f) = {1}.
2.98/1.44	
2.98/1.44	The TRS P consists of the following rules:
2.98/1.44	none
2.98/1.44	
2.98/1.44	The TRS R consists of the following rules:
2.98/1.44	
2.98/1.44	   from(X) -> cons(X, from(s(X)))
2.98/1.44	   first(0, Z) -> nil
2.98/1.44	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
2.98/1.44	   sel(0, cons(X, Z)) -> X
2.98/1.44	   sel(s(X), cons(Y, Z)) -> sel(X, Z)
2.98/1.44	
2.98/1.44	The set Q consists of the following terms:
2.98/1.44	
2.98/1.44	   from(x0)
2.98/1.44	   first(0, x0)
2.98/1.44	   first(s(x0), cons(x1, x2))
2.98/1.44	   sel(0, cons(x0, x1))
2.98/1.44	   sel(s(x0), cons(x1, x2))
2.98/1.44	
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(10) PIsEmptyProof (EQUIVALENT)
2.98/1.44	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(11)
2.98/1.44	YES
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(12)
2.98/1.44	Obligation:
2.98/1.44	Q-restricted context-sensitive dependency pair problem:
2.98/1.44	The symbols in {from_1, s_1, first_2, sel_2, SEL_2} are replacing on all positions.
2.98/1.44	For all symbols f in {cons_2} we have mu(f) = {1}.
2.98/1.44	
2.98/1.44	The TRS P consists of the following rules:
2.98/1.44	
2.98/1.44	   SEL(s(X), cons(Y, Z)) -> SEL(X, Z)
2.98/1.44	
2.98/1.44	The TRS R consists of the following rules:
2.98/1.44	
2.98/1.44	   from(X) -> cons(X, from(s(X)))
2.98/1.44	   first(0, Z) -> nil
2.98/1.44	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
2.98/1.44	   sel(0, cons(X, Z)) -> X
2.98/1.44	   sel(s(X), cons(Y, Z)) -> sel(X, Z)
2.98/1.44	
2.98/1.44	The set Q consists of the following terms:
2.98/1.44	
2.98/1.44	   from(x0)
2.98/1.44	   first(0, x0)
2.98/1.44	   first(s(x0), cons(x1, x2))
2.98/1.44	   sel(0, cons(x0, x1))
2.98/1.44	   sel(s(x0), cons(x1, x2))
2.98/1.44	
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(13) QCSDPSubtermProof (EQUIVALENT)
2.98/1.44	We use the subterm processor [DA_EMMES].
2.98/1.44	
2.98/1.44	
2.98/1.44	The following pairs can be oriented strictly and are deleted.
2.98/1.44	
2.98/1.44	   SEL(s(X), cons(Y, Z)) -> SEL(X, Z)
2.98/1.44	The remaining pairs can at least be oriented weakly.
2.98/1.44	none
2.98/1.44	Used ordering:  Combined order from the following AFS and order.
2.98/1.44	SEL(x1, x2)  =  x1
2.98/1.44	
2.98/1.44	
2.98/1.44	Subterm Order
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(14)
2.98/1.44	Obligation:
2.98/1.44	Q-restricted context-sensitive dependency pair problem:
2.98/1.44	The symbols in {from_1, s_1, first_2, sel_2} are replacing on all positions.
2.98/1.44	For all symbols f in {cons_2} we have mu(f) = {1}.
2.98/1.44	
2.98/1.44	The TRS P consists of the following rules:
2.98/1.44	none
2.98/1.44	
2.98/1.44	The TRS R consists of the following rules:
2.98/1.44	
2.98/1.44	   from(X) -> cons(X, from(s(X)))
2.98/1.44	   first(0, Z) -> nil
2.98/1.44	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
2.98/1.44	   sel(0, cons(X, Z)) -> X
2.98/1.44	   sel(s(X), cons(Y, Z)) -> sel(X, Z)
2.98/1.44	
2.98/1.44	The set Q consists of the following terms:
2.98/1.44	
2.98/1.44	   from(x0)
2.98/1.44	   first(0, x0)
2.98/1.44	   first(s(x0), cons(x1, x2))
2.98/1.44	   sel(0, cons(x0, x1))
2.98/1.44	   sel(s(x0), cons(x1, x2))
2.98/1.44	
2.98/1.44	
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(15) PIsEmptyProof (EQUIVALENT)
2.98/1.44	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
2.98/1.44	----------------------------------------
2.98/1.44	
2.98/1.44	(16)
2.98/1.44	YES
2.98/1.46	EOF