/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: 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, 56 ms]
(4) QCSDP
(5) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) QCSDP
        (8) QCSDPSubtermProof [EQUIVALENT, 0 ms]
        (9) QCSDP
        (10) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
        (11) TRUE
    (12) QCSDP
        (13) QCSUsableRulesProof [EQUIVALENT, 0 ms]
        (14) QCSDP
        (15) QCSDPMuMonotonicPoloProof [EQUIVALENT, 61 ms]
        (16) QCSDP
        (17) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
        (18) TRUE
    (19) QCSDP
        (20) QCSDPSubtermProof [EQUIVALENT, 0 ms]
        (21) QCSDP
        (22) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
        (23) TRUE
    (24) QCSDP
        (25) QCSDPSubtermProof [EQUIVALENT, 0 ms]
        (26) QCSDP
        (27) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
        (28) TRUE


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

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

   active(U101(tt, M, N)) -> mark(U102(isNatKind(M), M, N))
   active(U102(tt, M, N)) -> mark(U103(isNat(N), M, N))
   active(U103(tt, M, N)) -> mark(U104(isNatKind(N), M, N))
   active(U104(tt, M, N)) -> mark(plus(x(N, M), N))
   active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2))
   active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2))
   active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2))
   active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2))
   active(U15(tt, V2)) -> mark(U16(isNat(V2)))
   active(U16(tt)) -> mark(tt)
   active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1))
   active(U22(tt, V1)) -> mark(U23(isNat(V1)))
   active(U23(tt)) -> mark(tt)
   active(U31(tt, V1, V2)) -> mark(U32(isNatKind(V1), V1, V2))
   active(U32(tt, V1, V2)) -> mark(U33(isNatKind(V2), V1, V2))
   active(U33(tt, V1, V2)) -> mark(U34(isNatKind(V2), V1, V2))
   active(U34(tt, V1, V2)) -> mark(U35(isNat(V1), V2))
   active(U35(tt, V2)) -> mark(U36(isNat(V2)))
   active(U36(tt)) -> mark(tt)
   active(U41(tt, V2)) -> mark(U42(isNatKind(V2)))
   active(U42(tt)) -> mark(tt)
   active(U51(tt)) -> mark(tt)
   active(U61(tt, V2)) -> mark(U62(isNatKind(V2)))
   active(U62(tt)) -> mark(tt)
   active(U71(tt, N)) -> mark(U72(isNatKind(N), N))
   active(U72(tt, N)) -> mark(N)
   active(U81(tt, M, N)) -> mark(U82(isNatKind(M), M, N))
   active(U82(tt, M, N)) -> mark(U83(isNat(N), M, N))
   active(U83(tt, M, N)) -> mark(U84(isNatKind(N), M, N))
   active(U84(tt, M, N)) -> mark(s(plus(N, M)))
   active(U91(tt, N)) -> mark(U92(isNatKind(N)))
   active(U92(tt)) -> mark(0)
   active(isNat(0)) -> mark(tt)
   active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2))
   active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1))
   active(isNat(x(V1, V2))) -> mark(U31(isNatKind(V1), V1, V2))
   active(isNatKind(0)) -> mark(tt)
   active(isNatKind(plus(V1, V2))) -> mark(U41(isNatKind(V1), V2))
   active(isNatKind(s(V1))) -> mark(U51(isNatKind(V1)))
   active(isNatKind(x(V1, V2))) -> mark(U61(isNatKind(V1), V2))
   active(plus(N, 0)) -> mark(U71(isNat(N), N))
   active(plus(N, s(M))) -> mark(U81(isNat(M), M, N))
   active(x(N, 0)) -> mark(U91(isNat(N), N))
   active(x(N, s(M))) -> mark(U101(isNat(M), M, N))
   active(U101(X1, X2, X3)) -> U101(active(X1), X2, X3)
   active(U102(X1, X2, X3)) -> U102(active(X1), X2, X3)
   active(U103(X1, X2, X3)) -> U103(active(X1), X2, X3)
   active(U104(X1, X2, X3)) -> U104(active(X1), X2, X3)
   active(plus(X1, X2)) -> plus(active(X1), X2)
   active(plus(X1, X2)) -> plus(X1, active(X2))
   active(x(X1, X2)) -> x(active(X1), X2)
   active(x(X1, X2)) -> x(X1, active(X2))
   active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3)
   active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3)
   active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3)
   active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3)
   active(U15(X1, X2)) -> U15(active(X1), X2)
   active(U16(X)) -> U16(active(X))
   active(U21(X1, X2)) -> U21(active(X1), X2)
   active(U22(X1, X2)) -> U22(active(X1), X2)
   active(U23(X)) -> U23(active(X))
   active(U31(X1, X2, X3)) -> U31(active(X1), X2, X3)
   active(U32(X1, X2, X3)) -> U32(active(X1), X2, X3)
   active(U33(X1, X2, X3)) -> U33(active(X1), X2, X3)
   active(U34(X1, X2, X3)) -> U34(active(X1), X2, X3)
   active(U35(X1, X2)) -> U35(active(X1), X2)
   active(U36(X)) -> U36(active(X))
   active(U41(X1, X2)) -> U41(active(X1), X2)
   active(U42(X)) -> U42(active(X))
   active(U51(X)) -> U51(active(X))
   active(U61(X1, X2)) -> U61(active(X1), X2)
   active(U62(X)) -> U62(active(X))
   active(U71(X1, X2)) -> U71(active(X1), X2)
   active(U72(X1, X2)) -> U72(active(X1), X2)
   active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3)
   active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3)
   active(U83(X1, X2, X3)) -> U83(active(X1), X2, X3)
   active(U84(X1, X2, X3)) -> U84(active(X1), X2, X3)
   active(s(X)) -> s(active(X))
   active(U91(X1, X2)) -> U91(active(X1), X2)
   active(U92(X)) -> U92(active(X))
   U101(mark(X1), X2, X3) -> mark(U101(X1, X2, X3))
   U102(mark(X1), X2, X3) -> mark(U102(X1, X2, X3))
   U103(mark(X1), X2, X3) -> mark(U103(X1, X2, X3))
   U104(mark(X1), X2, X3) -> mark(U104(X1, X2, X3))
   plus(mark(X1), X2) -> mark(plus(X1, X2))
   plus(X1, mark(X2)) -> mark(plus(X1, X2))
   x(mark(X1), X2) -> mark(x(X1, X2))
   x(X1, mark(X2)) -> mark(x(X1, X2))
   U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3))
   U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3))
   U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3))
   U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3))
   U15(mark(X1), X2) -> mark(U15(X1, X2))
   U16(mark(X)) -> mark(U16(X))
   U21(mark(X1), X2) -> mark(U21(X1, X2))
   U22(mark(X1), X2) -> mark(U22(X1, X2))
   U23(mark(X)) -> mark(U23(X))
   U31(mark(X1), X2, X3) -> mark(U31(X1, X2, X3))
   U32(mark(X1), X2, X3) -> mark(U32(X1, X2, X3))
   U33(mark(X1), X2, X3) -> mark(U33(X1, X2, X3))
   U34(mark(X1), X2, X3) -> mark(U34(X1, X2, X3))
   U35(mark(X1), X2) -> mark(U35(X1, X2))
   U36(mark(X)) -> mark(U36(X))
   U41(mark(X1), X2) -> mark(U41(X1, X2))
   U42(mark(X)) -> mark(U42(X))
   U51(mark(X)) -> mark(U51(X))
   U61(mark(X1), X2) -> mark(U61(X1, X2))
   U62(mark(X)) -> mark(U62(X))
   U71(mark(X1), X2) -> mark(U71(X1, X2))
   U72(mark(X1), X2) -> mark(U72(X1, X2))
   U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3))
   U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3))
   U83(mark(X1), X2, X3) -> mark(U83(X1, X2, X3))
   U84(mark(X1), X2, X3) -> mark(U84(X1, X2, X3))
   s(mark(X)) -> mark(s(X))
   U91(mark(X1), X2) -> mark(U91(X1, X2))
   U92(mark(X)) -> mark(U92(X))
   proper(U101(X1, X2, X3)) -> U101(proper(X1), proper(X2), proper(X3))
   proper(tt) -> ok(tt)
   proper(U102(X1, X2, X3)) -> U102(proper(X1), proper(X2), proper(X3))
   proper(isNatKind(X)) -> isNatKind(proper(X))
   proper(U103(X1, X2, X3)) -> U103(proper(X1), proper(X2), proper(X3))
   proper(isNat(X)) -> isNat(proper(X))
   proper(U104(X1, X2, X3)) -> U104(proper(X1), proper(X2), proper(X3))
   proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
   proper(x(X1, X2)) -> x(proper(X1), proper(X2))
   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(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3))
   proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3))
   proper(U15(X1, X2)) -> U15(proper(X1), proper(X2))
   proper(U16(X)) -> U16(proper(X))
   proper(U21(X1, X2)) -> U21(proper(X1), proper(X2))
   proper(U22(X1, X2)) -> U22(proper(X1), proper(X2))
   proper(U23(X)) -> U23(proper(X))
   proper(U31(X1, X2, X3)) -> U31(proper(X1), proper(X2), proper(X3))
   proper(U32(X1, X2, X3)) -> U32(proper(X1), proper(X2), proper(X3))
   proper(U33(X1, X2, X3)) -> U33(proper(X1), proper(X2), proper(X3))
   proper(U34(X1, X2, X3)) -> U34(proper(X1), proper(X2), proper(X3))
   proper(U35(X1, X2)) -> U35(proper(X1), proper(X2))
   proper(U36(X)) -> U36(proper(X))
   proper(U41(X1, X2)) -> U41(proper(X1), proper(X2))
   proper(U42(X)) -> U42(proper(X))
   proper(U51(X)) -> U51(proper(X))
   proper(U61(X1, X2)) -> U61(proper(X1), proper(X2))
   proper(U62(X)) -> U62(proper(X))
   proper(U71(X1, X2)) -> U71(proper(X1), proper(X2))
   proper(U72(X1, X2)) -> U72(proper(X1), proper(X2))
   proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3))
   proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3))
   proper(U83(X1, X2, X3)) -> U83(proper(X1), proper(X2), proper(X3))
   proper(U84(X1, X2, X3)) -> U84(proper(X1), proper(X2), proper(X3))
   proper(s(X)) -> s(proper(X))
   proper(U91(X1, X2)) -> U91(proper(X1), proper(X2))
   proper(U92(X)) -> U92(proper(X))
   proper(0) -> ok(0)
   U101(ok(X1), ok(X2), ok(X3)) -> ok(U101(X1, X2, X3))
   U102(ok(X1), ok(X2), ok(X3)) -> ok(U102(X1, X2, X3))
   isNatKind(ok(X)) -> ok(isNatKind(X))
   U103(ok(X1), ok(X2), ok(X3)) -> ok(U103(X1, X2, X3))
   isNat(ok(X)) -> ok(isNat(X))
   U104(ok(X1), ok(X2), ok(X3)) -> ok(U104(X1, X2, X3))
   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
   x(ok(X1), ok(X2)) -> ok(x(X1, X2))
   U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3))
   U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3))
   U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3))
   U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3))
   U15(ok(X1), ok(X2)) -> ok(U15(X1, X2))
   U16(ok(X)) -> ok(U16(X))
   U21(ok(X1), ok(X2)) -> ok(U21(X1, X2))
   U22(ok(X1), ok(X2)) -> ok(U22(X1, X2))
   U23(ok(X)) -> ok(U23(X))
   U31(ok(X1), ok(X2), ok(X3)) -> ok(U31(X1, X2, X3))
   U32(ok(X1), ok(X2), ok(X3)) -> ok(U32(X1, X2, X3))
   U33(ok(X1), ok(X2), ok(X3)) -> ok(U33(X1, X2, X3))
   U34(ok(X1), ok(X2), ok(X3)) -> ok(U34(X1, X2, X3))
   U35(ok(X1), ok(X2)) -> ok(U35(X1, X2))
   U36(ok(X)) -> ok(U36(X))
   U41(ok(X1), ok(X2)) -> ok(U41(X1, X2))
   U42(ok(X)) -> ok(U42(X))
   U51(ok(X)) -> ok(U51(X))
   U61(ok(X1), ok(X2)) -> ok(U61(X1, X2))
   U62(ok(X)) -> ok(U62(X))
   U71(ok(X1), ok(X2)) -> ok(U71(X1, X2))
   U72(ok(X1), ok(X2)) -> ok(U72(X1, X2))
   U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3))
   U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3))
   U83(ok(X1), ok(X2), ok(X3)) -> ok(U83(X1, X2, X3))
   U84(ok(X1), ok(X2), ok(X3)) -> ok(U84(X1, X2, X3))
   s(ok(X)) -> ok(s(X))
   U91(ok(X1), ok(X2)) -> ok(U91(X1, X2))
   U92(ok(X)) -> ok(U92(X))
   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, M, N)) -> mark(U102(isNatKind(M), M, N))
   active(U102(tt, M, N)) -> mark(U103(isNat(N), M, N))
   active(U103(tt, M, N)) -> mark(U104(isNatKind(N), M, N))
   active(U104(tt, M, N)) -> mark(plus(x(N, M), N))
   active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2))
   active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2))
   active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2))
   active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2))
   active(U15(tt, V2)) -> mark(U16(isNat(V2)))
   active(U16(tt)) -> mark(tt)
   active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1))
   active(U22(tt, V1)) -> mark(U23(isNat(V1)))
   active(U23(tt)) -> mark(tt)
   active(U31(tt, V1, V2)) -> mark(U32(isNatKind(V1), V1, V2))
   active(U32(tt, V1, V2)) -> mark(U33(isNatKind(V2), V1, V2))
   active(U33(tt, V1, V2)) -> mark(U34(isNatKind(V2), V1, V2))
   active(U34(tt, V1, V2)) -> mark(U35(isNat(V1), V2))
   active(U35(tt, V2)) -> mark(U36(isNat(V2)))
   active(U36(tt)) -> mark(tt)
   active(U41(tt, V2)) -> mark(U42(isNatKind(V2)))
   active(U42(tt)) -> mark(tt)
   active(U51(tt)) -> mark(tt)
   active(U61(tt, V2)) -> mark(U62(isNatKind(V2)))
   active(U62(tt)) -> mark(tt)
   active(U71(tt, N)) -> mark(U72(isNatKind(N), N))
   active(U72(tt, N)) -> mark(N)
   active(U81(tt, M, N)) -> mark(U82(isNatKind(M), M, N))
   active(U82(tt, M, N)) -> mark(U83(isNat(N), M, N))
   active(U83(tt, M, N)) -> mark(U84(isNatKind(N), M, N))
   active(U84(tt, M, N)) -> mark(s(plus(N, M)))
   active(U91(tt, N)) -> mark(U92(isNatKind(N)))
   active(U92(tt)) -> mark(0)
   active(isNat(0)) -> mark(tt)
   active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2))
   active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1))
   active(isNat(x(V1, V2))) -> mark(U31(isNatKind(V1), V1, V2))
   active(isNatKind(0)) -> mark(tt)
   active(isNatKind(plus(V1, V2))) -> mark(U41(isNatKind(V1), V2))
   active(isNatKind(s(V1))) -> mark(U51(isNatKind(V1)))
   active(isNatKind(x(V1, V2))) -> mark(U61(isNatKind(V1), V2))
   active(plus(N, 0)) -> mark(U71(isNat(N), N))
   active(plus(N, s(M))) -> mark(U81(isNat(M), M, N))
   active(x(N, 0)) -> mark(U91(isNat(N), N))
   active(x(N, s(M))) -> mark(U101(isNat(M), M, N))
   active(U101(X1, X2, X3)) -> U101(active(X1), X2, X3)
   active(U102(X1, X2, X3)) -> U102(active(X1), X2, X3)
   active(U103(X1, X2, X3)) -> U103(active(X1), X2, X3)
   active(U104(X1, X2, X3)) -> U104(active(X1), X2, X3)
   active(plus(X1, X2)) -> plus(active(X1), X2)
   active(plus(X1, X2)) -> plus(X1, active(X2))
   active(x(X1, X2)) -> x(active(X1), X2)
   active(x(X1, X2)) -> x(X1, active(X2))
   active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3)
   active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3)
   active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3)
   active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3)
   active(U15(X1, X2)) -> U15(active(X1), X2)
   active(U16(X)) -> U16(active(X))
   active(U21(X1, X2)) -> U21(active(X1), X2)
   active(U22(X1, X2)) -> U22(active(X1), X2)
   active(U23(X)) -> U23(active(X))
   active(U31(X1, X2, X3)) -> U31(active(X1), X2, X3)
   active(U32(X1, X2, X3)) -> U32(active(X1), X2, X3)
   active(U33(X1, X2, X3)) -> U33(active(X1), X2, X3)
   active(U34(X1, X2, X3)) -> U34(active(X1), X2, X3)
   active(U35(X1, X2)) -> U35(active(X1), X2)
   active(U36(X)) -> U36(active(X))
   active(U41(X1, X2)) -> U41(active(X1), X2)
   active(U42(X)) -> U42(active(X))
   active(U51(X)) -> U51(active(X))
   active(U61(X1, X2)) -> U61(active(X1), X2)
   active(U62(X)) -> U62(active(X))
   active(U71(X1, X2)) -> U71(active(X1), X2)
   active(U72(X1, X2)) -> U72(active(X1), X2)
   active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3)
   active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3)
   active(U83(X1, X2, X3)) -> U83(active(X1), X2, X3)
   active(U84(X1, X2, X3)) -> U84(active(X1), X2, X3)
   active(s(X)) -> s(active(X))
   active(U91(X1, X2)) -> U91(active(X1), X2)
   active(U92(X)) -> U92(active(X))
   U101(mark(X1), X2, X3) -> mark(U101(X1, X2, X3))
   U102(mark(X1), X2, X3) -> mark(U102(X1, X2, X3))
   U103(mark(X1), X2, X3) -> mark(U103(X1, X2, X3))
   U104(mark(X1), X2, X3) -> mark(U104(X1, X2, X3))
   plus(mark(X1), X2) -> mark(plus(X1, X2))
   plus(X1, mark(X2)) -> mark(plus(X1, X2))
   x(mark(X1), X2) -> mark(x(X1, X2))
   x(X1, mark(X2)) -> mark(x(X1, X2))
   U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3))
   U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3))
   U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3))
   U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3))
   U15(mark(X1), X2) -> mark(U15(X1, X2))
   U16(mark(X)) -> mark(U16(X))
   U21(mark(X1), X2) -> mark(U21(X1, X2))
   U22(mark(X1), X2) -> mark(U22(X1, X2))
   U23(mark(X)) -> mark(U23(X))
   U31(mark(X1), X2, X3) -> mark(U31(X1, X2, X3))
   U32(mark(X1), X2, X3) -> mark(U32(X1, X2, X3))
   U33(mark(X1), X2, X3) -> mark(U33(X1, X2, X3))
   U34(mark(X1), X2, X3) -> mark(U34(X1, X2, X3))
   U35(mark(X1), X2) -> mark(U35(X1, X2))
   U36(mark(X)) -> mark(U36(X))
   U41(mark(X1), X2) -> mark(U41(X1, X2))
   U42(mark(X)) -> mark(U42(X))
   U51(mark(X)) -> mark(U51(X))
   U61(mark(X1), X2) -> mark(U61(X1, X2))
   U62(mark(X)) -> mark(U62(X))
   U71(mark(X1), X2) -> mark(U71(X1, X2))
   U72(mark(X1), X2) -> mark(U72(X1, X2))
   U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3))
   U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3))
   U83(mark(X1), X2, X3) -> mark(U83(X1, X2, X3))
   U84(mark(X1), X2, X3) -> mark(U84(X1, X2, X3))
   s(mark(X)) -> mark(s(X))
   U91(mark(X1), X2) -> mark(U91(X1, X2))
   U92(mark(X)) -> mark(U92(X))
   proper(U101(X1, X2, X3)) -> U101(proper(X1), proper(X2), proper(X3))
   proper(tt) -> ok(tt)
   proper(U102(X1, X2, X3)) -> U102(proper(X1), proper(X2), proper(X3))
   proper(isNatKind(X)) -> isNatKind(proper(X))
   proper(U103(X1, X2, X3)) -> U103(proper(X1), proper(X2), proper(X3))
   proper(isNat(X)) -> isNat(proper(X))
   proper(U104(X1, X2, X3)) -> U104(proper(X1), proper(X2), proper(X3))
   proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
   proper(x(X1, X2)) -> x(proper(X1), proper(X2))
   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(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3))
   proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3))
   proper(U15(X1, X2)) -> U15(proper(X1), proper(X2))
   proper(U16(X)) -> U16(proper(X))
   proper(U21(X1, X2)) -> U21(proper(X1), proper(X2))
   proper(U22(X1, X2)) -> U22(proper(X1), proper(X2))
   proper(U23(X)) -> U23(proper(X))
   proper(U31(X1, X2, X3)) -> U31(proper(X1), proper(X2), proper(X3))
   proper(U32(X1, X2, X3)) -> U32(proper(X1), proper(X2), proper(X3))
   proper(U33(X1, X2, X3)) -> U33(proper(X1), proper(X2), proper(X3))
   proper(U34(X1, X2, X3)) -> U34(proper(X1), proper(X2), proper(X3))
   proper(U35(X1, X2)) -> U35(proper(X1), proper(X2))
   proper(U36(X)) -> U36(proper(X))
   proper(U41(X1, X2)) -> U41(proper(X1), proper(X2))
   proper(U42(X)) -> U42(proper(X))
   proper(U51(X)) -> U51(proper(X))
   proper(U61(X1, X2)) -> U61(proper(X1), proper(X2))
   proper(U62(X)) -> U62(proper(X))
   proper(U71(X1, X2)) -> U71(proper(X1), proper(X2))
   proper(U72(X1, X2)) -> U72(proper(X1), proper(X2))
   proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3))
   proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3))
   proper(U83(X1, X2, X3)) -> U83(proper(X1), proper(X2), proper(X3))
   proper(U84(X1, X2, X3)) -> U84(proper(X1), proper(X2), proper(X3))
   proper(s(X)) -> s(proper(X))
   proper(U91(X1, X2)) -> U91(proper(X1), proper(X2))
   proper(U92(X)) -> U92(proper(X))
   proper(0) -> ok(0)
   U101(ok(X1), ok(X2), ok(X3)) -> ok(U101(X1, X2, X3))
   U102(ok(X1), ok(X2), ok(X3)) -> ok(U102(X1, X2, X3))
   isNatKind(ok(X)) -> ok(isNatKind(X))
   U103(ok(X1), ok(X2), ok(X3)) -> ok(U103(X1, X2, X3))
   isNat(ok(X)) -> ok(isNat(X))
   U104(ok(X1), ok(X2), ok(X3)) -> ok(U104(X1, X2, X3))
   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
   x(ok(X1), ok(X2)) -> ok(x(X1, X2))
   U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3))
   U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3))
   U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3))
   U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3))
   U15(ok(X1), ok(X2)) -> ok(U15(X1, X2))
   U16(ok(X)) -> ok(U16(X))
   U21(ok(X1), ok(X2)) -> ok(U21(X1, X2))
   U22(ok(X1), ok(X2)) -> ok(U22(X1, X2))
   U23(ok(X)) -> ok(U23(X))
   U31(ok(X1), ok(X2), ok(X3)) -> ok(U31(X1, X2, X3))
   U32(ok(X1), ok(X2), ok(X3)) -> ok(U32(X1, X2, X3))
   U33(ok(X1), ok(X2), ok(X3)) -> ok(U33(X1, X2, X3))
   U34(ok(X1), ok(X2), ok(X3)) -> ok(U34(X1, X2, X3))
   U35(ok(X1), ok(X2)) -> ok(U35(X1, X2))
   U36(ok(X)) -> ok(U36(X))
   U41(ok(X1), ok(X2)) -> ok(U41(X1, X2))
   U42(ok(X)) -> ok(U42(X))
   U51(ok(X)) -> ok(U51(X))
   U61(ok(X1), ok(X2)) -> ok(U61(X1, X2))
   U62(ok(X)) -> ok(U62(X))
   U71(ok(X1), ok(X2)) -> ok(U71(X1, X2))
   U72(ok(X1), ok(X2)) -> ok(U72(X1, X2))
   U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3))
   U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3))
   U83(ok(X1), ok(X2), ok(X3)) -> ok(U83(X1, X2, X3))
   U84(ok(X1), ok(X2), ok(X3)) -> ok(U84(X1, X2, X3))
   s(ok(X)) -> ok(s(X))
   U91(ok(X1), ok(X2)) -> ok(U91(X1, X2))
   U92(ok(X)) -> ok(U92(X))
   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}
isNatKind: empty set
U103: {1}
isNat: empty set
U104: {1}
plus: {1, 2}
x: {1, 2}
U11: {1}
U12: {1}
U13: {1}
U14: {1}
U15: {1}
U16: {1}
U21: {1}
U22: {1}
U23: {1}
U31: {1}
U32: {1}
U33: {1}
U34: {1}
U35: {1}
U36: {1}
U41: {1}
U42: {1}
U51: {1}
U61: {1}
U62: {1}
U71: {1}
U72: {1}
U81: {1}
U82: {1}
U83: {1}
U84: {1}
s: {1}
U91: {1}
U92: {1}
0: empty set
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, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

The replacement map contains the following entries:

U101: {1}
tt: empty set
U102: {1}
isNatKind: empty set
U103: {1}
isNat: empty set
U104: {1}
plus: {1, 2}
x: {1, 2}
U11: {1}
U12: {1}
U13: {1}
U14: {1}
U15: {1}
U16: {1}
U21: {1}
U22: {1}
U23: {1}
U31: {1}
U32: {1}
U33: {1}
U34: {1}
U35: {1}
U36: {1}
U41: {1}
U42: {1}
U51: {1}
U61: {1}
U62: {1}
U71: {1}
U72: {1}
U81: {1}
U82: {1}
U83: {1}
U84: {1}
s: {1}
U91: {1}
U92: {1}
0: empty set

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

(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 {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, PLUS_2, X_2, U16'_1, U23'_1, U36'_1, U42'_1, U62'_1, U92'_1, U51'_1} are replacing on all positions.
For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U102'_3, U101'_3, U103'_3, U104'_3, U12'_3, U11'_3, U13'_3, U14'_3, U15'_2, U22'_2, U21'_2, U32'_3, U31'_3, U33'_3, U34'_3, U35'_2, U41'_2, U61'_2, U72'_2, U71'_2, U82'_3, U81'_3, U83'_3, U84'_3, U91'_2} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1, ISNATKIND_1, ISNAT_1, U_1} are not replacing on any position.

The ordinary context-sensitive dependency pairs DP_o are:
   U101'(tt, M, N) -> U102'(isNatKind(M), M, N)
   U101'(tt, M, N) -> ISNATKIND(M)
   U102'(tt, M, N) -> U103'(isNat(N), M, N)
   U102'(tt, M, N) -> ISNAT(N)
   U103'(tt, M, N) -> U104'(isNatKind(N), M, N)
   U103'(tt, M, N) -> ISNATKIND(N)
   U104'(tt, M, N) -> PLUS(x(N, M), N)
   U104'(tt, M, N) -> X(N, M)
   U11'(tt, V1, V2) -> U12'(isNatKind(V1), V1, V2)
   U11'(tt, V1, V2) -> ISNATKIND(V1)
   U12'(tt, V1, V2) -> U13'(isNatKind(V2), V1, V2)
   U12'(tt, V1, V2) -> ISNATKIND(V2)
   U13'(tt, V1, V2) -> U14'(isNatKind(V2), V1, V2)
   U13'(tt, V1, V2) -> ISNATKIND(V2)
   U14'(tt, V1, V2) -> U15'(isNat(V1), V2)
   U14'(tt, V1, V2) -> ISNAT(V1)
   U15'(tt, V2) -> U16'(isNat(V2))
   U15'(tt, V2) -> ISNAT(V2)
   U21'(tt, V1) -> U22'(isNatKind(V1), V1)
   U21'(tt, V1) -> ISNATKIND(V1)
   U22'(tt, V1) -> U23'(isNat(V1))
   U22'(tt, V1) -> ISNAT(V1)
   U31'(tt, V1, V2) -> U32'(isNatKind(V1), V1, V2)
   U31'(tt, V1, V2) -> ISNATKIND(V1)
   U32'(tt, V1, V2) -> U33'(isNatKind(V2), V1, V2)
   U32'(tt, V1, V2) -> ISNATKIND(V2)
   U33'(tt, V1, V2) -> U34'(isNatKind(V2), V1, V2)
   U33'(tt, V1, V2) -> ISNATKIND(V2)
   U34'(tt, V1, V2) -> U35'(isNat(V1), V2)
   U34'(tt, V1, V2) -> ISNAT(V1)
   U35'(tt, V2) -> U36'(isNat(V2))
   U35'(tt, V2) -> ISNAT(V2)
   U41'(tt, V2) -> U42'(isNatKind(V2))
   U41'(tt, V2) -> ISNATKIND(V2)
   U61'(tt, V2) -> U62'(isNatKind(V2))
   U61'(tt, V2) -> ISNATKIND(V2)
   U71'(tt, N) -> U72'(isNatKind(N), N)
   U71'(tt, N) -> ISNATKIND(N)
   U81'(tt, M, N) -> U82'(isNatKind(M), M, N)
   U81'(tt, M, N) -> ISNATKIND(M)
   U82'(tt, M, N) -> U83'(isNat(N), M, N)
   U82'(tt, M, N) -> ISNAT(N)
   U83'(tt, M, N) -> U84'(isNatKind(N), M, N)
   U83'(tt, M, N) -> ISNATKIND(N)
   U84'(tt, M, N) -> PLUS(N, M)
   U91'(tt, N) -> U92'(isNatKind(N))
   U91'(tt, N) -> ISNATKIND(N)
   ISNAT(plus(V1, V2)) -> U11'(isNatKind(V1), V1, V2)
   ISNAT(plus(V1, V2)) -> ISNATKIND(V1)
   ISNAT(s(V1)) -> U21'(isNatKind(V1), V1)
   ISNAT(s(V1)) -> ISNATKIND(V1)
   ISNAT(x(V1, V2)) -> U31'(isNatKind(V1), V1, V2)
   ISNAT(x(V1, V2)) -> ISNATKIND(V1)
   ISNATKIND(plus(V1, V2)) -> U41'(isNatKind(V1), V2)
   ISNATKIND(plus(V1, V2)) -> ISNATKIND(V1)
   ISNATKIND(s(V1)) -> U51'(isNatKind(V1))
   ISNATKIND(s(V1)) -> ISNATKIND(V1)
   ISNATKIND(x(V1, V2)) -> U61'(isNatKind(V1), V2)
   ISNATKIND(x(V1, V2)) -> ISNATKIND(V1)
   PLUS(N, 0) -> U71'(isNat(N), N)
   PLUS(N, 0) -> ISNAT(N)
   PLUS(N, s(M)) -> U81'(isNat(M), M, N)
   PLUS(N, s(M)) -> ISNAT(M)
   X(N, 0) -> U91'(isNat(N), N)
   X(N, 0) -> ISNAT(N)
   X(N, s(M)) -> U101'(isNat(M), M, N)
   X(N, s(M)) -> ISNAT(M)

The collapsing dependency pairs are DP_c:
   U104'(tt, M, N) -> N
   U104'(tt, M, N) -> M
   U72'(tt, N) -> N
   U84'(tt, M, N) -> N
   U84'(tt, M, N) -> M


The hidden terms of R are:
none

Every hiding context is built from:none

Hence, the new unhiding pairs DP_u are :
   U104'(tt, M, N) -> U(N)
   U104'(tt, M, N) -> U(M)
   U72'(tt, N) -> U(N)
   U84'(tt, M, N) -> U(N)
   U84'(tt, M, N) -> U(M)

The TRS R consists of the following rules:

   U101(tt, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

Q is empty.

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

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

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

(6)
Complex Obligation (AND)

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

(7)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1} are replacing on all positions.
For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U41'_2, U61'_2} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1, ISNATKIND_1} are not replacing on any position.

The TRS P consists of the following rules:

   U41'(tt, V2) -> ISNATKIND(V2)
   ISNATKIND(plus(V1, V2)) -> U41'(isNatKind(V1), V2)
   ISNATKIND(plus(V1, V2)) -> ISNATKIND(V1)
   ISNATKIND(s(V1)) -> ISNATKIND(V1)
   ISNATKIND(x(V1, V2)) -> U61'(isNatKind(V1), V2)
   U61'(tt, V2) -> ISNATKIND(V2)
   ISNATKIND(x(V1, V2)) -> ISNATKIND(V1)

The TRS R consists of the following rules:

   U101(tt, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

Q is empty.

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

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


The following pairs can be oriented strictly and are deleted.

   ISNATKIND(plus(V1, V2)) -> U41'(isNatKind(V1), V2)
   ISNATKIND(plus(V1, V2)) -> ISNATKIND(V1)
   ISNATKIND(s(V1)) -> ISNATKIND(V1)
   ISNATKIND(x(V1, V2)) -> U61'(isNatKind(V1), V2)
   ISNATKIND(x(V1, V2)) -> ISNATKIND(V1)
The remaining pairs can at least be oriented weakly.

   U41'(tt, V2) -> ISNATKIND(V2)
   U61'(tt, V2) -> ISNATKIND(V2)
Used ordering:  Combined order from the following AFS and order.
ISNATKIND(x1)  =  x1

U41'(x1, x2)  =  x2

U61'(x1, x2)  =  x2


Subterm Order

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

(9)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1} are replacing on all positions.
For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U41'_2, U61'_2} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1, ISNATKIND_1} are not replacing on any position.

The TRS P consists of the following rules:

   U41'(tt, V2) -> ISNATKIND(V2)
   U61'(tt, V2) -> ISNATKIND(V2)

The TRS R consists of the following rules:

   U101(tt, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

Q is empty.

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

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

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

(11)
TRUE

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

(12)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1} are replacing on all positions.
For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U12'_3, U11'_3, U13'_3, U14'_3, U15'_2, U21'_2, U22'_2, U31'_3, U32'_3, U33'_3, U34'_3, U35'_2} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1, ISNAT_1} are not replacing on any position.

The TRS P consists of the following rules:

   U11'(tt, V1, V2) -> U12'(isNatKind(V1), V1, V2)
   U12'(tt, V1, V2) -> U13'(isNatKind(V2), V1, V2)
   U13'(tt, V1, V2) -> U14'(isNatKind(V2), V1, V2)
   U14'(tt, V1, V2) -> U15'(isNat(V1), V2)
   U15'(tt, V2) -> ISNAT(V2)
   ISNAT(plus(V1, V2)) -> U11'(isNatKind(V1), V1, V2)
   ISNAT(s(V1)) -> U21'(isNatKind(V1), V1)
   U21'(tt, V1) -> U22'(isNatKind(V1), V1)
   U22'(tt, V1) -> ISNAT(V1)
   ISNAT(x(V1, V2)) -> U31'(isNatKind(V1), V1, V2)
   U31'(tt, V1, V2) -> U32'(isNatKind(V1), V1, V2)
   U32'(tt, V1, V2) -> U33'(isNatKind(V2), V1, V2)
   U33'(tt, V1, V2) -> U34'(isNatKind(V2), V1, V2)
   U34'(tt, V1, V2) -> U35'(isNat(V1), V2)
   U35'(tt, V2) -> ISNAT(V2)
   U34'(tt, V1, V2) -> ISNAT(V1)
   U14'(tt, V1, V2) -> ISNAT(V1)

The TRS R consists of the following rules:

   U101(tt, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

Q is empty.

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

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

   U101(tt, x0, x1) -> U102(isNatKind(x0), x0, x1)
   U102(tt, x0, x1) -> U103(isNat(x1), x0, x1)
   U103(tt, x0, x1) -> U104(isNatKind(x1), x0, x1)
   U104(tt, x0, x1) -> plus(x(x1, x0), x1)
   U71(tt, x0) -> U72(isNatKind(x0), x0)
   U72(tt, x0) -> x0
   U81(tt, x0, x1) -> U82(isNatKind(x0), x0, x1)
   U82(tt, x0, x1) -> U83(isNat(x1), x0, x1)
   U83(tt, x0, x1) -> U84(isNatKind(x1), x0, x1)
   U84(tt, x0, x1) -> s(plus(x1, x0))
   U91(tt, x0) -> U92(isNatKind(x0))
   U92(tt) -> 0
   plus(x0, 0) -> U71(isNat(x0), x0)
   plus(x0, s(x1)) -> U81(isNat(x1), x1, x0)
   x(x0, 0) -> U91(isNat(x0), x0)
   x(x0, s(x1)) -> U101(isNat(x1), x1, x0)

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

(14)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, s_1, U51_1, x_2, U62_1, U42_1, U23_1, U36_1, U16_1} are replacing on all positions.
For all symbols f in {U41_2, U61_2, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U12'_3, U11'_3, U13'_3, U14'_3, U15'_2, U21'_2, U22'_2, U31'_3, U32'_3, U33'_3, U34'_3, U35'_2} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1, ISNAT_1} are not replacing on any position.

The TRS P consists of the following rules:

   U11'(tt, V1, V2) -> U12'(isNatKind(V1), V1, V2)
   U12'(tt, V1, V2) -> U13'(isNatKind(V2), V1, V2)
   U13'(tt, V1, V2) -> U14'(isNatKind(V2), V1, V2)
   U14'(tt, V1, V2) -> U15'(isNat(V1), V2)
   U15'(tt, V2) -> ISNAT(V2)
   ISNAT(plus(V1, V2)) -> U11'(isNatKind(V1), V1, V2)
   ISNAT(s(V1)) -> U21'(isNatKind(V1), V1)
   U21'(tt, V1) -> U22'(isNatKind(V1), V1)
   U22'(tt, V1) -> ISNAT(V1)
   ISNAT(x(V1, V2)) -> U31'(isNatKind(V1), V1, V2)
   U31'(tt, V1, V2) -> U32'(isNatKind(V1), V1, V2)
   U32'(tt, V1, V2) -> U33'(isNatKind(V2), V1, V2)
   U33'(tt, V1, V2) -> U34'(isNatKind(V2), V1, V2)
   U34'(tt, V1, V2) -> U35'(isNat(V1), V2)
   U35'(tt, V2) -> ISNAT(V2)
   U34'(tt, V1, V2) -> ISNAT(V1)
   U14'(tt, V1, V2) -> ISNAT(V1)

The TRS R consists of the following rules:

   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U51(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U23(tt) -> tt
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt

Q is empty.

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

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

   U14'(tt, V1, V2) -> U15'(isNat(V1), V2)
   U15'(tt, V2) -> ISNAT(V2)
   ISNAT(plus(V1, V2)) -> U11'(isNatKind(V1), V1, V2)
   ISNAT(s(V1)) -> U21'(isNatKind(V1), V1)
   U21'(tt, V1) -> U22'(isNatKind(V1), V1)
   U22'(tt, V1) -> ISNAT(V1)
   ISNAT(x(V1, V2)) -> U31'(isNatKind(V1), V1, V2)
   U34'(tt, V1, V2) -> U35'(isNat(V1), V2)
   U35'(tt, V2) -> ISNAT(V2)
   U34'(tt, V1, V2) -> ISNAT(V1)
   U14'(tt, V1, V2) -> ISNAT(V1)

Strictly oriented rules of the TRS R:

   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U22(tt, V1) -> U23(isNat(V1))
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U23(tt) -> tt
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt

Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(0) = 2
   POL(ISNAT(x_1)) = 2 + 2*x_1
   POL(U11(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3
   POL(U11'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
   POL(U12(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3
   POL(U12'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
   POL(U13(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3
   POL(U13'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
   POL(U14(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3
   POL(U14'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
   POL(U15(x_1, x_2)) = x_1 + 2*x_2
   POL(U15'(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(U16(x_1)) = 2*x_1
   POL(U21(x_1, x_2)) = x_1 + 2*x_2
   POL(U21'(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(U22(x_1, x_2)) = x_1 + 2*x_2
   POL(U22'(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(U23(x_1)) = 1 + 2*x_1
   POL(U31(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3
   POL(U31'(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3
   POL(U32(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3
   POL(U32'(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3
   POL(U33(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3
   POL(U33'(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3
   POL(U34(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3
   POL(U34'(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3
   POL(U35(x_1, x_2)) = 1 + 2*x_1 + x_2
   POL(U35'(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(U36(x_1)) = x_1
   POL(U41(x_1, x_2)) = x_1
   POL(U42(x_1)) = x_1
   POL(U51(x_1)) = x_1
   POL(U61(x_1, x_2)) = x_1
   POL(U62(x_1)) = x_1
   POL(isNat(x_1)) = x_1
   POL(isNatKind(x_1)) = 2
   POL(plus(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(s(x_1)) = 2 + 2*x_1
   POL(tt) = 2
   POL(x(x_1, x_2)) = 2 + 2*x_1 + 2*x_2


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

(16)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, s_1, U51_1, x_2, U62_1, U42_1, U36_1} are replacing on all positions.
For all symbols f in {U41_2, U61_2, U11_3, U12_3, U13_3, U14_3, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U12'_3, U11'_3, U13'_3, U14'_3, U32'_3, U31'_3, U33'_3, U34'_3} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1} are not replacing on any position.

The TRS P consists of the following rules:

   U11'(tt, V1, V2) -> U12'(isNatKind(V1), V1, V2)
   U12'(tt, V1, V2) -> U13'(isNatKind(V2), V1, V2)
   U13'(tt, V1, V2) -> U14'(isNatKind(V2), V1, V2)
   U31'(tt, V1, V2) -> U32'(isNatKind(V1), V1, V2)
   U32'(tt, V1, V2) -> U33'(isNatKind(V2), V1, V2)
   U33'(tt, V1, V2) -> U34'(isNatKind(V2), V1, V2)

The TRS R consists of the following rules:

   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U51(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U36(tt) -> tt

Q is empty.

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

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

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

(18)
TRUE

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

(19)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, PLUS_2} are replacing on all positions.
For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U83'_3, U82'_3, U84'_3, U81'_3} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1} are not replacing on any position.

The TRS P consists of the following rules:

   U82'(tt, M, N) -> U83'(isNat(N), M, N)
   U83'(tt, M, N) -> U84'(isNatKind(N), M, N)
   U84'(tt, M, N) -> PLUS(N, M)
   PLUS(N, s(M)) -> U81'(isNat(M), M, N)
   U81'(tt, M, N) -> U82'(isNatKind(M), M, N)

The TRS R consists of the following rules:

   U101(tt, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

Q is empty.

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

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


The following pairs can be oriented strictly and are deleted.

   PLUS(N, s(M)) -> U81'(isNat(M), M, N)
The remaining pairs can at least be oriented weakly.

   U82'(tt, M, N) -> U83'(isNat(N), M, N)
   U83'(tt, M, N) -> U84'(isNatKind(N), M, N)
   U84'(tt, M, N) -> PLUS(N, M)
   U81'(tt, M, N) -> U82'(isNatKind(M), M, N)
Used ordering:  Combined order from the following AFS and order.
U83'(x1, x2, x3)  =  x2

U82'(x1, x2, x3)  =  x2

U84'(x1, x2, x3)  =  x2

PLUS(x1, x2)  =  x2

U81'(x1, x2, x3)  =  x2


Subterm Order

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

(21)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, PLUS_2} are replacing on all positions.
For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U83'_3, U82'_3, U84'_3, U81'_3} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1} are not replacing on any position.

The TRS P consists of the following rules:

   U82'(tt, M, N) -> U83'(isNat(N), M, N)
   U83'(tt, M, N) -> U84'(isNatKind(N), M, N)
   U84'(tt, M, N) -> PLUS(N, M)
   U81'(tt, M, N) -> U82'(isNatKind(M), M, N)

The TRS R consists of the following rules:

   U101(tt, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

Q is empty.

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

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

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

(23)
TRUE

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

(24)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, X_2} are replacing on all positions.
For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U103'_3, U102'_3, U104'_3, U101'_3} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1} are not replacing on any position.

The TRS P consists of the following rules:

   U102'(tt, M, N) -> U103'(isNat(N), M, N)
   U103'(tt, M, N) -> U104'(isNatKind(N), M, N)
   U104'(tt, M, N) -> X(N, M)
   X(N, s(M)) -> U101'(isNat(M), M, N)
   U101'(tt, M, N) -> U102'(isNatKind(M), M, N)

The TRS R consists of the following rules:

   U101(tt, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

Q is empty.

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

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


The following pairs can be oriented strictly and are deleted.

   X(N, s(M)) -> U101'(isNat(M), M, N)
The remaining pairs can at least be oriented weakly.

   U102'(tt, M, N) -> U103'(isNat(N), M, N)
   U103'(tt, M, N) -> U104'(isNatKind(N), M, N)
   U104'(tt, M, N) -> X(N, M)
   U101'(tt, M, N) -> U102'(isNatKind(M), M, N)
Used ordering:  Combined order from the following AFS and order.
U103'(x1, x2, x3)  =  x2

U102'(x1, x2, x3)  =  x2

U104'(x1, x2, x3)  =  x2

X(x1, x2)  =  x2

U101'(x1, x2, x3)  =  x2


Subterm Order

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

(26)
Obligation:
Q-restricted context-sensitive dependency pair problem:
The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, X_2} are replacing on all positions.
For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U103'_3, U102'_3, U104'_3, U101'_3} we have mu(f) = {1}.
The symbols in {isNatKind_1, isNat_1} are not replacing on any position.

The TRS P consists of the following rules:

   U102'(tt, M, N) -> U103'(isNat(N), M, N)
   U103'(tt, M, N) -> U104'(isNatKind(N), M, N)
   U104'(tt, M, N) -> X(N, M)
   U101'(tt, M, N) -> U102'(isNatKind(M), M, N)

The TRS R consists of the following rules:

   U101(tt, M, N) -> U102(isNatKind(M), M, N)
   U102(tt, M, N) -> U103(isNat(N), M, N)
   U103(tt, M, N) -> U104(isNatKind(N), M, N)
   U104(tt, M, N) -> plus(x(N, M), N)
   U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2)
   U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2)
   U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2)
   U14(tt, V1, V2) -> U15(isNat(V1), V2)
   U15(tt, V2) -> U16(isNat(V2))
   U16(tt) -> tt
   U21(tt, V1) -> U22(isNatKind(V1), V1)
   U22(tt, V1) -> U23(isNat(V1))
   U23(tt) -> tt
   U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2)
   U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2)
   U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2)
   U34(tt, V1, V2) -> U35(isNat(V1), V2)
   U35(tt, V2) -> U36(isNat(V2))
   U36(tt) -> tt
   U41(tt, V2) -> U42(isNatKind(V2))
   U42(tt) -> tt
   U51(tt) -> tt
   U61(tt, V2) -> U62(isNatKind(V2))
   U62(tt) -> tt
   U71(tt, N) -> U72(isNatKind(N), N)
   U72(tt, N) -> N
   U81(tt, M, N) -> U82(isNatKind(M), M, N)
   U82(tt, M, N) -> U83(isNat(N), M, N)
   U83(tt, M, N) -> U84(isNatKind(N), M, N)
   U84(tt, M, N) -> s(plus(N, M))
   U91(tt, N) -> U92(isNatKind(N))
   U92(tt) -> 0
   isNat(0) -> tt
   isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2)
   isNat(s(V1)) -> U21(isNatKind(V1), V1)
   isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2)
   isNatKind(0) -> tt
   isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2)
   isNatKind(s(V1)) -> U51(isNatKind(V1))
   isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2)
   plus(N, 0) -> U71(isNat(N), N)
   plus(N, s(M)) -> U81(isNat(M), M, N)
   x(N, 0) -> U91(isNat(N), N)
   x(N, s(M)) -> U101(isNat(M), M, N)

Q is empty.

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

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

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

(28)
TRUE