3.96/1.77	YES
3.96/1.78	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.96/1.78	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.96/1.78	
3.96/1.78	
3.96/1.78	Termination of the given CSR could be proven:
3.96/1.78	
3.96/1.78	(0) CSR
3.96/1.78	(1) CSRInnermostProof [EQUIVALENT, 14 ms]
3.96/1.78	(2) CSR
3.96/1.78	(3) CSDependencyPairsProof [EQUIVALENT, 0 ms]
3.96/1.78	(4) QCSDP
3.96/1.78	(5) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
3.96/1.78	(6) AND
3.96/1.78	    (7) QCSDP
3.96/1.78	        (8) QCSDPSubtermProof [EQUIVALENT, 20 ms]
3.96/1.78	        (9) QCSDP
3.96/1.78	        (10) PIsEmptyProof [EQUIVALENT, 0 ms]
3.96/1.78	        (11) YES
3.96/1.78	    (12) QCSDP
3.96/1.78	        (13) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.96/1.78	        (14) QCSDP
3.96/1.78	        (15) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
3.96/1.78	        (16) TRUE
3.96/1.78	
3.96/1.78	
3.96/1.78	----------------------------------------
3.96/1.78	
3.96/1.78	(0)
3.96/1.78	Obligation:
3.96/1.78	Context-sensitive rewrite system:
3.96/1.78	The TRS R consists of the following rules:
3.96/1.78	
3.96/1.78	   U11(tt, N, XS) -> U12(tt, N, XS)
3.96/1.78	   U12(tt, N, XS) -> snd(splitAt(N, XS))
3.96/1.78	   U21(tt, X) -> U22(tt, X)
3.96/1.78	   U22(tt, X) -> X
3.96/1.78	   U31(tt, N) -> U32(tt, N)
3.96/1.78	   U32(tt, N) -> N
3.96/1.78	   U41(tt, N, XS) -> U42(tt, N, XS)
3.96/1.78	   U42(tt, N, XS) -> head(afterNth(N, XS))
3.96/1.78	   U51(tt, Y) -> U52(tt, Y)
3.96/1.78	   U52(tt, Y) -> Y
3.96/1.78	   U61(tt, N, X, XS) -> U62(tt, N, X, XS)
3.96/1.78	   U62(tt, N, X, XS) -> U63(tt, N, X, XS)
3.96/1.78	   U63(tt, N, X, XS) -> U64(splitAt(N, XS), X)
3.96/1.78	   U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
3.96/1.78	   U71(tt, XS) -> U72(tt, XS)
3.96/1.78	   U72(tt, XS) -> XS
3.96/1.78	   U81(tt, N, XS) -> U82(tt, N, XS)
3.96/1.78	   U82(tt, N, XS) -> fst(splitAt(N, XS))
3.96/1.78	   afterNth(N, XS) -> U11(tt, N, XS)
3.96/1.78	   fst(pair(X, Y)) -> U21(tt, X)
3.96/1.78	   head(cons(N, XS)) -> U31(tt, N)
3.96/1.78	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.96/1.78	   sel(N, XS) -> U41(tt, N, XS)
3.96/1.78	   snd(pair(X, Y)) -> U51(tt, Y)
3.96/1.78	   splitAt(0, XS) -> pair(nil, XS)
3.96/1.78	   splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS)
3.96/1.78	   tail(cons(N, XS)) -> U71(tt, XS)
3.96/1.78	   take(N, XS) -> U81(tt, N, XS)
3.96/1.78	
3.96/1.78	The replacement map contains the following entries:
3.96/1.78	
3.96/1.78	U11: {1}
3.96/1.78	tt: empty set
3.96/1.78	U12: {1}
3.96/1.78	snd: {1}
3.96/1.78	splitAt: {1, 2}
3.96/1.78	U21: {1}
3.96/1.78	U22: {1}
3.96/1.78	U31: {1}
3.96/1.78	U32: {1}
3.96/1.78	U41: {1}
3.96/1.78	U42: {1}
3.96/1.78	head: {1}
3.96/1.78	afterNth: {1, 2}
3.96/1.78	U51: {1}
3.96/1.78	U52: {1}
3.96/1.78	U61: {1}
3.96/1.78	U62: {1}
3.96/1.78	U63: {1}
3.96/1.78	U64: {1}
3.96/1.78	pair: {1, 2}
3.96/1.78	cons: {1}
3.96/1.79	U71: {1}
3.96/1.79	U72: {1}
3.96/1.79	U81: {1}
3.96/1.79	U82: {1}
3.96/1.79	fst: {1}
3.96/1.79	natsFrom: {1}
3.96/1.79	s: {1}
3.96/1.79	sel: {1, 2}
3.96/1.79	0: empty set
3.96/1.79	nil: empty set
3.96/1.79	tail: {1}
3.96/1.79	take: {1, 2}
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(1) CSRInnermostProof (EQUIVALENT)
3.96/1.79	The CSR is orthogonal. By [CS_Inn] we can switch to innermost.
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(2)
3.96/1.79	Obligation:
3.96/1.79	Context-sensitive rewrite system:
3.96/1.79	The TRS R consists of the following rules:
3.96/1.79	
3.96/1.79	   U11(tt, N, XS) -> U12(tt, N, XS)
3.96/1.79	   U12(tt, N, XS) -> snd(splitAt(N, XS))
3.96/1.79	   U21(tt, X) -> U22(tt, X)
3.96/1.79	   U22(tt, X) -> X
3.96/1.79	   U31(tt, N) -> U32(tt, N)
3.96/1.79	   U32(tt, N) -> N
3.96/1.79	   U41(tt, N, XS) -> U42(tt, N, XS)
3.96/1.79	   U42(tt, N, XS) -> head(afterNth(N, XS))
3.96/1.79	   U51(tt, Y) -> U52(tt, Y)
3.96/1.79	   U52(tt, Y) -> Y
3.96/1.79	   U61(tt, N, X, XS) -> U62(tt, N, X, XS)
3.96/1.79	   U62(tt, N, X, XS) -> U63(tt, N, X, XS)
3.96/1.79	   U63(tt, N, X, XS) -> U64(splitAt(N, XS), X)
3.96/1.79	   U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
3.96/1.79	   U71(tt, XS) -> U72(tt, XS)
3.96/1.79	   U72(tt, XS) -> XS
3.96/1.79	   U81(tt, N, XS) -> U82(tt, N, XS)
3.96/1.79	   U82(tt, N, XS) -> fst(splitAt(N, XS))
3.96/1.79	   afterNth(N, XS) -> U11(tt, N, XS)
3.96/1.79	   fst(pair(X, Y)) -> U21(tt, X)
3.96/1.79	   head(cons(N, XS)) -> U31(tt, N)
3.96/1.79	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.96/1.79	   sel(N, XS) -> U41(tt, N, XS)
3.96/1.79	   snd(pair(X, Y)) -> U51(tt, Y)
3.96/1.79	   splitAt(0, XS) -> pair(nil, XS)
3.96/1.79	   splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS)
3.96/1.79	   tail(cons(N, XS)) -> U71(tt, XS)
3.96/1.79	   take(N, XS) -> U81(tt, N, XS)
3.96/1.79	
3.96/1.79	The replacement map contains the following entries:
3.96/1.79	
3.96/1.79	U11: {1}
3.96/1.79	tt: empty set
3.96/1.79	U12: {1}
3.96/1.79	snd: {1}
3.96/1.79	splitAt: {1, 2}
3.96/1.79	U21: {1}
3.96/1.79	U22: {1}
3.96/1.79	U31: {1}
3.96/1.79	U32: {1}
3.96/1.79	U41: {1}
3.96/1.79	U42: {1}
3.96/1.79	head: {1}
3.96/1.79	afterNth: {1, 2}
3.96/1.79	U51: {1}
3.96/1.79	U52: {1}
3.96/1.79	U61: {1}
3.96/1.79	U62: {1}
3.96/1.79	U63: {1}
3.96/1.79	U64: {1}
3.96/1.79	pair: {1, 2}
3.96/1.79	cons: {1}
3.96/1.79	U71: {1}
3.96/1.79	U72: {1}
3.96/1.79	U81: {1}
3.96/1.79	U82: {1}
3.96/1.79	fst: {1}
3.96/1.79	natsFrom: {1}
3.96/1.79	s: {1}
3.96/1.79	sel: {1, 2}
3.96/1.79	0: empty set
3.96/1.79	nil: empty set
3.96/1.79	tail: {1}
3.96/1.79	take: {1, 2}
3.96/1.79	
3.96/1.79	
3.96/1.79	Innermost Strategy.
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(3) CSDependencyPairsProof (EQUIVALENT)
3.96/1.79	Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(4)
3.96/1.79	Obligation:
3.96/1.79	Q-restricted context-sensitive dependency pair problem:
3.96/1.79	The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, SND_1, SPLITAT_2, HEAD_1, AFTERNTH_2, FST_1, SEL_2, TAIL_1, TAKE_2, NATSFROM_1} are replacing on all positions.
3.96/1.79	For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3, U12'_3, U11'_3, U22'_2, U21'_2, U32'_2, U31'_2, U42'_3, U41'_3, U52'_2, U51'_2, U62'_4, U61'_4, U63'_4, U64'_2, U72'_2, U71'_2, U82'_3, U81'_3} we have mu(f) = {1}.
3.96/1.79	The symbols in {U_1} are not replacing on any position.
3.96/1.79	
3.96/1.79	The ordinary context-sensitive dependency pairs DP_o are:
3.96/1.79	   U11'(tt, N, XS) -> U12'(tt, N, XS)
3.96/1.79	   U12'(tt, N, XS) -> SND(splitAt(N, XS))
3.96/1.79	   U12'(tt, N, XS) -> SPLITAT(N, XS)
3.96/1.79	   U21'(tt, X) -> U22'(tt, X)
3.96/1.79	   U31'(tt, N) -> U32'(tt, N)
3.96/1.79	   U41'(tt, N, XS) -> U42'(tt, N, XS)
3.96/1.79	   U42'(tt, N, XS) -> HEAD(afterNth(N, XS))
3.96/1.79	   U42'(tt, N, XS) -> AFTERNTH(N, XS)
3.96/1.79	   U51'(tt, Y) -> U52'(tt, Y)
3.96/1.79	   U61'(tt, N, X, XS) -> U62'(tt, N, X, XS)
3.96/1.79	   U62'(tt, N, X, XS) -> U63'(tt, N, X, XS)
3.96/1.79	   U63'(tt, N, X, XS) -> U64'(splitAt(N, XS), X)
3.96/1.79	   U63'(tt, N, X, XS) -> SPLITAT(N, XS)
3.96/1.79	   U71'(tt, XS) -> U72'(tt, XS)
3.96/1.79	   U81'(tt, N, XS) -> U82'(tt, N, XS)
3.96/1.79	   U82'(tt, N, XS) -> FST(splitAt(N, XS))
3.96/1.79	   U82'(tt, N, XS) -> SPLITAT(N, XS)
3.96/1.79	   AFTERNTH(N, XS) -> U11'(tt, N, XS)
3.96/1.79	   FST(pair(X, Y)) -> U21'(tt, X)
3.96/1.79	   HEAD(cons(N, XS)) -> U31'(tt, N)
3.96/1.79	   SEL(N, XS) -> U41'(tt, N, XS)
3.96/1.79	   SND(pair(X, Y)) -> U51'(tt, Y)
3.96/1.79	   SPLITAT(s(N), cons(X, XS)) -> U61'(tt, N, X, XS)
3.96/1.79	   TAIL(cons(N, XS)) -> U71'(tt, XS)
3.96/1.79	   TAKE(N, XS) -> U81'(tt, N, XS)
3.96/1.79	
3.96/1.79	The collapsing dependency pairs are DP_c:
3.96/1.79	   U12'(tt, N, XS) -> N
3.96/1.79	   U12'(tt, N, XS) -> XS
3.96/1.79	   U22'(tt, X) -> X
3.96/1.79	   U32'(tt, N) -> N
3.96/1.79	   U42'(tt, N, XS) -> N
3.96/1.79	   U42'(tt, N, XS) -> XS
3.96/1.79	   U52'(tt, Y) -> Y
3.96/1.79	   U63'(tt, N, X, XS) -> N
3.96/1.79	   U63'(tt, N, X, XS) -> XS
3.96/1.79	   U64'(pair(YS, ZS), X) -> X
3.96/1.79	   U72'(tt, XS) -> XS
3.96/1.79	   U82'(tt, N, XS) -> N
3.96/1.79	   U82'(tt, N, XS) -> XS
3.96/1.79	
3.96/1.79	
3.96/1.79	The hidden terms of R are:
3.96/1.79	
3.96/1.79	   natsFrom(s(x0))
3.96/1.79	
3.96/1.79	Every hiding context is built from:
3.96/1.79	   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@29b0525f
3.96/1.79	   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@6d4b0bb9
3.96/1.79	
3.96/1.79	Hence, the new unhiding pairs DP_u are :
3.96/1.79	   U12'(tt, N, XS) -> U(N)
3.96/1.79	   U12'(tt, N, XS) -> U(XS)
3.96/1.79	   U22'(tt, X) -> U(X)
3.96/1.79	   U32'(tt, N) -> U(N)
3.96/1.79	   U42'(tt, N, XS) -> U(N)
3.96/1.79	   U42'(tt, N, XS) -> U(XS)
3.96/1.79	   U52'(tt, Y) -> U(Y)
3.96/1.79	   U63'(tt, N, X, XS) -> U(N)
3.96/1.79	   U63'(tt, N, X, XS) -> U(XS)
3.96/1.79	   U64'(pair(YS, ZS), X) -> U(X)
3.96/1.79	   U72'(tt, XS) -> U(XS)
3.96/1.79	   U82'(tt, N, XS) -> U(N)
3.96/1.79	   U82'(tt, N, XS) -> U(XS)
3.96/1.79	   U(s(x_0)) -> U(x_0)
3.96/1.79	   U(natsFrom(x_0)) -> U(x_0)
3.96/1.79	   U(natsFrom(s(x0))) -> NATSFROM(s(x0))
3.96/1.79	
3.96/1.79	The TRS R consists of the following rules:
3.96/1.79	
3.96/1.79	   U11(tt, N, XS) -> U12(tt, N, XS)
3.96/1.79	   U12(tt, N, XS) -> snd(splitAt(N, XS))
3.96/1.79	   U21(tt, X) -> U22(tt, X)
3.96/1.79	   U22(tt, X) -> X
3.96/1.79	   U31(tt, N) -> U32(tt, N)
3.96/1.79	   U32(tt, N) -> N
3.96/1.79	   U41(tt, N, XS) -> U42(tt, N, XS)
3.96/1.79	   U42(tt, N, XS) -> head(afterNth(N, XS))
3.96/1.79	   U51(tt, Y) -> U52(tt, Y)
3.96/1.79	   U52(tt, Y) -> Y
3.96/1.79	   U61(tt, N, X, XS) -> U62(tt, N, X, XS)
3.96/1.79	   U62(tt, N, X, XS) -> U63(tt, N, X, XS)
3.96/1.79	   U63(tt, N, X, XS) -> U64(splitAt(N, XS), X)
3.96/1.79	   U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
3.96/1.79	   U71(tt, XS) -> U72(tt, XS)
3.96/1.79	   U72(tt, XS) -> XS
3.96/1.79	   U81(tt, N, XS) -> U82(tt, N, XS)
3.96/1.79	   U82(tt, N, XS) -> fst(splitAt(N, XS))
3.96/1.79	   afterNth(N, XS) -> U11(tt, N, XS)
3.96/1.79	   fst(pair(X, Y)) -> U21(tt, X)
3.96/1.79	   head(cons(N, XS)) -> U31(tt, N)
3.96/1.79	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.96/1.79	   sel(N, XS) -> U41(tt, N, XS)
3.96/1.79	   snd(pair(X, Y)) -> U51(tt, Y)
3.96/1.79	   splitAt(0, XS) -> pair(nil, XS)
3.96/1.79	   splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS)
3.96/1.79	   tail(cons(N, XS)) -> U71(tt, XS)
3.96/1.79	   take(N, XS) -> U81(tt, N, XS)
3.96/1.79	
3.96/1.79	The set Q consists of the following terms:
3.96/1.79	
3.96/1.79	   U11(tt, x0, x1)
3.96/1.79	   U12(tt, x0, x1)
3.96/1.79	   U21(tt, x0)
3.96/1.79	   U22(tt, x0)
3.96/1.79	   U31(tt, x0)
3.96/1.79	   U32(tt, x0)
3.96/1.79	   U41(tt, x0, x1)
3.96/1.79	   U42(tt, x0, x1)
3.96/1.79	   U51(tt, x0)
3.96/1.79	   U52(tt, x0)
3.96/1.79	   U61(tt, x0, x1, x2)
3.96/1.79	   U62(tt, x0, x1, x2)
3.96/1.79	   U63(tt, x0, x1, x2)
3.96/1.79	   U64(pair(x0, x1), x2)
3.96/1.79	   U71(tt, x0)
3.96/1.79	   U72(tt, x0)
3.96/1.79	   U81(tt, x0, x1)
3.96/1.79	   U82(tt, x0, x1)
3.96/1.79	   afterNth(x0, x1)
3.96/1.79	   fst(pair(x0, x1))
3.96/1.79	   head(cons(x0, x1))
3.96/1.79	   natsFrom(x0)
3.96/1.79	   sel(x0, x1)
3.96/1.79	   snd(pair(x0, x1))
3.96/1.79	   splitAt(0, x0)
3.96/1.79	   splitAt(s(x0), cons(x1, x2))
3.96/1.79	   tail(cons(x0, x1))
3.96/1.79	   take(x0, x1)
3.96/1.79	
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(5) QCSDependencyGraphProof (EQUIVALENT)
3.96/1.79	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 2 SCCs with 35 less nodes.
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(6)
3.96/1.79	Complex Obligation (AND)
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(7)
3.96/1.79	Obligation:
3.96/1.79	Q-restricted context-sensitive dependency pair problem:
3.96/1.79	The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2} are replacing on all positions.
3.96/1.79	For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3} we have mu(f) = {1}.
3.96/1.79	The symbols in {U_1} are not replacing on any position.
3.96/1.79	
3.96/1.79	The TRS P consists of the following rules:
3.96/1.79	
3.96/1.79	   U(s(x_0)) -> U(x_0)
3.96/1.79	   U(natsFrom(x_0)) -> U(x_0)
3.96/1.79	
3.96/1.79	The TRS R consists of the following rules:
3.96/1.79	
3.96/1.79	   U11(tt, N, XS) -> U12(tt, N, XS)
3.96/1.79	   U12(tt, N, XS) -> snd(splitAt(N, XS))
3.96/1.79	   U21(tt, X) -> U22(tt, X)
3.96/1.79	   U22(tt, X) -> X
3.96/1.79	   U31(tt, N) -> U32(tt, N)
3.96/1.79	   U32(tt, N) -> N
3.96/1.79	   U41(tt, N, XS) -> U42(tt, N, XS)
3.96/1.79	   U42(tt, N, XS) -> head(afterNth(N, XS))
3.96/1.79	   U51(tt, Y) -> U52(tt, Y)
3.96/1.79	   U52(tt, Y) -> Y
3.96/1.79	   U61(tt, N, X, XS) -> U62(tt, N, X, XS)
3.96/1.79	   U62(tt, N, X, XS) -> U63(tt, N, X, XS)
3.96/1.79	   U63(tt, N, X, XS) -> U64(splitAt(N, XS), X)
3.96/1.79	   U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
3.96/1.79	   U71(tt, XS) -> U72(tt, XS)
3.96/1.79	   U72(tt, XS) -> XS
3.96/1.79	   U81(tt, N, XS) -> U82(tt, N, XS)
3.96/1.79	   U82(tt, N, XS) -> fst(splitAt(N, XS))
3.96/1.79	   afterNth(N, XS) -> U11(tt, N, XS)
3.96/1.79	   fst(pair(X, Y)) -> U21(tt, X)
3.96/1.79	   head(cons(N, XS)) -> U31(tt, N)
3.96/1.79	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.96/1.79	   sel(N, XS) -> U41(tt, N, XS)
3.96/1.79	   snd(pair(X, Y)) -> U51(tt, Y)
3.96/1.79	   splitAt(0, XS) -> pair(nil, XS)
3.96/1.79	   splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS)
3.96/1.79	   tail(cons(N, XS)) -> U71(tt, XS)
3.96/1.79	   take(N, XS) -> U81(tt, N, XS)
3.96/1.79	
3.96/1.79	The set Q consists of the following terms:
3.96/1.79	
3.96/1.79	   U11(tt, x0, x1)
3.96/1.79	   U12(tt, x0, x1)
3.96/1.79	   U21(tt, x0)
3.96/1.79	   U22(tt, x0)
3.96/1.79	   U31(tt, x0)
3.96/1.79	   U32(tt, x0)
3.96/1.79	   U41(tt, x0, x1)
3.96/1.79	   U42(tt, x0, x1)
3.96/1.79	   U51(tt, x0)
3.96/1.79	   U52(tt, x0)
3.96/1.79	   U61(tt, x0, x1, x2)
3.96/1.79	   U62(tt, x0, x1, x2)
3.96/1.79	   U63(tt, x0, x1, x2)
3.96/1.79	   U64(pair(x0, x1), x2)
3.96/1.79	   U71(tt, x0)
3.96/1.79	   U72(tt, x0)
3.96/1.79	   U81(tt, x0, x1)
3.96/1.79	   U82(tt, x0, x1)
3.96/1.79	   afterNth(x0, x1)
3.96/1.79	   fst(pair(x0, x1))
3.96/1.79	   head(cons(x0, x1))
3.96/1.79	   natsFrom(x0)
3.96/1.79	   sel(x0, x1)
3.96/1.79	   snd(pair(x0, x1))
3.96/1.79	   splitAt(0, x0)
3.96/1.79	   splitAt(s(x0), cons(x1, x2))
3.96/1.79	   tail(cons(x0, x1))
3.96/1.79	   take(x0, x1)
3.96/1.79	
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(8) QCSDPSubtermProof (EQUIVALENT)
3.96/1.79	We use the subterm processor [DA_EMMES].
3.96/1.79	
3.96/1.79	
3.96/1.79	The following pairs can be oriented strictly and are deleted.
3.96/1.79	
3.96/1.79	   U(s(x_0)) -> U(x_0)
3.96/1.79	   U(natsFrom(x_0)) -> U(x_0)
3.96/1.79	The remaining pairs can at least be oriented weakly.
3.96/1.79	none
3.96/1.79	Used ordering:  Combined order from the following AFS and order.
3.96/1.79	U(x1)  =  x1
3.96/1.79	
3.96/1.79	
3.96/1.79	Subterm Order
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(9)
3.96/1.79	Obligation:
3.96/1.79	Q-restricted context-sensitive dependency pair problem:
3.96/1.79	The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2} are replacing on all positions.
3.96/1.79	For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3} we have mu(f) = {1}.
3.96/1.79	
3.96/1.79	The TRS P consists of the following rules:
3.96/1.79	none
3.96/1.79	
3.96/1.79	The TRS R consists of the following rules:
3.96/1.79	
3.96/1.79	   U11(tt, N, XS) -> U12(tt, N, XS)
3.96/1.79	   U12(tt, N, XS) -> snd(splitAt(N, XS))
3.96/1.79	   U21(tt, X) -> U22(tt, X)
3.96/1.79	   U22(tt, X) -> X
3.96/1.79	   U31(tt, N) -> U32(tt, N)
3.96/1.79	   U32(tt, N) -> N
3.96/1.79	   U41(tt, N, XS) -> U42(tt, N, XS)
3.96/1.79	   U42(tt, N, XS) -> head(afterNth(N, XS))
3.96/1.79	   U51(tt, Y) -> U52(tt, Y)
3.96/1.79	   U52(tt, Y) -> Y
3.96/1.79	   U61(tt, N, X, XS) -> U62(tt, N, X, XS)
3.96/1.79	   U62(tt, N, X, XS) -> U63(tt, N, X, XS)
3.96/1.79	   U63(tt, N, X, XS) -> U64(splitAt(N, XS), X)
3.96/1.79	   U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
3.96/1.79	   U71(tt, XS) -> U72(tt, XS)
3.96/1.79	   U72(tt, XS) -> XS
3.96/1.79	   U81(tt, N, XS) -> U82(tt, N, XS)
3.96/1.79	   U82(tt, N, XS) -> fst(splitAt(N, XS))
3.96/1.79	   afterNth(N, XS) -> U11(tt, N, XS)
3.96/1.79	   fst(pair(X, Y)) -> U21(tt, X)
3.96/1.79	   head(cons(N, XS)) -> U31(tt, N)
3.96/1.79	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.96/1.79	   sel(N, XS) -> U41(tt, N, XS)
3.96/1.79	   snd(pair(X, Y)) -> U51(tt, Y)
3.96/1.79	   splitAt(0, XS) -> pair(nil, XS)
3.96/1.79	   splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS)
3.96/1.79	   tail(cons(N, XS)) -> U71(tt, XS)
3.96/1.79	   take(N, XS) -> U81(tt, N, XS)
3.96/1.79	
3.96/1.79	The set Q consists of the following terms:
3.96/1.79	
3.96/1.79	   U11(tt, x0, x1)
3.96/1.79	   U12(tt, x0, x1)
3.96/1.79	   U21(tt, x0)
3.96/1.79	   U22(tt, x0)
3.96/1.79	   U31(tt, x0)
3.96/1.79	   U32(tt, x0)
3.96/1.79	   U41(tt, x0, x1)
3.96/1.79	   U42(tt, x0, x1)
3.96/1.79	   U51(tt, x0)
3.96/1.79	   U52(tt, x0)
3.96/1.79	   U61(tt, x0, x1, x2)
3.96/1.79	   U62(tt, x0, x1, x2)
3.96/1.79	   U63(tt, x0, x1, x2)
3.96/1.79	   U64(pair(x0, x1), x2)
3.96/1.79	   U71(tt, x0)
3.96/1.79	   U72(tt, x0)
3.96/1.79	   U81(tt, x0, x1)
3.96/1.79	   U82(tt, x0, x1)
3.96/1.79	   afterNth(x0, x1)
3.96/1.79	   fst(pair(x0, x1))
3.96/1.79	   head(cons(x0, x1))
3.96/1.79	   natsFrom(x0)
3.96/1.79	   sel(x0, x1)
3.96/1.79	   snd(pair(x0, x1))
3.96/1.79	   splitAt(0, x0)
3.96/1.79	   splitAt(s(x0), cons(x1, x2))
3.96/1.79	   tail(cons(x0, x1))
3.96/1.79	   take(x0, x1)
3.96/1.79	
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(10) PIsEmptyProof (EQUIVALENT)
3.96/1.79	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(11)
3.96/1.79	YES
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(12)
3.96/1.79	Obligation:
3.96/1.79	Q-restricted context-sensitive dependency pair problem:
3.96/1.79	The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, SPLITAT_2} are replacing on all positions.
3.96/1.79	For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3, U62'_4, U61'_4, U63'_4} we have mu(f) = {1}.
3.96/1.79	
3.96/1.79	The TRS P consists of the following rules:
3.96/1.79	
3.96/1.79	   U61'(tt, N, X, XS) -> U62'(tt, N, X, XS)
3.96/1.79	   U62'(tt, N, X, XS) -> U63'(tt, N, X, XS)
3.96/1.79	   U63'(tt, N, X, XS) -> SPLITAT(N, XS)
3.96/1.79	   SPLITAT(s(N), cons(X, XS)) -> U61'(tt, N, X, XS)
3.96/1.79	
3.96/1.79	The TRS R consists of the following rules:
3.96/1.79	
3.96/1.79	   U11(tt, N, XS) -> U12(tt, N, XS)
3.96/1.79	   U12(tt, N, XS) -> snd(splitAt(N, XS))
3.96/1.79	   U21(tt, X) -> U22(tt, X)
3.96/1.79	   U22(tt, X) -> X
3.96/1.79	   U31(tt, N) -> U32(tt, N)
3.96/1.79	   U32(tt, N) -> N
3.96/1.79	   U41(tt, N, XS) -> U42(tt, N, XS)
3.96/1.79	   U42(tt, N, XS) -> head(afterNth(N, XS))
3.96/1.79	   U51(tt, Y) -> U52(tt, Y)
3.96/1.79	   U52(tt, Y) -> Y
3.96/1.79	   U61(tt, N, X, XS) -> U62(tt, N, X, XS)
3.96/1.79	   U62(tt, N, X, XS) -> U63(tt, N, X, XS)
3.96/1.79	   U63(tt, N, X, XS) -> U64(splitAt(N, XS), X)
3.96/1.79	   U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
3.96/1.79	   U71(tt, XS) -> U72(tt, XS)
3.96/1.79	   U72(tt, XS) -> XS
3.96/1.79	   U81(tt, N, XS) -> U82(tt, N, XS)
3.96/1.79	   U82(tt, N, XS) -> fst(splitAt(N, XS))
3.96/1.79	   afterNth(N, XS) -> U11(tt, N, XS)
3.96/1.79	   fst(pair(X, Y)) -> U21(tt, X)
3.96/1.79	   head(cons(N, XS)) -> U31(tt, N)
3.96/1.79	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.96/1.79	   sel(N, XS) -> U41(tt, N, XS)
3.96/1.79	   snd(pair(X, Y)) -> U51(tt, Y)
3.96/1.79	   splitAt(0, XS) -> pair(nil, XS)
3.96/1.79	   splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS)
3.96/1.79	   tail(cons(N, XS)) -> U71(tt, XS)
3.96/1.79	   take(N, XS) -> U81(tt, N, XS)
3.96/1.79	
3.96/1.79	The set Q consists of the following terms:
3.96/1.79	
3.96/1.79	   U11(tt, x0, x1)
3.96/1.79	   U12(tt, x0, x1)
3.96/1.79	   U21(tt, x0)
3.96/1.79	   U22(tt, x0)
3.96/1.79	   U31(tt, x0)
3.96/1.79	   U32(tt, x0)
3.96/1.79	   U41(tt, x0, x1)
3.96/1.79	   U42(tt, x0, x1)
3.96/1.79	   U51(tt, x0)
3.96/1.79	   U52(tt, x0)
3.96/1.79	   U61(tt, x0, x1, x2)
3.96/1.79	   U62(tt, x0, x1, x2)
3.96/1.79	   U63(tt, x0, x1, x2)
3.96/1.79	   U64(pair(x0, x1), x2)
3.96/1.79	   U71(tt, x0)
3.96/1.79	   U72(tt, x0)
3.96/1.79	   U81(tt, x0, x1)
3.96/1.79	   U82(tt, x0, x1)
3.96/1.79	   afterNth(x0, x1)
3.96/1.79	   fst(pair(x0, x1))
3.96/1.79	   head(cons(x0, x1))
3.96/1.79	   natsFrom(x0)
3.96/1.79	   sel(x0, x1)
3.96/1.79	   snd(pair(x0, x1))
3.96/1.79	   splitAt(0, x0)
3.96/1.79	   splitAt(s(x0), cons(x1, x2))
3.96/1.79	   tail(cons(x0, x1))
3.96/1.79	   take(x0, x1)
3.96/1.79	
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(13) QCSDPSubtermProof (EQUIVALENT)
3.96/1.79	We use the subterm processor [DA_EMMES].
3.96/1.79	
3.96/1.79	
3.96/1.79	The following pairs can be oriented strictly and are deleted.
3.96/1.79	
3.96/1.79	   SPLITAT(s(N), cons(X, XS)) -> U61'(tt, N, X, XS)
3.96/1.79	The remaining pairs can at least be oriented weakly.
3.96/1.79	
3.96/1.79	   U61'(tt, N, X, XS) -> U62'(tt, N, X, XS)
3.96/1.79	   U62'(tt, N, X, XS) -> U63'(tt, N, X, XS)
3.96/1.79	   U63'(tt, N, X, XS) -> SPLITAT(N, XS)
3.96/1.79	Used ordering:  Combined order from the following AFS and order.
3.96/1.79	U62'(x1, x2, x3, x4)  =  x2
3.96/1.79	
3.96/1.79	U61'(x1, x2, x3, x4)  =  x2
3.96/1.79	
3.96/1.79	U63'(x1, x2, x3, x4)  =  x2
3.96/1.79	
3.96/1.79	SPLITAT(x1, x2)  =  x1
3.96/1.79	
3.96/1.79	
3.96/1.79	Subterm Order
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(14)
3.96/1.79	Obligation:
3.96/1.79	Q-restricted context-sensitive dependency pair problem:
3.96/1.79	The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, SPLITAT_2} are replacing on all positions.
3.96/1.79	For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3, U62'_4, U61'_4, U63'_4} we have mu(f) = {1}.
3.96/1.79	
3.96/1.79	The TRS P consists of the following rules:
3.96/1.79	
3.96/1.79	   U61'(tt, N, X, XS) -> U62'(tt, N, X, XS)
3.96/1.79	   U62'(tt, N, X, XS) -> U63'(tt, N, X, XS)
3.96/1.79	   U63'(tt, N, X, XS) -> SPLITAT(N, XS)
3.96/1.79	
3.96/1.79	The TRS R consists of the following rules:
3.96/1.79	
3.96/1.79	   U11(tt, N, XS) -> U12(tt, N, XS)
3.96/1.79	   U12(tt, N, XS) -> snd(splitAt(N, XS))
3.96/1.79	   U21(tt, X) -> U22(tt, X)
3.96/1.79	   U22(tt, X) -> X
3.96/1.79	   U31(tt, N) -> U32(tt, N)
3.96/1.79	   U32(tt, N) -> N
3.96/1.79	   U41(tt, N, XS) -> U42(tt, N, XS)
3.96/1.79	   U42(tt, N, XS) -> head(afterNth(N, XS))
3.96/1.79	   U51(tt, Y) -> U52(tt, Y)
3.96/1.79	   U52(tt, Y) -> Y
3.96/1.79	   U61(tt, N, X, XS) -> U62(tt, N, X, XS)
3.96/1.79	   U62(tt, N, X, XS) -> U63(tt, N, X, XS)
3.96/1.79	   U63(tt, N, X, XS) -> U64(splitAt(N, XS), X)
3.96/1.79	   U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
3.96/1.79	   U71(tt, XS) -> U72(tt, XS)
3.96/1.79	   U72(tt, XS) -> XS
3.96/1.79	   U81(tt, N, XS) -> U82(tt, N, XS)
3.96/1.79	   U82(tt, N, XS) -> fst(splitAt(N, XS))
3.96/1.79	   afterNth(N, XS) -> U11(tt, N, XS)
3.96/1.79	   fst(pair(X, Y)) -> U21(tt, X)
3.96/1.79	   head(cons(N, XS)) -> U31(tt, N)
3.96/1.79	   natsFrom(N) -> cons(N, natsFrom(s(N)))
3.96/1.79	   sel(N, XS) -> U41(tt, N, XS)
3.96/1.79	   snd(pair(X, Y)) -> U51(tt, Y)
3.96/1.79	   splitAt(0, XS) -> pair(nil, XS)
3.96/1.79	   splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS)
3.96/1.79	   tail(cons(N, XS)) -> U71(tt, XS)
3.96/1.79	   take(N, XS) -> U81(tt, N, XS)
3.96/1.79	
3.96/1.79	The set Q consists of the following terms:
3.96/1.79	
3.96/1.79	   U11(tt, x0, x1)
3.96/1.79	   U12(tt, x0, x1)
3.96/1.79	   U21(tt, x0)
3.96/1.79	   U22(tt, x0)
3.96/1.79	   U31(tt, x0)
3.96/1.79	   U32(tt, x0)
3.96/1.79	   U41(tt, x0, x1)
3.96/1.79	   U42(tt, x0, x1)
3.96/1.79	   U51(tt, x0)
3.96/1.79	   U52(tt, x0)
3.96/1.79	   U61(tt, x0, x1, x2)
3.96/1.79	   U62(tt, x0, x1, x2)
3.96/1.79	   U63(tt, x0, x1, x2)
3.96/1.79	   U64(pair(x0, x1), x2)
3.96/1.79	   U71(tt, x0)
3.96/1.79	   U72(tt, x0)
3.96/1.79	   U81(tt, x0, x1)
3.96/1.79	   U82(tt, x0, x1)
3.96/1.79	   afterNth(x0, x1)
3.96/1.79	   fst(pair(x0, x1))
3.96/1.79	   head(cons(x0, x1))
3.96/1.79	   natsFrom(x0)
3.96/1.79	   sel(x0, x1)
3.96/1.79	   snd(pair(x0, x1))
3.96/1.79	   splitAt(0, x0)
3.96/1.79	   splitAt(s(x0), cons(x1, x2))
3.96/1.79	   tail(cons(x0, x1))
3.96/1.79	   take(x0, x1)
3.96/1.79	
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(15) QCSDependencyGraphProof (EQUIVALENT)
3.96/1.79	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 3 less nodes.
3.96/1.79	
3.96/1.79	----------------------------------------
3.96/1.79	
3.96/1.79	(16)
3.96/1.79	TRUE
4.19/1.87	EOF