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


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


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


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

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


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

(0)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

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

Q is empty.

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

(1) QTRSToCSRProof (EQUIVALENT)
The following Q TRS is given: Q restricted rewrite system:
The TRS R consists of the following rules:

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

Q is empty.
Special symbols used for the transformation (see [GM04]):
top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1
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}
The QTRS contained all rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is complete (and sound).
----------------------------------------

(2)
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}

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

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

(4)
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@34ce9c0b
   aprove.DPFramework.CSDPProblem.QCSDPProblem$1@2437372e

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.

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

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

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

(6)
Complex Obligation (AND)

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

(7)
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.

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

(8) 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)

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

(9)
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.

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

(10) 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


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

(11)
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.

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

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

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

(13)
Complex Obligation (AND)

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

(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, 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.

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

(15) 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

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

(16)
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.

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

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

(18)
YES

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

(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, 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.

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

(20) 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

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

(21)
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.

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

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

(23)
YES

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

(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)
   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.

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

(25) 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

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

(26)
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.

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

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

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

(28)
TRUE

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

(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)
   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.

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

(30) 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

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

(31)
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.

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

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

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

(33)
TRUE