/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished


Termination of the given CSR could be proven:

(0) CSR
(1) CSDependencyPairsProof [EQUIVALENT, 176 ms]
(2) QCSDP
(3) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) QCSDP
        (6) QCSUsableRulesProof [EQUIVALENT, 0 ms]
        (7) QCSDP
        (8) QCSDPMuMonotonicPoloProof [EQUIVALENT, 54 ms]
        (9) QCSDP
        (10) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
        (11) AND
            (12) QCSDP
                (13) QCSDPSubtermProof [EQUIVALENT, 2 ms]
                (14) QCSDP
                (15) PIsEmptyProof [EQUIVALENT, 0 ms]
                (16) YES
            (17) QCSDP
                (18) QCSDPSubtermProof [EQUIVALENT, 0 ms]
                (19) QCSDP
                (20) PIsEmptyProof [EQUIVALENT, 0 ms]
                (21) YES
    (22) QCSDP
        (23) QCSDPSubtermProof [EQUIVALENT, 0 ms]
        (24) QCSDP
        (25) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
        (26) TRUE
    (27) QCSDP
        (28) QCSDPSubtermProof [EQUIVALENT, 0 ms]
        (29) QCSDP
        (30) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
        (31) TRUE


----------------------------------------

(0)
Obligation:
Context-sensitive rewrite system:
The TRS R consists of the following rules:

   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U11(tt, N, XS) -> U12(isLNat(XS), N, XS)
   U111(tt) -> tt
   U12(tt, N, XS) -> snd(splitAt(N, XS))
   U121(tt) -> tt
   U131(tt, V2) -> U132(isLNat(V2))
   U132(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U151(tt, V2) -> U152(isLNat(V2))
   U152(tt) -> tt
   U161(tt, N) -> cons(N, natsFrom(s(N)))
   U171(tt, N, XS) -> U172(isLNat(XS), N, XS)
   U172(tt, N, XS) -> head(afterNth(N, XS))
   U181(tt, Y) -> U182(isLNat(Y), Y)
   U182(tt, Y) -> Y
   U191(tt, XS) -> pair(nil, XS)
   U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS)
   U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS)
   U203(tt, N, X, XS) -> U204(splitAt(N, XS), X)
   U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
   U21(tt, X, Y) -> U22(isLNat(Y), X)
   U211(tt, XS) -> U212(isLNat(XS), XS)
   U212(tt, XS) -> XS
   U22(tt, X) -> X
   U221(tt, N, XS) -> U222(isLNat(XS), N, XS)
   U222(tt, N, XS) -> fst(splitAt(N, XS))
   U31(tt, N, XS) -> U32(isLNat(XS), N)
   U32(tt, N) -> N
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isLNat(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, XS)
   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isNatural(s(V1)) -> U121(isNatural(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), 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, XS)
   tail(cons(N, XS)) -> U211(isNatural(N), XS)
   take(N, XS) -> U221(isNatural(N), N, XS)

The replacement map contains the following entries:

U101: {1}
tt: empty set
U102: {1}
isLNat: empty set
U11: {1}
U12: {1}
U111: {1}
snd: {1}
splitAt: {1, 2}
U121: {1}
U131: {1}
U132: {1}
U141: {1}
U142: {1}
U151: {1}
U152: {1}
U161: {1}
cons: {1}
natsFrom: {1}
s: {1}
U171: {1}
U172: {1}
head: {1}
afterNth: {1, 2}
U181: {1}
U182: {1}
U191: {1}
pair: {1, 2}
nil: empty set
U201: {1}
U202: {1}
isNatural: empty set
U203: {1}
U204: {1}
U21: {1}
U22: {1}
U211: {1}
U212: {1}
U221: {1}
U222: {1}
fst: {1}
U31: {1}
U32: {1}
U41: {1}
U42: {1}
U51: {1}
U52: {1}
U61: {1}
U71: {1}
U81: {1}
U91: {1}
isPLNat: empty set
tail: {1}
take: {1, 2}
0: empty set
sel: {1, 2}

----------------------------------------

(1) CSDependencyPairsProof (EQUIVALENT)
Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
----------------------------------------

(2)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, U102'_1, SND_1, SPLITAT_2, U132'_1, U142'_1, U152'_1, HEAD_1, AFTERNTH_2, FST_1, U42'_1, U52'_1, U61'_1, U71'_1, U81'_1, U91'_1, U111'_1, U121'_1, NATSFROM_1, SEL_2, TAIL_1, TAKE_2} are replacing on all positions.
For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U101'_2, U12'_3, U11'_3, U131'_2, U141'_2, U151'_2, U172'_3, U171'_3, U182'_2, U181'_2, U202'_4, U201'_4, U203'_4, U204'_2, U22'_2, U21'_3, U212'_2, U211'_2, U222'_3, U221'_3, U32'_2, U31'_3, U41'_2, U51'_2, U161'_2, U191'_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, isPLNat_1, ISLNAT_1, ISNATURAL_1, ISPLNAT_1, U_1} are not replacing on any position.

The ordinary context-sensitive dependency pairs DP_o are:
   U101'(tt, V2) -> U102'(isLNat(V2))
   U101'(tt, V2) -> ISLNAT(V2)
   U11'(tt, N, XS) -> U12'(isLNat(XS), N, XS)
   U11'(tt, N, XS) -> ISLNAT(XS)
   U12'(tt, N, XS) -> SND(splitAt(N, XS))
   U12'(tt, N, XS) -> SPLITAT(N, XS)
   U131'(tt, V2) -> U132'(isLNat(V2))
   U131'(tt, V2) -> ISLNAT(V2)
   U141'(tt, V2) -> U142'(isLNat(V2))
   U141'(tt, V2) -> ISLNAT(V2)
   U151'(tt, V2) -> U152'(isLNat(V2))
   U151'(tt, V2) -> ISLNAT(V2)
   U171'(tt, N, XS) -> U172'(isLNat(XS), N, XS)
   U171'(tt, N, XS) -> ISLNAT(XS)
   U172'(tt, N, XS) -> HEAD(afterNth(N, XS))
   U172'(tt, N, XS) -> AFTERNTH(N, XS)
   U181'(tt, Y) -> U182'(isLNat(Y), Y)
   U181'(tt, Y) -> ISLNAT(Y)
   U201'(tt, N, X, XS) -> U202'(isNatural(X), N, X, XS)
   U201'(tt, N, X, XS) -> ISNATURAL(X)
   U202'(tt, N, X, XS) -> U203'(isLNat(XS), N, X, XS)
   U202'(tt, N, X, XS) -> ISLNAT(XS)
   U203'(tt, N, X, XS) -> U204'(splitAt(N, XS), X)
   U203'(tt, N, X, XS) -> SPLITAT(N, XS)
   U21'(tt, X, Y) -> U22'(isLNat(Y), X)
   U21'(tt, X, Y) -> ISLNAT(Y)
   U211'(tt, XS) -> U212'(isLNat(XS), XS)
   U211'(tt, XS) -> ISLNAT(XS)
   U221'(tt, N, XS) -> U222'(isLNat(XS), N, XS)
   U221'(tt, N, XS) -> ISLNAT(XS)
   U222'(tt, N, XS) -> FST(splitAt(N, XS))
   U222'(tt, N, XS) -> SPLITAT(N, XS)
   U31'(tt, N, XS) -> U32'(isLNat(XS), N)
   U31'(tt, N, XS) -> ISLNAT(XS)
   U41'(tt, V2) -> U42'(isLNat(V2))
   U41'(tt, V2) -> ISLNAT(V2)
   U51'(tt, V2) -> U52'(isLNat(V2))
   U51'(tt, V2) -> ISLNAT(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, XS)
   HEAD(cons(N, XS)) -> ISNATURAL(N)
   ISLNAT(afterNth(V1, V2)) -> U41'(isNatural(V1), V2)
   ISLNAT(afterNth(V1, V2)) -> ISNATURAL(V1)
   ISLNAT(cons(V1, V2)) -> U51'(isNatural(V1), V2)
   ISLNAT(cons(V1, V2)) -> ISNATURAL(V1)
   ISLNAT(fst(V1)) -> U61'(isPLNat(V1))
   ISLNAT(fst(V1)) -> ISPLNAT(V1)
   ISLNAT(natsFrom(V1)) -> U71'(isNatural(V1))
   ISLNAT(natsFrom(V1)) -> ISNATURAL(V1)
   ISLNAT(snd(V1)) -> U81'(isPLNat(V1))
   ISLNAT(snd(V1)) -> ISPLNAT(V1)
   ISLNAT(tail(V1)) -> U91'(isLNat(V1))
   ISLNAT(tail(V1)) -> ISLNAT(V1)
   ISLNAT(take(V1, V2)) -> U101'(isNatural(V1), V2)
   ISLNAT(take(V1, V2)) -> ISNATURAL(V1)
   ISNATURAL(head(V1)) -> U111'(isLNat(V1))
   ISNATURAL(head(V1)) -> ISLNAT(V1)
   ISNATURAL(s(V1)) -> U121'(isNatural(V1))
   ISNATURAL(s(V1)) -> ISNATURAL(V1)
   ISNATURAL(sel(V1, V2)) -> U131'(isNatural(V1), V2)
   ISNATURAL(sel(V1, V2)) -> ISNATURAL(V1)
   ISPLNAT(pair(V1, V2)) -> U141'(isLNat(V1), V2)
   ISPLNAT(pair(V1, V2)) -> ISLNAT(V1)
   ISPLNAT(splitAt(V1, V2)) -> U151'(isNatural(V1), V2)
   ISPLNAT(splitAt(V1, V2)) -> ISNATURAL(V1)
   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, XS)
   SPLITAT(s(N), cons(X, XS)) -> ISNATURAL(N)
   TAIL(cons(N, XS)) -> U211'(isNatural(N), XS)
   TAIL(cons(N, XS)) -> ISNATURAL(N)
   TAKE(N, XS) -> U221'(isNatural(N), N, XS)
   TAKE(N, XS) -> ISNATURAL(N)

The collapsing dependency pairs are DP_c:
   U12'(tt, N, XS) -> N
   U12'(tt, N, XS) -> XS
   U161'(tt, N) -> N
   U172'(tt, N, XS) -> N
   U172'(tt, N, XS) -> XS
   U182'(tt, Y) -> Y
   U191'(tt, XS) -> XS
   U203'(tt, N, X, XS) -> N
   U203'(tt, N, X, XS) -> XS
   U204'(pair(YS, ZS), X) -> X
   U212'(tt, XS) -> XS
   U22'(tt, X) -> X
   U222'(tt, N, XS) -> N
   U222'(tt, N, XS) -> XS
   U32'(tt, N) -> N


The hidden terms of R are:

   natsFrom(s(x0))

Every hiding context is built from:
   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@7295e72c
   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@1e4affb

Hence, the new unhiding pairs DP_u are :
   U12'(tt, N, XS) -> U(N)
   U12'(tt, N, XS) -> U(XS)
   U161'(tt, N) -> U(N)
   U172'(tt, N, XS) -> U(N)
   U172'(tt, N, XS) -> U(XS)
   U182'(tt, Y) -> U(Y)
   U191'(tt, XS) -> U(XS)
   U203'(tt, N, X, XS) -> U(N)
   U203'(tt, N, X, XS) -> U(XS)
   U204'(pair(YS, ZS), X) -> U(X)
   U212'(tt, XS) -> U(XS)
   U22'(tt, X) -> U(X)
   U222'(tt, N, XS) -> U(N)
   U222'(tt, N, XS) -> U(XS)
   U32'(tt, N) -> U(N)
   U(s(x_0)) -> U(x_0)
   U(natsFrom(x_0)) -> U(x_0)
   U(natsFrom(s(x0))) -> NATSFROM(s(x0))

The TRS R consists of the following rules:

   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U11(tt, N, XS) -> U12(isLNat(XS), N, XS)
   U111(tt) -> tt
   U12(tt, N, XS) -> snd(splitAt(N, XS))
   U121(tt) -> tt
   U131(tt, V2) -> U132(isLNat(V2))
   U132(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U151(tt, V2) -> U152(isLNat(V2))
   U152(tt) -> tt
   U161(tt, N) -> cons(N, natsFrom(s(N)))
   U171(tt, N, XS) -> U172(isLNat(XS), N, XS)
   U172(tt, N, XS) -> head(afterNth(N, XS))
   U181(tt, Y) -> U182(isLNat(Y), Y)
   U182(tt, Y) -> Y
   U191(tt, XS) -> pair(nil, XS)
   U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS)
   U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS)
   U203(tt, N, X, XS) -> U204(splitAt(N, XS), X)
   U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
   U21(tt, X, Y) -> U22(isLNat(Y), X)
   U211(tt, XS) -> U212(isLNat(XS), XS)
   U212(tt, XS) -> XS
   U22(tt, X) -> X
   U221(tt, N, XS) -> U222(isLNat(XS), N, XS)
   U222(tt, N, XS) -> fst(splitAt(N, XS))
   U31(tt, N, XS) -> U32(isLNat(XS), N)
   U32(tt, N) -> N
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isLNat(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, XS)
   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isNatural(s(V1)) -> U121(isNatural(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), 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, XS)
   tail(cons(N, XS)) -> U211(isNatural(N), XS)
   take(N, XS) -> U221(isNatural(N), N, XS)

Q is empty.

----------------------------------------

(3) QCSDependencyGraphProof (EQUIVALENT)
The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 3 SCCs with 67 less nodes.

----------------------------------------

(4)
Complex Obligation (AND)

----------------------------------------

(5)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2} are replacing on all positions.
For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U41'_2, U51'_2, U131'_2, U141'_2, U101'_2, U151'_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, isPLNat_1, ISLNAT_1, ISNATURAL_1, ISPLNAT_1} are not replacing on any position.

The TRS P consists of the following rules:

   ISLNAT(afterNth(V1, V2)) -> U41'(isNatural(V1), V2)
   U41'(tt, V2) -> ISLNAT(V2)
   ISLNAT(afterNth(V1, V2)) -> ISNATURAL(V1)
   ISNATURAL(head(V1)) -> ISLNAT(V1)
   ISLNAT(cons(V1, V2)) -> U51'(isNatural(V1), V2)
   U51'(tt, V2) -> ISLNAT(V2)
   ISLNAT(cons(V1, V2)) -> ISNATURAL(V1)
   ISNATURAL(s(V1)) -> ISNATURAL(V1)
   ISNATURAL(sel(V1, V2)) -> U131'(isNatural(V1), V2)
   U131'(tt, V2) -> ISLNAT(V2)
   ISLNAT(fst(V1)) -> ISPLNAT(V1)
   ISPLNAT(pair(V1, V2)) -> U141'(isLNat(V1), V2)
   U141'(tt, V2) -> ISLNAT(V2)
   ISLNAT(natsFrom(V1)) -> ISNATURAL(V1)
   ISNATURAL(sel(V1, V2)) -> ISNATURAL(V1)
   ISLNAT(snd(V1)) -> ISPLNAT(V1)
   ISPLNAT(pair(V1, V2)) -> ISLNAT(V1)
   ISLNAT(tail(V1)) -> ISLNAT(V1)
   ISLNAT(take(V1, V2)) -> U101'(isNatural(V1), V2)
   U101'(tt, V2) -> ISLNAT(V2)
   ISLNAT(take(V1, V2)) -> ISNATURAL(V1)
   ISPLNAT(splitAt(V1, V2)) -> U151'(isNatural(V1), V2)
   U151'(tt, V2) -> ISLNAT(V2)
   ISPLNAT(splitAt(V1, V2)) -> ISNATURAL(V1)

The TRS R consists of the following rules:

   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U11(tt, N, XS) -> U12(isLNat(XS), N, XS)
   U111(tt) -> tt
   U12(tt, N, XS) -> snd(splitAt(N, XS))
   U121(tt) -> tt
   U131(tt, V2) -> U132(isLNat(V2))
   U132(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U151(tt, V2) -> U152(isLNat(V2))
   U152(tt) -> tt
   U161(tt, N) -> cons(N, natsFrom(s(N)))
   U171(tt, N, XS) -> U172(isLNat(XS), N, XS)
   U172(tt, N, XS) -> head(afterNth(N, XS))
   U181(tt, Y) -> U182(isLNat(Y), Y)
   U182(tt, Y) -> Y
   U191(tt, XS) -> pair(nil, XS)
   U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS)
   U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS)
   U203(tt, N, X, XS) -> U204(splitAt(N, XS), X)
   U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
   U21(tt, X, Y) -> U22(isLNat(Y), X)
   U211(tt, XS) -> U212(isLNat(XS), XS)
   U212(tt, XS) -> XS
   U22(tt, X) -> X
   U221(tt, N, XS) -> U222(isLNat(XS), N, XS)
   U222(tt, N, XS) -> fst(splitAt(N, XS))
   U31(tt, N, XS) -> U32(isLNat(XS), N)
   U32(tt, N) -> N
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isLNat(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, XS)
   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isNatural(s(V1)) -> U121(isNatural(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), 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, XS)
   tail(cons(N, XS)) -> U211(isNatural(N), XS)
   take(N, XS) -> U221(isNatural(N), N, XS)

Q is empty.

----------------------------------------

(6) QCSUsableRulesProof (EQUIVALENT)
The following rules are not useable [DA_EMMES] and can be deleted:

   U11(tt, x0, x1) -> U12(isLNat(x1), x0, x1)
   U12(tt, x0, x1) -> snd(splitAt(x0, x1))
   U161(tt, x0) -> cons(x0, natsFrom(s(x0)))
   U171(tt, x0, x1) -> U172(isLNat(x1), x0, x1)
   U172(tt, x0, x1) -> head(afterNth(x0, x1))
   U181(tt, x0) -> U182(isLNat(x0), x0)
   U182(tt, x0) -> x0
   U191(tt, x0) -> pair(nil, x0)
   U201(tt, x0, x1, x2) -> U202(isNatural(x1), x0, x1, x2)
   U202(tt, x0, x1, x2) -> U203(isLNat(x2), x0, x1, x2)
   U203(tt, x0, x1, x2) -> U204(splitAt(x0, x2), x1)
   U204(pair(x0, x1), x2) -> pair(cons(x2, x0), x1)
   U21(tt, x0, x1) -> U22(isLNat(x1), x0)
   U211(tt, x0) -> U212(isLNat(x0), x0)
   U212(tt, x0) -> x0
   U22(tt, x0) -> x0
   U221(tt, x0, x1) -> U222(isLNat(x1), x0, x1)
   U222(tt, x0, x1) -> fst(splitAt(x0, x1))
   U31(tt, x0, x1) -> U32(isLNat(x1), x0)
   U32(tt, x0) -> x0
   afterNth(x0, x1) -> U11(isNatural(x0), x0, x1)
   fst(pair(x0, x1)) -> U21(isLNat(x0), x0, x1)
   head(cons(x0, x1)) -> U31(isNatural(x0), x0, x1)
   natsFrom(x0) -> U161(isNatural(x0), x0)
   sel(x0, x1) -> U171(isNatural(x0), x0, x1)
   snd(pair(x0, x1)) -> U181(isLNat(x0), x1)
   splitAt(0, x0) -> U191(isLNat(x0), x0)
   splitAt(s(x0), cons(x1, x2)) -> U201(isNatural(x0), x0, x1, x2)
   tail(cons(x0, x1)) -> U211(isNatural(x0), x1)
   take(x0, x1) -> U221(isNatural(x0), x0, x1)

----------------------------------------

(7)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {head_1, U111_1, afterNth_2, s_1, U121_1, sel_2, U132_1, U52_1, fst_1, U61_1, pair_2, natsFrom_1, U71_1, snd_1, U81_1, splitAt_2, U152_1, tail_1, U91_1, take_2, U102_1, U142_1, U42_1} are replacing on all positions.
For all symbols f in {U41_2, U131_2, cons_2, U51_2, U141_2, U151_2, U101_2, U41'_2, U51'_2, U131'_2, U141'_2, U101'_2, U151'_2} we have mu(f) = {1}.
The symbols in {isNatural_1, isLNat_1, isPLNat_1, ISLNAT_1, ISNATURAL_1, ISPLNAT_1} are not replacing on any position.

The TRS P consists of the following rules:

   ISLNAT(afterNth(V1, V2)) -> U41'(isNatural(V1), V2)
   U41'(tt, V2) -> ISLNAT(V2)
   ISLNAT(afterNth(V1, V2)) -> ISNATURAL(V1)
   ISNATURAL(head(V1)) -> ISLNAT(V1)
   ISLNAT(cons(V1, V2)) -> U51'(isNatural(V1), V2)
   U51'(tt, V2) -> ISLNAT(V2)
   ISLNAT(cons(V1, V2)) -> ISNATURAL(V1)
   ISNATURAL(s(V1)) -> ISNATURAL(V1)
   ISNATURAL(sel(V1, V2)) -> U131'(isNatural(V1), V2)
   U131'(tt, V2) -> ISLNAT(V2)
   ISLNAT(fst(V1)) -> ISPLNAT(V1)
   ISPLNAT(pair(V1, V2)) -> U141'(isLNat(V1), V2)
   U141'(tt, V2) -> ISLNAT(V2)
   ISLNAT(natsFrom(V1)) -> ISNATURAL(V1)
   ISNATURAL(sel(V1, V2)) -> ISNATURAL(V1)
   ISLNAT(snd(V1)) -> ISPLNAT(V1)
   ISPLNAT(pair(V1, V2)) -> ISLNAT(V1)
   ISLNAT(tail(V1)) -> ISLNAT(V1)
   ISLNAT(take(V1, V2)) -> U101'(isNatural(V1), V2)
   U101'(tt, V2) -> ISLNAT(V2)
   ISLNAT(take(V1, V2)) -> ISNATURAL(V1)
   ISPLNAT(splitAt(V1, V2)) -> U151'(isNatural(V1), V2)
   U151'(tt, V2) -> ISLNAT(V2)
   ISPLNAT(splitAt(V1, V2)) -> ISNATURAL(V1)

The TRS R consists of the following rules:

   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isNatural(s(V1)) -> U121(isNatural(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   U131(tt, V2) -> U132(isLNat(V2))
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   U51(tt, V2) -> U52(isLNat(V2))
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   U71(tt) -> tt
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2)
   U151(tt, V2) -> U152(isLNat(V2))
   isLNat(tail(V1)) -> U91(isLNat(V1))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U91(tt) -> tt
   U152(tt) -> tt
   U81(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U61(tt) -> tt
   U52(tt) -> tt
   U132(tt) -> tt
   U121(tt) -> tt
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U111(tt) -> tt

Q is empty.

----------------------------------------

(8) QCSDPMuMonotonicPoloProof (EQUIVALENT)
By using the following mu-monotonic polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this Q-CSDP problem can be strictly oriented and thus deleted.

Strictly oriented dependency pairs:

   ISLNAT(afterNth(V1, V2)) -> U41'(isNatural(V1), V2)
   U41'(tt, V2) -> ISLNAT(V2)
   ISLNAT(afterNth(V1, V2)) -> ISNATURAL(V1)
   ISNATURAL(head(V1)) -> ISLNAT(V1)
   ISLNAT(cons(V1, V2)) -> U51'(isNatural(V1), V2)
   U51'(tt, V2) -> ISLNAT(V2)
   ISLNAT(cons(V1, V2)) -> ISNATURAL(V1)
   ISNATURAL(sel(V1, V2)) -> U131'(isNatural(V1), V2)
   U131'(tt, V2) -> ISLNAT(V2)
   ISLNAT(fst(V1)) -> ISPLNAT(V1)
   ISPLNAT(pair(V1, V2)) -> U141'(isLNat(V1), V2)
   U141'(tt, V2) -> ISLNAT(V2)
   ISLNAT(natsFrom(V1)) -> ISNATURAL(V1)
   ISNATURAL(sel(V1, V2)) -> ISNATURAL(V1)
   ISLNAT(snd(V1)) -> ISPLNAT(V1)
   ISPLNAT(pair(V1, V2)) -> ISLNAT(V1)
   ISLNAT(take(V1, V2)) -> U101'(isNatural(V1), V2)
   U101'(tt, V2) -> ISLNAT(V2)
   ISLNAT(take(V1, V2)) -> ISNATURAL(V1)
   ISPLNAT(splitAt(V1, V2)) -> U151'(isNatural(V1), V2)
   U151'(tt, V2) -> ISLNAT(V2)
   ISPLNAT(splitAt(V1, V2)) -> ISNATURAL(V1)

Strictly oriented rules of the TRS R:

   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   U131(tt, V2) -> U132(isLNat(V2))
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   U51(tt, V2) -> U52(isLNat(V2))
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   U71(tt) -> tt
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2)
   U151(tt, V2) -> U152(isLNat(V2))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U91(tt) -> tt
   U152(tt) -> tt
   U81(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U61(tt) -> tt
   U52(tt) -> tt
   U132(tt) -> tt
   U121(tt) -> tt
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U111(tt) -> tt

Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 2
   POL(ISLNAT(x_1)) = 1 + 2*x_1
   POL(ISNATURAL(x_1)) = 2 + 2*x_1
   POL(ISPLNAT(x_1)) = 1 + 2*x_1
   POL(U101(x_1, x_2)) = x_1 + 2*x_2
   POL(U101'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(U102(x_1)) = 1 + 2*x_1
   POL(U111(x_1)) = 1 + 2*x_1
   POL(U121(x_1)) = 2*x_1
   POL(U131(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(U131'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(U132(x_1)) = 2*x_1
   POL(U141(x_1, x_2)) = x_1 + 2*x_2
   POL(U141'(x_1, x_2)) = x_1 + 2*x_2
   POL(U142(x_1)) = 1 + 2*x_1
   POL(U151(x_1, x_2)) = x_1 + 2*x_2
   POL(U151'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(U152(x_1)) = 1 + 2*x_1
   POL(U41(x_1, x_2)) = 2 + x_1 + 2*x_2
   POL(U41'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(U42(x_1)) = 1 + 2*x_1
   POL(U51(x_1, x_2)) = x_1 + 2*x_2
   POL(U51'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(U52(x_1)) = 1 + 2*x_1
   POL(U61(x_1)) = 1 + 2*x_1
   POL(U71(x_1)) = 1 + x_1
   POL(U81(x_1)) = 1 + 2*x_1
   POL(U91(x_1)) = 2*x_1
   POL(afterNth(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(cons(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(fst(x_1)) = 2 + 2*x_1
   POL(head(x_1)) = 2 + 2*x_1
   POL(isLNat(x_1)) = x_1
   POL(isNatural(x_1)) = 2*x_1
   POL(isPLNat(x_1)) = x_1
   POL(natsFrom(x_1)) = 2 + 2*x_1
   POL(nil) = 2
   POL(pair(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(s(x_1)) = 2*x_1
   POL(sel(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(snd(x_1)) = 2 + 2*x_1
   POL(splitAt(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(tail(x_1)) = 2*x_1
   POL(take(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(tt) = 2


----------------------------------------

(9)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions.
For all symbols f in {U41_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, ISNATURAL_1, ISLNAT_1} are not replacing on any position.

The TRS P consists of the following rules:

   ISNATURAL(s(V1)) -> ISNATURAL(V1)
   ISLNAT(tail(V1)) -> ISLNAT(V1)

The TRS R consists of the following rules:

   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isNatural(s(V1)) -> U121(isNatural(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))

Q is empty.

----------------------------------------

(10) QCSDependencyGraphProof (EQUIVALENT)
The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 2 SCCs.

----------------------------------------

(11)
Complex Obligation (AND)

----------------------------------------

(12)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions.
For all symbols f in {U41_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, ISLNAT_1} are not replacing on any position.

The TRS P consists of the following rules:

   ISLNAT(tail(V1)) -> ISLNAT(V1)

The TRS R consists of the following rules:

   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isNatural(s(V1)) -> U121(isNatural(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))

Q is empty.

----------------------------------------

(13) QCSDPSubtermProof (EQUIVALENT)
We use the subterm processor [DA_EMMES].


The following pairs can be oriented strictly and are deleted.

   ISLNAT(tail(V1)) -> ISLNAT(V1)
The remaining pairs can at least be oriented weakly.
none
Used ordering:  Combined order from the following AFS and order.
ISLNAT(x1)  =  x1


Subterm Order

----------------------------------------

(14)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions.
For all symbols f in {U41_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1} are not replacing on any position.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isNatural(s(V1)) -> U121(isNatural(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))

Q is empty.

----------------------------------------

(15) PIsEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
----------------------------------------

(16)
YES

----------------------------------------

(17)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions.
For all symbols f in {U41_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, ISNATURAL_1} are not replacing on any position.

The TRS P consists of the following rules:

   ISNATURAL(s(V1)) -> ISNATURAL(V1)

The TRS R consists of the following rules:

   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isNatural(s(V1)) -> U121(isNatural(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))

Q is empty.

----------------------------------------

(18) QCSDPSubtermProof (EQUIVALENT)
We use the subterm processor [DA_EMMES].


The following pairs can be oriented strictly and are deleted.

   ISNATURAL(s(V1)) -> ISNATURAL(V1)
The remaining pairs can at least be oriented weakly.
none
Used ordering:  Combined order from the following AFS and order.
ISNATURAL(x1)  =  x1


Subterm Order

----------------------------------------

(19)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions.
For all symbols f in {U41_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1} are not replacing on any position.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isNatural(s(V1)) -> U121(isNatural(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))

Q is empty.

----------------------------------------

(20) PIsEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
----------------------------------------

(21)
YES

----------------------------------------

(22)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, NATSFROM_1} are replacing on all positions.
For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U161'_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, isPLNat_1, U_1} are not replacing on any position.

The TRS P consists of the following rules:

   NATSFROM(N) -> U161'(isNatural(N), N)
   U161'(tt, N) -> U(N)
   U(s(x_0)) -> U(x_0)
   U(natsFrom(x_0)) -> U(x_0)
   U(natsFrom(s(x0))) -> NATSFROM(s(x0))

The TRS R consists of the following rules:

   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U11(tt, N, XS) -> U12(isLNat(XS), N, XS)
   U111(tt) -> tt
   U12(tt, N, XS) -> snd(splitAt(N, XS))
   U121(tt) -> tt
   U131(tt, V2) -> U132(isLNat(V2))
   U132(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U151(tt, V2) -> U152(isLNat(V2))
   U152(tt) -> tt
   U161(tt, N) -> cons(N, natsFrom(s(N)))
   U171(tt, N, XS) -> U172(isLNat(XS), N, XS)
   U172(tt, N, XS) -> head(afterNth(N, XS))
   U181(tt, Y) -> U182(isLNat(Y), Y)
   U182(tt, Y) -> Y
   U191(tt, XS) -> pair(nil, XS)
   U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS)
   U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS)
   U203(tt, N, X, XS) -> U204(splitAt(N, XS), X)
   U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
   U21(tt, X, Y) -> U22(isLNat(Y), X)
   U211(tt, XS) -> U212(isLNat(XS), XS)
   U212(tt, XS) -> XS
   U22(tt, X) -> X
   U221(tt, N, XS) -> U222(isLNat(XS), N, XS)
   U222(tt, N, XS) -> fst(splitAt(N, XS))
   U31(tt, N, XS) -> U32(isLNat(XS), N)
   U32(tt, N) -> N
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isLNat(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, XS)
   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isNatural(s(V1)) -> U121(isNatural(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), 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, XS)
   tail(cons(N, XS)) -> U211(isNatural(N), XS)
   take(N, XS) -> U221(isNatural(N), N, XS)

Q is empty.

----------------------------------------

(23) QCSDPSubtermProof (EQUIVALENT)
We use the subterm processor [DA_EMMES].


The following pairs can be oriented strictly and are deleted.

   U(s(x_0)) -> U(x_0)
   U(natsFrom(x_0)) -> U(x_0)
   U(natsFrom(s(x0))) -> NATSFROM(s(x0))
The remaining pairs can at least be oriented weakly.

   NATSFROM(N) -> U161'(isNatural(N), N)
   U161'(tt, N) -> U(N)
Used ordering:  Combined order from the following AFS and order.
U161'(x1, x2)  =  x2

NATSFROM(x1)  =  x1

U(x1)  =  x1


Subterm Order

----------------------------------------

(24)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, NATSFROM_1} are replacing on all positions.
For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U161'_2} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, isPLNat_1, U_1} are not replacing on any position.

The TRS P consists of the following rules:

   NATSFROM(N) -> U161'(isNatural(N), N)
   U161'(tt, N) -> U(N)

The TRS R consists of the following rules:

   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U11(tt, N, XS) -> U12(isLNat(XS), N, XS)
   U111(tt) -> tt
   U12(tt, N, XS) -> snd(splitAt(N, XS))
   U121(tt) -> tt
   U131(tt, V2) -> U132(isLNat(V2))
   U132(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U151(tt, V2) -> U152(isLNat(V2))
   U152(tt) -> tt
   U161(tt, N) -> cons(N, natsFrom(s(N)))
   U171(tt, N, XS) -> U172(isLNat(XS), N, XS)
   U172(tt, N, XS) -> head(afterNth(N, XS))
   U181(tt, Y) -> U182(isLNat(Y), Y)
   U182(tt, Y) -> Y
   U191(tt, XS) -> pair(nil, XS)
   U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS)
   U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS)
   U203(tt, N, X, XS) -> U204(splitAt(N, XS), X)
   U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
   U21(tt, X, Y) -> U22(isLNat(Y), X)
   U211(tt, XS) -> U212(isLNat(XS), XS)
   U212(tt, XS) -> XS
   U22(tt, X) -> X
   U221(tt, N, XS) -> U222(isLNat(XS), N, XS)
   U222(tt, N, XS) -> fst(splitAt(N, XS))
   U31(tt, N, XS) -> U32(isLNat(XS), N)
   U32(tt, N) -> N
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isLNat(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, XS)
   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isNatural(s(V1)) -> U121(isNatural(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), 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, XS)
   tail(cons(N, XS)) -> U211(isNatural(N), XS)
   take(N, XS) -> U221(isNatural(N), N, XS)

Q is empty.

----------------------------------------

(25) QCSDependencyGraphProof (EQUIVALENT)
The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes.

----------------------------------------

(26)
TRUE

----------------------------------------

(27)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, SPLITAT_2} are replacing on all positions.
For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U202'_4, U201'_4, U203'_4} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, isPLNat_1} are not replacing on any position.

The TRS P consists of the following rules:

   U201'(tt, N, X, XS) -> U202'(isNatural(X), N, X, XS)
   U202'(tt, N, X, XS) -> U203'(isLNat(XS), N, X, XS)
   U203'(tt, N, X, XS) -> SPLITAT(N, XS)
   SPLITAT(s(N), cons(X, XS)) -> U201'(isNatural(N), N, X, XS)

The TRS R consists of the following rules:

   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U11(tt, N, XS) -> U12(isLNat(XS), N, XS)
   U111(tt) -> tt
   U12(tt, N, XS) -> snd(splitAt(N, XS))
   U121(tt) -> tt
   U131(tt, V2) -> U132(isLNat(V2))
   U132(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U151(tt, V2) -> U152(isLNat(V2))
   U152(tt) -> tt
   U161(tt, N) -> cons(N, natsFrom(s(N)))
   U171(tt, N, XS) -> U172(isLNat(XS), N, XS)
   U172(tt, N, XS) -> head(afterNth(N, XS))
   U181(tt, Y) -> U182(isLNat(Y), Y)
   U182(tt, Y) -> Y
   U191(tt, XS) -> pair(nil, XS)
   U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS)
   U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS)
   U203(tt, N, X, XS) -> U204(splitAt(N, XS), X)
   U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
   U21(tt, X, Y) -> U22(isLNat(Y), X)
   U211(tt, XS) -> U212(isLNat(XS), XS)
   U212(tt, XS) -> XS
   U22(tt, X) -> X
   U221(tt, N, XS) -> U222(isLNat(XS), N, XS)
   U222(tt, N, XS) -> fst(splitAt(N, XS))
   U31(tt, N, XS) -> U32(isLNat(XS), N)
   U32(tt, N) -> N
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isLNat(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, XS)
   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isNatural(s(V1)) -> U121(isNatural(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), 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, XS)
   tail(cons(N, XS)) -> U211(isNatural(N), XS)
   take(N, XS) -> U221(isNatural(N), N, XS)

Q is empty.

----------------------------------------

(28) QCSDPSubtermProof (EQUIVALENT)
We use the subterm processor [DA_EMMES].


The following pairs can be oriented strictly and are deleted.

   SPLITAT(s(N), cons(X, XS)) -> U201'(isNatural(N), N, X, XS)
The remaining pairs can at least be oriented weakly.

   U201'(tt, N, X, XS) -> U202'(isNatural(X), N, X, XS)
   U202'(tt, N, X, XS) -> U203'(isLNat(XS), N, X, XS)
   U203'(tt, N, X, XS) -> SPLITAT(N, XS)
Used ordering:  Combined order from the following AFS and order.
U202'(x1, x2, x3, x4)  =  x2

U201'(x1, x2, x3, x4)  =  x2

U203'(x1, x2, x3, x4)  =  x2

SPLITAT(x1, x2)  =  x1


Subterm Order

----------------------------------------

(29)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, SPLITAT_2} are replacing on all positions.
For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U202'_4, U201'_4, U203'_4} we have mu(f) = {1}.
The symbols in {isLNat_1, isNatural_1, isPLNat_1} are not replacing on any position.

The TRS P consists of the following rules:

   U201'(tt, N, X, XS) -> U202'(isNatural(X), N, X, XS)
   U202'(tt, N, X, XS) -> U203'(isLNat(XS), N, X, XS)
   U203'(tt, N, X, XS) -> SPLITAT(N, XS)

The TRS R consists of the following rules:

   U101(tt, V2) -> U102(isLNat(V2))
   U102(tt) -> tt
   U11(tt, N, XS) -> U12(isLNat(XS), N, XS)
   U111(tt) -> tt
   U12(tt, N, XS) -> snd(splitAt(N, XS))
   U121(tt) -> tt
   U131(tt, V2) -> U132(isLNat(V2))
   U132(tt) -> tt
   U141(tt, V2) -> U142(isLNat(V2))
   U142(tt) -> tt
   U151(tt, V2) -> U152(isLNat(V2))
   U152(tt) -> tt
   U161(tt, N) -> cons(N, natsFrom(s(N)))
   U171(tt, N, XS) -> U172(isLNat(XS), N, XS)
   U172(tt, N, XS) -> head(afterNth(N, XS))
   U181(tt, Y) -> U182(isLNat(Y), Y)
   U182(tt, Y) -> Y
   U191(tt, XS) -> pair(nil, XS)
   U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS)
   U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS)
   U203(tt, N, X, XS) -> U204(splitAt(N, XS), X)
   U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS)
   U21(tt, X, Y) -> U22(isLNat(Y), X)
   U211(tt, XS) -> U212(isLNat(XS), XS)
   U212(tt, XS) -> XS
   U22(tt, X) -> X
   U221(tt, N, XS) -> U222(isLNat(XS), N, XS)
   U222(tt, N, XS) -> fst(splitAt(N, XS))
   U31(tt, N, XS) -> U32(isLNat(XS), N)
   U32(tt, N) -> N
   U41(tt, V2) -> U42(isLNat(V2))
   U42(tt) -> tt
   U51(tt, V2) -> U52(isLNat(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, XS)
   isLNat(nil) -> tt
   isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2)
   isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2)
   isLNat(fst(V1)) -> U61(isPLNat(V1))
   isLNat(natsFrom(V1)) -> U71(isNatural(V1))
   isLNat(snd(V1)) -> U81(isPLNat(V1))
   isLNat(tail(V1)) -> U91(isLNat(V1))
   isLNat(take(V1, V2)) -> U101(isNatural(V1), V2)
   isNatural(0) -> tt
   isNatural(head(V1)) -> U111(isLNat(V1))
   isNatural(s(V1)) -> U121(isNatural(V1))
   isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2)
   isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2)
   isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), 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, XS)
   tail(cons(N, XS)) -> U211(isNatural(N), XS)
   take(N, XS) -> U221(isNatural(N), N, XS)

Q is empty.

----------------------------------------

(30) QCSDependencyGraphProof (EQUIVALENT)
The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 3 less nodes.

----------------------------------------

(31)
TRUE