Termination w.r.t. Q proof of /tmp/tmpZyYXPx/LISTUTILITIES_nokinds-noand

Termination w.r.t. Q of the given QTRS could not be shown:

0 QTRS

↳1 DependencyPairsProof (⇔)

↳2 QDP

↳3 DependencyGraphProof (⇔)

↳4 QDP

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

U101(tt, V2) → U102(isLNat(activate(V2)))
U102(tt) → tt
U11(tt, N, XS) → U12(isLNat(activate(XS)), activate(N), activate(XS))
U111(tt) → tt
U12(tt, N, XS) → snd(splitAt(activate(N), activate(XS)))
U121(tt) → tt
U131(tt, V2) → U132(isLNat(activate(V2)))
U132(tt) → tt
U141(tt, V2) → U142(isLNat(activate(V2)))
U142(tt) → tt
U151(tt, V2) → U152(isLNat(activate(V2)))
U152(tt) → tt
U161(tt, N) → cons(activate(N), n__natsFrom(s(activate(N))))
U171(tt, N, XS) → U172(isLNat(activate(XS)), activate(N), activate(XS))
U172(tt, N, XS) → head(afterNth(activate(N), activate(XS)))
U181(tt, Y) → U182(isLNat(activate(Y)), activate(Y))
U182(tt, Y) → activate(Y)
U191(tt, XS) → pair(nil, activate(XS))
U201(tt, N, X, XS) → U202(isNatural(activate(X)), activate(N), activate(X), activate(XS))
U202(tt, N, X, XS) → U203(isLNat(activate(XS)), activate(N), activate(X), activate(XS))
U203(tt, N, X, XS) → U204(splitAt(activate(N), activate(XS)), activate(X))
U204(pair(YS, ZS), X) → pair(cons(activate(X), YS), ZS)
U21(tt, X, Y) → U22(isLNat(activate(Y)), activate(X))
U211(tt, XS) → U212(isLNat(activate(XS)), activate(XS))
U212(tt, XS) → activate(XS)
U22(tt, X) → activate(X)
U221(tt, N, XS) → U222(isLNat(activate(XS)), activate(N), activate(XS))
U222(tt, N, XS) → fst(splitAt(activate(N), activate(XS)))
U31(tt, N, XS) → U32(isLNat(activate(XS)), activate(N))
U32(tt, N) → activate(N)
U41(tt, V2) → U42(isLNat(activate(V2)))
U42(tt) → tt
U51(tt, V2) → U52(isLNat(activate(V2)))
U52(tt) → tt
U61(tt) → tt
U71(tt) → tt
U81(tt) → tt
U91(tt) → tt
afterNth(N, XS) → U11(isNatural(N), N, XS)
fst(pair(X, Y)) → U21(isLNat(X), X, Y)
head(cons(N, XS)) → U31(isNatural(N), N, activate(XS))
isLNat(n__nil) → tt
isLNat(n__afterNth(V1, V2)) → U41(isNatural(activate(V1)), activate(V2))
isLNat(n__cons(V1, V2)) → U51(isNatural(activate(V1)), activate(V2))
isLNat(n__fst(V1)) → U61(isPLNat(activate(V1)))
isLNat(n__natsFrom(V1)) → U71(isNatural(activate(V1)))
isLNat(n__snd(V1)) → U81(isPLNat(activate(V1)))
isLNat(n__tail(V1)) → U91(isLNat(activate(V1)))
isLNat(n__take(V1, V2)) → U101(isNatural(activate(V1)), activate(V2))
isNatural(n__0) → tt
isNatural(n__head(V1)) → U111(isLNat(activate(V1)))
isNatural(n__s(V1)) → U121(isNatural(activate(V1)))
isNatural(n__sel(V1, V2)) → U131(isNatural(activate(V1)), activate(V2))
isPLNat(n__pair(V1, V2)) → U141(isLNat(activate(V1)), activate(V2))
isPLNat(n__splitAt(V1, V2)) → U151(isNatural(activate(V1)), activate(V2))
natsFrom(N) → U161(isNatural(N), N)
sel(N, XS) → U171(isNatural(N), N, XS)
snd(pair(X, Y)) → U181(isLNat(X), Y)
splitAt(0, XS) → U191(isLNat(XS), XS)
splitAt(s(N), cons(X, XS)) → U201(isNatural(N), N, X, activate(XS))
tail(cons(N, XS)) → U211(isNatural(N), activate(XS))
take(N, XS) → U221(isNatural(N), N, XS)
natsFrom(X) → n__natsFrom(X)
nil → n__nil
afterNth(X1, X2) → n__afterNth(X1, X2)
cons(X1, X2) → n__cons(X1, X2)
fst(X) → n__fst(X)
snd(X) → n__snd(X)
tail(X) → n__tail(X)
take(X1, X2) → n__take(X1, X2)
0 → n__0
head(X) → n__head(X)
s(X) → n__s(X)
sel(X1, X2) → n__sel(X1, X2)
pair(X1, X2) → n__pair(X1, X2)
splitAt(X1, X2) → n__splitAt(X1, X2)
activate(n__natsFrom(X)) → natsFrom(X)
activate(n__nil) → nil
activate(n__afterNth(X1, X2)) → afterNth(X1, X2)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(n__fst(X)) → fst(X)
activate(n__snd(X)) → snd(X)
activate(n__tail(X)) → tail(X)
activate(n__take(X1, X2)) → take(X1, X2)
activate(n__0) → 0
activate(n__head(X)) → head(X)
activate(n__s(X)) → s(X)
activate(n__sel(X1, X2)) → sel(X1, X2)
activate(n__pair(X1, X2)) → pair(X1, X2)
activate(n__splitAt(X1, X2)) → splitAt(X1, X2)
activate(X) → X

Q is empty.

(1) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(2) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U101¹(tt, V2) → U102¹(isLNat(activate(V2)))
U101¹(tt, V2) → ISLNAT(activate(V2))
U101¹(tt, V2) → ACTIVATE(V2)
U11¹(tt, N, XS) → U12¹(isLNat(activate(XS)), activate(N), activate(XS))
U11¹(tt, N, XS) → ISLNAT(activate(XS))
U11¹(tt, N, XS) → ACTIVATE(XS)
U11¹(tt, N, XS) → ACTIVATE(N)
U12¹(tt, N, XS) → SND(splitAt(activate(N), activate(XS)))
U12¹(tt, N, XS) → SPLITAT(activate(N), activate(XS))
U12¹(tt, N, XS) → ACTIVATE(N)
U12¹(tt, N, XS) → ACTIVATE(XS)
U131¹(tt, V2) → U132¹(isLNat(activate(V2)))
U131¹(tt, V2) → ISLNAT(activate(V2))
U131¹(tt, V2) → ACTIVATE(V2)
U141¹(tt, V2) → U142¹(isLNat(activate(V2)))
U141¹(tt, V2) → ISLNAT(activate(V2))
U141¹(tt, V2) → ACTIVATE(V2)
U151¹(tt, V2) → U152¹(isLNat(activate(V2)))
U151¹(tt, V2) → ISLNAT(activate(V2))
U151¹(tt, V2) → ACTIVATE(V2)
U161¹(tt, N) → CONS(activate(N), n__natsFrom(s(activate(N))))
U161¹(tt, N) → ACTIVATE(N)
U161¹(tt, N) → S(activate(N))
U171¹(tt, N, XS) → U172¹(isLNat(activate(XS)), activate(N), activate(XS))
U171¹(tt, N, XS) → ISLNAT(activate(XS))
U171¹(tt, N, XS) → ACTIVATE(XS)
U171¹(tt, N, XS) → ACTIVATE(N)
U172¹(tt, N, XS) → HEAD(afterNth(activate(N), activate(XS)))
U172¹(tt, N, XS) → AFTERNTH(activate(N), activate(XS))
U172¹(tt, N, XS) → ACTIVATE(N)
U172¹(tt, N, XS) → ACTIVATE(XS)
U181¹(tt, Y) → U182¹(isLNat(activate(Y)), activate(Y))
U181¹(tt, Y) → ISLNAT(activate(Y))
U181¹(tt, Y) → ACTIVATE(Y)
U182¹(tt, Y) → ACTIVATE(Y)
U191¹(tt, XS) → PAIR(nil, activate(XS))
U191¹(tt, XS) → NIL
U191¹(tt, XS) → ACTIVATE(XS)
U201¹(tt, N, X, XS) → U202¹(isNatural(activate(X)), activate(N), activate(X), activate(XS))
U201¹(tt, N, X, XS) → ISNATURAL(activate(X))
U201¹(tt, N, X, XS) → ACTIVATE(X)
U201¹(tt, N, X, XS) → ACTIVATE(N)
U201¹(tt, N, X, XS) → ACTIVATE(XS)
U202¹(tt, N, X, XS) → U203¹(isLNat(activate(XS)), activate(N), activate(X), activate(XS))
U202¹(tt, N, X, XS) → ISLNAT(activate(XS))
U202¹(tt, N, X, XS) → ACTIVATE(XS)
U202¹(tt, N, X, XS) → ACTIVATE(N)
U202¹(tt, N, X, XS) → ACTIVATE(X)
U203¹(tt, N, X, XS) → U204¹(splitAt(activate(N), activate(XS)), activate(X))
U203¹(tt, N, X, XS) → SPLITAT(activate(N), activate(XS))
U203¹(tt, N, X, XS) → ACTIVATE(N)
U203¹(tt, N, X, XS) → ACTIVATE(XS)
U203¹(tt, N, X, XS) → ACTIVATE(X)
U204¹(pair(YS, ZS), X) → PAIR(cons(activate(X), YS), ZS)
U204¹(pair(YS, ZS), X) → CONS(activate(X), YS)
U204¹(pair(YS, ZS), X) → ACTIVATE(X)
U21¹(tt, X, Y) → U22¹(isLNat(activate(Y)), activate(X))
U21¹(tt, X, Y) → ISLNAT(activate(Y))
U21¹(tt, X, Y) → ACTIVATE(Y)
U21¹(tt, X, Y) → ACTIVATE(X)
U211¹(tt, XS) → U212¹(isLNat(activate(XS)), activate(XS))
U211¹(tt, XS) → ISLNAT(activate(XS))
U211¹(tt, XS) → ACTIVATE(XS)
U212¹(tt, XS) → ACTIVATE(XS)
U22¹(tt, X) → ACTIVATE(X)
U221¹(tt, N, XS) → U222¹(isLNat(activate(XS)), activate(N), activate(XS))
U221¹(tt, N, XS) → ISLNAT(activate(XS))
U221¹(tt, N, XS) → ACTIVATE(XS)
U221¹(tt, N, XS) → ACTIVATE(N)
U222¹(tt, N, XS) → FST(splitAt(activate(N), activate(XS)))
U222¹(tt, N, XS) → SPLITAT(activate(N), activate(XS))
U222¹(tt, N, XS) → ACTIVATE(N)
U222¹(tt, N, XS) → ACTIVATE(XS)
U31¹(tt, N, XS) → U32¹(isLNat(activate(XS)), activate(N))
U31¹(tt, N, XS) → ISLNAT(activate(XS))
U31¹(tt, N, XS) → ACTIVATE(XS)
U31¹(tt, N, XS) → ACTIVATE(N)
U32¹(tt, N) → ACTIVATE(N)
U41¹(tt, V2) → U42¹(isLNat(activate(V2)))
U41¹(tt, V2) → ISLNAT(activate(V2))
U41¹(tt, V2) → ACTIVATE(V2)
U51¹(tt, V2) → U52¹(isLNat(activate(V2)))
U51¹(tt, V2) → ISLNAT(activate(V2))
U51¹(tt, V2) → ACTIVATE(V2)
AFTERNTH(N, XS) → U11¹(isNatural(N), N, XS)
AFTERNTH(N, XS) → ISNATURAL(N)
FST(pair(X, Y)) → U21¹(isLNat(X), X, Y)
FST(pair(X, Y)) → ISLNAT(X)
HEAD(cons(N, XS)) → U31¹(isNatural(N), N, activate(XS))
HEAD(cons(N, XS)) → ISNATURAL(N)
HEAD(cons(N, XS)) → ACTIVATE(XS)
ISLNAT(n__afterNth(V1, V2)) → U41¹(isNatural(activate(V1)), activate(V2))
ISLNAT(n__afterNth(V1, V2)) → ISNATURAL(activate(V1))
ISLNAT(n__afterNth(V1, V2)) → ACTIVATE(V1)
ISLNAT(n__afterNth(V1, V2)) → ACTIVATE(V2)
ISLNAT(n__cons(V1, V2)) → U51¹(isNatural(activate(V1)), activate(V2))
ISLNAT(n__cons(V1, V2)) → ISNATURAL(activate(V1))
ISLNAT(n__cons(V1, V2)) → ACTIVATE(V1)
ISLNAT(n__cons(V1, V2)) → ACTIVATE(V2)
ISLNAT(n__fst(V1)) → U61¹(isPLNat(activate(V1)))
ISLNAT(n__fst(V1)) → ISPLNAT(activate(V1))
ISLNAT(n__fst(V1)) → ACTIVATE(V1)
ISLNAT(n__natsFrom(V1)) → U71¹(isNatural(activate(V1)))
ISLNAT(n__natsFrom(V1)) → ISNATURAL(activate(V1))
ISLNAT(n__natsFrom(V1)) → ACTIVATE(V1)
ISLNAT(n__snd(V1)) → U81¹(isPLNat(activate(V1)))
ISLNAT(n__snd(V1)) → ISPLNAT(activate(V1))
ISLNAT(n__snd(V1)) → ACTIVATE(V1)
ISLNAT(n__tail(V1)) → U91¹(isLNat(activate(V1)))
ISLNAT(n__tail(V1)) → ISLNAT(activate(V1))
ISLNAT(n__tail(V1)) → ACTIVATE(V1)
ISLNAT(n__take(V1, V2)) → U101¹(isNatural(activate(V1)), activate(V2))
ISLNAT(n__take(V1, V2)) → ISNATURAL(activate(V1))
ISLNAT(n__take(V1, V2)) → ACTIVATE(V1)
ISLNAT(n__take(V1, V2)) → ACTIVATE(V2)
ISNATURAL(n__head(V1)) → U111¹(isLNat(activate(V1)))
ISNATURAL(n__head(V1)) → ISLNAT(activate(V1))
ISNATURAL(n__head(V1)) → ACTIVATE(V1)
ISNATURAL(n__s(V1)) → U121¹(isNatural(activate(V1)))
ISNATURAL(n__s(V1)) → ISNATURAL(activate(V1))
ISNATURAL(n__s(V1)) → ACTIVATE(V1)
ISNATURAL(n__sel(V1, V2)) → U131¹(isNatural(activate(V1)), activate(V2))
ISNATURAL(n__sel(V1, V2)) → ISNATURAL(activate(V1))
ISNATURAL(n__sel(V1, V2)) → ACTIVATE(V1)
ISNATURAL(n__sel(V1, V2)) → ACTIVATE(V2)
ISPLNAT(n__pair(V1, V2)) → U141¹(isLNat(activate(V1)), activate(V2))
ISPLNAT(n__pair(V1, V2)) → ISLNAT(activate(V1))
ISPLNAT(n__pair(V1, V2)) → ACTIVATE(V1)
ISPLNAT(n__pair(V1, V2)) → ACTIVATE(V2)
ISPLNAT(n__splitAt(V1, V2)) → U151¹(isNatural(activate(V1)), activate(V2))
ISPLNAT(n__splitAt(V1, V2)) → ISNATURAL(activate(V1))
ISPLNAT(n__splitAt(V1, V2)) → ACTIVATE(V1)
ISPLNAT(n__splitAt(V1, V2)) → ACTIVATE(V2)
NATSFROM(N) → U161¹(isNatural(N), N)
NATSFROM(N) → ISNATURAL(N)
SEL(N, XS) → U171¹(isNatural(N), N, XS)
SEL(N, XS) → ISNATURAL(N)
SND(pair(X, Y)) → U181¹(isLNat(X), Y)
SND(pair(X, Y)) → ISLNAT(X)
SPLITAT(0, XS) → U191¹(isLNat(XS), XS)
SPLITAT(0, XS) → ISLNAT(XS)
SPLITAT(s(N), cons(X, XS)) → U201¹(isNatural(N), N, X, activate(XS))
SPLITAT(s(N), cons(X, XS)) → ISNATURAL(N)
SPLITAT(s(N), cons(X, XS)) → ACTIVATE(XS)
TAIL(cons(N, XS)) → U211¹(isNatural(N), activate(XS))
TAIL(cons(N, XS)) → ISNATURAL(N)
TAIL(cons(N, XS)) → ACTIVATE(XS)
TAKE(N, XS) → U221¹(isNatural(N), N, XS)
TAKE(N, XS) → ISNATURAL(N)
ACTIVATE(n__natsFrom(X)) → NATSFROM(X)
ACTIVATE(n__nil) → NIL
ACTIVATE(n__afterNth(X1, X2)) → AFTERNTH(X1, X2)
ACTIVATE(n__cons(X1, X2)) → CONS(X1, X2)
ACTIVATE(n__fst(X)) → FST(X)
ACTIVATE(n__snd(X)) → SND(X)
ACTIVATE(n__tail(X)) → TAIL(X)
ACTIVATE(n__take(X1, X2)) → TAKE(X1, X2)
ACTIVATE(n__0) → 0¹
ACTIVATE(n__head(X)) → HEAD(X)
ACTIVATE(n__s(X)) → S(X)
ACTIVATE(n__sel(X1, X2)) → SEL(X1, X2)
ACTIVATE(n__pair(X1, X2)) → PAIR(X1, X2)
ACTIVATE(n__splitAt(X1, X2)) → SPLITAT(X1, X2)

The TRS R consists of the following rules:

U101(tt, V2) → U102(isLNat(activate(V2)))
U102(tt) → tt
U11(tt, N, XS) → U12(isLNat(activate(XS)), activate(N), activate(XS))
U111(tt) → tt
U12(tt, N, XS) → snd(splitAt(activate(N), activate(XS)))
U121(tt) → tt
U131(tt, V2) → U132(isLNat(activate(V2)))
U132(tt) → tt
U141(tt, V2) → U142(isLNat(activate(V2)))
U142(tt) → tt
U151(tt, V2) → U152(isLNat(activate(V2)))
U152(tt) → tt
U161(tt, N) → cons(activate(N), n__natsFrom(s(activate(N))))
U171(tt, N, XS) → U172(isLNat(activate(XS)), activate(N), activate(XS))
U172(tt, N, XS) → head(afterNth(activate(N), activate(XS)))
U181(tt, Y) → U182(isLNat(activate(Y)), activate(Y))
U182(tt, Y) → activate(Y)
U191(tt, XS) → pair(nil, activate(XS))
U201(tt, N, X, XS) → U202(isNatural(activate(X)), activate(N), activate(X), activate(XS))
U202(tt, N, X, XS) → U203(isLNat(activate(XS)), activate(N), activate(X), activate(XS))
U203(tt, N, X, XS) → U204(splitAt(activate(N), activate(XS)), activate(X))
U204(pair(YS, ZS), X) → pair(cons(activate(X), YS), ZS)
U21(tt, X, Y) → U22(isLNat(activate(Y)), activate(X))
U211(tt, XS) → U212(isLNat(activate(XS)), activate(XS))
U212(tt, XS) → activate(XS)
U22(tt, X) → activate(X)
U221(tt, N, XS) → U222(isLNat(activate(XS)), activate(N), activate(XS))
U222(tt, N, XS) → fst(splitAt(activate(N), activate(XS)))
U31(tt, N, XS) → U32(isLNat(activate(XS)), activate(N))
U32(tt, N) → activate(N)
U41(tt, V2) → U42(isLNat(activate(V2)))
U42(tt) → tt
U51(tt, V2) → U52(isLNat(activate(V2)))
U52(tt) → tt
U61(tt) → tt
U71(tt) → tt
U81(tt) → tt
U91(tt) → tt
afterNth(N, XS) → U11(isNatural(N), N, XS)
fst(pair(X, Y)) → U21(isLNat(X), X, Y)
head(cons(N, XS)) → U31(isNatural(N), N, activate(XS))
isLNat(n__nil) → tt
isLNat(n__afterNth(V1, V2)) → U41(isNatural(activate(V1)), activate(V2))
isLNat(n__cons(V1, V2)) → U51(isNatural(activate(V1)), activate(V2))
isLNat(n__fst(V1)) → U61(isPLNat(activate(V1)))
isLNat(n__natsFrom(V1)) → U71(isNatural(activate(V1)))
isLNat(n__snd(V1)) → U81(isPLNat(activate(V1)))
isLNat(n__tail(V1)) → U91(isLNat(activate(V1)))
isLNat(n__take(V1, V2)) → U101(isNatural(activate(V1)), activate(V2))
isNatural(n__0) → tt
isNatural(n__head(V1)) → U111(isLNat(activate(V1)))
isNatural(n__s(V1)) → U121(isNatural(activate(V1)))
isNatural(n__sel(V1, V2)) → U131(isNatural(activate(V1)), activate(V2))
isPLNat(n__pair(V1, V2)) → U141(isLNat(activate(V1)), activate(V2))
isPLNat(n__splitAt(V1, V2)) → U151(isNatural(activate(V1)), activate(V2))
natsFrom(N) → U161(isNatural(N), N)
sel(N, XS) → U171(isNatural(N), N, XS)
snd(pair(X, Y)) → U181(isLNat(X), Y)
splitAt(0, XS) → U191(isLNat(XS), XS)
splitAt(s(N), cons(X, XS)) → U201(isNatural(N), N, X, activate(XS))
tail(cons(N, XS)) → U211(isNatural(N), activate(XS))
take(N, XS) → U221(isNatural(N), N, XS)
natsFrom(X) → n__natsFrom(X)
nil → n__nil
afterNth(X1, X2) → n__afterNth(X1, X2)
cons(X1, X2) → n__cons(X1, X2)
fst(X) → n__fst(X)
snd(X) → n__snd(X)
tail(X) → n__tail(X)
take(X1, X2) → n__take(X1, X2)
0 → n__0
head(X) → n__head(X)
s(X) → n__s(X)
sel(X1, X2) → n__sel(X1, X2)
pair(X1, X2) → n__pair(X1, X2)
splitAt(X1, X2) → n__splitAt(X1, X2)
activate(n__natsFrom(X)) → natsFrom(X)
activate(n__nil) → nil
activate(n__afterNth(X1, X2)) → afterNth(X1, X2)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(n__fst(X)) → fst(X)
activate(n__snd(X)) → snd(X)
activate(n__tail(X)) → tail(X)
activate(n__take(X1, X2)) → take(X1, X2)
activate(n__0) → 0
activate(n__head(X)) → head(X)
activate(n__s(X)) → s(X)
activate(n__sel(X1, X2)) → sel(X1, X2)
activate(n__pair(X1, X2)) → pair(X1, X2)
activate(n__splitAt(X1, X2)) → splitAt(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(3) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 23 less nodes.

(4) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U101¹(tt, V2) → ISLNAT(activate(V2))
ISLNAT(n__afterNth(V1, V2)) → U41¹(isNatural(activate(V1)), activate(V2))
U41¹(tt, V2) → ISLNAT(activate(V2))
ISLNAT(n__afterNth(V1, V2)) → ISNATURAL(activate(V1))
ISNATURAL(n__head(V1)) → ISLNAT(activate(V1))
ISLNAT(n__afterNth(V1, V2)) → ACTIVATE(V1)
ACTIVATE(n__natsFrom(X)) → NATSFROM(X)
NATSFROM(N) → U161¹(isNatural(N), N)
U161¹(tt, N) → ACTIVATE(N)
ACTIVATE(n__afterNth(X1, X2)) → AFTERNTH(X1, X2)
AFTERNTH(N, XS) → U11¹(isNatural(N), N, XS)
U11¹(tt, N, XS) → U12¹(isLNat(activate(XS)), activate(N), activate(XS))
U12¹(tt, N, XS) → SND(splitAt(activate(N), activate(XS)))
SND(pair(X, Y)) → U181¹(isLNat(X), Y)
U181¹(tt, Y) → U182¹(isLNat(activate(Y)), activate(Y))
U182¹(tt, Y) → ACTIVATE(Y)
ACTIVATE(n__fst(X)) → FST(X)
FST(pair(X, Y)) → U21¹(isLNat(X), X, Y)
U21¹(tt, X, Y) → U22¹(isLNat(activate(Y)), activate(X))
U22¹(tt, X) → ACTIVATE(X)
ACTIVATE(n__snd(X)) → SND(X)
SND(pair(X, Y)) → ISLNAT(X)
ISLNAT(n__afterNth(V1, V2)) → ACTIVATE(V2)
ACTIVATE(n__tail(X)) → TAIL(X)
TAIL(cons(N, XS)) → U211¹(isNatural(N), activate(XS))
U211¹(tt, XS) → U212¹(isLNat(activate(XS)), activate(XS))
U212¹(tt, XS) → ACTIVATE(XS)
ACTIVATE(n__take(X1, X2)) → TAKE(X1, X2)
TAKE(N, XS) → U221¹(isNatural(N), N, XS)
U221¹(tt, N, XS) → U222¹(isLNat(activate(XS)), activate(N), activate(XS))
U222¹(tt, N, XS) → FST(splitAt(activate(N), activate(XS)))
FST(pair(X, Y)) → ISLNAT(X)
ISLNAT(n__cons(V1, V2)) → U51¹(isNatural(activate(V1)), activate(V2))
U51¹(tt, V2) → ISLNAT(activate(V2))
ISLNAT(n__cons(V1, V2)) → ISNATURAL(activate(V1))
ISNATURAL(n__head(V1)) → ACTIVATE(V1)
ACTIVATE(n__head(X)) → HEAD(X)
HEAD(cons(N, XS)) → U31¹(isNatural(N), N, activate(XS))
U31¹(tt, N, XS) → U32¹(isLNat(activate(XS)), activate(N))
U32¹(tt, N) → ACTIVATE(N)
ACTIVATE(n__sel(X1, X2)) → SEL(X1, X2)
SEL(N, XS) → U171¹(isNatural(N), N, XS)
U171¹(tt, N, XS) → U172¹(isLNat(activate(XS)), activate(N), activate(XS))
U172¹(tt, N, XS) → HEAD(afterNth(activate(N), activate(XS)))
HEAD(cons(N, XS)) → ISNATURAL(N)
ISNATURAL(n__s(V1)) → ISNATURAL(activate(V1))
ISNATURAL(n__s(V1)) → ACTIVATE(V1)
ACTIVATE(n__splitAt(X1, X2)) → SPLITAT(X1, X2)
SPLITAT(0, XS) → U191¹(isLNat(XS), XS)
U191¹(tt, XS) → ACTIVATE(XS)
SPLITAT(0, XS) → ISLNAT(XS)
ISLNAT(n__cons(V1, V2)) → ACTIVATE(V1)
ISLNAT(n__cons(V1, V2)) → ACTIVATE(V2)
ISLNAT(n__fst(V1)) → ISPLNAT(activate(V1))
ISPLNAT(n__pair(V1, V2)) → U141¹(isLNat(activate(V1)), activate(V2))
U141¹(tt, V2) → ISLNAT(activate(V2))
ISLNAT(n__fst(V1)) → ACTIVATE(V1)
ISLNAT(n__natsFrom(V1)) → ISNATURAL(activate(V1))
ISNATURAL(n__sel(V1, V2)) → U131¹(isNatural(activate(V1)), activate(V2))
U131¹(tt, V2) → ISLNAT(activate(V2))
ISLNAT(n__natsFrom(V1)) → ACTIVATE(V1)
ISLNAT(n__snd(V1)) → ISPLNAT(activate(V1))
ISPLNAT(n__pair(V1, V2)) → ISLNAT(activate(V1))
ISLNAT(n__snd(V1)) → ACTIVATE(V1)
ISLNAT(n__tail(V1)) → ISLNAT(activate(V1))
ISLNAT(n__tail(V1)) → ACTIVATE(V1)
ISLNAT(n__take(V1, V2)) → U101¹(isNatural(activate(V1)), activate(V2))
U101¹(tt, V2) → ACTIVATE(V2)
ISLNAT(n__take(V1, V2)) → ISNATURAL(activate(V1))
ISNATURAL(n__sel(V1, V2)) → ISNATURAL(activate(V1))
ISNATURAL(n__sel(V1, V2)) → ACTIVATE(V1)
ISNATURAL(n__sel(V1, V2)) → ACTIVATE(V2)
ISLNAT(n__take(V1, V2)) → ACTIVATE(V1)
ISLNAT(n__take(V1, V2)) → ACTIVATE(V2)
ISPLNAT(n__pair(V1, V2)) → ACTIVATE(V1)
ISPLNAT(n__pair(V1, V2)) → ACTIVATE(V2)
ISPLNAT(n__splitAt(V1, V2)) → U151¹(isNatural(activate(V1)), activate(V2))
U151¹(tt, V2) → ISLNAT(activate(V2))
U151¹(tt, V2) → ACTIVATE(V2)
ISPLNAT(n__splitAt(V1, V2)) → ISNATURAL(activate(V1))
ISPLNAT(n__splitAt(V1, V2)) → ACTIVATE(V1)
ISPLNAT(n__splitAt(V1, V2)) → ACTIVATE(V2)
U131¹(tt, V2) → ACTIVATE(V2)
U141¹(tt, V2) → ACTIVATE(V2)
SPLITAT(s(N), cons(X, XS)) → U201¹(isNatural(N), N, X, activate(XS))
U201¹(tt, N, X, XS) → U202¹(isNatural(activate(X)), activate(N), activate(X), activate(XS))
U202¹(tt, N, X, XS) → U203¹(isLNat(activate(XS)), activate(N), activate(X), activate(XS))
U203¹(tt, N, X, XS) → U204¹(splitAt(activate(N), activate(XS)), activate(X))
U204¹(pair(YS, ZS), X) → ACTIVATE(X)
U203¹(tt, N, X, XS) → SPLITAT(activate(N), activate(XS))
SPLITAT(s(N), cons(X, XS)) → ISNATURAL(N)
SPLITAT(s(N), cons(X, XS)) → ACTIVATE(XS)
U203¹(tt, N, X, XS) → ACTIVATE(N)
U203¹(tt, N, X, XS) → ACTIVATE(XS)
U203¹(tt, N, X, XS) → ACTIVATE(X)
U202¹(tt, N, X, XS) → ISLNAT(activate(XS))
U202¹(tt, N, X, XS) → ACTIVATE(XS)
U202¹(tt, N, X, XS) → ACTIVATE(N)
U202¹(tt, N, X, XS) → ACTIVATE(X)
U201¹(tt, N, X, XS) → ISNATURAL(activate(X))
U201¹(tt, N, X, XS) → ACTIVATE(X)
U201¹(tt, N, X, XS) → ACTIVATE(N)
U201¹(tt, N, X, XS) → ACTIVATE(XS)
HEAD(cons(N, XS)) → ACTIVATE(XS)
U172¹(tt, N, XS) → AFTERNTH(activate(N), activate(XS))
AFTERNTH(N, XS) → ISNATURAL(N)
U172¹(tt, N, XS) → ACTIVATE(N)
U172¹(tt, N, XS) → ACTIVATE(XS)
U171¹(tt, N, XS) → ISLNAT(activate(XS))
U171¹(tt, N, XS) → ACTIVATE(XS)
U171¹(tt, N, XS) → ACTIVATE(N)
SEL(N, XS) → ISNATURAL(N)
U31¹(tt, N, XS) → ISLNAT(activate(XS))
U31¹(tt, N, XS) → ACTIVATE(XS)
U31¹(tt, N, XS) → ACTIVATE(N)
U51¹(tt, V2) → ACTIVATE(V2)
U222¹(tt, N, XS) → SPLITAT(activate(N), activate(XS))
U222¹(tt, N, XS) → ACTIVATE(N)
U222¹(tt, N, XS) → ACTIVATE(XS)
U221¹(tt, N, XS) → ISLNAT(activate(XS))
U221¹(tt, N, XS) → ACTIVATE(XS)
U221¹(tt, N, XS) → ACTIVATE(N)
TAKE(N, XS) → ISNATURAL(N)
U211¹(tt, XS) → ISLNAT(activate(XS))
U211¹(tt, XS) → ACTIVATE(XS)
TAIL(cons(N, XS)) → ISNATURAL(N)
TAIL(cons(N, XS)) → ACTIVATE(XS)
U21¹(tt, X, Y) → ISLNAT(activate(Y))
U21¹(tt, X, Y) → ACTIVATE(Y)
U21¹(tt, X, Y) → ACTIVATE(X)
U181¹(tt, Y) → ISLNAT(activate(Y))
U181¹(tt, Y) → ACTIVATE(Y)
U12¹(tt, N, XS) → SPLITAT(activate(N), activate(XS))
U12¹(tt, N, XS) → ACTIVATE(N)
U12¹(tt, N, XS) → ACTIVATE(XS)
U11¹(tt, N, XS) → ISLNAT(activate(XS))
U11¹(tt, N, XS) → ACTIVATE(XS)
U11¹(tt, N, XS) → ACTIVATE(N)
NATSFROM(N) → ISNATURAL(N)
U41¹(tt, V2) → ACTIVATE(V2)

The TRS R consists of the following rules:

U101(tt, V2) → U102(isLNat(activate(V2)))
U102(tt) → tt
U11(tt, N, XS) → U12(isLNat(activate(XS)), activate(N), activate(XS))
U111(tt) → tt
U12(tt, N, XS) → snd(splitAt(activate(N), activate(XS)))
U121(tt) → tt
U131(tt, V2) → U132(isLNat(activate(V2)))
U132(tt) → tt
U141(tt, V2) → U142(isLNat(activate(V2)))
U142(tt) → tt
U151(tt, V2) → U152(isLNat(activate(V2)))
U152(tt) → tt
U161(tt, N) → cons(activate(N), n__natsFrom(s(activate(N))))
U171(tt, N, XS) → U172(isLNat(activate(XS)), activate(N), activate(XS))
U172(tt, N, XS) → head(afterNth(activate(N), activate(XS)))
U181(tt, Y) → U182(isLNat(activate(Y)), activate(Y))
U182(tt, Y) → activate(Y)
U191(tt, XS) → pair(nil, activate(XS))
U201(tt, N, X, XS) → U202(isNatural(activate(X)), activate(N), activate(X), activate(XS))
U202(tt, N, X, XS) → U203(isLNat(activate(XS)), activate(N), activate(X), activate(XS))
U203(tt, N, X, XS) → U204(splitAt(activate(N), activate(XS)), activate(X))
U204(pair(YS, ZS), X) → pair(cons(activate(X), YS), ZS)
U21(tt, X, Y) → U22(isLNat(activate(Y)), activate(X))
U211(tt, XS) → U212(isLNat(activate(XS)), activate(XS))
U212(tt, XS) → activate(XS)
U22(tt, X) → activate(X)
U221(tt, N, XS) → U222(isLNat(activate(XS)), activate(N), activate(XS))
U222(tt, N, XS) → fst(splitAt(activate(N), activate(XS)))
U31(tt, N, XS) → U32(isLNat(activate(XS)), activate(N))
U32(tt, N) → activate(N)
U41(tt, V2) → U42(isLNat(activate(V2)))
U42(tt) → tt
U51(tt, V2) → U52(isLNat(activate(V2)))
U52(tt) → tt
U61(tt) → tt
U71(tt) → tt
U81(tt) → tt
U91(tt) → tt
afterNth(N, XS) → U11(isNatural(N), N, XS)
fst(pair(X, Y)) → U21(isLNat(X), X, Y)
head(cons(N, XS)) → U31(isNatural(N), N, activate(XS))
isLNat(n__nil) → tt
isLNat(n__afterNth(V1, V2)) → U41(isNatural(activate(V1)), activate(V2))
isLNat(n__cons(V1, V2)) → U51(isNatural(activate(V1)), activate(V2))
isLNat(n__fst(V1)) → U61(isPLNat(activate(V1)))
isLNat(n__natsFrom(V1)) → U71(isNatural(activate(V1)))
isLNat(n__snd(V1)) → U81(isPLNat(activate(V1)))
isLNat(n__tail(V1)) → U91(isLNat(activate(V1)))
isLNat(n__take(V1, V2)) → U101(isNatural(activate(V1)), activate(V2))
isNatural(n__0) → tt
isNatural(n__head(V1)) → U111(isLNat(activate(V1)))
isNatural(n__s(V1)) → U121(isNatural(activate(V1)))
isNatural(n__sel(V1, V2)) → U131(isNatural(activate(V1)), activate(V2))
isPLNat(n__pair(V1, V2)) → U141(isLNat(activate(V1)), activate(V2))
isPLNat(n__splitAt(V1, V2)) → U151(isNatural(activate(V1)), activate(V2))
natsFrom(N) → U161(isNatural(N), N)
sel(N, XS) → U171(isNatural(N), N, XS)
snd(pair(X, Y)) → U181(isLNat(X), Y)
splitAt(0, XS) → U191(isLNat(XS), XS)
splitAt(s(N), cons(X, XS)) → U201(isNatural(N), N, X, activate(XS))
tail(cons(N, XS)) → U211(isNatural(N), activate(XS))
take(N, XS) → U221(isNatural(N), N, XS)
natsFrom(X) → n__natsFrom(X)
nil → n__nil
afterNth(X1, X2) → n__afterNth(X1, X2)
cons(X1, X2) → n__cons(X1, X2)
fst(X) → n__fst(X)
snd(X) → n__snd(X)
tail(X) → n__tail(X)
take(X1, X2) → n__take(X1, X2)
0 → n__0
head(X) → n__head(X)
s(X) → n__s(X)
sel(X1, X2) → n__sel(X1, X2)
pair(X1, X2) → n__pair(X1, X2)
splitAt(X1, X2) → n__splitAt(X1, X2)
activate(n__natsFrom(X)) → natsFrom(X)
activate(n__nil) → nil
activate(n__afterNth(X1, X2)) → afterNth(X1, X2)
activate(n__cons(X1, X2)) → cons(X1, X2)
activate(n__fst(X)) → fst(X)
activate(n__snd(X)) → snd(X)
activate(n__tail(X)) → tail(X)
activate(n__take(X1, X2)) → take(X1, X2)
activate(n__0) → 0
activate(n__head(X)) → head(X)
activate(n__s(X)) → s(X)
activate(n__sel(X1, X2)) → sel(X1, X2)
activate(n__pair(X1, X2)) → pair(X1, X2)
activate(n__splitAt(X1, X2)) → splitAt(X1, X2)
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.