(VAR N X XS YS ZS Y)
(STRATEGY CONTEXTSENSITIVE 
  (U11 1)
  (tt)
  (U12 1)
  (splitAt 1 2)
  (pair 1 2)
  (cons 1)
  (afterNth 1 2)
  (snd 1)
  (and 1)
  (fst 1)
  (head 1)
  (natsFrom 1)
  (s 1)
  (sel 1 2)
  (0)
  (nil)
  (tail 1)
  (take 1 2)
)
(RULES 
U11(tt,N,X,XS) -> U12(splitAt(N,XS),X)
U12(pair(YS,ZS),X) -> pair(cons(X,YS),ZS)
afterNth(N,XS) -> snd(splitAt(N,XS))
and(tt,X) -> X
fst(pair(X,Y)) -> X
head(cons(N,XS)) -> N
natsFrom(N) -> cons(N,natsFrom(s(N)))
sel(N,XS) -> head(afterNth(N,XS))
snd(pair(X,Y)) -> Y
splitAt(0,XS) -> pair(nil,XS)
splitAt(s(N),cons(X,XS)) -> U11(tt,N,X,XS)
tail(cons(N,XS)) -> XS
take(N,XS) -> fst(splitAt(N,XS))
)

The TRS is orthogonal, thus termination of innermost context-sensitive rewriting is equivalent to termination of context-sensitive rewriting.

Proving termination of context-sensitive rewriting for LISTUTILITIES_nosorts:

-> Dependency pairs:
nF_U11(tt,N,X,XS) -> nF_U12(splitAt(N,XS),X)
nF_U11(tt,N,X,XS) -> nF_splitAt(N,XS)
nF_U11(tt,N,X,XS) -> N
nF_U11(tt,N,X,XS) -> XS
nF_U12(pair(YS,ZS),X) -> X
nF_afterNth(N,XS) -> nF_snd(splitAt(N,XS))
nF_afterNth(N,XS) -> nF_splitAt(N,XS)
nF_and(tt,X) -> X
nF_sel(N,XS) -> nF_head(afterNth(N,XS))
nF_sel(N,XS) -> nF_afterNth(N,XS)
nF_splitAt(s(N),cons(X,XS)) -> nF_U11(tt,N,X,XS)
nF_tail(cons(N,XS)) -> XS
nF_take(N,XS) -> nF_fst(splitAt(N,XS))
nF_take(N,XS) -> nF_splitAt(N,XS)

-> Proof of termination for LISTUTILITIES_nosorts_1:
-> -> Dependency pairs in cycle:
nF_U11(tt,N,X,XS) -> nF_splitAt(N,XS)
nF_splitAt(s(N),cons(X,XS)) -> nF_U11(tt,N,X,XS)

Termination proved: Cycles verify subterm criterion.

SETTINGS:
Base ordering: Polynomial ordering
Proof mode: SCCs in CSDG + base ordering
Upper bound for coeffs: 1
Rationals below 1 for all non-replacing args: No
Polynomial interpretation: Linear
Coeffs in polynomials: No rationals
Delta: automatic



Termination was proved succesfully.