/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 0 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) QDPOrderProof [EQUIVALENT, 6606 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(X1, X2) activate(n__s(X)) -> s(X) activate(n__x(X1, X2)) -> x(X1, 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(X1, X2) ACTIVATE(n__s(X)) -> S(X) ACTIVATE(n__x(X1, X2)) -> X(X1, 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(X1, X2) activate(n__s(X)) -> s(X) activate(n__x(X1, X2)) -> x(X1, 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(X1, 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__x(X1, X2)) -> X(X1, X2) X(N, 0) -> U91^1(isNat(N), N) U91^1(tt, N) -> ISNATKIND(activate(N)) ISNATKIND(n__plus(V1, V2)) -> ACTIVATE(V2) 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(X1, X2) activate(n__s(X)) -> s(X) activate(n__x(X1, X2)) -> x(X1, 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)) U72^1(tt, N) -> ACTIVATE(N) PLUS(N, 0) -> ISNAT(N) U14^1(tt, V1, V2) -> U15^1(isNat(activate(V1)), 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) X(N, 0) -> U91^1(isNat(N), N) U91^1(tt, N) -> ISNATKIND(activate(N)) ISNATKIND(n__plus(V1, V2)) -> ACTIVATE(V2) 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)) 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)) 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)) 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) 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) 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) 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) 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 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(x2) U72^1(x1, x2) = U72^1(x1, x2) ACTIVATE(x1) = x1 n__plus(x1, x2) = n__plus(x1, x2) ISNAT(x1) = x1 U11^1(x1, x2, x3) = U11^1(x2, x3) U12^1(x1, x2, x3) = U12^1(x2, x3) U13^1(x1, x2, x3) = U13^1(x2, x3) U14^1(x1, x2, x3) = U14^1(x2, x3) U15^1(x1, x2) = x2 ISNATKIND(x1) = x1 U41^1(x1, x2) = U41^1(x2) n__x(x1, x2) = n__x(x1, x2) X(x1, x2) = X(x1, x2) U91^1(x1, x2) = U91^1(x2) n__s(x1) = n__s(x1) U61^1(x1, x2) = U61^1(x1, x2) U21^1(x1, x2) = U21^1(x1, x2) U22^1(x1, x2) = U22^1(x1, x2) U31^1(x1, x2, x3) = U31^1(x2, x3) U32^1(x1, x2, x3) = U32^1(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) = 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(x1, 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(x2) U72(x1, x2) = U72(x1, x2) U101(x1, x2, x3) = U101(x1, x2, x3) U11(x1, x2, x3) = U11 U21(x1, x2) = x1 U31(x1, x2, x3) = U31 U41(x1, x2) = x1 U51(x1) = x1 U61(x1, x2) = U61 U91(x1, x2) = U91(x1, x2) U62(x1) = x1 U22(x1, x2) = U22 U23(x1) = x1 U32(x1, x2, x3) = x1 U33(x1, x2, x3) = x1 U34(x1, x2, x3) = x1 U35(x1, x2) = x1 U36(x1) = x1 U92(x1) = x1 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) U42(x1) = x1 U12(x1, x2, x3) = U12 U13(x1, x2, x3) = U13 U14(x1, x2, x3) = U14 U15(x1, x2) = x1 U16(x1) = x1 Recursive path order with status [RPO]. Quasi-Precedence: [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [PLUS_2, n__plus_2, U11^1_2, U12^1_2, U13^1_2, U14^1_2, U81^1_3, U82^1_3, U83^1_3, U84^1_3, plus_2, U81_3, U82_3, U83_3, U84_3] > U71^1_1 > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > [0, n__0] [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [PLUS_2, n__plus_2, U11^1_2, U12^1_2, U13^1_2, U14^1_2, U81^1_3, U82^1_3, U83^1_3, U84^1_3, plus_2, U81_3, U82_3, U83_3, U84_3] > U71^1_1 > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > U72^1_2 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [PLUS_2, n__plus_2, U11^1_2, U12^1_2, U13^1_2, U14^1_2, U81^1_3, U82^1_3, U83^1_3, U84^1_3, plus_2, U81_3, U82_3, U83_3, U84_3] > U41^1_1 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [PLUS_2, n__plus_2, U11^1_2, U12^1_2, U13^1_2, U14^1_2, U81^1_3, U82^1_3, U83^1_3, U84^1_3, plus_2, U81_3, U82_3, U83_3, U84_3] > [n__s_1, s_1] > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > [0, n__0] [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [PLUS_2, n__plus_2, U11^1_2, U12^1_2, U13^1_2, U14^1_2, U81^1_3, U82^1_3, U83^1_3, U84^1_3, plus_2, U81_3, U82_3, U83_3, U84_3] > [n__s_1, s_1] > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > U72^1_2 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [PLUS_2, n__plus_2, U11^1_2, U12^1_2, U13^1_2, U14^1_2, U81^1_3, U82^1_3, U83^1_3, U84^1_3, plus_2, U81_3, U82_3, U83_3, U84_3] > U71_1 > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > [0, n__0] [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [PLUS_2, n__plus_2, U11^1_2, U12^1_2, U13^1_2, U14^1_2, U81^1_3, U82^1_3, U83^1_3, U84^1_3, plus_2, U81_3, U82_3, U83_3, U84_3] > U71_1 > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > U72^1_2 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [PLUS_2, n__plus_2, U11^1_2, U12^1_2, U13^1_2, U14^1_2, U81^1_3, U82^1_3, U83^1_3, U84^1_3, plus_2, U81_3, U82_3, U83_3, U84_3] > U71_1 > U72_2 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > U91^1_1 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > U61^1_2 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [U31^1_2, U32^1_2] > U33^1_3 > U34^1_3 > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > [0, n__0] [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > [U31^1_2, U32^1_2] > U33^1_3 > U34^1_3 > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > U72^1_2 [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > U91_2 > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > [0, n__0] [U102^1_3, U103^1_3, U104^1_3, x_2, n__x_2, X_2, U101^1_3, U102_3, U103_3, U104_3, U101_3] > U91_2 > [tt, isNat, isNatKind, U21^1_2, U22^1_2, U11, U31, U61, U22, U12, U13, U14] > U72^1_2 Status: U102^1_3: multiset status tt: multiset status U103^1_3: multiset status isNat: multiset status U104^1_3: multiset status isNatKind: multiset status PLUS_2: multiset status x_2: multiset status 0: multiset status U71^1_1: multiset status U72^1_2: multiset status n__plus_2: multiset status U11^1_2: multiset status U12^1_2: multiset status U13^1_2: multiset status U14^1_2: multiset status U41^1_1: multiset status n__x_2: multiset status X_2: multiset status U91^1_1: [1] n__s_1: multiset status U61^1_2: [1,2] U21^1_2: [1,2] U22^1_2: [1,2] U31^1_2: multiset status U32^1_2: multiset status U33^1_3: multiset status U34^1_3: [1,3,2] s_1: multiset status U101^1_3: multiset status U81^1_3: multiset status U82^1_3: multiset status U83^1_3: multiset status U84^1_3: multiset status n__0: multiset status U102_3: multiset status U103_3: multiset status U104_3: multiset status plus_2: multiset status U71_1: multiset status U72_2: [1,2] U101_3: multiset status U11: multiset status U31: multiset status U61: multiset status U91_2: multiset status U22: multiset status U81_3: multiset status U82_3: multiset status U83_3: multiset status U84_3: multiset status U12: multiset status U13: multiset status U14: multiset status 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(X1, X2) activate(n__x(X1, X2)) -> x(X1, 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(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) U51(tt) -> tt U61(tt, V2) -> U62(isNatKind(activate(V2))) U62(tt) -> tt plus(X1, X2) -> n__plus(X1, X2) 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 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))) s(X) -> n__s(X) 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)) U15(tt, V2) -> U16(isNat(activate(V2))) U16(tt) -> tt 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)) ACTIVATE(n__plus(X1, X2)) -> PLUS(X1, X2) 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)) U15^1(tt, V2) -> ISNAT(activate(V2)) ACTIVATE(n__x(X1, X2)) -> X(X1, X2) U21^1(tt, V1) -> U22^1(isNatKind(activate(V1)), activate(V1)) U31^1(tt, V1, V2) -> U32^1(isNatKind(activate(V1)), activate(V1), activate(V2)) U35^1(tt, V2) -> ISNAT(activate(V2)) U35^1(tt, V2) -> ACTIVATE(V2) U101^1(tt, M, N) -> U102^1(isNatKind(activate(M)), activate(M), activate(N)) U15^1(tt, V2) -> ACTIVATE(V2) 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)) 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(X1, X2) activate(n__s(X)) -> s(X) activate(n__x(X1, X2)) -> x(X1, 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 18 less nodes. ---------------------------------------- (8) TRUE