3.04/1.54	YES
3.04/1.56	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
3.04/1.56	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.04/1.56	
3.04/1.56	
3.04/1.56	Termination of the given CSR could be proven:
3.04/1.56	
3.04/1.56	(0) CSR
3.04/1.56	(1) CSRInnermostProof [EQUIVALENT, 1 ms]
3.04/1.56	(2) CSR
3.04/1.56	(3) CSDependencyPairsProof [EQUIVALENT, 0 ms]
3.04/1.56	(4) QCSDP
3.04/1.56	(5) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
3.04/1.56	(6) AND
3.04/1.56	    (7) QCSDP
3.04/1.56	        (8) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.04/1.56	        (9) QCSDP
3.04/1.56	        (10) PIsEmptyProof [EQUIVALENT, 0 ms]
3.04/1.56	        (11) YES
3.04/1.56	    (12) QCSDP
3.04/1.56	        (13) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.04/1.56	        (14) QCSDP
3.04/1.56	        (15) PIsEmptyProof [EQUIVALENT, 0 ms]
3.04/1.56	        (16) YES
3.04/1.56	
3.04/1.56	
3.04/1.56	----------------------------------------
3.04/1.56	
3.04/1.56	(0)
3.04/1.56	Obligation:
3.04/1.56	Context-sensitive rewrite system:
3.04/1.56	The TRS R consists of the following rules:
3.04/1.56	
3.04/1.56	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.04/1.56	   fst(pair(XS, YS)) -> XS
3.04/1.56	   snd(pair(XS, YS)) -> YS
3.04/1.56	   splitAt(0, XS) -> pair(nil, XS)
3.04/1.56	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, XS), N, X, XS)
3.04/1.56	   u(pair(YS, ZS), N, X, XS) -> pair(cons(X, YS), ZS)
3.30/1.61	   head(cons(N, XS)) -> N
3.30/1.61	   tail(cons(N, XS)) -> XS
3.30/1.61	   sel(N, XS) -> head(afterNth(N, XS))
3.30/1.61	   take(N, XS) -> fst(splitAt(N, XS))
3.30/1.61	   afterNth(N, XS) -> snd(splitAt(N, XS))
3.30/1.61	
3.30/1.61	The replacement map contains the following entries:
3.30/1.61	
3.30/1.61	natsFrom: {1}
3.30/1.61	cons: {1}
3.30/1.61	s: {1}
3.30/1.61	fst: {1}
3.30/1.61	pair: {1, 2}
3.30/1.61	snd: {1}
3.30/1.61	splitAt: {1, 2}
3.30/1.61	0: empty set
3.30/1.61	nil: empty set
3.30/1.61	u: {1}
3.30/1.61	head: {1}
3.30/1.61	tail: {1}
3.30/1.61	sel: {1, 2}
3.30/1.61	afterNth: {1, 2}
3.30/1.61	take: {1, 2}
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(1) CSRInnermostProof (EQUIVALENT)
3.30/1.61	The CSR is orthogonal. By [CS_Inn] we can switch to innermost.
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(2)
3.30/1.61	Obligation:
3.30/1.61	Context-sensitive rewrite system:
3.30/1.61	The TRS R consists of the following rules:
3.30/1.61	
3.30/1.61	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.30/1.61	   fst(pair(XS, YS)) -> XS
3.30/1.61	   snd(pair(XS, YS)) -> YS
3.30/1.61	   splitAt(0, XS) -> pair(nil, XS)
3.30/1.61	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, XS), N, X, XS)
3.30/1.61	   u(pair(YS, ZS), N, X, XS) -> pair(cons(X, YS), ZS)
3.30/1.61	   head(cons(N, XS)) -> N
3.30/1.61	   tail(cons(N, XS)) -> XS
3.30/1.61	   sel(N, XS) -> head(afterNth(N, XS))
3.30/1.61	   take(N, XS) -> fst(splitAt(N, XS))
3.30/1.61	   afterNth(N, XS) -> snd(splitAt(N, XS))
3.30/1.61	
3.30/1.61	The replacement map contains the following entries:
3.30/1.61	
3.30/1.61	natsFrom: {1}
3.30/1.61	cons: {1}
3.30/1.61	s: {1}
3.30/1.61	fst: {1}
3.30/1.61	pair: {1, 2}
3.30/1.61	snd: {1}
3.30/1.61	splitAt: {1, 2}
3.30/1.61	0: empty set
3.30/1.61	nil: empty set
3.30/1.61	u: {1}
3.30/1.61	head: {1}
3.30/1.61	tail: {1}
3.30/1.61	sel: {1, 2}
3.30/1.61	afterNth: {1, 2}
3.30/1.61	take: {1, 2}
3.30/1.61	
3.30/1.61	
3.30/1.61	Innermost Strategy.
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(3) CSDependencyPairsProof (EQUIVALENT)
3.30/1.61	Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(4)
3.30/1.61	Obligation:
3.30/1.61	Q-restricted context-sensitive dependency pair problem:
3.30/1.61	The symbols in {natsFrom_1, s_1, fst_1, pair_2, snd_1, splitAt_2, head_1, tail_1, sel_2, afterNth_2, take_2, SPLITAT_2, HEAD_1, SEL_2, AFTERNTH_2, FST_1, TAKE_2, SND_1, TAIL_1, NATSFROM_1} are replacing on all positions.
3.30/1.61	For all symbols f in {cons_2, u_4, U_4} we have mu(f) = {1}.
3.30/1.61	The symbols in {U'_1} are not replacing on any position.
3.30/1.61	
3.30/1.61	The ordinary context-sensitive dependency pairs DP_o are:
3.30/1.61	   SPLITAT(s(N), cons(X, XS)) -> U(splitAt(N, XS), N, X, XS)
3.30/1.61	   SPLITAT(s(N), cons(X, XS)) -> SPLITAT(N, XS)
3.30/1.61	   SEL(N, XS) -> HEAD(afterNth(N, XS))
3.30/1.61	   SEL(N, XS) -> AFTERNTH(N, XS)
3.30/1.61	   TAKE(N, XS) -> FST(splitAt(N, XS))
3.30/1.61	   TAKE(N, XS) -> SPLITAT(N, XS)
3.30/1.61	   AFTERNTH(N, XS) -> SND(splitAt(N, XS))
3.30/1.61	   AFTERNTH(N, XS) -> SPLITAT(N, XS)
3.30/1.61	
3.30/1.61	The collapsing dependency pairs are DP_c:
3.30/1.61	   SPLITAT(s(N), cons(X, XS)) -> XS
3.30/1.61	   U(pair(YS, ZS), N, X, XS) -> X
3.30/1.61	   TAIL(cons(N, XS)) -> XS
3.30/1.61	
3.30/1.61	
3.30/1.61	The hidden terms of R are:
3.30/1.61	
3.30/1.61	   natsFrom(s(x0))
3.30/1.61	
3.30/1.61	Every hiding context is built from:
3.30/1.61	   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@69ba325
3.30/1.61	   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@3d947032
3.30/1.61	
3.30/1.61	Hence, the new unhiding pairs DP_u are :
3.30/1.61	   SPLITAT(s(N), cons(X, XS)) -> U'(XS)
3.30/1.61	   U(pair(YS, ZS), N, X, XS) -> U'(X)
3.30/1.61	   TAIL(cons(N, XS)) -> U'(XS)
3.30/1.61	   U'(s(x_0)) -> U'(x_0)
3.30/1.61	   U'(natsFrom(x_0)) -> U'(x_0)
3.30/1.61	   U'(natsFrom(s(x0))) -> NATSFROM(s(x0))
3.30/1.61	
3.30/1.61	The TRS R consists of the following rules:
3.30/1.61	
3.30/1.61	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.30/1.61	   fst(pair(XS, YS)) -> XS
3.30/1.61	   snd(pair(XS, YS)) -> YS
3.30/1.61	   splitAt(0, XS) -> pair(nil, XS)
3.30/1.61	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, XS), N, X, XS)
3.30/1.61	   u(pair(YS, ZS), N, X, XS) -> pair(cons(X, YS), ZS)
3.30/1.61	   head(cons(N, XS)) -> N
3.30/1.61	   tail(cons(N, XS)) -> XS
3.30/1.61	   sel(N, XS) -> head(afterNth(N, XS))
3.30/1.61	   take(N, XS) -> fst(splitAt(N, XS))
3.30/1.61	   afterNth(N, XS) -> snd(splitAt(N, XS))
3.30/1.61	
3.30/1.61	The set Q consists of the following terms:
3.30/1.61	
3.30/1.61	   natsFrom(x0)
3.30/1.61	   fst(pair(x0, x1))
3.30/1.61	   snd(pair(x0, x1))
3.30/1.61	   splitAt(0, x0)
3.30/1.61	   splitAt(s(x0), cons(x1, x2))
3.30/1.61	   u(pair(x0, x1), x2, x3, x4)
3.30/1.61	   head(cons(x0, x1))
3.30/1.61	   tail(cons(x0, x1))
3.30/1.61	   sel(x0, x1)
3.30/1.61	   take(x0, x1)
3.30/1.61	   afterNth(x0, x1)
3.30/1.61	
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(5) QCSDependencyGraphProof (EQUIVALENT)
3.30/1.61	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 2 SCCs with 9 less nodes.
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(6)
3.30/1.61	Complex Obligation (AND)
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(7)
3.30/1.61	Obligation:
3.30/1.61	Q-restricted context-sensitive dependency pair problem:
3.30/1.61	The symbols in {natsFrom_1, s_1, fst_1, pair_2, snd_1, splitAt_2, head_1, tail_1, sel_2, afterNth_2, take_2} are replacing on all positions.
3.30/1.61	For all symbols f in {cons_2, u_4} we have mu(f) = {1}.
3.30/1.61	The symbols in {U'_1} are not replacing on any position.
3.30/1.61	
3.30/1.61	The TRS P consists of the following rules:
3.30/1.61	
3.30/1.61	   U'(s(x_0)) -> U'(x_0)
3.30/1.61	   U'(natsFrom(x_0)) -> U'(x_0)
3.30/1.61	
3.30/1.61	The TRS R consists of the following rules:
3.30/1.61	
3.30/1.61	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.30/1.61	   fst(pair(XS, YS)) -> XS
3.30/1.61	   snd(pair(XS, YS)) -> YS
3.30/1.61	   splitAt(0, XS) -> pair(nil, XS)
3.30/1.61	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, XS), N, X, XS)
3.30/1.61	   u(pair(YS, ZS), N, X, XS) -> pair(cons(X, YS), ZS)
3.30/1.61	   head(cons(N, XS)) -> N
3.30/1.61	   tail(cons(N, XS)) -> XS
3.30/1.61	   sel(N, XS) -> head(afterNth(N, XS))
3.30/1.61	   take(N, XS) -> fst(splitAt(N, XS))
3.30/1.61	   afterNth(N, XS) -> snd(splitAt(N, XS))
3.30/1.61	
3.30/1.61	The set Q consists of the following terms:
3.30/1.61	
3.30/1.61	   natsFrom(x0)
3.30/1.61	   fst(pair(x0, x1))
3.30/1.61	   snd(pair(x0, x1))
3.30/1.61	   splitAt(0, x0)
3.30/1.61	   splitAt(s(x0), cons(x1, x2))
3.30/1.61	   u(pair(x0, x1), x2, x3, x4)
3.30/1.61	   head(cons(x0, x1))
3.30/1.61	   tail(cons(x0, x1))
3.30/1.61	   sel(x0, x1)
3.30/1.61	   take(x0, x1)
3.30/1.61	   afterNth(x0, x1)
3.30/1.61	
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(8) QCSDPSubtermProof (EQUIVALENT)
3.30/1.61	We use the subterm processor [DA_EMMES].
3.30/1.61	
3.30/1.61	
3.30/1.61	The following pairs can be oriented strictly and are deleted.
3.30/1.61	
3.30/1.61	   U'(s(x_0)) -> U'(x_0)
3.30/1.61	   U'(natsFrom(x_0)) -> U'(x_0)
3.30/1.61	The remaining pairs can at least be oriented weakly.
3.30/1.61	none
3.30/1.61	Used ordering:  Combined order from the following AFS and order.
3.30/1.61	U'(x1)  =  x1
3.30/1.61	
3.30/1.61	
3.30/1.61	Subterm Order
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(9)
3.30/1.61	Obligation:
3.30/1.61	Q-restricted context-sensitive dependency pair problem:
3.30/1.61	The symbols in {natsFrom_1, s_1, fst_1, pair_2, snd_1, splitAt_2, head_1, tail_1, sel_2, afterNth_2, take_2} are replacing on all positions.
3.30/1.61	For all symbols f in {cons_2, u_4} we have mu(f) = {1}.
3.30/1.61	
3.30/1.61	The TRS P consists of the following rules:
3.30/1.61	none
3.30/1.61	
3.30/1.61	The TRS R consists of the following rules:
3.30/1.61	
3.30/1.61	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.30/1.61	   fst(pair(XS, YS)) -> XS
3.30/1.61	   snd(pair(XS, YS)) -> YS
3.30/1.61	   splitAt(0, XS) -> pair(nil, XS)
3.30/1.61	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, XS), N, X, XS)
3.30/1.61	   u(pair(YS, ZS), N, X, XS) -> pair(cons(X, YS), ZS)
3.30/1.61	   head(cons(N, XS)) -> N
3.30/1.61	   tail(cons(N, XS)) -> XS
3.30/1.61	   sel(N, XS) -> head(afterNth(N, XS))
3.30/1.61	   take(N, XS) -> fst(splitAt(N, XS))
3.30/1.61	   afterNth(N, XS) -> snd(splitAt(N, XS))
3.30/1.61	
3.30/1.61	The set Q consists of the following terms:
3.30/1.61	
3.30/1.61	   natsFrom(x0)
3.30/1.61	   fst(pair(x0, x1))
3.30/1.61	   snd(pair(x0, x1))
3.30/1.61	   splitAt(0, x0)
3.30/1.61	   splitAt(s(x0), cons(x1, x2))
3.30/1.61	   u(pair(x0, x1), x2, x3, x4)
3.30/1.61	   head(cons(x0, x1))
3.30/1.61	   tail(cons(x0, x1))
3.30/1.61	   sel(x0, x1)
3.30/1.61	   take(x0, x1)
3.30/1.61	   afterNth(x0, x1)
3.30/1.61	
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(10) PIsEmptyProof (EQUIVALENT)
3.30/1.61	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(11)
3.30/1.61	YES
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(12)
3.30/1.61	Obligation:
3.30/1.61	Q-restricted context-sensitive dependency pair problem:
3.30/1.61	The symbols in {natsFrom_1, s_1, fst_1, pair_2, snd_1, splitAt_2, head_1, tail_1, sel_2, afterNth_2, take_2, SPLITAT_2} are replacing on all positions.
3.30/1.61	For all symbols f in {cons_2, u_4} we have mu(f) = {1}.
3.30/1.61	
3.30/1.61	The TRS P consists of the following rules:
3.30/1.61	
3.30/1.61	   SPLITAT(s(N), cons(X, XS)) -> SPLITAT(N, XS)
3.30/1.61	
3.30/1.61	The TRS R consists of the following rules:
3.30/1.61	
3.30/1.61	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.30/1.61	   fst(pair(XS, YS)) -> XS
3.30/1.61	   snd(pair(XS, YS)) -> YS
3.30/1.61	   splitAt(0, XS) -> pair(nil, XS)
3.30/1.61	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, XS), N, X, XS)
3.30/1.61	   u(pair(YS, ZS), N, X, XS) -> pair(cons(X, YS), ZS)
3.30/1.61	   head(cons(N, XS)) -> N
3.30/1.61	   tail(cons(N, XS)) -> XS
3.30/1.61	   sel(N, XS) -> head(afterNth(N, XS))
3.30/1.61	   take(N, XS) -> fst(splitAt(N, XS))
3.30/1.61	   afterNth(N, XS) -> snd(splitAt(N, XS))
3.30/1.61	
3.30/1.61	The set Q consists of the following terms:
3.30/1.61	
3.30/1.61	   natsFrom(x0)
3.30/1.61	   fst(pair(x0, x1))
3.30/1.61	   snd(pair(x0, x1))
3.30/1.61	   splitAt(0, x0)
3.30/1.61	   splitAt(s(x0), cons(x1, x2))
3.30/1.61	   u(pair(x0, x1), x2, x3, x4)
3.30/1.61	   head(cons(x0, x1))
3.30/1.61	   tail(cons(x0, x1))
3.30/1.61	   sel(x0, x1)
3.30/1.61	   take(x0, x1)
3.30/1.61	   afterNth(x0, x1)
3.30/1.61	
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(13) QCSDPSubtermProof (EQUIVALENT)
3.30/1.61	We use the subterm processor [DA_EMMES].
3.30/1.61	
3.30/1.61	
3.30/1.61	The following pairs can be oriented strictly and are deleted.
3.30/1.61	
3.30/1.61	   SPLITAT(s(N), cons(X, XS)) -> SPLITAT(N, XS)
3.30/1.61	The remaining pairs can at least be oriented weakly.
3.30/1.61	none
3.30/1.61	Used ordering:  Combined order from the following AFS and order.
3.30/1.61	SPLITAT(x1, x2)  =  x1
3.30/1.61	
3.30/1.61	
3.30/1.61	Subterm Order
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(14)
3.30/1.61	Obligation:
3.30/1.61	Q-restricted context-sensitive dependency pair problem:
3.30/1.61	The symbols in {natsFrom_1, s_1, fst_1, pair_2, snd_1, splitAt_2, head_1, tail_1, sel_2, afterNth_2, take_2} are replacing on all positions.
3.30/1.61	For all symbols f in {cons_2, u_4} we have mu(f) = {1}.
3.30/1.61	
3.30/1.61	The TRS P consists of the following rules:
3.30/1.61	none
3.30/1.61	
3.30/1.61	The TRS R consists of the following rules:
3.30/1.61	
3.30/1.61	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.30/1.61	   fst(pair(XS, YS)) -> XS
3.30/1.61	   snd(pair(XS, YS)) -> YS
3.30/1.61	   splitAt(0, XS) -> pair(nil, XS)
3.30/1.61	   splitAt(s(N), cons(X, XS)) -> u(splitAt(N, XS), N, X, XS)
3.30/1.61	   u(pair(YS, ZS), N, X, XS) -> pair(cons(X, YS), ZS)
3.30/1.61	   head(cons(N, XS)) -> N
3.30/1.61	   tail(cons(N, XS)) -> XS
3.30/1.61	   sel(N, XS) -> head(afterNth(N, XS))
3.30/1.61	   take(N, XS) -> fst(splitAt(N, XS))
3.30/1.61	   afterNth(N, XS) -> snd(splitAt(N, XS))
3.30/1.61	
3.30/1.61	The set Q consists of the following terms:
3.30/1.61	
3.30/1.61	   natsFrom(x0)
3.30/1.61	   fst(pair(x0, x1))
3.30/1.61	   snd(pair(x0, x1))
3.30/1.61	   splitAt(0, x0)
3.30/1.61	   splitAt(s(x0), cons(x1, x2))
3.30/1.61	   u(pair(x0, x1), x2, x3, x4)
3.30/1.61	   head(cons(x0, x1))
3.30/1.61	   tail(cons(x0, x1))
3.30/1.61	   sel(x0, x1)
3.30/1.61	   take(x0, x1)
3.30/1.61	   afterNth(x0, x1)
3.30/1.61	
3.30/1.61	
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(15) PIsEmptyProof (EQUIVALENT)
3.30/1.61	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
3.30/1.61	----------------------------------------
3.30/1.61	
3.30/1.61	(16)
3.30/1.61	YES
3.30/1.62	EOF