YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 296 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) QReductionProof [EQUIVALENT, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) QDP (13) UsableRulesProof [EQUIVALENT, 0 ms] (14) QDP (15) QReductionProof [EQUIVALENT, 0 ms] (16) QDP (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] (18) YES (19) QDP (20) QDPOrderProof [EQUIVALENT, 6375 ms] (21) QDP (22) DependencyGraphProof [EQUIVALENT, 0 ms] (23) QDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) QDP (26) QReductionProof [EQUIVALENT, 1 ms] (27) QDP (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] (29) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__U101(tt, M, N) -> a__U102(a__isNatKind(M), M, N) a__U102(tt, M, N) -> a__U103(a__isNat(N), M, N) a__U103(tt, M, N) -> a__U104(a__isNatKind(N), M, N) a__U104(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U16(tt) -> tt a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U23(tt) -> tt a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U36(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U42(tt) -> tt a__U51(tt) -> tt a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U62(tt) -> tt a__U71(tt, N) -> a__U72(a__isNatKind(N), N) a__U72(tt, N) -> mark(N) a__U81(tt, M, N) -> a__U82(a__isNatKind(M), M, N) a__U82(tt, M, N) -> a__U83(a__isNat(N), M, N) a__U83(tt, M, N) -> a__U84(a__isNatKind(N), M, N) a__U84(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U91(tt, N) -> a__U92(a__isNatKind(N)) a__U92(tt) -> 0 a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__plus(N, 0) -> a__U71(a__isNat(N), N) a__plus(N, s(M)) -> a__U81(a__isNat(M), M, N) a__x(N, 0) -> a__U91(a__isNat(N), N) a__x(N, s(M)) -> a__U101(a__isNat(M), M, N) mark(U101(X1, X2, X3)) -> a__U101(mark(X1), X2, X3) mark(U102(X1, X2, X3)) -> a__U102(mark(X1), X2, X3) mark(isNatKind(X)) -> a__isNatKind(X) mark(U103(X1, X2, X3)) -> a__U103(mark(X1), X2, X3) mark(isNat(X)) -> a__isNat(X) mark(U104(X1, X2, X3)) -> a__U104(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) mark(U13(X1, X2, X3)) -> a__U13(mark(X1), X2, X3) mark(U14(X1, X2, X3)) -> a__U14(mark(X1), X2, X3) mark(U15(X1, X2)) -> a__U15(mark(X1), X2) mark(U16(X)) -> a__U16(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) mark(U32(X1, X2, X3)) -> a__U32(mark(X1), X2, X3) mark(U33(X1, X2, X3)) -> a__U33(mark(X1), X2, X3) mark(U34(X1, X2, X3)) -> a__U34(mark(X1), X2, X3) mark(U35(X1, X2)) -> a__U35(mark(X1), X2) mark(U36(X)) -> a__U36(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X)) -> a__U51(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U81(X1, X2, X3)) -> a__U81(mark(X1), X2, X3) mark(U82(X1, X2, X3)) -> a__U82(mark(X1), X2, X3) mark(U83(X1, X2, X3)) -> a__U83(mark(X1), X2, X3) mark(U84(X1, X2, X3)) -> a__U84(mark(X1), X2, X3) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U101(X1, X2, X3) -> U101(X1, X2, X3) a__U102(X1, X2, X3) -> U102(X1, X2, X3) a__isNatKind(X) -> isNatKind(X) a__U103(X1, X2, X3) -> U103(X1, X2, X3) a__isNat(X) -> isNat(X) a__U104(X1, X2, X3) -> U104(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__x(X1, X2) -> x(X1, X2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(X1, X2) -> U15(X1, X2) a__U16(X) -> U16(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X1, X2) -> U22(X1, X2) a__U23(X) -> U23(X) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(X1, X2) -> U35(X1, X2) a__U36(X) -> U36(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X) -> U51(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X1, X2) -> U72(X1, X2) a__U81(X1, X2, X3) -> U81(X1, X2, X3) a__U82(X1, X2, X3) -> U82(X1, X2, X3) a__U83(X1, X2, X3) -> U83(X1, X2, X3) a__U84(X1, X2, X3) -> U84(X1, X2, X3) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: A__U101(tt, M, N) -> A__U102(a__isNatKind(M), M, N) A__U101(tt, M, N) -> A__ISNATKIND(M) A__U102(tt, M, N) -> A__U103(a__isNat(N), M, N) A__U102(tt, M, N) -> A__ISNAT(N) A__U103(tt, M, N) -> A__U104(a__isNatKind(N), M, N) A__U103(tt, M, N) -> A__ISNATKIND(N) A__U104(tt, M, N) -> A__PLUS(a__x(mark(N), mark(M)), mark(N)) A__U104(tt, M, N) -> A__X(mark(N), mark(M)) A__U104(tt, M, N) -> MARK(N) A__U104(tt, M, N) -> MARK(M) A__U11(tt, V1, V2) -> A__U12(a__isNatKind(V1), V1, V2) A__U11(tt, V1, V2) -> A__ISNATKIND(V1) A__U12(tt, V1, V2) -> A__U13(a__isNatKind(V2), V1, V2) A__U12(tt, V1, V2) -> A__ISNATKIND(V2) A__U13(tt, V1, V2) -> A__U14(a__isNatKind(V2), V1, V2) A__U13(tt, V1, V2) -> A__ISNATKIND(V2) A__U14(tt, V1, V2) -> A__U15(a__isNat(V1), V2) A__U14(tt, V1, V2) -> A__ISNAT(V1) A__U15(tt, V2) -> A__U16(a__isNat(V2)) A__U15(tt, V2) -> A__ISNAT(V2) A__U21(tt, V1) -> A__U22(a__isNatKind(V1), V1) A__U21(tt, V1) -> A__ISNATKIND(V1) A__U22(tt, V1) -> A__U23(a__isNat(V1)) A__U22(tt, V1) -> A__ISNAT(V1) A__U31(tt, V1, V2) -> A__U32(a__isNatKind(V1), V1, V2) A__U31(tt, V1, V2) -> A__ISNATKIND(V1) A__U32(tt, V1, V2) -> A__U33(a__isNatKind(V2), V1, V2) A__U32(tt, V1, V2) -> A__ISNATKIND(V2) A__U33(tt, V1, V2) -> A__U34(a__isNatKind(V2), V1, V2) A__U33(tt, V1, V2) -> A__ISNATKIND(V2) A__U34(tt, V1, V2) -> A__U35(a__isNat(V1), V2) A__U34(tt, V1, V2) -> A__ISNAT(V1) A__U35(tt, V2) -> A__U36(a__isNat(V2)) A__U35(tt, V2) -> A__ISNAT(V2) A__U41(tt, V2) -> A__U42(a__isNatKind(V2)) A__U41(tt, V2) -> A__ISNATKIND(V2) A__U61(tt, V2) -> A__U62(a__isNatKind(V2)) A__U61(tt, V2) -> A__ISNATKIND(V2) A__U71(tt, N) -> A__U72(a__isNatKind(N), N) A__U71(tt, N) -> A__ISNATKIND(N) A__U72(tt, N) -> MARK(N) A__U81(tt, M, N) -> A__U82(a__isNatKind(M), M, N) A__U81(tt, M, N) -> A__ISNATKIND(M) A__U82(tt, M, N) -> A__U83(a__isNat(N), M, N) A__U82(tt, M, N) -> A__ISNAT(N) A__U83(tt, M, N) -> A__U84(a__isNatKind(N), M, N) A__U83(tt, M, N) -> A__ISNATKIND(N) A__U84(tt, M, N) -> A__PLUS(mark(N), mark(M)) A__U84(tt, M, N) -> MARK(N) A__U84(tt, M, N) -> MARK(M) A__U91(tt, N) -> A__U92(a__isNatKind(N)) A__U91(tt, N) -> A__ISNATKIND(N) A__ISNAT(plus(V1, V2)) -> A__U11(a__isNatKind(V1), V1, V2) A__ISNAT(plus(V1, V2)) -> A__ISNATKIND(V1) A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) A__ISNAT(s(V1)) -> A__ISNATKIND(V1) A__ISNAT(x(V1, V2)) -> A__U31(a__isNatKind(V1), V1, V2) A__ISNAT(x(V1, V2)) -> A__ISNATKIND(V1) A__ISNATKIND(plus(V1, V2)) -> A__U41(a__isNatKind(V1), V2) A__ISNATKIND(plus(V1, V2)) -> A__ISNATKIND(V1) A__ISNATKIND(s(V1)) -> A__U51(a__isNatKind(V1)) A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) A__ISNATKIND(x(V1, V2)) -> A__U61(a__isNatKind(V1), V2) A__ISNATKIND(x(V1, V2)) -> A__ISNATKIND(V1) A__PLUS(N, 0) -> A__U71(a__isNat(N), N) A__PLUS(N, 0) -> A__ISNAT(N) A__PLUS(N, s(M)) -> A__U81(a__isNat(M), M, N) A__PLUS(N, s(M)) -> A__ISNAT(M) A__X(N, 0) -> A__U91(a__isNat(N), N) A__X(N, 0) -> A__ISNAT(N) A__X(N, s(M)) -> A__U101(a__isNat(M), M, N) A__X(N, s(M)) -> A__ISNAT(M) MARK(U101(X1, X2, X3)) -> A__U101(mark(X1), X2, X3) MARK(U101(X1, X2, X3)) -> MARK(X1) MARK(U102(X1, X2, X3)) -> A__U102(mark(X1), X2, X3) MARK(U102(X1, X2, X3)) -> MARK(X1) MARK(isNatKind(X)) -> A__ISNATKIND(X) MARK(U103(X1, X2, X3)) -> A__U103(mark(X1), X2, X3) MARK(U103(X1, X2, X3)) -> MARK(X1) MARK(isNat(X)) -> A__ISNAT(X) MARK(U104(X1, X2, X3)) -> A__U104(mark(X1), X2, X3) MARK(U104(X1, X2, X3)) -> MARK(X1) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(x(X1, X2)) -> A__X(mark(X1), mark(X2)) MARK(x(X1, X2)) -> MARK(X1) MARK(x(X1, X2)) -> MARK(X2) MARK(U11(X1, X2, X3)) -> A__U11(mark(X1), X2, X3) MARK(U11(X1, X2, X3)) -> MARK(X1) MARK(U12(X1, X2, X3)) -> A__U12(mark(X1), X2, X3) MARK(U12(X1, X2, X3)) -> MARK(X1) MARK(U13(X1, X2, X3)) -> A__U13(mark(X1), X2, X3) MARK(U13(X1, X2, X3)) -> MARK(X1) MARK(U14(X1, X2, X3)) -> A__U14(mark(X1), X2, X3) MARK(U14(X1, X2, X3)) -> MARK(X1) MARK(U15(X1, X2)) -> A__U15(mark(X1), X2) MARK(U15(X1, X2)) -> MARK(X1) MARK(U16(X)) -> A__U16(mark(X)) MARK(U16(X)) -> MARK(X) MARK(U21(X1, X2)) -> A__U21(mark(X1), X2) MARK(U21(X1, X2)) -> MARK(X1) MARK(U22(X1, X2)) -> A__U22(mark(X1), X2) MARK(U22(X1, X2)) -> MARK(X1) MARK(U23(X)) -> A__U23(mark(X)) MARK(U23(X)) -> MARK(X) MARK(U31(X1, X2, X3)) -> A__U31(mark(X1), X2, X3) MARK(U31(X1, X2, X3)) -> MARK(X1) MARK(U32(X1, X2, X3)) -> A__U32(mark(X1), X2, X3) MARK(U32(X1, X2, X3)) -> MARK(X1) MARK(U33(X1, X2, X3)) -> A__U33(mark(X1), X2, X3) MARK(U33(X1, X2, X3)) -> MARK(X1) MARK(U34(X1, X2, X3)) -> A__U34(mark(X1), X2, X3) MARK(U34(X1, X2, X3)) -> MARK(X1) MARK(U35(X1, X2)) -> A__U35(mark(X1), X2) MARK(U35(X1, X2)) -> MARK(X1) MARK(U36(X)) -> A__U36(mark(X)) MARK(U36(X)) -> MARK(X) MARK(U41(X1, X2)) -> A__U41(mark(X1), X2) MARK(U41(X1, X2)) -> MARK(X1) MARK(U42(X)) -> A__U42(mark(X)) MARK(U42(X)) -> MARK(X) MARK(U51(X)) -> A__U51(mark(X)) MARK(U51(X)) -> MARK(X) MARK(U61(X1, X2)) -> A__U61(mark(X1), X2) MARK(U61(X1, X2)) -> MARK(X1) MARK(U62(X)) -> A__U62(mark(X)) MARK(U62(X)) -> MARK(X) MARK(U71(X1, X2)) -> A__U71(mark(X1), X2) MARK(U71(X1, X2)) -> MARK(X1) MARK(U72(X1, X2)) -> A__U72(mark(X1), X2) MARK(U72(X1, X2)) -> MARK(X1) MARK(U81(X1, X2, X3)) -> A__U81(mark(X1), X2, X3) MARK(U81(X1, X2, X3)) -> MARK(X1) MARK(U82(X1, X2, X3)) -> A__U82(mark(X1), X2, X3) MARK(U82(X1, X2, X3)) -> MARK(X1) MARK(U83(X1, X2, X3)) -> A__U83(mark(X1), X2, X3) MARK(U83(X1, X2, X3)) -> MARK(X1) MARK(U84(X1, X2, X3)) -> A__U84(mark(X1), X2, X3) MARK(U84(X1, X2, X3)) -> MARK(X1) MARK(U91(X1, X2)) -> A__U91(mark(X1), X2) MARK(U91(X1, X2)) -> MARK(X1) MARK(U92(X)) -> A__U92(mark(X)) MARK(U92(X)) -> MARK(X) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__U101(tt, M, N) -> a__U102(a__isNatKind(M), M, N) a__U102(tt, M, N) -> a__U103(a__isNat(N), M, N) a__U103(tt, M, N) -> a__U104(a__isNatKind(N), M, N) a__U104(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U16(tt) -> tt a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U23(tt) -> tt a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U36(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U42(tt) -> tt a__U51(tt) -> tt a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U62(tt) -> tt a__U71(tt, N) -> a__U72(a__isNatKind(N), N) a__U72(tt, N) -> mark(N) a__U81(tt, M, N) -> a__U82(a__isNatKind(M), M, N) a__U82(tt, M, N) -> a__U83(a__isNat(N), M, N) a__U83(tt, M, N) -> a__U84(a__isNatKind(N), M, N) a__U84(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U91(tt, N) -> a__U92(a__isNatKind(N)) a__U92(tt) -> 0 a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__plus(N, 0) -> a__U71(a__isNat(N), N) a__plus(N, s(M)) -> a__U81(a__isNat(M), M, N) a__x(N, 0) -> a__U91(a__isNat(N), N) a__x(N, s(M)) -> a__U101(a__isNat(M), M, N) mark(U101(X1, X2, X3)) -> a__U101(mark(X1), X2, X3) mark(U102(X1, X2, X3)) -> a__U102(mark(X1), X2, X3) mark(isNatKind(X)) -> a__isNatKind(X) mark(U103(X1, X2, X3)) -> a__U103(mark(X1), X2, X3) mark(isNat(X)) -> a__isNat(X) mark(U104(X1, X2, X3)) -> a__U104(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) mark(U13(X1, X2, X3)) -> a__U13(mark(X1), X2, X3) mark(U14(X1, X2, X3)) -> a__U14(mark(X1), X2, X3) mark(U15(X1, X2)) -> a__U15(mark(X1), X2) mark(U16(X)) -> a__U16(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) mark(U32(X1, X2, X3)) -> a__U32(mark(X1), X2, X3) mark(U33(X1, X2, X3)) -> a__U33(mark(X1), X2, X3) mark(U34(X1, X2, X3)) -> a__U34(mark(X1), X2, X3) mark(U35(X1, X2)) -> a__U35(mark(X1), X2) mark(U36(X)) -> a__U36(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X)) -> a__U51(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U81(X1, X2, X3)) -> a__U81(mark(X1), X2, X3) mark(U82(X1, X2, X3)) -> a__U82(mark(X1), X2, X3) mark(U83(X1, X2, X3)) -> a__U83(mark(X1), X2, X3) mark(U84(X1, X2, X3)) -> a__U84(mark(X1), X2, X3) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U101(X1, X2, X3) -> U101(X1, X2, X3) a__U102(X1, X2, X3) -> U102(X1, X2, X3) a__isNatKind(X) -> isNatKind(X) a__U103(X1, X2, X3) -> U103(X1, X2, X3) a__isNat(X) -> isNat(X) a__U104(X1, X2, X3) -> U104(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__x(X1, X2) -> x(X1, X2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(X1, X2) -> U15(X1, X2) a__U16(X) -> U16(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X1, X2) -> U22(X1, X2) a__U23(X) -> U23(X) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(X1, X2) -> U35(X1, X2) a__U36(X) -> U36(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X) -> U51(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X1, X2) -> U72(X1, X2) a__U81(X1, X2, X3) -> U81(X1, X2, X3) a__U82(X1, X2, X3) -> U82(X1, X2, X3) a__U83(X1, X2, X3) -> U83(X1, X2, X3) a__U84(X1, X2, X3) -> U84(X1, X2, X3) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 54 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: A__U41(tt, V2) -> A__ISNATKIND(V2) A__ISNATKIND(plus(V1, V2)) -> A__U41(a__isNatKind(V1), V2) A__ISNATKIND(plus(V1, V2)) -> A__ISNATKIND(V1) A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) A__ISNATKIND(x(V1, V2)) -> A__U61(a__isNatKind(V1), V2) A__U61(tt, V2) -> A__ISNATKIND(V2) A__ISNATKIND(x(V1, V2)) -> A__ISNATKIND(V1) The TRS R consists of the following rules: a__U101(tt, M, N) -> a__U102(a__isNatKind(M), M, N) a__U102(tt, M, N) -> a__U103(a__isNat(N), M, N) a__U103(tt, M, N) -> a__U104(a__isNatKind(N), M, N) a__U104(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U16(tt) -> tt a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U23(tt) -> tt a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U36(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U42(tt) -> tt a__U51(tt) -> tt a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U62(tt) -> tt a__U71(tt, N) -> a__U72(a__isNatKind(N), N) a__U72(tt, N) -> mark(N) a__U81(tt, M, N) -> a__U82(a__isNatKind(M), M, N) a__U82(tt, M, N) -> a__U83(a__isNat(N), M, N) a__U83(tt, M, N) -> a__U84(a__isNatKind(N), M, N) a__U84(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U91(tt, N) -> a__U92(a__isNatKind(N)) a__U92(tt) -> 0 a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__plus(N, 0) -> a__U71(a__isNat(N), N) a__plus(N, s(M)) -> a__U81(a__isNat(M), M, N) a__x(N, 0) -> a__U91(a__isNat(N), N) a__x(N, s(M)) -> a__U101(a__isNat(M), M, N) mark(U101(X1, X2, X3)) -> a__U101(mark(X1), X2, X3) mark(U102(X1, X2, X3)) -> a__U102(mark(X1), X2, X3) mark(isNatKind(X)) -> a__isNatKind(X) mark(U103(X1, X2, X3)) -> a__U103(mark(X1), X2, X3) mark(isNat(X)) -> a__isNat(X) mark(U104(X1, X2, X3)) -> a__U104(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) mark(U13(X1, X2, X3)) -> a__U13(mark(X1), X2, X3) mark(U14(X1, X2, X3)) -> a__U14(mark(X1), X2, X3) mark(U15(X1, X2)) -> a__U15(mark(X1), X2) mark(U16(X)) -> a__U16(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) mark(U32(X1, X2, X3)) -> a__U32(mark(X1), X2, X3) mark(U33(X1, X2, X3)) -> a__U33(mark(X1), X2, X3) mark(U34(X1, X2, X3)) -> a__U34(mark(X1), X2, X3) mark(U35(X1, X2)) -> a__U35(mark(X1), X2) mark(U36(X)) -> a__U36(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X)) -> a__U51(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U81(X1, X2, X3)) -> a__U81(mark(X1), X2, X3) mark(U82(X1, X2, X3)) -> a__U82(mark(X1), X2, X3) mark(U83(X1, X2, X3)) -> a__U83(mark(X1), X2, X3) mark(U84(X1, X2, X3)) -> a__U84(mark(X1), X2, X3) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U101(X1, X2, X3) -> U101(X1, X2, X3) a__U102(X1, X2, X3) -> U102(X1, X2, X3) a__isNatKind(X) -> isNatKind(X) a__U103(X1, X2, X3) -> U103(X1, X2, X3) a__isNat(X) -> isNat(X) a__U104(X1, X2, X3) -> U104(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__x(X1, X2) -> x(X1, X2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(X1, X2) -> U15(X1, X2) a__U16(X) -> U16(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X1, X2) -> U22(X1, X2) a__U23(X) -> U23(X) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(X1, X2) -> U35(X1, X2) a__U36(X) -> U36(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X) -> U51(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X1, X2) -> U72(X1, X2) a__U81(X1, X2, X3) -> U81(X1, X2, X3) a__U82(X1, X2, X3) -> U82(X1, X2, X3) a__U83(X1, X2, X3) -> U83(X1, X2, X3) a__U84(X1, X2, X3) -> U84(X1, X2, X3) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: A__U41(tt, V2) -> A__ISNATKIND(V2) A__ISNATKIND(plus(V1, V2)) -> A__U41(a__isNatKind(V1), V2) A__ISNATKIND(plus(V1, V2)) -> A__ISNATKIND(V1) A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) A__ISNATKIND(x(V1, V2)) -> A__U61(a__isNatKind(V1), V2) A__U61(tt, V2) -> A__ISNATKIND(V2) A__ISNATKIND(x(V1, V2)) -> A__ISNATKIND(V1) The TRS R consists of the following rules: a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__isNatKind(X) -> isNatKind(X) a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U61(X1, X2) -> U61(X1, X2) a__U62(tt) -> tt a__U62(X) -> U62(X) a__U51(tt) -> tt a__U51(X) -> U51(X) a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U41(X1, X2) -> U41(X1, X2) a__U42(tt) -> tt a__U42(X) -> U42(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: A__U41(tt, V2) -> A__ISNATKIND(V2) A__ISNATKIND(plus(V1, V2)) -> A__U41(a__isNatKind(V1), V2) A__ISNATKIND(plus(V1, V2)) -> A__ISNATKIND(V1) A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) A__ISNATKIND(x(V1, V2)) -> A__U61(a__isNatKind(V1), V2) A__U61(tt, V2) -> A__ISNATKIND(V2) A__ISNATKIND(x(V1, V2)) -> A__ISNATKIND(V1) The TRS R consists of the following rules: a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__isNatKind(X) -> isNatKind(X) a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U61(X1, X2) -> U61(X1, X2) a__U62(tt) -> tt a__U62(X) -> U62(X) a__U51(tt) -> tt a__U51(X) -> U51(X) a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U41(X1, X2) -> U41(X1, X2) a__U42(tt) -> tt a__U42(X) -> U42(X) The set Q consists of the following terms: a__isNatKind(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *A__ISNATKIND(plus(V1, V2)) -> A__U41(a__isNatKind(V1), V2) The graph contains the following edges 1 > 2 *A__ISNATKIND(x(V1, V2)) -> A__U61(a__isNatKind(V1), V2) The graph contains the following edges 1 > 2 *A__U41(tt, V2) -> A__ISNATKIND(V2) The graph contains the following edges 2 >= 1 *A__U61(tt, V2) -> A__ISNATKIND(V2) The graph contains the following edges 2 >= 1 *A__ISNATKIND(plus(V1, V2)) -> A__ISNATKIND(V1) The graph contains the following edges 1 > 1 *A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) The graph contains the following edges 1 > 1 *A__ISNATKIND(x(V1, V2)) -> A__ISNATKIND(V1) The graph contains the following edges 1 > 1 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: A__U12(tt, V1, V2) -> A__U13(a__isNatKind(V2), V1, V2) A__U13(tt, V1, V2) -> A__U14(a__isNatKind(V2), V1, V2) A__U14(tt, V1, V2) -> A__U15(a__isNat(V1), V2) A__U15(tt, V2) -> A__ISNAT(V2) A__ISNAT(plus(V1, V2)) -> A__U11(a__isNatKind(V1), V1, V2) A__U11(tt, V1, V2) -> A__U12(a__isNatKind(V1), V1, V2) A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) A__U21(tt, V1) -> A__U22(a__isNatKind(V1), V1) A__U22(tt, V1) -> A__ISNAT(V1) A__ISNAT(x(V1, V2)) -> A__U31(a__isNatKind(V1), V1, V2) A__U31(tt, V1, V2) -> A__U32(a__isNatKind(V1), V1, V2) A__U32(tt, V1, V2) -> A__U33(a__isNatKind(V2), V1, V2) A__U33(tt, V1, V2) -> A__U34(a__isNatKind(V2), V1, V2) A__U34(tt, V1, V2) -> A__U35(a__isNat(V1), V2) A__U35(tt, V2) -> A__ISNAT(V2) A__U34(tt, V1, V2) -> A__ISNAT(V1) A__U14(tt, V1, V2) -> A__ISNAT(V1) The TRS R consists of the following rules: a__U101(tt, M, N) -> a__U102(a__isNatKind(M), M, N) a__U102(tt, M, N) -> a__U103(a__isNat(N), M, N) a__U103(tt, M, N) -> a__U104(a__isNatKind(N), M, N) a__U104(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U16(tt) -> tt a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U23(tt) -> tt a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U36(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U42(tt) -> tt a__U51(tt) -> tt a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U62(tt) -> tt a__U71(tt, N) -> a__U72(a__isNatKind(N), N) a__U72(tt, N) -> mark(N) a__U81(tt, M, N) -> a__U82(a__isNatKind(M), M, N) a__U82(tt, M, N) -> a__U83(a__isNat(N), M, N) a__U83(tt, M, N) -> a__U84(a__isNatKind(N), M, N) a__U84(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U91(tt, N) -> a__U92(a__isNatKind(N)) a__U92(tt) -> 0 a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__plus(N, 0) -> a__U71(a__isNat(N), N) a__plus(N, s(M)) -> a__U81(a__isNat(M), M, N) a__x(N, 0) -> a__U91(a__isNat(N), N) a__x(N, s(M)) -> a__U101(a__isNat(M), M, N) mark(U101(X1, X2, X3)) -> a__U101(mark(X1), X2, X3) mark(U102(X1, X2, X3)) -> a__U102(mark(X1), X2, X3) mark(isNatKind(X)) -> a__isNatKind(X) mark(U103(X1, X2, X3)) -> a__U103(mark(X1), X2, X3) mark(isNat(X)) -> a__isNat(X) mark(U104(X1, X2, X3)) -> a__U104(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) mark(U13(X1, X2, X3)) -> a__U13(mark(X1), X2, X3) mark(U14(X1, X2, X3)) -> a__U14(mark(X1), X2, X3) mark(U15(X1, X2)) -> a__U15(mark(X1), X2) mark(U16(X)) -> a__U16(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) mark(U32(X1, X2, X3)) -> a__U32(mark(X1), X2, X3) mark(U33(X1, X2, X3)) -> a__U33(mark(X1), X2, X3) mark(U34(X1, X2, X3)) -> a__U34(mark(X1), X2, X3) mark(U35(X1, X2)) -> a__U35(mark(X1), X2) mark(U36(X)) -> a__U36(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X)) -> a__U51(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U81(X1, X2, X3)) -> a__U81(mark(X1), X2, X3) mark(U82(X1, X2, X3)) -> a__U82(mark(X1), X2, X3) mark(U83(X1, X2, X3)) -> a__U83(mark(X1), X2, X3) mark(U84(X1, X2, X3)) -> a__U84(mark(X1), X2, X3) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U101(X1, X2, X3) -> U101(X1, X2, X3) a__U102(X1, X2, X3) -> U102(X1, X2, X3) a__isNatKind(X) -> isNatKind(X) a__U103(X1, X2, X3) -> U103(X1, X2, X3) a__isNat(X) -> isNat(X) a__U104(X1, X2, X3) -> U104(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__x(X1, X2) -> x(X1, X2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(X1, X2) -> U15(X1, X2) a__U16(X) -> U16(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X1, X2) -> U22(X1, X2) a__U23(X) -> U23(X) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(X1, X2) -> U35(X1, X2) a__U36(X) -> U36(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X) -> U51(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X1, X2) -> U72(X1, X2) a__U81(X1, X2, X3) -> U81(X1, X2, X3) a__U82(X1, X2, X3) -> U82(X1, X2, X3) a__U83(X1, X2, X3) -> U83(X1, X2, X3) a__U84(X1, X2, X3) -> U84(X1, X2, X3) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: A__U12(tt, V1, V2) -> A__U13(a__isNatKind(V2), V1, V2) A__U13(tt, V1, V2) -> A__U14(a__isNatKind(V2), V1, V2) A__U14(tt, V1, V2) -> A__U15(a__isNat(V1), V2) A__U15(tt, V2) -> A__ISNAT(V2) A__ISNAT(plus(V1, V2)) -> A__U11(a__isNatKind(V1), V1, V2) A__U11(tt, V1, V2) -> A__U12(a__isNatKind(V1), V1, V2) A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) A__U21(tt, V1) -> A__U22(a__isNatKind(V1), V1) A__U22(tt, V1) -> A__ISNAT(V1) A__ISNAT(x(V1, V2)) -> A__U31(a__isNatKind(V1), V1, V2) A__U31(tt, V1, V2) -> A__U32(a__isNatKind(V1), V1, V2) A__U32(tt, V1, V2) -> A__U33(a__isNatKind(V2), V1, V2) A__U33(tt, V1, V2) -> A__U34(a__isNatKind(V2), V1, V2) A__U34(tt, V1, V2) -> A__U35(a__isNat(V1), V2) A__U35(tt, V2) -> A__ISNAT(V2) A__U34(tt, V1, V2) -> A__ISNAT(V1) A__U14(tt, V1, V2) -> A__ISNAT(V1) The TRS R consists of the following rules: a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNat(X) -> isNat(X) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__isNatKind(X) -> isNatKind(X) a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U35(X1, X2) -> U35(X1, X2) a__U36(tt) -> tt a__U36(X) -> U36(X) a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U61(X1, X2) -> U61(X1, X2) a__U62(tt) -> tt a__U62(X) -> U62(X) a__U51(tt) -> tt a__U51(X) -> U51(X) a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U41(X1, X2) -> U41(X1, X2) a__U42(tt) -> tt a__U42(X) -> U42(X) a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U21(X1, X2) -> U21(X1, X2) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U22(X1, X2) -> U22(X1, X2) a__U23(tt) -> tt a__U23(X) -> U23(X) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U15(X1, X2) -> U15(X1, X2) a__U16(tt) -> tt a__U16(X) -> U16(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__U103(x0, x1, x2) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: A__U12(tt, V1, V2) -> A__U13(a__isNatKind(V2), V1, V2) A__U13(tt, V1, V2) -> A__U14(a__isNatKind(V2), V1, V2) A__U14(tt, V1, V2) -> A__U15(a__isNat(V1), V2) A__U15(tt, V2) -> A__ISNAT(V2) A__ISNAT(plus(V1, V2)) -> A__U11(a__isNatKind(V1), V1, V2) A__U11(tt, V1, V2) -> A__U12(a__isNatKind(V1), V1, V2) A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) A__U21(tt, V1) -> A__U22(a__isNatKind(V1), V1) A__U22(tt, V1) -> A__ISNAT(V1) A__ISNAT(x(V1, V2)) -> A__U31(a__isNatKind(V1), V1, V2) A__U31(tt, V1, V2) -> A__U32(a__isNatKind(V1), V1, V2) A__U32(tt, V1, V2) -> A__U33(a__isNatKind(V2), V1, V2) A__U33(tt, V1, V2) -> A__U34(a__isNatKind(V2), V1, V2) A__U34(tt, V1, V2) -> A__U35(a__isNat(V1), V2) A__U35(tt, V2) -> A__ISNAT(V2) A__U34(tt, V1, V2) -> A__ISNAT(V1) A__U14(tt, V1, V2) -> A__ISNAT(V1) The TRS R consists of the following rules: a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNat(X) -> isNat(X) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__isNatKind(X) -> isNatKind(X) a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U35(X1, X2) -> U35(X1, X2) a__U36(tt) -> tt a__U36(X) -> U36(X) a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U61(X1, X2) -> U61(X1, X2) a__U62(tt) -> tt a__U62(X) -> U62(X) a__U51(tt) -> tt a__U51(X) -> U51(X) a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U41(X1, X2) -> U41(X1, X2) a__U42(tt) -> tt a__U42(X) -> U42(X) a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U21(X1, X2) -> U21(X1, X2) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U22(X1, X2) -> U22(X1, X2) a__U23(tt) -> tt a__U23(X) -> U23(X) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U15(X1, X2) -> U15(X1, X2) a__U16(tt) -> tt a__U16(X) -> U16(X) The set Q consists of the following terms: a__isNatKind(x0) a__isNat(x0) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *A__U13(tt, V1, V2) -> A__U14(a__isNatKind(V2), V1, V2) The graph contains the following edges 2 >= 2, 3 >= 3 *A__U11(tt, V1, V2) -> A__U12(a__isNatKind(V1), V1, V2) The graph contains the following edges 2 >= 2, 3 >= 3 *A__U12(tt, V1, V2) -> A__U13(a__isNatKind(V2), V1, V2) The graph contains the following edges 2 >= 2, 3 >= 3 *A__U15(tt, V2) -> A__ISNAT(V2) The graph contains the following edges 2 >= 1 *A__U14(tt, V1, V2) -> A__U15(a__isNat(V1), V2) The graph contains the following edges 3 >= 2 *A__U14(tt, V1, V2) -> A__ISNAT(V1) The graph contains the following edges 2 >= 1 *A__ISNAT(plus(V1, V2)) -> A__U11(a__isNatKind(V1), V1, V2) The graph contains the following edges 1 > 2, 1 > 3 *A__U21(tt, V1) -> A__U22(a__isNatKind(V1), V1) The graph contains the following edges 2 >= 2 *A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) The graph contains the following edges 1 > 2 *A__ISNAT(x(V1, V2)) -> A__U31(a__isNatKind(V1), V1, V2) The graph contains the following edges 1 > 2, 1 > 3 *A__U22(tt, V1) -> A__ISNAT(V1) The graph contains the following edges 2 >= 1 *A__U31(tt, V1, V2) -> A__U32(a__isNatKind(V1), V1, V2) The graph contains the following edges 2 >= 2, 3 >= 3 *A__U32(tt, V1, V2) -> A__U33(a__isNatKind(V2), V1, V2) The graph contains the following edges 2 >= 2, 3 >= 3 *A__U33(tt, V1, V2) -> A__U34(a__isNatKind(V2), V1, V2) The graph contains the following edges 2 >= 2, 3 >= 3 *A__U34(tt, V1, V2) -> A__U35(a__isNat(V1), V2) The graph contains the following edges 3 >= 2 *A__U34(tt, V1, V2) -> A__ISNAT(V1) The graph contains the following edges 2 >= 1 *A__U35(tt, V2) -> A__ISNAT(V2) The graph contains the following edges 2 >= 1 ---------------------------------------- (18) YES ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: A__U102(tt, M, N) -> A__U103(a__isNat(N), M, N) A__U103(tt, M, N) -> A__U104(a__isNatKind(N), M, N) A__U104(tt, M, N) -> A__PLUS(a__x(mark(N), mark(M)), mark(N)) A__PLUS(N, 0) -> A__U71(a__isNat(N), N) A__U71(tt, N) -> A__U72(a__isNatKind(N), N) A__U72(tt, N) -> MARK(N) MARK(U101(X1, X2, X3)) -> A__U101(mark(X1), X2, X3) A__U101(tt, M, N) -> A__U102(a__isNatKind(M), M, N) MARK(U101(X1, X2, X3)) -> MARK(X1) MARK(U102(X1, X2, X3)) -> A__U102(mark(X1), X2, X3) MARK(U102(X1, X2, X3)) -> MARK(X1) MARK(U103(X1, X2, X3)) -> A__U103(mark(X1), X2, X3) MARK(U103(X1, X2, X3)) -> MARK(X1) MARK(U104(X1, X2, X3)) -> A__U104(mark(X1), X2, X3) A__U104(tt, M, N) -> A__X(mark(N), mark(M)) A__X(N, s(M)) -> A__U101(a__isNat(M), M, N) A__U104(tt, M, N) -> MARK(N) MARK(U104(X1, X2, X3)) -> MARK(X1) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(N, s(M)) -> A__U81(a__isNat(M), M, N) A__U81(tt, M, N) -> A__U82(a__isNatKind(M), M, N) A__U82(tt, M, N) -> A__U83(a__isNat(N), M, N) A__U83(tt, M, N) -> A__U84(a__isNatKind(N), M, N) A__U84(tt, M, N) -> A__PLUS(mark(N), mark(M)) A__U84(tt, M, N) -> MARK(N) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(x(X1, X2)) -> A__X(mark(X1), mark(X2)) MARK(x(X1, X2)) -> MARK(X1) MARK(x(X1, X2)) -> MARK(X2) MARK(U11(X1, X2, X3)) -> MARK(X1) MARK(U12(X1, X2, X3)) -> MARK(X1) MARK(U13(X1, X2, X3)) -> MARK(X1) MARK(U14(X1, X2, X3)) -> MARK(X1) MARK(U15(X1, X2)) -> MARK(X1) MARK(U16(X)) -> MARK(X) MARK(U21(X1, X2)) -> MARK(X1) MARK(U22(X1, X2)) -> MARK(X1) MARK(U23(X)) -> MARK(X) MARK(U31(X1, X2, X3)) -> MARK(X1) MARK(U32(X1, X2, X3)) -> MARK(X1) MARK(U33(X1, X2, X3)) -> MARK(X1) MARK(U34(X1, X2, X3)) -> MARK(X1) MARK(U35(X1, X2)) -> MARK(X1) MARK(U36(X)) -> MARK(X) MARK(U41(X1, X2)) -> MARK(X1) MARK(U42(X)) -> MARK(X) MARK(U51(X)) -> MARK(X) MARK(U61(X1, X2)) -> MARK(X1) MARK(U62(X)) -> MARK(X) MARK(U71(X1, X2)) -> A__U71(mark(X1), X2) MARK(U71(X1, X2)) -> MARK(X1) MARK(U72(X1, X2)) -> A__U72(mark(X1), X2) MARK(U72(X1, X2)) -> MARK(X1) MARK(U81(X1, X2, X3)) -> A__U81(mark(X1), X2, X3) MARK(U81(X1, X2, X3)) -> MARK(X1) MARK(U82(X1, X2, X3)) -> A__U82(mark(X1), X2, X3) MARK(U82(X1, X2, X3)) -> MARK(X1) MARK(U83(X1, X2, X3)) -> A__U83(mark(X1), X2, X3) MARK(U83(X1, X2, X3)) -> MARK(X1) MARK(U84(X1, X2, X3)) -> A__U84(mark(X1), X2, X3) A__U84(tt, M, N) -> MARK(M) MARK(U84(X1, X2, X3)) -> MARK(X1) MARK(U91(X1, X2)) -> MARK(X1) MARK(U92(X)) -> MARK(X) MARK(s(X)) -> MARK(X) A__U104(tt, M, N) -> MARK(M) The TRS R consists of the following rules: a__U101(tt, M, N) -> a__U102(a__isNatKind(M), M, N) a__U102(tt, M, N) -> a__U103(a__isNat(N), M, N) a__U103(tt, M, N) -> a__U104(a__isNatKind(N), M, N) a__U104(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U16(tt) -> tt a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U23(tt) -> tt a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U36(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U42(tt) -> tt a__U51(tt) -> tt a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U62(tt) -> tt a__U71(tt, N) -> a__U72(a__isNatKind(N), N) a__U72(tt, N) -> mark(N) a__U81(tt, M, N) -> a__U82(a__isNatKind(M), M, N) a__U82(tt, M, N) -> a__U83(a__isNat(N), M, N) a__U83(tt, M, N) -> a__U84(a__isNatKind(N), M, N) a__U84(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U91(tt, N) -> a__U92(a__isNatKind(N)) a__U92(tt) -> 0 a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__plus(N, 0) -> a__U71(a__isNat(N), N) a__plus(N, s(M)) -> a__U81(a__isNat(M), M, N) a__x(N, 0) -> a__U91(a__isNat(N), N) a__x(N, s(M)) -> a__U101(a__isNat(M), M, N) mark(U101(X1, X2, X3)) -> a__U101(mark(X1), X2, X3) mark(U102(X1, X2, X3)) -> a__U102(mark(X1), X2, X3) mark(isNatKind(X)) -> a__isNatKind(X) mark(U103(X1, X2, X3)) -> a__U103(mark(X1), X2, X3) mark(isNat(X)) -> a__isNat(X) mark(U104(X1, X2, X3)) -> a__U104(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) mark(U13(X1, X2, X3)) -> a__U13(mark(X1), X2, X3) mark(U14(X1, X2, X3)) -> a__U14(mark(X1), X2, X3) mark(U15(X1, X2)) -> a__U15(mark(X1), X2) mark(U16(X)) -> a__U16(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) mark(U32(X1, X2, X3)) -> a__U32(mark(X1), X2, X3) mark(U33(X1, X2, X3)) -> a__U33(mark(X1), X2, X3) mark(U34(X1, X2, X3)) -> a__U34(mark(X1), X2, X3) mark(U35(X1, X2)) -> a__U35(mark(X1), X2) mark(U36(X)) -> a__U36(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X)) -> a__U51(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U81(X1, X2, X3)) -> a__U81(mark(X1), X2, X3) mark(U82(X1, X2, X3)) -> a__U82(mark(X1), X2, X3) mark(U83(X1, X2, X3)) -> a__U83(mark(X1), X2, X3) mark(U84(X1, X2, X3)) -> a__U84(mark(X1), X2, X3) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U101(X1, X2, X3) -> U101(X1, X2, X3) a__U102(X1, X2, X3) -> U102(X1, X2, X3) a__isNatKind(X) -> isNatKind(X) a__U103(X1, X2, X3) -> U103(X1, X2, X3) a__isNat(X) -> isNat(X) a__U104(X1, X2, X3) -> U104(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__x(X1, X2) -> x(X1, X2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(X1, X2) -> U15(X1, X2) a__U16(X) -> U16(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X1, X2) -> U22(X1, X2) a__U23(X) -> U23(X) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(X1, X2) -> U35(X1, X2) a__U36(X) -> U36(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X) -> U51(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X1, X2) -> U72(X1, X2) a__U81(X1, X2, X3) -> U81(X1, X2, X3) a__U82(X1, X2, X3) -> U82(X1, X2, X3) a__U83(X1, X2, X3) -> U83(X1, X2, X3) a__U84(X1, X2, X3) -> U84(X1, X2, X3) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A__U104(tt, M, N) -> A__PLUS(a__x(mark(N), mark(M)), mark(N)) A__PLUS(N, 0) -> A__U71(a__isNat(N), N) MARK(U101(X1, X2, X3)) -> MARK(X1) MARK(U102(X1, X2, X3)) -> MARK(X1) MARK(U103(X1, X2, X3)) -> MARK(X1) A__U104(tt, M, N) -> A__X(mark(N), mark(M)) A__X(N, s(M)) -> A__U101(a__isNat(M), M, N) A__U104(tt, M, N) -> MARK(N) MARK(U104(X1, X2, X3)) -> MARK(X1) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) A__PLUS(N, s(M)) -> A__U81(a__isNat(M), M, N) A__U83(tt, M, N) -> A__U84(a__isNatKind(N), M, N) A__U84(tt, M, N) -> MARK(N) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(x(X1, X2)) -> MARK(X1) MARK(x(X1, X2)) -> MARK(X2) MARK(U71(X1, X2)) -> A__U71(mark(X1), X2) MARK(U71(X1, X2)) -> MARK(X1) MARK(U72(X1, X2)) -> A__U72(mark(X1), X2) MARK(U72(X1, X2)) -> MARK(X1) MARK(U81(X1, X2, X3)) -> A__U81(mark(X1), X2, X3) MARK(U81(X1, X2, X3)) -> MARK(X1) MARK(U82(X1, X2, X3)) -> A__U82(mark(X1), X2, X3) MARK(U82(X1, X2, X3)) -> MARK(X1) MARK(U83(X1, X2, X3)) -> A__U83(mark(X1), X2, X3) MARK(U83(X1, X2, X3)) -> MARK(X1) MARK(U84(X1, X2, X3)) -> A__U84(mark(X1), X2, X3) A__U84(tt, M, N) -> MARK(M) MARK(U84(X1, X2, X3)) -> MARK(X1) MARK(U91(X1, X2)) -> MARK(X1) MARK(s(X)) -> MARK(X) A__U104(tt, M, N) -> MARK(M) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. A__U102(x1, x2, x3) = A__U102(x1, x2, x3) tt = tt A__U103(x1, x2, x3) = A__U103(x1, x2, x3) a__isNat(x1) = a__isNat A__U104(x1, x2, x3) = A__U104(x1, x2, x3) a__isNatKind(x1) = a__isNatKind A__PLUS(x1, x2) = A__PLUS(x1, x2) a__x(x1, x2) = a__x(x1, x2) mark(x1) = x1 0 = 0 A__U71(x1, x2) = x2 A__U72(x1, x2) = x2 MARK(x1) = x1 U101(x1, x2, x3) = U101(x1, x2, x3) A__U101(x1, x2, x3) = A__U101(x1, x2, x3) U102(x1, x2, x3) = U102(x1, x2, x3) U103(x1, x2, x3) = U103(x1, x2, x3) U104(x1, x2, x3) = U104(x1, x2, x3) A__X(x1, x2) = A__X(x1, x2) s(x1) = s(x1) plus(x1, x2) = plus(x1, x2) A__U81(x1, x2, x3) = A__U81(x1, x2, x3) A__U82(x1, x2, x3) = A__U82(x1, x2, x3) A__U83(x1, x2, x3) = A__U83(x1, x2, x3) A__U84(x1, x2, x3) = A__U84(x2, x3) x(x1, x2) = x(x1, x2) U11(x1, x2, x3) = x1 U12(x1, x2, x3) = x1 U13(x1, x2, x3) = x1 U14(x1, x2, x3) = x1 U15(x1, x2) = x1 U16(x1) = x1 U21(x1, x2) = x1 U22(x1, x2) = x1 U23(x1) = x1 U31(x1, x2, x3) = x1 U32(x1, x2, x3) = x1 U33(x1, x2, x3) = x1 U34(x1, x2, x3) = x1 U35(x1, x2) = x1 U36(x1) = x1 U41(x1, x2) = x1 U42(x1) = x1 U51(x1) = x1 U61(x1, x2) = x1 U62(x1) = x1 U71(x1, x2) = U71(x1, x2) U72(x1, x2) = U72(x1, x2) U81(x1, x2, x3) = U81(x1, x2, x3) U82(x1, x2, x3) = U82(x1, x2, x3) U83(x1, x2, x3) = U83(x1, x2, x3) U84(x1, x2, x3) = U84(x1, x2, x3) U91(x1, x2) = U91(x1, x2) U92(x1) = x1 a__U11(x1, x2, x3) = x1 a__U21(x1, x2) = x1 a__U31(x1, x2, x3) = x1 isNat(x1) = isNat a__U41(x1, x2) = x1 a__U51(x1) = x1 a__U61(x1, x2) = x1 isNatKind(x1) = isNatKind a__U102(x1, x2, x3) = a__U102(x1, x2, x3) a__U103(x1, x2, x3) = a__U103(x1, x2, x3) a__U104(x1, x2, x3) = a__U104(x1, x2, x3) a__plus(x1, x2) = a__plus(x1, x2) a__U71(x1, x2) = a__U71(x1, x2) a__U72(x1, x2) = a__U72(x1, x2) a__U101(x1, x2, x3) = a__U101(x1, x2, x3) a__U12(x1, x2, x3) = x1 a__U13(x1, x2, x3) = x1 a__U14(x1, x2, x3) = x1 a__U15(x1, x2) = x1 a__U16(x1) = x1 a__U22(x1, x2) = x1 a__U23(x1) = x1 a__U32(x1, x2, x3) = x1 a__U33(x1, x2, x3) = x1 a__U34(x1, x2, x3) = x1 a__U35(x1, x2) = x1 a__U36(x1) = x1 a__U42(x1) = x1 a__U62(x1) = x1 a__U81(x1, x2, x3) = a__U81(x1, x2, x3) a__U82(x1, x2, x3) = a__U82(x1, x2, x3) a__U83(x1, x2, x3) = a__U83(x1, x2, x3) a__U84(x1, x2, x3) = a__U84(x1, x2, x3) a__U91(x1, x2) = a__U91(x1, x2) a__U92(x1) = x1 Recursive path order with status [RPO]. Quasi-Precedence: [A__U102_3, A__U103_3, A__U104_3, a__x_2, U101_3, A__U101_3, U102_3, U103_3, U104_3, A__X_2, x_2, a__U102_3, a__U103_3, a__U104_3, a__U101_3] > [plus_2, U81_3, U82_3, U83_3, U84_3, a__plus_2, a__U81_3, a__U82_3, a__U83_3, a__U84_3] > [A__PLUS_2, A__U81_3, A__U82_3, A__U83_3, A__U84_2] > [tt, a__isNat, a__isNatKind, U91_2, isNat, isNatKind, a__U91_2] > 0 > [U71_2, U72_2, a__U71_2, a__U72_2] [A__U102_3, A__U103_3, A__U104_3, a__x_2, U101_3, A__U101_3, U102_3, U103_3, U104_3, A__X_2, x_2, a__U102_3, a__U103_3, a__U104_3, a__U101_3] > [plus_2, U81_3, U82_3, U83_3, U84_3, a__plus_2, a__U81_3, a__U82_3, a__U83_3, a__U84_3] > s_1 > [tt, a__isNat, a__isNatKind, U91_2, isNat, isNatKind, a__U91_2] > 0 > [U71_2, U72_2, a__U71_2, a__U72_2] Status: A__U102_3: multiset status tt: multiset status A__U103_3: multiset status a__isNat: multiset status A__U104_3: multiset status a__isNatKind: multiset status A__PLUS_2: multiset status a__x_2: multiset status 0: multiset status U101_3: multiset status A__U101_3: multiset status U102_3: multiset status U103_3: multiset status U104_3: multiset status A__X_2: multiset status s_1: [1] plus_2: multiset status A__U81_3: multiset status A__U82_3: multiset status A__U83_3: multiset status A__U84_2: multiset status x_2: multiset status U71_2: multiset status U72_2: multiset status U81_3: multiset status U82_3: multiset status U83_3: multiset status U84_3: multiset status U91_2: multiset status isNat: multiset status isNatKind: multiset status a__U102_3: multiset status a__U103_3: multiset status a__U104_3: multiset status a__plus_2: multiset status a__U71_2: multiset status a__U72_2: multiset status a__U101_3: multiset status a__U81_3: multiset status a__U82_3: multiset status a__U83_3: multiset status a__U84_3: multiset status a__U91_2: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNat(X) -> isNat(X) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__isNatKind(X) -> isNatKind(X) a__U102(tt, M, N) -> a__U103(a__isNat(N), M, N) a__U103(tt, M, N) -> a__U104(a__isNatKind(N), M, N) a__U104(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__plus(N, 0) -> a__U71(a__isNat(N), N) a__U71(tt, N) -> a__U72(a__isNatKind(N), N) a__U72(tt, N) -> mark(N) mark(U101(X1, X2, X3)) -> a__U101(mark(X1), X2, X3) a__U101(tt, M, N) -> a__U102(a__isNatKind(M), M, N) mark(U102(X1, X2, X3)) -> a__U102(mark(X1), X2, X3) mark(U103(X1, X2, X3)) -> a__U103(mark(X1), X2, X3) mark(U104(X1, X2, X3)) -> a__U104(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) a__x(N, s(M)) -> a__U101(a__isNat(M), M, N) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(isNatKind(X)) -> a__isNatKind(X) mark(isNat(X)) -> a__isNat(X) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) mark(U13(X1, X2, X3)) -> a__U13(mark(X1), X2, X3) mark(U14(X1, X2, X3)) -> a__U14(mark(X1), X2, X3) mark(U15(X1, X2)) -> a__U15(mark(X1), X2) mark(U16(X)) -> a__U16(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) mark(U32(X1, X2, X3)) -> a__U32(mark(X1), X2, X3) mark(U33(X1, X2, X3)) -> a__U33(mark(X1), X2, X3) mark(U34(X1, X2, X3)) -> a__U34(mark(X1), X2, X3) mark(U35(X1, X2)) -> a__U35(mark(X1), X2) mark(U36(X)) -> a__U36(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X)) -> a__U51(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U81(X1, X2, X3)) -> a__U81(mark(X1), X2, X3) mark(U82(X1, X2, X3)) -> a__U82(mark(X1), X2, X3) mark(U83(X1, X2, X3)) -> a__U83(mark(X1), X2, X3) mark(U84(X1, X2, X3)) -> a__U84(mark(X1), X2, X3) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__x(N, 0) -> a__U91(a__isNat(N), N) a__x(X1, X2) -> x(X1, X2) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U15(X1, X2) -> U15(X1, X2) a__U16(tt) -> tt a__U16(X) -> U16(X) a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U21(X1, X2) -> U21(X1, X2) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U22(X1, X2) -> U22(X1, X2) a__U23(tt) -> tt a__U23(X) -> U23(X) a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U35(X1, X2) -> U35(X1, X2) a__U36(tt) -> tt a__U36(X) -> U36(X) a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U41(X1, X2) -> U41(X1, X2) a__U42(tt) -> tt a__U42(X) -> U42(X) a__U51(tt) -> tt a__U51(X) -> U51(X) a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U61(X1, X2) -> U61(X1, X2) a__U62(tt) -> tt a__U62(X) -> U62(X) a__U81(X1, X2, X3) -> U81(X1, X2, X3) a__U82(X1, X2, X3) -> U82(X1, X2, X3) a__U83(X1, X2, X3) -> U83(X1, X2, X3) a__U84(X1, X2, X3) -> U84(X1, X2, X3) a__U91(tt, N) -> a__U92(a__isNatKind(N)) a__U91(X1, X2) -> U91(X1, X2) a__U92(tt) -> 0 a__U92(X) -> U92(X) a__U103(X1, X2, X3) -> U103(X1, X2, X3) a__U104(X1, X2, X3) -> U104(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__U71(X1, X2) -> U71(X1, X2) a__U72(X1, X2) -> U72(X1, X2) a__U101(X1, X2, X3) -> U101(X1, X2, X3) a__U102(X1, X2, X3) -> U102(X1, X2, X3) a__plus(N, s(M)) -> a__U81(a__isNat(M), M, N) a__U81(tt, M, N) -> a__U82(a__isNatKind(M), M, N) a__U82(tt, M, N) -> a__U83(a__isNat(N), M, N) a__U83(tt, M, N) -> a__U84(a__isNatKind(N), M, N) a__U84(tt, M, N) -> s(a__plus(mark(N), mark(M))) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: A__U102(tt, M, N) -> A__U103(a__isNat(N), M, N) A__U103(tt, M, N) -> A__U104(a__isNatKind(N), M, N) A__U71(tt, N) -> A__U72(a__isNatKind(N), N) A__U72(tt, N) -> MARK(N) MARK(U101(X1, X2, X3)) -> A__U101(mark(X1), X2, X3) A__U101(tt, M, N) -> A__U102(a__isNatKind(M), M, N) MARK(U102(X1, X2, X3)) -> A__U102(mark(X1), X2, X3) MARK(U103(X1, X2, X3)) -> A__U103(mark(X1), X2, X3) MARK(U104(X1, X2, X3)) -> A__U104(mark(X1), X2, X3) A__U81(tt, M, N) -> A__U82(a__isNatKind(M), M, N) A__U82(tt, M, N) -> A__U83(a__isNat(N), M, N) A__U84(tt, M, N) -> A__PLUS(mark(N), mark(M)) MARK(x(X1, X2)) -> A__X(mark(X1), mark(X2)) MARK(U11(X1, X2, X3)) -> MARK(X1) MARK(U12(X1, X2, X3)) -> MARK(X1) MARK(U13(X1, X2, X3)) -> MARK(X1) MARK(U14(X1, X2, X3)) -> MARK(X1) MARK(U15(X1, X2)) -> MARK(X1) MARK(U16(X)) -> MARK(X) MARK(U21(X1, X2)) -> MARK(X1) MARK(U22(X1, X2)) -> MARK(X1) MARK(U23(X)) -> MARK(X) MARK(U31(X1, X2, X3)) -> MARK(X1) MARK(U32(X1, X2, X3)) -> MARK(X1) MARK(U33(X1, X2, X3)) -> MARK(X1) MARK(U34(X1, X2, X3)) -> MARK(X1) MARK(U35(X1, X2)) -> MARK(X1) MARK(U36(X)) -> MARK(X) MARK(U41(X1, X2)) -> MARK(X1) MARK(U42(X)) -> MARK(X) MARK(U51(X)) -> MARK(X) MARK(U61(X1, X2)) -> MARK(X1) MARK(U62(X)) -> MARK(X) MARK(U92(X)) -> MARK(X) The TRS R consists of the following rules: a__U101(tt, M, N) -> a__U102(a__isNatKind(M), M, N) a__U102(tt, M, N) -> a__U103(a__isNat(N), M, N) a__U103(tt, M, N) -> a__U104(a__isNatKind(N), M, N) a__U104(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U16(tt) -> tt a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U23(tt) -> tt a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U36(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U42(tt) -> tt a__U51(tt) -> tt a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U62(tt) -> tt a__U71(tt, N) -> a__U72(a__isNatKind(N), N) a__U72(tt, N) -> mark(N) a__U81(tt, M, N) -> a__U82(a__isNatKind(M), M, N) a__U82(tt, M, N) -> a__U83(a__isNat(N), M, N) a__U83(tt, M, N) -> a__U84(a__isNatKind(N), M, N) a__U84(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U91(tt, N) -> a__U92(a__isNatKind(N)) a__U92(tt) -> 0 a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__plus(N, 0) -> a__U71(a__isNat(N), N) a__plus(N, s(M)) -> a__U81(a__isNat(M), M, N) a__x(N, 0) -> a__U91(a__isNat(N), N) a__x(N, s(M)) -> a__U101(a__isNat(M), M, N) mark(U101(X1, X2, X3)) -> a__U101(mark(X1), X2, X3) mark(U102(X1, X2, X3)) -> a__U102(mark(X1), X2, X3) mark(isNatKind(X)) -> a__isNatKind(X) mark(U103(X1, X2, X3)) -> a__U103(mark(X1), X2, X3) mark(isNat(X)) -> a__isNat(X) mark(U104(X1, X2, X3)) -> a__U104(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) mark(U13(X1, X2, X3)) -> a__U13(mark(X1), X2, X3) mark(U14(X1, X2, X3)) -> a__U14(mark(X1), X2, X3) mark(U15(X1, X2)) -> a__U15(mark(X1), X2) mark(U16(X)) -> a__U16(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) mark(U32(X1, X2, X3)) -> a__U32(mark(X1), X2, X3) mark(U33(X1, X2, X3)) -> a__U33(mark(X1), X2, X3) mark(U34(X1, X2, X3)) -> a__U34(mark(X1), X2, X3) mark(U35(X1, X2)) -> a__U35(mark(X1), X2) mark(U36(X)) -> a__U36(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X)) -> a__U51(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U81(X1, X2, X3)) -> a__U81(mark(X1), X2, X3) mark(U82(X1, X2, X3)) -> a__U82(mark(X1), X2, X3) mark(U83(X1, X2, X3)) -> a__U83(mark(X1), X2, X3) mark(U84(X1, X2, X3)) -> a__U84(mark(X1), X2, X3) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U101(X1, X2, X3) -> U101(X1, X2, X3) a__U102(X1, X2, X3) -> U102(X1, X2, X3) a__isNatKind(X) -> isNatKind(X) a__U103(X1, X2, X3) -> U103(X1, X2, X3) a__isNat(X) -> isNat(X) a__U104(X1, X2, X3) -> U104(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__x(X1, X2) -> x(X1, X2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(X1, X2) -> U15(X1, X2) a__U16(X) -> U16(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X1, X2) -> U22(X1, X2) a__U23(X) -> U23(X) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(X1, X2) -> U35(X1, X2) a__U36(X) -> U36(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X) -> U51(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X1, X2) -> U72(X1, X2) a__U81(X1, X2, X3) -> U81(X1, X2, X3) a__U82(X1, X2, X3) -> U82(X1, X2, X3) a__U83(X1, X2, X3) -> U83(X1, X2, X3) a__U84(X1, X2, X3) -> U84(X1, X2, X3) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 13 less nodes. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U12(X1, X2, X3)) -> MARK(X1) MARK(U11(X1, X2, X3)) -> MARK(X1) MARK(U13(X1, X2, X3)) -> MARK(X1) MARK(U14(X1, X2, X3)) -> MARK(X1) MARK(U15(X1, X2)) -> MARK(X1) MARK(U16(X)) -> MARK(X) MARK(U21(X1, X2)) -> MARK(X1) MARK(U22(X1, X2)) -> MARK(X1) MARK(U23(X)) -> MARK(X) MARK(U31(X1, X2, X3)) -> MARK(X1) MARK(U32(X1, X2, X3)) -> MARK(X1) MARK(U33(X1, X2, X3)) -> MARK(X1) MARK(U34(X1, X2, X3)) -> MARK(X1) MARK(U35(X1, X2)) -> MARK(X1) MARK(U36(X)) -> MARK(X) MARK(U41(X1, X2)) -> MARK(X1) MARK(U42(X)) -> MARK(X) MARK(U51(X)) -> MARK(X) MARK(U61(X1, X2)) -> MARK(X1) MARK(U62(X)) -> MARK(X) MARK(U92(X)) -> MARK(X) The TRS R consists of the following rules: a__U101(tt, M, N) -> a__U102(a__isNatKind(M), M, N) a__U102(tt, M, N) -> a__U103(a__isNat(N), M, N) a__U103(tt, M, N) -> a__U104(a__isNatKind(N), M, N) a__U104(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__U11(tt, V1, V2) -> a__U12(a__isNatKind(V1), V1, V2) a__U12(tt, V1, V2) -> a__U13(a__isNatKind(V2), V1, V2) a__U13(tt, V1, V2) -> a__U14(a__isNatKind(V2), V1, V2) a__U14(tt, V1, V2) -> a__U15(a__isNat(V1), V2) a__U15(tt, V2) -> a__U16(a__isNat(V2)) a__U16(tt) -> tt a__U21(tt, V1) -> a__U22(a__isNatKind(V1), V1) a__U22(tt, V1) -> a__U23(a__isNat(V1)) a__U23(tt) -> tt a__U31(tt, V1, V2) -> a__U32(a__isNatKind(V1), V1, V2) a__U32(tt, V1, V2) -> a__U33(a__isNatKind(V2), V1, V2) a__U33(tt, V1, V2) -> a__U34(a__isNatKind(V2), V1, V2) a__U34(tt, V1, V2) -> a__U35(a__isNat(V1), V2) a__U35(tt, V2) -> a__U36(a__isNat(V2)) a__U36(tt) -> tt a__U41(tt, V2) -> a__U42(a__isNatKind(V2)) a__U42(tt) -> tt a__U51(tt) -> tt a__U61(tt, V2) -> a__U62(a__isNatKind(V2)) a__U62(tt) -> tt a__U71(tt, N) -> a__U72(a__isNatKind(N), N) a__U72(tt, N) -> mark(N) a__U81(tt, M, N) -> a__U82(a__isNatKind(M), M, N) a__U82(tt, M, N) -> a__U83(a__isNat(N), M, N) a__U83(tt, M, N) -> a__U84(a__isNatKind(N), M, N) a__U84(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U91(tt, N) -> a__U92(a__isNatKind(N)) a__U92(tt) -> 0 a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNatKind(V1), V1, V2) a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) a__isNat(x(V1, V2)) -> a__U31(a__isNatKind(V1), V1, V2) a__isNatKind(0) -> tt a__isNatKind(plus(V1, V2)) -> a__U41(a__isNatKind(V1), V2) a__isNatKind(s(V1)) -> a__U51(a__isNatKind(V1)) a__isNatKind(x(V1, V2)) -> a__U61(a__isNatKind(V1), V2) a__plus(N, 0) -> a__U71(a__isNat(N), N) a__plus(N, s(M)) -> a__U81(a__isNat(M), M, N) a__x(N, 0) -> a__U91(a__isNat(N), N) a__x(N, s(M)) -> a__U101(a__isNat(M), M, N) mark(U101(X1, X2, X3)) -> a__U101(mark(X1), X2, X3) mark(U102(X1, X2, X3)) -> a__U102(mark(X1), X2, X3) mark(isNatKind(X)) -> a__isNatKind(X) mark(U103(X1, X2, X3)) -> a__U103(mark(X1), X2, X3) mark(isNat(X)) -> a__isNat(X) mark(U104(X1, X2, X3)) -> a__U104(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(U11(X1, X2, X3)) -> a__U11(mark(X1), X2, X3) mark(U12(X1, X2, X3)) -> a__U12(mark(X1), X2, X3) mark(U13(X1, X2, X3)) -> a__U13(mark(X1), X2, X3) mark(U14(X1, X2, X3)) -> a__U14(mark(X1), X2, X3) mark(U15(X1, X2)) -> a__U15(mark(X1), X2) mark(U16(X)) -> a__U16(mark(X)) mark(U21(X1, X2)) -> a__U21(mark(X1), X2) mark(U22(X1, X2)) -> a__U22(mark(X1), X2) mark(U23(X)) -> a__U23(mark(X)) mark(U31(X1, X2, X3)) -> a__U31(mark(X1), X2, X3) mark(U32(X1, X2, X3)) -> a__U32(mark(X1), X2, X3) mark(U33(X1, X2, X3)) -> a__U33(mark(X1), X2, X3) mark(U34(X1, X2, X3)) -> a__U34(mark(X1), X2, X3) mark(U35(X1, X2)) -> a__U35(mark(X1), X2) mark(U36(X)) -> a__U36(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U42(X)) -> a__U42(mark(X)) mark(U51(X)) -> a__U51(mark(X)) mark(U61(X1, X2)) -> a__U61(mark(X1), X2) mark(U62(X)) -> a__U62(mark(X)) mark(U71(X1, X2)) -> a__U71(mark(X1), X2) mark(U72(X1, X2)) -> a__U72(mark(X1), X2) mark(U81(X1, X2, X3)) -> a__U81(mark(X1), X2, X3) mark(U82(X1, X2, X3)) -> a__U82(mark(X1), X2, X3) mark(U83(X1, X2, X3)) -> a__U83(mark(X1), X2, X3) mark(U84(X1, X2, X3)) -> a__U84(mark(X1), X2, X3) mark(U91(X1, X2)) -> a__U91(mark(X1), X2) mark(U92(X)) -> a__U92(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U101(X1, X2, X3) -> U101(X1, X2, X3) a__U102(X1, X2, X3) -> U102(X1, X2, X3) a__isNatKind(X) -> isNatKind(X) a__U103(X1, X2, X3) -> U103(X1, X2, X3) a__isNat(X) -> isNat(X) a__U104(X1, X2, X3) -> U104(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__x(X1, X2) -> x(X1, X2) a__U11(X1, X2, X3) -> U11(X1, X2, X3) a__U12(X1, X2, X3) -> U12(X1, X2, X3) a__U13(X1, X2, X3) -> U13(X1, X2, X3) a__U14(X1, X2, X3) -> U14(X1, X2, X3) a__U15(X1, X2) -> U15(X1, X2) a__U16(X) -> U16(X) a__U21(X1, X2) -> U21(X1, X2) a__U22(X1, X2) -> U22(X1, X2) a__U23(X) -> U23(X) a__U31(X1, X2, X3) -> U31(X1, X2, X3) a__U32(X1, X2, X3) -> U32(X1, X2, X3) a__U33(X1, X2, X3) -> U33(X1, X2, X3) a__U34(X1, X2, X3) -> U34(X1, X2, X3) a__U35(X1, X2) -> U35(X1, X2) a__U36(X) -> U36(X) a__U41(X1, X2) -> U41(X1, X2) a__U42(X) -> U42(X) a__U51(X) -> U51(X) a__U61(X1, X2) -> U61(X1, X2) a__U62(X) -> U62(X) a__U71(X1, X2) -> U71(X1, X2) a__U72(X1, X2) -> U72(X1, X2) a__U81(X1, X2, X3) -> U81(X1, X2, X3) a__U82(X1, X2, X3) -> U82(X1, X2, X3) a__U83(X1, X2, X3) -> U83(X1, X2, X3) a__U84(X1, X2, X3) -> U84(X1, X2, X3) a__U91(X1, X2) -> U91(X1, X2) a__U92(X) -> U92(X) The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U12(X1, X2, X3)) -> MARK(X1) MARK(U11(X1, X2, X3)) -> MARK(X1) MARK(U13(X1, X2, X3)) -> MARK(X1) MARK(U14(X1, X2, X3)) -> MARK(X1) MARK(U15(X1, X2)) -> MARK(X1) MARK(U16(X)) -> MARK(X) MARK(U21(X1, X2)) -> MARK(X1) MARK(U22(X1, X2)) -> MARK(X1) MARK(U23(X)) -> MARK(X) MARK(U31(X1, X2, X3)) -> MARK(X1) MARK(U32(X1, X2, X3)) -> MARK(X1) MARK(U33(X1, X2, X3)) -> MARK(X1) MARK(U34(X1, X2, X3)) -> MARK(X1) MARK(U35(X1, X2)) -> MARK(X1) MARK(U36(X)) -> MARK(X) MARK(U41(X1, X2)) -> MARK(X1) MARK(U42(X)) -> MARK(X) MARK(U51(X)) -> MARK(X) MARK(U61(X1, X2)) -> MARK(X1) MARK(U62(X)) -> MARK(X) MARK(U92(X)) -> MARK(X) R is empty. The set Q consists of the following terms: mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. mark(U101(x0, x1, x2)) mark(U102(x0, x1, x2)) mark(isNatKind(x0)) mark(U103(x0, x1, x2)) mark(isNat(x0)) mark(U104(x0, x1, x2)) mark(plus(x0, x1)) mark(x(x0, x1)) mark(U11(x0, x1, x2)) mark(U12(x0, x1, x2)) mark(U13(x0, x1, x2)) mark(U14(x0, x1, x2)) mark(U15(x0, x1)) mark(U16(x0)) mark(U21(x0, x1)) mark(U22(x0, x1)) mark(U23(x0)) mark(U31(x0, x1, x2)) mark(U32(x0, x1, x2)) mark(U33(x0, x1, x2)) mark(U34(x0, x1, x2)) mark(U35(x0, x1)) mark(U36(x0)) mark(U41(x0, x1)) mark(U42(x0)) mark(U51(x0)) mark(U61(x0, x1)) mark(U62(x0)) mark(U71(x0, x1)) mark(U72(x0, x1)) mark(U81(x0, x1, x2)) mark(U82(x0, x1, x2)) mark(U83(x0, x1, x2)) mark(U84(x0, x1, x2)) mark(U91(x0, x1)) mark(U92(x0)) mark(tt) mark(s(x0)) mark(0) a__U101(x0, x1, x2) a__U102(x0, x1, x2) a__isNatKind(x0) a__U103(x0, x1, x2) a__isNat(x0) a__U104(x0, x1, x2) a__plus(x0, x1) a__x(x0, x1) a__U11(x0, x1, x2) a__U12(x0, x1, x2) a__U13(x0, x1, x2) a__U14(x0, x1, x2) a__U15(x0, x1) a__U16(x0) a__U21(x0, x1) a__U22(x0, x1) a__U23(x0) a__U31(x0, x1, x2) a__U32(x0, x1, x2) a__U33(x0, x1, x2) a__U34(x0, x1, x2) a__U35(x0, x1) a__U36(x0) a__U41(x0, x1) a__U42(x0) a__U51(x0) a__U61(x0, x1) a__U62(x0) a__U71(x0, x1) a__U72(x0, x1) a__U81(x0, x1, x2) a__U82(x0, x1, x2) a__U83(x0, x1, x2) a__U84(x0, x1, x2) a__U91(x0, x1) a__U92(x0) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U12(X1, X2, X3)) -> MARK(X1) MARK(U11(X1, X2, X3)) -> MARK(X1) MARK(U13(X1, X2, X3)) -> MARK(X1) MARK(U14(X1, X2, X3)) -> MARK(X1) MARK(U15(X1, X2)) -> MARK(X1) MARK(U16(X)) -> MARK(X) MARK(U21(X1, X2)) -> MARK(X1) MARK(U22(X1, X2)) -> MARK(X1) MARK(U23(X)) -> MARK(X) MARK(U31(X1, X2, X3)) -> MARK(X1) MARK(U32(X1, X2, X3)) -> MARK(X1) MARK(U33(X1, X2, X3)) -> MARK(X1) MARK(U34(X1, X2, X3)) -> MARK(X1) MARK(U35(X1, X2)) -> MARK(X1) MARK(U36(X)) -> MARK(X) MARK(U41(X1, X2)) -> MARK(X1) MARK(U42(X)) -> MARK(X) MARK(U51(X)) -> MARK(X) MARK(U61(X1, X2)) -> MARK(X1) MARK(U62(X)) -> MARK(X) MARK(U92(X)) -> MARK(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MARK(U12(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U11(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U13(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U14(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U15(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U16(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U21(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U22(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U23(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U31(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U32(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U33(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U34(X1, X2, X3)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U35(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U36(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U41(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U42(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U51(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U61(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U62(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U92(X)) -> MARK(X) The graph contains the following edges 1 > 1 ---------------------------------------- (29) YES