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, 80 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) QDPOrderProof [EQUIVALENT, 8723 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) TRUE ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: U101(tt, M, N) -> U102(isNatKind(activate(M)), activate(M), activate(N)) U102(tt, M, N) -> U103(isNat(activate(N)), activate(M), activate(N)) U103(tt, M, N) -> U104(isNatKind(activate(N)), activate(M), activate(N)) U104(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) U11(tt, V1, V2) -> U12(isNatKind(activate(V1)), activate(V1), activate(V2)) U12(tt, V1, V2) -> U13(isNatKind(activate(V2)), activate(V1), activate(V2)) U13(tt, V1, V2) -> U14(isNatKind(activate(V2)), activate(V1), activate(V2)) U14(tt, V1, V2) -> U15(isNat(activate(V1)), activate(V2)) U15(tt, V2) -> U16(isNat(activate(V2))) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(activate(V1)), activate(V1)) U22(tt, V1) -> U23(isNat(activate(V1))) U23(tt) -> tt U31(tt, V1, V2) -> U32(isNatKind(activate(V1)), activate(V1), activate(V2)) U32(tt, V1, V2) -> U33(isNatKind(activate(V2)), activate(V1), activate(V2)) U33(tt, V1, V2) -> U34(isNatKind(activate(V2)), activate(V1), activate(V2)) U34(tt, V1, V2) -> U35(isNat(activate(V1)), activate(V2)) U35(tt, V2) -> U36(isNat(activate(V2))) U36(tt) -> tt U41(tt, V2) -> U42(isNatKind(activate(V2))) U42(tt) -> tt U51(tt) -> tt U61(tt, V2) -> U62(isNatKind(activate(V2))) U62(tt) -> tt U71(tt, N) -> U72(isNatKind(activate(N)), activate(N)) U72(tt, N) -> activate(N) U81(tt, M, N) -> U82(isNatKind(activate(M)), activate(M), activate(N)) U82(tt, M, N) -> U83(isNat(activate(N)), activate(M), activate(N)) U83(tt, M, N) -> U84(isNatKind(activate(N)), activate(M), activate(N)) U84(tt, M, N) -> s(plus(activate(N), activate(M))) U91(tt, N) -> U92(isNatKind(activate(N))) U92(tt) -> 0 isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNatKind(activate(V1)), activate(V1), activate(V2)) isNat(n__s(V1)) -> U21(isNatKind(activate(V1)), activate(V1)) isNat(n__x(V1, V2)) -> U31(isNatKind(activate(V1)), activate(V1), activate(V2)) isNatKind(n__0) -> tt isNatKind(n__plus(V1, V2)) -> U41(isNatKind(activate(V1)), activate(V2)) isNatKind(n__s(V1)) -> U51(isNatKind(activate(V1))) isNatKind(n__x(V1, V2)) -> U61(isNatKind(activate(V1)), activate(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) 0 -> n__0 plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) x(X1, X2) -> n__x(X1, X2) activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__s(X)) -> s(activate(X)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) activate(X) -> X Q is empty. ---------------------------------------- (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: U101^1(tt, M, N) -> U102^1(isNatKind(activate(M)), activate(M), activate(N)) U101^1(tt, M, N) -> ISNATKIND(activate(M)) U101^1(tt, M, N) -> ACTIVATE(M) U101^1(tt, M, N) -> ACTIVATE(N) U102^1(tt, M, N) -> U103^1(isNat(activate(N)), activate(M), activate(N)) U102^1(tt, M, N) -> ISNAT(activate(N)) U102^1(tt, M, N) -> ACTIVATE(N) U102^1(tt, M, N) -> ACTIVATE(M) U103^1(tt, M, N) -> U104^1(isNatKind(activate(N)), activate(M), activate(N)) U103^1(tt, M, N) -> ISNATKIND(activate(N)) U103^1(tt, M, N) -> ACTIVATE(N) U103^1(tt, M, N) -> ACTIVATE(M) U104^1(tt, M, N) -> PLUS(x(activate(N), activate(M)), activate(N)) U104^1(tt, M, N) -> X(activate(N), activate(M)) U104^1(tt, M, N) -> ACTIVATE(N) U104^1(tt, M, N) -> ACTIVATE(M) U11^1(tt, V1, V2) -> U12^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U11^1(tt, V1, V2) -> ISNATKIND(activate(V1)) U11^1(tt, V1, V2) -> ACTIVATE(V1) U11^1(tt, V1, V2) -> ACTIVATE(V2) U12^1(tt, V1, V2) -> U13^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U12^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U12^1(tt, V1, V2) -> ACTIVATE(V2) U12^1(tt, V1, V2) -> ACTIVATE(V1) U13^1(tt, V1, V2) -> U14^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U13^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U13^1(tt, V1, V2) -> ACTIVATE(V2) U13^1(tt, V1, V2) -> ACTIVATE(V1) U14^1(tt, V1, V2) -> U15^1(isNat(activate(V1)), activate(V2)) U14^1(tt, V1, V2) -> ISNAT(activate(V1)) U14^1(tt, V1, V2) -> ACTIVATE(V1) U14^1(tt, V1, V2) -> ACTIVATE(V2) U15^1(tt, V2) -> U16^1(isNat(activate(V2))) U15^1(tt, V2) -> ISNAT(activate(V2)) U15^1(tt, V2) -> ACTIVATE(V2) U21^1(tt, V1) -> U22^1(isNatKind(activate(V1)), activate(V1)) U21^1(tt, V1) -> ISNATKIND(activate(V1)) U21^1(tt, V1) -> ACTIVATE(V1) U22^1(tt, V1) -> U23^1(isNat(activate(V1))) U22^1(tt, V1) -> ISNAT(activate(V1)) U22^1(tt, V1) -> ACTIVATE(V1) U31^1(tt, V1, V2) -> U32^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U31^1(tt, V1, V2) -> ISNATKIND(activate(V1)) U31^1(tt, V1, V2) -> ACTIVATE(V1) U31^1(tt, V1, V2) -> ACTIVATE(V2) U32^1(tt, V1, V2) -> U33^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U32^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U32^1(tt, V1, V2) -> ACTIVATE(V2) U32^1(tt, V1, V2) -> ACTIVATE(V1) U33^1(tt, V1, V2) -> U34^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U33^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U33^1(tt, V1, V2) -> ACTIVATE(V2) U33^1(tt, V1, V2) -> ACTIVATE(V1) U34^1(tt, V1, V2) -> U35^1(isNat(activate(V1)), activate(V2)) U34^1(tt, V1, V2) -> ISNAT(activate(V1)) U34^1(tt, V1, V2) -> ACTIVATE(V1) U34^1(tt, V1, V2) -> ACTIVATE(V2) U35^1(tt, V2) -> U36^1(isNat(activate(V2))) U35^1(tt, V2) -> ISNAT(activate(V2)) U35^1(tt, V2) -> ACTIVATE(V2) U41^1(tt, V2) -> U42^1(isNatKind(activate(V2))) U41^1(tt, V2) -> ISNATKIND(activate(V2)) U41^1(tt, V2) -> ACTIVATE(V2) U61^1(tt, V2) -> U62^1(isNatKind(activate(V2))) U61^1(tt, V2) -> ISNATKIND(activate(V2)) U61^1(tt, V2) -> ACTIVATE(V2) U71^1(tt, N) -> U72^1(isNatKind(activate(N)), activate(N)) U71^1(tt, N) -> ISNATKIND(activate(N)) U71^1(tt, N) -> ACTIVATE(N) U72^1(tt, N) -> ACTIVATE(N) U81^1(tt, M, N) -> U82^1(isNatKind(activate(M)), activate(M), activate(N)) U81^1(tt, M, N) -> ISNATKIND(activate(M)) U81^1(tt, M, N) -> ACTIVATE(M) U81^1(tt, M, N) -> ACTIVATE(N) U82^1(tt, M, N) -> U83^1(isNat(activate(N)), activate(M), activate(N)) U82^1(tt, M, N) -> ISNAT(activate(N)) U82^1(tt, M, N) -> ACTIVATE(N) U82^1(tt, M, N) -> ACTIVATE(M) U83^1(tt, M, N) -> U84^1(isNatKind(activate(N)), activate(M), activate(N)) U83^1(tt, M, N) -> ISNATKIND(activate(N)) U83^1(tt, M, N) -> ACTIVATE(N) U83^1(tt, M, N) -> ACTIVATE(M) U84^1(tt, M, N) -> S(plus(activate(N), activate(M))) U84^1(tt, M, N) -> PLUS(activate(N), activate(M)) U84^1(tt, M, N) -> ACTIVATE(N) U84^1(tt, M, N) -> ACTIVATE(M) U91^1(tt, N) -> U92^1(isNatKind(activate(N))) U91^1(tt, N) -> ISNATKIND(activate(N)) U91^1(tt, N) -> ACTIVATE(N) U92^1(tt) -> 0^1 ISNAT(n__plus(V1, V2)) -> U11^1(isNatKind(activate(V1)), activate(V1), activate(V2)) ISNAT(n__plus(V1, V2)) -> ISNATKIND(activate(V1)) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V1) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V2) ISNAT(n__s(V1)) -> U21^1(isNatKind(activate(V1)), activate(V1)) ISNAT(n__s(V1)) -> ISNATKIND(activate(V1)) ISNAT(n__s(V1)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> U31^1(isNatKind(activate(V1)), activate(V1), activate(V2)) ISNAT(n__x(V1, V2)) -> ISNATKIND(activate(V1)) ISNAT(n__x(V1, V2)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> ACTIVATE(V2) ISNATKIND(n__plus(V1, V2)) -> U41^1(isNatKind(activate(V1)), activate(V2)) ISNATKIND(n__plus(V1, V2)) -> ISNATKIND(activate(V1)) ISNATKIND(n__plus(V1, V2)) -> ACTIVATE(V1) ISNATKIND(n__plus(V1, V2)) -> ACTIVATE(V2) ISNATKIND(n__s(V1)) -> U51^1(isNatKind(activate(V1))) ISNATKIND(n__s(V1)) -> ISNATKIND(activate(V1)) ISNATKIND(n__s(V1)) -> ACTIVATE(V1) ISNATKIND(n__x(V1, V2)) -> U61^1(isNatKind(activate(V1)), activate(V2)) ISNATKIND(n__x(V1, V2)) -> ISNATKIND(activate(V1)) ISNATKIND(n__x(V1, V2)) -> ACTIVATE(V1) ISNATKIND(n__x(V1, V2)) -> ACTIVATE(V2) PLUS(N, 0) -> U71^1(isNat(N), N) PLUS(N, 0) -> ISNAT(N) PLUS(N, s(M)) -> U81^1(isNat(M), M, N) PLUS(N, s(M)) -> ISNAT(M) X(N, 0) -> U91^1(isNat(N), N) X(N, 0) -> ISNAT(N) X(N, s(M)) -> U101^1(isNat(M), M, N) X(N, s(M)) -> ISNAT(M) ACTIVATE(n__0) -> 0^1 ACTIVATE(n__plus(X1, X2)) -> PLUS(activate(X1), activate(X2)) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__s(X)) -> S(activate(X)) ACTIVATE(n__s(X)) -> ACTIVATE(X) ACTIVATE(n__x(X1, X2)) -> X(activate(X1), activate(X2)) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X2) The TRS R consists of the following rules: U101(tt, M, N) -> U102(isNatKind(activate(M)), activate(M), activate(N)) U102(tt, M, N) -> U103(isNat(activate(N)), activate(M), activate(N)) U103(tt, M, N) -> U104(isNatKind(activate(N)), activate(M), activate(N)) U104(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) U11(tt, V1, V2) -> U12(isNatKind(activate(V1)), activate(V1), activate(V2)) U12(tt, V1, V2) -> U13(isNatKind(activate(V2)), activate(V1), activate(V2)) U13(tt, V1, V2) -> U14(isNatKind(activate(V2)), activate(V1), activate(V2)) U14(tt, V1, V2) -> U15(isNat(activate(V1)), activate(V2)) U15(tt, V2) -> U16(isNat(activate(V2))) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(activate(V1)), activate(V1)) U22(tt, V1) -> U23(isNat(activate(V1))) U23(tt) -> tt U31(tt, V1, V2) -> U32(isNatKind(activate(V1)), activate(V1), activate(V2)) U32(tt, V1, V2) -> U33(isNatKind(activate(V2)), activate(V1), activate(V2)) U33(tt, V1, V2) -> U34(isNatKind(activate(V2)), activate(V1), activate(V2)) U34(tt, V1, V2) -> U35(isNat(activate(V1)), activate(V2)) U35(tt, V2) -> U36(isNat(activate(V2))) U36(tt) -> tt U41(tt, V2) -> U42(isNatKind(activate(V2))) U42(tt) -> tt U51(tt) -> tt U61(tt, V2) -> U62(isNatKind(activate(V2))) U62(tt) -> tt U71(tt, N) -> U72(isNatKind(activate(N)), activate(N)) U72(tt, N) -> activate(N) U81(tt, M, N) -> U82(isNatKind(activate(M)), activate(M), activate(N)) U82(tt, M, N) -> U83(isNat(activate(N)), activate(M), activate(N)) U83(tt, M, N) -> U84(isNatKind(activate(N)), activate(M), activate(N)) U84(tt, M, N) -> s(plus(activate(N), activate(M))) U91(tt, N) -> U92(isNatKind(activate(N))) U92(tt) -> 0 isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNatKind(activate(V1)), activate(V1), activate(V2)) isNat(n__s(V1)) -> U21(isNatKind(activate(V1)), activate(V1)) isNat(n__x(V1, V2)) -> U31(isNatKind(activate(V1)), activate(V1), activate(V2)) isNatKind(n__0) -> tt isNatKind(n__plus(V1, V2)) -> U41(isNatKind(activate(V1)), activate(V2)) isNatKind(n__s(V1)) -> U51(isNatKind(activate(V1))) isNatKind(n__x(V1, V2)) -> U61(isNatKind(activate(V1)), activate(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) 0 -> n__0 plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) x(X1, X2) -> n__x(X1, X2) activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__s(X)) -> s(activate(X)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 11 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: U102^1(tt, M, N) -> U103^1(isNat(activate(N)), activate(M), activate(N)) U103^1(tt, M, N) -> U104^1(isNatKind(activate(N)), activate(M), activate(N)) U104^1(tt, M, N) -> PLUS(x(activate(N), activate(M)), activate(N)) PLUS(N, 0) -> U71^1(isNat(N), N) U71^1(tt, N) -> U72^1(isNatKind(activate(N)), activate(N)) U72^1(tt, N) -> ACTIVATE(N) ACTIVATE(n__plus(X1, X2)) -> PLUS(activate(X1), activate(X2)) PLUS(N, 0) -> ISNAT(N) ISNAT(n__plus(V1, V2)) -> U11^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U11^1(tt, V1, V2) -> U12^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U12^1(tt, V1, V2) -> U13^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U13^1(tt, V1, V2) -> U14^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U14^1(tt, V1, V2) -> U15^1(isNat(activate(V1)), activate(V2)) U15^1(tt, V2) -> ISNAT(activate(V2)) ISNAT(n__plus(V1, V2)) -> ISNATKIND(activate(V1)) ISNATKIND(n__plus(V1, V2)) -> U41^1(isNatKind(activate(V1)), activate(V2)) U41^1(tt, V2) -> ISNATKIND(activate(V2)) ISNATKIND(n__plus(V1, V2)) -> ISNATKIND(activate(V1)) ISNATKIND(n__plus(V1, V2)) -> ACTIVATE(V1) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__s(X)) -> ACTIVATE(X) ACTIVATE(n__x(X1, X2)) -> X(activate(X1), activate(X2)) X(N, 0) -> U91^1(isNat(N), N) U91^1(tt, N) -> ISNATKIND(activate(N)) ISNATKIND(n__plus(V1, V2)) -> ACTIVATE(V2) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X2) ISNATKIND(n__s(V1)) -> ISNATKIND(activate(V1)) ISNATKIND(n__s(V1)) -> ACTIVATE(V1) ISNATKIND(n__x(V1, V2)) -> U61^1(isNatKind(activate(V1)), activate(V2)) U61^1(tt, V2) -> ISNATKIND(activate(V2)) ISNATKIND(n__x(V1, V2)) -> ISNATKIND(activate(V1)) ISNATKIND(n__x(V1, V2)) -> ACTIVATE(V1) ISNATKIND(n__x(V1, V2)) -> ACTIVATE(V2) U61^1(tt, V2) -> ACTIVATE(V2) U91^1(tt, N) -> ACTIVATE(N) X(N, 0) -> ISNAT(N) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V1) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V2) ISNAT(n__s(V1)) -> U21^1(isNatKind(activate(V1)), activate(V1)) U21^1(tt, V1) -> U22^1(isNatKind(activate(V1)), activate(V1)) U22^1(tt, V1) -> ISNAT(activate(V1)) ISNAT(n__s(V1)) -> ISNATKIND(activate(V1)) ISNAT(n__s(V1)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> U31^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U31^1(tt, V1, V2) -> U32^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U32^1(tt, V1, V2) -> U33^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U33^1(tt, V1, V2) -> U34^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U34^1(tt, V1, V2) -> U35^1(isNat(activate(V1)), activate(V2)) U35^1(tt, V2) -> ISNAT(activate(V2)) ISNAT(n__x(V1, V2)) -> ISNATKIND(activate(V1)) ISNAT(n__x(V1, V2)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> ACTIVATE(V2) U35^1(tt, V2) -> ACTIVATE(V2) U34^1(tt, V1, V2) -> ISNAT(activate(V1)) U34^1(tt, V1, V2) -> ACTIVATE(V1) U34^1(tt, V1, V2) -> ACTIVATE(V2) U33^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U33^1(tt, V1, V2) -> ACTIVATE(V2) U33^1(tt, V1, V2) -> ACTIVATE(V1) U32^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U32^1(tt, V1, V2) -> ACTIVATE(V2) U32^1(tt, V1, V2) -> ACTIVATE(V1) U31^1(tt, V1, V2) -> ISNATKIND(activate(V1)) U31^1(tt, V1, V2) -> ACTIVATE(V1) U31^1(tt, V1, V2) -> ACTIVATE(V2) U22^1(tt, V1) -> ACTIVATE(V1) U21^1(tt, V1) -> ISNATKIND(activate(V1)) U21^1(tt, V1) -> ACTIVATE(V1) X(N, s(M)) -> U101^1(isNat(M), M, N) U101^1(tt, M, N) -> U102^1(isNatKind(activate(M)), activate(M), activate(N)) U102^1(tt, M, N) -> ISNAT(activate(N)) U102^1(tt, M, N) -> ACTIVATE(N) U102^1(tt, M, N) -> ACTIVATE(M) U101^1(tt, M, N) -> ISNATKIND(activate(M)) U101^1(tt, M, N) -> ACTIVATE(M) U101^1(tt, M, N) -> ACTIVATE(N) X(N, s(M)) -> ISNAT(M) U41^1(tt, V2) -> ACTIVATE(V2) U15^1(tt, V2) -> ACTIVATE(V2) U14^1(tt, V1, V2) -> ISNAT(activate(V1)) U14^1(tt, V1, V2) -> ACTIVATE(V1) U14^1(tt, V1, V2) -> ACTIVATE(V2) U13^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U13^1(tt, V1, V2) -> ACTIVATE(V2) U13^1(tt, V1, V2) -> ACTIVATE(V1) U12^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U12^1(tt, V1, V2) -> ACTIVATE(V2) U12^1(tt, V1, V2) -> ACTIVATE(V1) U11^1(tt, V1, V2) -> ISNATKIND(activate(V1)) U11^1(tt, V1, V2) -> ACTIVATE(V1) U11^1(tt, V1, V2) -> ACTIVATE(V2) PLUS(N, s(M)) -> U81^1(isNat(M), M, N) U81^1(tt, M, N) -> U82^1(isNatKind(activate(M)), activate(M), activate(N)) U82^1(tt, M, N) -> U83^1(isNat(activate(N)), activate(M), activate(N)) U83^1(tt, M, N) -> U84^1(isNatKind(activate(N)), activate(M), activate(N)) U84^1(tt, M, N) -> PLUS(activate(N), activate(M)) PLUS(N, s(M)) -> ISNAT(M) U84^1(tt, M, N) -> ACTIVATE(N) U84^1(tt, M, N) -> ACTIVATE(M) U83^1(tt, M, N) -> ISNATKIND(activate(N)) U83^1(tt, M, N) -> ACTIVATE(N) U83^1(tt, M, N) -> ACTIVATE(M) U82^1(tt, M, N) -> ISNAT(activate(N)) U82^1(tt, M, N) -> ACTIVATE(N) U82^1(tt, M, N) -> ACTIVATE(M) U81^1(tt, M, N) -> ISNATKIND(activate(M)) U81^1(tt, M, N) -> ACTIVATE(M) U81^1(tt, M, N) -> ACTIVATE(N) U71^1(tt, N) -> ISNATKIND(activate(N)) U71^1(tt, N) -> ACTIVATE(N) U104^1(tt, M, N) -> X(activate(N), activate(M)) U104^1(tt, M, N) -> ACTIVATE(N) U104^1(tt, M, N) -> ACTIVATE(M) U103^1(tt, M, N) -> ISNATKIND(activate(N)) U103^1(tt, M, N) -> ACTIVATE(N) U103^1(tt, M, N) -> ACTIVATE(M) The TRS R consists of the following rules: U101(tt, M, N) -> U102(isNatKind(activate(M)), activate(M), activate(N)) U102(tt, M, N) -> U103(isNat(activate(N)), activate(M), activate(N)) U103(tt, M, N) -> U104(isNatKind(activate(N)), activate(M), activate(N)) U104(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) U11(tt, V1, V2) -> U12(isNatKind(activate(V1)), activate(V1), activate(V2)) U12(tt, V1, V2) -> U13(isNatKind(activate(V2)), activate(V1), activate(V2)) U13(tt, V1, V2) -> U14(isNatKind(activate(V2)), activate(V1), activate(V2)) U14(tt, V1, V2) -> U15(isNat(activate(V1)), activate(V2)) U15(tt, V2) -> U16(isNat(activate(V2))) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(activate(V1)), activate(V1)) U22(tt, V1) -> U23(isNat(activate(V1))) U23(tt) -> tt U31(tt, V1, V2) -> U32(isNatKind(activate(V1)), activate(V1), activate(V2)) U32(tt, V1, V2) -> U33(isNatKind(activate(V2)), activate(V1), activate(V2)) U33(tt, V1, V2) -> U34(isNatKind(activate(V2)), activate(V1), activate(V2)) U34(tt, V1, V2) -> U35(isNat(activate(V1)), activate(V2)) U35(tt, V2) -> U36(isNat(activate(V2))) U36(tt) -> tt U41(tt, V2) -> U42(isNatKind(activate(V2))) U42(tt) -> tt U51(tt) -> tt U61(tt, V2) -> U62(isNatKind(activate(V2))) U62(tt) -> tt U71(tt, N) -> U72(isNatKind(activate(N)), activate(N)) U72(tt, N) -> activate(N) U81(tt, M, N) -> U82(isNatKind(activate(M)), activate(M), activate(N)) U82(tt, M, N) -> U83(isNat(activate(N)), activate(M), activate(N)) U83(tt, M, N) -> U84(isNatKind(activate(N)), activate(M), activate(N)) U84(tt, M, N) -> s(plus(activate(N), activate(M))) U91(tt, N) -> U92(isNatKind(activate(N))) U92(tt) -> 0 isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNatKind(activate(V1)), activate(V1), activate(V2)) isNat(n__s(V1)) -> U21(isNatKind(activate(V1)), activate(V1)) isNat(n__x(V1, V2)) -> U31(isNatKind(activate(V1)), activate(V1), activate(V2)) isNatKind(n__0) -> tt isNatKind(n__plus(V1, V2)) -> U41(isNatKind(activate(V1)), activate(V2)) isNatKind(n__s(V1)) -> U51(isNatKind(activate(V1))) isNatKind(n__x(V1, V2)) -> U61(isNatKind(activate(V1)), activate(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) 0 -> n__0 plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) x(X1, X2) -> n__x(X1, X2) activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__s(X)) -> s(activate(X)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U104^1(tt, M, N) -> PLUS(x(activate(N), activate(M)), activate(N)) PLUS(N, 0) -> U71^1(isNat(N), N) U71^1(tt, N) -> U72^1(isNatKind(activate(N)), activate(N)) ACTIVATE(n__plus(X1, X2)) -> PLUS(activate(X1), activate(X2)) PLUS(N, 0) -> ISNAT(N) ISNAT(n__plus(V1, V2)) -> U11^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U11^1(tt, V1, V2) -> U12^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U14^1(tt, V1, V2) -> U15^1(isNat(activate(V1)), activate(V2)) U15^1(tt, V2) -> ISNAT(activate(V2)) ISNAT(n__plus(V1, V2)) -> ISNATKIND(activate(V1)) ISNATKIND(n__plus(V1, V2)) -> U41^1(isNatKind(activate(V1)), activate(V2)) U41^1(tt, V2) -> ISNATKIND(activate(V2)) ISNATKIND(n__plus(V1, V2)) -> ISNATKIND(activate(V1)) ISNATKIND(n__plus(V1, V2)) -> ACTIVATE(V1) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__s(X)) -> ACTIVATE(X) ACTIVATE(n__x(X1, X2)) -> X(activate(X1), activate(X2)) X(N, 0) -> U91^1(isNat(N), N) U91^1(tt, N) -> ISNATKIND(activate(N)) ISNATKIND(n__plus(V1, V2)) -> ACTIVATE(V2) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X2) ISNATKIND(n__s(V1)) -> ISNATKIND(activate(V1)) ISNATKIND(n__x(V1, V2)) -> U61^1(isNatKind(activate(V1)), activate(V2)) U61^1(tt, V2) -> ISNATKIND(activate(V2)) ISNATKIND(n__x(V1, V2)) -> ISNATKIND(activate(V1)) ISNATKIND(n__x(V1, V2)) -> ACTIVATE(V1) ISNATKIND(n__x(V1, V2)) -> ACTIVATE(V2) U61^1(tt, V2) -> ACTIVATE(V2) X(N, 0) -> ISNAT(N) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V1) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V2) ISNAT(n__s(V1)) -> U21^1(isNatKind(activate(V1)), activate(V1)) U22^1(tt, V1) -> ISNAT(activate(V1)) ISNAT(n__s(V1)) -> ISNATKIND(activate(V1)) ISNAT(n__s(V1)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> U31^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U31^1(tt, V1, V2) -> U32^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U34^1(tt, V1, V2) -> U35^1(isNat(activate(V1)), activate(V2)) U35^1(tt, V2) -> ISNAT(activate(V2)) ISNAT(n__x(V1, V2)) -> ISNATKIND(activate(V1)) ISNAT(n__x(V1, V2)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> ACTIVATE(V2) U34^1(tt, V1, V2) -> ISNAT(activate(V1)) U34^1(tt, V1, V2) -> ACTIVATE(V1) U34^1(tt, V1, V2) -> ACTIVATE(V2) U33^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U33^1(tt, V1, V2) -> ACTIVATE(V2) U33^1(tt, V1, V2) -> ACTIVATE(V1) U32^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U32^1(tt, V1, V2) -> ACTIVATE(V2) U32^1(tt, V1, V2) -> ACTIVATE(V1) U31^1(tt, V1, V2) -> ISNATKIND(activate(V1)) U31^1(tt, V1, V2) -> ACTIVATE(V1) U31^1(tt, V1, V2) -> ACTIVATE(V2) U21^1(tt, V1) -> ISNATKIND(activate(V1)) X(N, s(M)) -> U101^1(isNat(M), M, N) U102^1(tt, M, N) -> ISNAT(activate(N)) U102^1(tt, M, N) -> ACTIVATE(N) U102^1(tt, M, N) -> ACTIVATE(M) U101^1(tt, M, N) -> ISNATKIND(activate(M)) U101^1(tt, M, N) -> ACTIVATE(M) U101^1(tt, M, N) -> ACTIVATE(N) X(N, s(M)) -> ISNAT(M) U41^1(tt, V2) -> ACTIVATE(V2) U15^1(tt, V2) -> ACTIVATE(V2) U14^1(tt, V1, V2) -> ISNAT(activate(V1)) U14^1(tt, V1, V2) -> ACTIVATE(V1) U14^1(tt, V1, V2) -> ACTIVATE(V2) U13^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U13^1(tt, V1, V2) -> ACTIVATE(V2) U13^1(tt, V1, V2) -> ACTIVATE(V1) U12^1(tt, V1, V2) -> ISNATKIND(activate(V2)) U12^1(tt, V1, V2) -> ACTIVATE(V2) U12^1(tt, V1, V2) -> ACTIVATE(V1) U11^1(tt, V1, V2) -> ISNATKIND(activate(V1)) U11^1(tt, V1, V2) -> ACTIVATE(V1) U11^1(tt, V1, V2) -> ACTIVATE(V2) PLUS(N, s(M)) -> U81^1(isNat(M), M, N) U83^1(tt, M, N) -> U84^1(isNatKind(activate(N)), activate(M), activate(N)) PLUS(N, s(M)) -> ISNAT(M) U84^1(tt, M, N) -> ACTIVATE(N) U84^1(tt, M, N) -> ACTIVATE(M) U83^1(tt, M, N) -> ISNATKIND(activate(N)) U83^1(tt, M, N) -> ACTIVATE(N) U83^1(tt, M, N) -> ACTIVATE(M) U82^1(tt, M, N) -> ISNAT(activate(N)) U82^1(tt, M, N) -> ACTIVATE(N) U82^1(tt, M, N) -> ACTIVATE(M) U81^1(tt, M, N) -> ISNATKIND(activate(M)) U81^1(tt, M, N) -> ACTIVATE(M) U81^1(tt, M, N) -> ACTIVATE(N) U71^1(tt, N) -> ISNATKIND(activate(N)) U71^1(tt, N) -> ACTIVATE(N) U104^1(tt, M, N) -> X(activate(N), activate(M)) U104^1(tt, M, N) -> ACTIVATE(N) U104^1(tt, M, N) -> ACTIVATE(M) U103^1(tt, M, N) -> ISNATKIND(activate(N)) U103^1(tt, M, N) -> ACTIVATE(N) U103^1(tt, M, N) -> ACTIVATE(M) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. U102^1(x1, x2, x3) = U102^1(x1, x2, x3) tt = tt U103^1(x1, x2, x3) = U103^1(x1, x2, x3) isNat(x1) = isNat activate(x1) = x1 U104^1(x1, x2, x3) = U104^1(x1, x2, x3) isNatKind(x1) = isNatKind PLUS(x1, x2) = PLUS(x1, x2) x(x1, x2) = x(x1, x2) 0 = 0 U71^1(x1, x2) = U71^1(x1, x2) U72^1(x1, x2) = U72^1(x2) ACTIVATE(x1) = ACTIVATE(x1) n__plus(x1, x2) = n__plus(x1, x2) ISNAT(x1) = ISNAT(x1) U11^1(x1, x2, x3) = U11^1(x2, x3) U12^1(x1, x2, x3) = U12^1(x1, x2, x3) U13^1(x1, x2, x3) = U13^1(x1, x2, x3) U14^1(x1, x2, x3) = U14^1(x1, x2, x3) U15^1(x1, x2) = U15^1(x1, x2) ISNATKIND(x1) = x1 U41^1(x1, x2) = U41^1(x1, x2) n__s(x1) = n__s(x1) n__x(x1, x2) = n__x(x1, x2) X(x1, x2) = X(x1, x2) U91^1(x1, x2) = U91^1(x2) U61^1(x1, x2) = U61^1(x1, x2) U21^1(x1, x2) = U21^1(x2) U22^1(x1, x2) = U22^1(x2) U31^1(x1, x2, x3) = U31^1(x2, x3) U32^1(x1, x2, x3) = U32^1(x1, x2, x3) U33^1(x1, x2, x3) = U33^1(x1, x2, x3) U34^1(x1, x2, x3) = U34^1(x1, x2, x3) U35^1(x1, x2) = U35^1(x2) s(x1) = s(x1) U101^1(x1, x2, x3) = U101^1(x1, x2, x3) U81^1(x1, x2, x3) = U81^1(x1, x2, x3) U82^1(x1, x2, x3) = U82^1(x1, x2, x3) U83^1(x1, x2, x3) = U83^1(x1, x2, x3) U84^1(x1, x2, x3) = U84^1(x2, x3) n__0 = n__0 U102(x1, x2, x3) = U102(x1, x2, x3) U103(x1, x2, x3) = U103(x1, x2, x3) U104(x1, x2, x3) = U104(x1, x2, x3) plus(x1, x2) = plus(x1, x2) U71(x1, x2) = U71(x1, x2) U72(x1, x2) = U72(x1, x2) U101(x1, x2, x3) = U101(x1, x2, x3) U11(x1, x2, x3) = x1 U21(x1, x2) = U21 U31(x1, x2, x3) = U31 U41(x1, x2) = U41 U51(x1) = U51 U61(x1, x2) = x1 U91(x1, x2) = U91 U62(x1) = U62 U42(x1) = U42 U12(x1, x2, x3) = U12 U13(x1, x2, x3) = U13 U14(x1, x2, x3) = x1 U15(x1, x2) = x1 U22(x1, x2) = x1 U23(x1) = U23 U32(x1, x2, x3) = U32 U33(x1, x2, x3) = x1 U34(x1, x2, x3) = U34 U35(x1, x2) = U35 U36(x1) = x1 U16(x1) = U16 U92(x1) = U92 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) Recursive path order with status [RPO]. Quasi-Precedence: [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U31^1_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [tt, isNat, isNatKind, PLUS_2, 0, n__plus_2, U11^1_2, U32^1_3, U33^1_3, U34^1_3, U81^1_3, U82^1_3, U83^1_3, U84^1_2, n__0, plus_2, U21, U31, U41, U51, U91, U62, U42, U12, U13, U23, U32, U34, U35, U16, U92, U81_3, U82_3, U83_3, U84_3] > U71^1_2 > [U72^1_1, ACTIVATE_1, n__s_1, U91^1_1, U21^1_1, U22^1_1, U35^1_1, s_1] > ISNAT_1 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U31^1_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [tt, isNat, isNatKind, PLUS_2, 0, n__plus_2, U11^1_2, U32^1_3, U33^1_3, U34^1_3, U81^1_3, U82^1_3, U83^1_3, U84^1_2, n__0, plus_2, U21, U31, U41, U51, U91, U62, U42, U12, U13, U23, U32, U34, U35, U16, U92, U81_3, U82_3, U83_3, U84_3] > [U12^1_3, U13^1_3, U14^1_3, U15^1_2] > [U72^1_1, ACTIVATE_1, n__s_1, U91^1_1, U21^1_1, U22^1_1, U35^1_1, s_1] > ISNAT_1 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U31^1_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [tt, isNat, isNatKind, PLUS_2, 0, n__plus_2, U11^1_2, U32^1_3, U33^1_3, U34^1_3, U81^1_3, U82^1_3, U83^1_3, U84^1_2, n__0, plus_2, U21, U31, U41, U51, U91, U62, U42, U12, U13, U23, U32, U34, U35, U16, U92, U81_3, U82_3, U83_3, U84_3] > U41^1_2 > [U72^1_1, ACTIVATE_1, n__s_1, U91^1_1, U21^1_1, U22^1_1, U35^1_1, s_1] > ISNAT_1 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U31^1_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [tt, isNat, isNatKind, PLUS_2, 0, n__plus_2, U11^1_2, U32^1_3, U33^1_3, U34^1_3, U81^1_3, U82^1_3, U83^1_3, U84^1_2, n__0, plus_2, U21, U31, U41, U51, U91, U62, U42, U12, U13, U23, U32, U34, U35, U16, U92, U81_3, U82_3, U83_3, U84_3] > U71_2 > U72_2 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U31^1_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > U61^1_2 > [U72^1_1, ACTIVATE_1, n__s_1, U91^1_1, U21^1_1, U22^1_1, U35^1_1, s_1] > ISNAT_1 Status: U102^1_3: [3,2,1] tt: multiset status U103^1_3: [3,2,1] isNat: [] U104^1_3: [3,2,1] isNatKind: [] PLUS_2: [2,1] x_2: [1,2] 0: multiset status U71^1_2: multiset status U72^1_1: [1] ACTIVATE_1: [1] n__plus_2: [2,1] ISNAT_1: [1] U11^1_2: [2,1] U12^1_3: multiset status U13^1_3: multiset status U14^1_3: multiset status U15^1_2: multiset status U41^1_2: multiset status n__s_1: [1] n__x_2: [1,2] X_2: [1,2] U91^1_1: [1] U61^1_2: [1,2] U21^1_1: [1] U22^1_1: [1] U31^1_2: [1,2] U32^1_3: multiset status U33^1_3: multiset status U34^1_3: multiset status U35^1_1: [1] s_1: [1] U101^1_3: [3,2,1] U81^1_3: [2,3,1] U82^1_3: [2,3,1] U83^1_3: [2,3,1] U84^1_2: [1,2] n__0: multiset status U102_3: [3,2,1] U103_3: [3,2,1] U104_3: [3,2,1] plus_2: [2,1] U71_2: [1,2] U72_2: [2,1] U101_3: [3,2,1] U21: [] U31: [] U41: [] U51: [] U91: multiset status U62: [] U42: [] U12: [] U13: [] U23: [] U32: [] U34: [] U35: [] U16: [] U92: multiset status U81_3: [2,3,1] U82_3: [2,3,1] U83_3: [2,3,1] U84_3: [2,3,1] The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__0) -> 0 U102(tt, M, N) -> U103(isNat(activate(N)), activate(M), activate(N)) U103(tt, M, N) -> U104(isNatKind(activate(N)), activate(M), activate(N)) U104(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) plus(N, 0) -> U71(isNat(N), N) U71(tt, N) -> U72(isNatKind(activate(N)), activate(N)) U72(tt, N) -> activate(N) activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) x(N, s(M)) -> U101(isNat(M), M, N) U101(tt, M, N) -> U102(isNatKind(activate(M)), activate(M), activate(N)) activate(n__s(X)) -> s(activate(X)) activate(X) -> X isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNatKind(activate(V1)), activate(V1), activate(V2)) isNat(n__s(V1)) -> U21(isNatKind(activate(V1)), activate(V1)) isNat(n__x(V1, V2)) -> U31(isNatKind(activate(V1)), activate(V1), activate(V2)) isNatKind(n__0) -> tt isNatKind(n__plus(V1, V2)) -> U41(isNatKind(activate(V1)), activate(V2)) isNatKind(n__s(V1)) -> U51(isNatKind(activate(V1))) isNatKind(n__x(V1, V2)) -> U61(isNatKind(activate(V1)), activate(V2)) x(N, 0) -> U91(isNat(N), N) x(X1, X2) -> n__x(X1, X2) s(X) -> n__s(X) plus(X1, X2) -> n__plus(X1, X2) U51(tt) -> tt U61(tt, V2) -> U62(isNatKind(activate(V2))) U62(tt) -> tt U41(tt, V2) -> U42(isNatKind(activate(V2))) U42(tt) -> tt U11(tt, V1, V2) -> U12(isNatKind(activate(V1)), activate(V1), activate(V2)) U12(tt, V1, V2) -> U13(isNatKind(activate(V2)), activate(V1), activate(V2)) U13(tt, V1, V2) -> U14(isNatKind(activate(V2)), activate(V1), activate(V2)) U14(tt, V1, V2) -> U15(isNat(activate(V1)), activate(V2)) U21(tt, V1) -> U22(isNatKind(activate(V1)), activate(V1)) U22(tt, V1) -> U23(isNat(activate(V1))) U23(tt) -> tt U31(tt, V1, V2) -> U32(isNatKind(activate(V1)), activate(V1), activate(V2)) U32(tt, V1, V2) -> U33(isNatKind(activate(V2)), activate(V1), activate(V2)) U33(tt, V1, V2) -> U34(isNatKind(activate(V2)), activate(V1), activate(V2)) U34(tt, V1, V2) -> U35(isNat(activate(V1)), activate(V2)) U35(tt, V2) -> U36(isNat(activate(V2))) U36(tt) -> tt U15(tt, V2) -> U16(isNat(activate(V2))) U16(tt) -> tt U91(tt, N) -> U92(isNatKind(activate(N))) U92(tt) -> 0 plus(N, s(M)) -> U81(isNat(M), M, N) U81(tt, M, N) -> U82(isNatKind(activate(M)), activate(M), activate(N)) U82(tt, M, N) -> U83(isNat(activate(N)), activate(M), activate(N)) U83(tt, M, N) -> U84(isNatKind(activate(N)), activate(M), activate(N)) U84(tt, M, N) -> s(plus(activate(N), activate(M))) 0 -> n__0 ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: U102^1(tt, M, N) -> U103^1(isNat(activate(N)), activate(M), activate(N)) U103^1(tt, M, N) -> U104^1(isNatKind(activate(N)), activate(M), activate(N)) U72^1(tt, N) -> ACTIVATE(N) U12^1(tt, V1, V2) -> U13^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U13^1(tt, V1, V2) -> U14^1(isNatKind(activate(V2)), activate(V1), activate(V2)) ISNATKIND(n__s(V1)) -> ACTIVATE(V1) U91^1(tt, N) -> ACTIVATE(N) U21^1(tt, V1) -> U22^1(isNatKind(activate(V1)), activate(V1)) U32^1(tt, V1, V2) -> U33^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U33^1(tt, V1, V2) -> U34^1(isNatKind(activate(V2)), activate(V1), activate(V2)) U35^1(tt, V2) -> ACTIVATE(V2) U22^1(tt, V1) -> ACTIVATE(V1) U21^1(tt, V1) -> ACTIVATE(V1) U101^1(tt, M, N) -> U102^1(isNatKind(activate(M)), activate(M), activate(N)) U81^1(tt, M, N) -> U82^1(isNatKind(activate(M)), activate(M), activate(N)) U82^1(tt, M, N) -> U83^1(isNat(activate(N)), activate(M), activate(N)) U84^1(tt, M, N) -> PLUS(activate(N), activate(M)) The TRS R consists of the following rules: U101(tt, M, N) -> U102(isNatKind(activate(M)), activate(M), activate(N)) U102(tt, M, N) -> U103(isNat(activate(N)), activate(M), activate(N)) U103(tt, M, N) -> U104(isNatKind(activate(N)), activate(M), activate(N)) U104(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) U11(tt, V1, V2) -> U12(isNatKind(activate(V1)), activate(V1), activate(V2)) U12(tt, V1, V2) -> U13(isNatKind(activate(V2)), activate(V1), activate(V2)) U13(tt, V1, V2) -> U14(isNatKind(activate(V2)), activate(V1), activate(V2)) U14(tt, V1, V2) -> U15(isNat(activate(V1)), activate(V2)) U15(tt, V2) -> U16(isNat(activate(V2))) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(activate(V1)), activate(V1)) U22(tt, V1) -> U23(isNat(activate(V1))) U23(tt) -> tt U31(tt, V1, V2) -> U32(isNatKind(activate(V1)), activate(V1), activate(V2)) U32(tt, V1, V2) -> U33(isNatKind(activate(V2)), activate(V1), activate(V2)) U33(tt, V1, V2) -> U34(isNatKind(activate(V2)), activate(V1), activate(V2)) U34(tt, V1, V2) -> U35(isNat(activate(V1)), activate(V2)) U35(tt, V2) -> U36(isNat(activate(V2))) U36(tt) -> tt U41(tt, V2) -> U42(isNatKind(activate(V2))) U42(tt) -> tt U51(tt) -> tt U61(tt, V2) -> U62(isNatKind(activate(V2))) U62(tt) -> tt U71(tt, N) -> U72(isNatKind(activate(N)), activate(N)) U72(tt, N) -> activate(N) U81(tt, M, N) -> U82(isNatKind(activate(M)), activate(M), activate(N)) U82(tt, M, N) -> U83(isNat(activate(N)), activate(M), activate(N)) U83(tt, M, N) -> U84(isNatKind(activate(N)), activate(M), activate(N)) U84(tt, M, N) -> s(plus(activate(N), activate(M))) U91(tt, N) -> U92(isNatKind(activate(N))) U92(tt) -> 0 isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNatKind(activate(V1)), activate(V1), activate(V2)) isNat(n__s(V1)) -> U21(isNatKind(activate(V1)), activate(V1)) isNat(n__x(V1, V2)) -> U31(isNatKind(activate(V1)), activate(V1), activate(V2)) isNatKind(n__0) -> tt isNatKind(n__plus(V1, V2)) -> U41(isNatKind(activate(V1)), activate(V2)) isNatKind(n__s(V1)) -> U51(isNatKind(activate(V1))) isNatKind(n__x(V1, V2)) -> U61(isNatKind(activate(V1)), activate(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) 0 -> n__0 plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) x(X1, X2) -> n__x(X1, X2) activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__s(X)) -> s(activate(X)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 17 less nodes. ---------------------------------------- (8) TRUE