6.19/2.42 YES 6.55/2.51 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 6.55/2.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.55/2.51 6.55/2.51 6.55/2.51 Termination w.r.t. Q of the given QTRS could be proven: 6.55/2.51 6.55/2.51 (0) QTRS 6.55/2.51 (1) QTRSToCSRProof [SOUND, 0 ms] 6.55/2.51 (2) CSR 6.55/2.51 (3) CSDependencyPairsProof [EQUIVALENT, 59 ms] 6.55/2.51 (4) QCSDP 6.55/2.51 (5) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 6.55/2.51 (6) AND 6.55/2.51 (7) QCSDP 6.55/2.51 (8) QCSDPSubtermProof [EQUIVALENT, 7 ms] 6.55/2.51 (9) QCSDP 6.55/2.51 (10) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 6.55/2.51 (11) TRUE 6.55/2.51 (12) QCSDP 6.55/2.51 (13) QCSUsableRulesProof [EQUIVALENT, 0 ms] 6.55/2.51 (14) QCSDP 6.55/2.51 (15) QCSDPMuMonotonicPoloProof [EQUIVALENT, 58 ms] 6.55/2.51 (16) QCSDP 6.55/2.51 (17) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 6.55/2.51 (18) TRUE 6.55/2.51 (19) QCSDP 6.55/2.51 (20) QCSDPSubtermProof [EQUIVALENT, 0 ms] 6.55/2.51 (21) QCSDP 6.55/2.51 (22) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 6.55/2.51 (23) TRUE 6.55/2.51 (24) QCSDP 6.55/2.51 (25) QCSDPSubtermProof [EQUIVALENT, 0 ms] 6.55/2.51 (26) QCSDP 6.55/2.51 (27) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 6.55/2.51 (28) TRUE 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (0) 6.55/2.51 Obligation: 6.55/2.51 Q restricted rewrite system: 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 active(U101(tt, M, N)) -> mark(U102(isNatKind(M), M, N)) 6.55/2.51 active(U102(tt, M, N)) -> mark(U103(isNat(N), M, N)) 6.55/2.51 active(U103(tt, M, N)) -> mark(U104(isNatKind(N), M, N)) 6.55/2.51 active(U104(tt, M, N)) -> mark(plus(x(N, M), N)) 6.55/2.51 active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) 6.55/2.51 active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) 6.55/2.51 active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) 6.55/2.51 active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) 6.55/2.51 active(U15(tt, V2)) -> mark(U16(isNat(V2))) 6.55/2.51 active(U16(tt)) -> mark(tt) 6.55/2.51 active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) 6.55/2.51 active(U22(tt, V1)) -> mark(U23(isNat(V1))) 6.55/2.51 active(U23(tt)) -> mark(tt) 6.55/2.51 active(U31(tt, V1, V2)) -> mark(U32(isNatKind(V1), V1, V2)) 6.55/2.51 active(U32(tt, V1, V2)) -> mark(U33(isNatKind(V2), V1, V2)) 6.55/2.51 active(U33(tt, V1, V2)) -> mark(U34(isNatKind(V2), V1, V2)) 6.55/2.51 active(U34(tt, V1, V2)) -> mark(U35(isNat(V1), V2)) 6.55/2.51 active(U35(tt, V2)) -> mark(U36(isNat(V2))) 6.55/2.51 active(U36(tt)) -> mark(tt) 6.55/2.51 active(U41(tt, V2)) -> mark(U42(isNatKind(V2))) 6.55/2.51 active(U42(tt)) -> mark(tt) 6.55/2.51 active(U51(tt)) -> mark(tt) 6.55/2.51 active(U61(tt, V2)) -> mark(U62(isNatKind(V2))) 6.55/2.51 active(U62(tt)) -> mark(tt) 6.55/2.51 active(U71(tt, N)) -> mark(U72(isNatKind(N), N)) 6.55/2.51 active(U72(tt, N)) -> mark(N) 6.55/2.51 active(U81(tt, M, N)) -> mark(U82(isNatKind(M), M, N)) 6.55/2.51 active(U82(tt, M, N)) -> mark(U83(isNat(N), M, N)) 6.55/2.51 active(U83(tt, M, N)) -> mark(U84(isNatKind(N), M, N)) 6.55/2.51 active(U84(tt, M, N)) -> mark(s(plus(N, M))) 6.55/2.51 active(U91(tt, N)) -> mark(U92(isNatKind(N))) 6.55/2.51 active(U92(tt)) -> mark(0) 6.55/2.51 active(isNat(0)) -> mark(tt) 6.55/2.51 active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) 6.55/2.51 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 6.55/2.51 active(isNat(x(V1, V2))) -> mark(U31(isNatKind(V1), V1, V2)) 6.55/2.51 active(isNatKind(0)) -> mark(tt) 6.55/2.51 active(isNatKind(plus(V1, V2))) -> mark(U41(isNatKind(V1), V2)) 6.55/2.51 active(isNatKind(s(V1))) -> mark(U51(isNatKind(V1))) 6.55/2.51 active(isNatKind(x(V1, V2))) -> mark(U61(isNatKind(V1), V2)) 6.55/2.51 active(plus(N, 0)) -> mark(U71(isNat(N), N)) 6.55/2.51 active(plus(N, s(M))) -> mark(U81(isNat(M), M, N)) 6.55/2.51 active(x(N, 0)) -> mark(U91(isNat(N), N)) 6.55/2.51 active(x(N, s(M))) -> mark(U101(isNat(M), M, N)) 6.55/2.51 active(U101(X1, X2, X3)) -> U101(active(X1), X2, X3) 6.55/2.51 active(U102(X1, X2, X3)) -> U102(active(X1), X2, X3) 6.55/2.51 active(U103(X1, X2, X3)) -> U103(active(X1), X2, X3) 6.55/2.51 active(U104(X1, X2, X3)) -> U104(active(X1), X2, X3) 6.55/2.51 active(plus(X1, X2)) -> plus(active(X1), X2) 6.55/2.51 active(plus(X1, X2)) -> plus(X1, active(X2)) 6.55/2.51 active(x(X1, X2)) -> x(active(X1), X2) 6.55/2.51 active(x(X1, X2)) -> x(X1, active(X2)) 6.55/2.51 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 6.55/2.51 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 6.55/2.51 active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) 6.55/2.51 active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) 6.55/2.51 active(U15(X1, X2)) -> U15(active(X1), X2) 6.55/2.51 active(U16(X)) -> U16(active(X)) 6.55/2.51 active(U21(X1, X2)) -> U21(active(X1), X2) 6.55/2.51 active(U22(X1, X2)) -> U22(active(X1), X2) 6.55/2.51 active(U23(X)) -> U23(active(X)) 6.55/2.51 active(U31(X1, X2, X3)) -> U31(active(X1), X2, X3) 6.55/2.51 active(U32(X1, X2, X3)) -> U32(active(X1), X2, X3) 6.55/2.51 active(U33(X1, X2, X3)) -> U33(active(X1), X2, X3) 6.55/2.51 active(U34(X1, X2, X3)) -> U34(active(X1), X2, X3) 6.55/2.51 active(U35(X1, X2)) -> U35(active(X1), X2) 6.55/2.51 active(U36(X)) -> U36(active(X)) 6.55/2.51 active(U41(X1, X2)) -> U41(active(X1), X2) 6.55/2.51 active(U42(X)) -> U42(active(X)) 6.55/2.51 active(U51(X)) -> U51(active(X)) 6.55/2.51 active(U61(X1, X2)) -> U61(active(X1), X2) 6.55/2.51 active(U62(X)) -> U62(active(X)) 6.55/2.51 active(U71(X1, X2)) -> U71(active(X1), X2) 6.55/2.51 active(U72(X1, X2)) -> U72(active(X1), X2) 6.55/2.51 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 6.55/2.51 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 6.55/2.51 active(U83(X1, X2, X3)) -> U83(active(X1), X2, X3) 6.55/2.51 active(U84(X1, X2, X3)) -> U84(active(X1), X2, X3) 6.55/2.51 active(s(X)) -> s(active(X)) 6.55/2.51 active(U91(X1, X2)) -> U91(active(X1), X2) 6.55/2.51 active(U92(X)) -> U92(active(X)) 6.55/2.51 U101(mark(X1), X2, X3) -> mark(U101(X1, X2, X3)) 6.55/2.51 U102(mark(X1), X2, X3) -> mark(U102(X1, X2, X3)) 6.55/2.51 U103(mark(X1), X2, X3) -> mark(U103(X1, X2, X3)) 6.55/2.51 U104(mark(X1), X2, X3) -> mark(U104(X1, X2, X3)) 6.55/2.51 plus(mark(X1), X2) -> mark(plus(X1, X2)) 6.55/2.51 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 6.55/2.51 x(mark(X1), X2) -> mark(x(X1, X2)) 6.55/2.51 x(X1, mark(X2)) -> mark(x(X1, X2)) 6.55/2.51 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 6.55/2.51 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 6.55/2.51 U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) 6.55/2.51 U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) 6.55/2.51 U15(mark(X1), X2) -> mark(U15(X1, X2)) 6.55/2.51 U16(mark(X)) -> mark(U16(X)) 6.55/2.51 U21(mark(X1), X2) -> mark(U21(X1, X2)) 6.55/2.51 U22(mark(X1), X2) -> mark(U22(X1, X2)) 6.55/2.51 U23(mark(X)) -> mark(U23(X)) 6.55/2.51 U31(mark(X1), X2, X3) -> mark(U31(X1, X2, X3)) 6.55/2.51 U32(mark(X1), X2, X3) -> mark(U32(X1, X2, X3)) 6.55/2.51 U33(mark(X1), X2, X3) -> mark(U33(X1, X2, X3)) 6.55/2.51 U34(mark(X1), X2, X3) -> mark(U34(X1, X2, X3)) 6.55/2.51 U35(mark(X1), X2) -> mark(U35(X1, X2)) 6.55/2.51 U36(mark(X)) -> mark(U36(X)) 6.55/2.51 U41(mark(X1), X2) -> mark(U41(X1, X2)) 6.55/2.51 U42(mark(X)) -> mark(U42(X)) 6.55/2.51 U51(mark(X)) -> mark(U51(X)) 6.55/2.51 U61(mark(X1), X2) -> mark(U61(X1, X2)) 6.55/2.51 U62(mark(X)) -> mark(U62(X)) 6.55/2.51 U71(mark(X1), X2) -> mark(U71(X1, X2)) 6.55/2.51 U72(mark(X1), X2) -> mark(U72(X1, X2)) 6.55/2.51 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 6.55/2.51 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 6.55/2.51 U83(mark(X1), X2, X3) -> mark(U83(X1, X2, X3)) 6.55/2.51 U84(mark(X1), X2, X3) -> mark(U84(X1, X2, X3)) 6.55/2.51 s(mark(X)) -> mark(s(X)) 6.55/2.51 U91(mark(X1), X2) -> mark(U91(X1, X2)) 6.55/2.51 U92(mark(X)) -> mark(U92(X)) 6.55/2.51 proper(U101(X1, X2, X3)) -> U101(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(tt) -> ok(tt) 6.55/2.51 proper(U102(X1, X2, X3)) -> U102(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(isNatKind(X)) -> isNatKind(proper(X)) 6.55/2.51 proper(U103(X1, X2, X3)) -> U103(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(isNat(X)) -> isNat(proper(X)) 6.55/2.51 proper(U104(X1, X2, X3)) -> U104(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 6.55/2.51 proper(x(X1, X2)) -> x(proper(X1), proper(X2)) 6.55/2.51 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) 6.55/2.51 proper(U16(X)) -> U16(proper(X)) 6.55/2.51 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 6.55/2.51 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 6.55/2.51 proper(U23(X)) -> U23(proper(X)) 6.55/2.51 proper(U31(X1, X2, X3)) -> U31(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U32(X1, X2, X3)) -> U32(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U33(X1, X2, X3)) -> U33(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U34(X1, X2, X3)) -> U34(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U35(X1, X2)) -> U35(proper(X1), proper(X2)) 6.55/2.51 proper(U36(X)) -> U36(proper(X)) 6.55/2.51 proper(U41(X1, X2)) -> U41(proper(X1), proper(X2)) 6.55/2.51 proper(U42(X)) -> U42(proper(X)) 6.55/2.51 proper(U51(X)) -> U51(proper(X)) 6.55/2.51 proper(U61(X1, X2)) -> U61(proper(X1), proper(X2)) 6.55/2.51 proper(U62(X)) -> U62(proper(X)) 6.55/2.51 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 6.55/2.51 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 6.55/2.51 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U83(X1, X2, X3)) -> U83(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U84(X1, X2, X3)) -> U84(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(s(X)) -> s(proper(X)) 6.55/2.51 proper(U91(X1, X2)) -> U91(proper(X1), proper(X2)) 6.55/2.51 proper(U92(X)) -> U92(proper(X)) 6.55/2.51 proper(0) -> ok(0) 6.55/2.51 U101(ok(X1), ok(X2), ok(X3)) -> ok(U101(X1, X2, X3)) 6.55/2.51 U102(ok(X1), ok(X2), ok(X3)) -> ok(U102(X1, X2, X3)) 6.55/2.51 isNatKind(ok(X)) -> ok(isNatKind(X)) 6.55/2.51 U103(ok(X1), ok(X2), ok(X3)) -> ok(U103(X1, X2, X3)) 6.55/2.51 isNat(ok(X)) -> ok(isNat(X)) 6.55/2.51 U104(ok(X1), ok(X2), ok(X3)) -> ok(U104(X1, X2, X3)) 6.55/2.51 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 6.55/2.51 x(ok(X1), ok(X2)) -> ok(x(X1, X2)) 6.55/2.51 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 6.55/2.51 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 6.55/2.51 U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) 6.55/2.51 U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) 6.55/2.51 U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) 6.55/2.51 U16(ok(X)) -> ok(U16(X)) 6.55/2.51 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 6.55/2.51 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 6.55/2.51 U23(ok(X)) -> ok(U23(X)) 6.55/2.51 U31(ok(X1), ok(X2), ok(X3)) -> ok(U31(X1, X2, X3)) 6.55/2.51 U32(ok(X1), ok(X2), ok(X3)) -> ok(U32(X1, X2, X3)) 6.55/2.51 U33(ok(X1), ok(X2), ok(X3)) -> ok(U33(X1, X2, X3)) 6.55/2.51 U34(ok(X1), ok(X2), ok(X3)) -> ok(U34(X1, X2, X3)) 6.55/2.51 U35(ok(X1), ok(X2)) -> ok(U35(X1, X2)) 6.55/2.51 U36(ok(X)) -> ok(U36(X)) 6.55/2.51 U41(ok(X1), ok(X2)) -> ok(U41(X1, X2)) 6.55/2.51 U42(ok(X)) -> ok(U42(X)) 6.55/2.51 U51(ok(X)) -> ok(U51(X)) 6.55/2.51 U61(ok(X1), ok(X2)) -> ok(U61(X1, X2)) 6.55/2.51 U62(ok(X)) -> ok(U62(X)) 6.55/2.51 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 6.55/2.51 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 6.55/2.51 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 6.55/2.51 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 6.55/2.51 U83(ok(X1), ok(X2), ok(X3)) -> ok(U83(X1, X2, X3)) 6.55/2.51 U84(ok(X1), ok(X2), ok(X3)) -> ok(U84(X1, X2, X3)) 6.55/2.51 s(ok(X)) -> ok(s(X)) 6.55/2.51 U91(ok(X1), ok(X2)) -> ok(U91(X1, X2)) 6.55/2.51 U92(ok(X)) -> ok(U92(X)) 6.55/2.51 top(mark(X)) -> top(proper(X)) 6.55/2.51 top(ok(X)) -> top(active(X)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 active(isNat(0)) 6.55/2.51 active(isNat(plus(x0, x1))) 6.55/2.51 active(isNat(s(x0))) 6.55/2.51 active(isNat(x(x0, x1))) 6.55/2.51 active(isNatKind(0)) 6.55/2.51 active(isNatKind(plus(x0, x1))) 6.55/2.51 active(isNatKind(s(x0))) 6.55/2.51 active(isNatKind(x(x0, x1))) 6.55/2.51 active(U101(x0, x1, x2)) 6.55/2.51 active(U102(x0, x1, x2)) 6.55/2.51 active(U103(x0, x1, x2)) 6.55/2.51 active(U104(x0, x1, x2)) 6.55/2.51 active(plus(x0, x1)) 6.55/2.51 active(x(x0, x1)) 6.55/2.51 active(U11(x0, x1, x2)) 6.55/2.51 active(U12(x0, x1, x2)) 6.55/2.51 active(U13(x0, x1, x2)) 6.55/2.51 active(U14(x0, x1, x2)) 6.55/2.51 active(U15(x0, x1)) 6.55/2.51 active(U16(x0)) 6.55/2.51 active(U21(x0, x1)) 6.55/2.51 active(U22(x0, x1)) 6.55/2.51 active(U23(x0)) 6.55/2.51 active(U31(x0, x1, x2)) 6.55/2.51 active(U32(x0, x1, x2)) 6.55/2.51 active(U33(x0, x1, x2)) 6.55/2.51 active(U34(x0, x1, x2)) 6.55/2.51 active(U35(x0, x1)) 6.55/2.51 active(U36(x0)) 6.55/2.51 active(U41(x0, x1)) 6.55/2.51 active(U42(x0)) 6.55/2.51 active(U51(x0)) 6.55/2.51 active(U61(x0, x1)) 6.55/2.51 active(U62(x0)) 6.55/2.51 active(U71(x0, x1)) 6.55/2.51 active(U72(x0, x1)) 6.55/2.51 active(U81(x0, x1, x2)) 6.55/2.51 active(U82(x0, x1, x2)) 6.55/2.51 active(U83(x0, x1, x2)) 6.55/2.51 active(U84(x0, x1, x2)) 6.55/2.51 active(s(x0)) 6.55/2.51 active(U91(x0, x1)) 6.55/2.51 active(U92(x0)) 6.55/2.51 U101(mark(x0), x1, x2) 6.55/2.51 U102(mark(x0), x1, x2) 6.55/2.51 U103(mark(x0), x1, x2) 6.55/2.51 U104(mark(x0), x1, x2) 6.55/2.51 plus(mark(x0), x1) 6.55/2.51 plus(x0, mark(x1)) 6.55/2.51 x(mark(x0), x1) 6.55/2.51 x(x0, mark(x1)) 6.55/2.51 U11(mark(x0), x1, x2) 6.55/2.51 U12(mark(x0), x1, x2) 6.55/2.51 U13(mark(x0), x1, x2) 6.55/2.51 U14(mark(x0), x1, x2) 6.55/2.51 U15(mark(x0), x1) 6.55/2.51 U16(mark(x0)) 6.55/2.51 U21(mark(x0), x1) 6.55/2.51 U22(mark(x0), x1) 6.55/2.51 U23(mark(x0)) 6.55/2.51 U31(mark(x0), x1, x2) 6.55/2.51 U32(mark(x0), x1, x2) 6.55/2.51 U33(mark(x0), x1, x2) 6.55/2.51 U34(mark(x0), x1, x2) 6.55/2.51 U35(mark(x0), x1) 6.55/2.51 U36(mark(x0)) 6.55/2.51 U41(mark(x0), x1) 6.55/2.51 U42(mark(x0)) 6.55/2.51 U51(mark(x0)) 6.55/2.51 U61(mark(x0), x1) 6.55/2.51 U62(mark(x0)) 6.55/2.51 U71(mark(x0), x1) 6.55/2.51 U72(mark(x0), x1) 6.55/2.51 U81(mark(x0), x1, x2) 6.55/2.51 U82(mark(x0), x1, x2) 6.55/2.51 U83(mark(x0), x1, x2) 6.55/2.51 U84(mark(x0), x1, x2) 6.55/2.51 s(mark(x0)) 6.55/2.51 U91(mark(x0), x1) 6.55/2.51 U92(mark(x0)) 6.55/2.51 proper(U101(x0, x1, x2)) 6.55/2.51 proper(tt) 6.55/2.51 proper(U102(x0, x1, x2)) 6.55/2.51 proper(isNatKind(x0)) 6.55/2.51 proper(U103(x0, x1, x2)) 6.55/2.51 proper(isNat(x0)) 6.55/2.51 proper(U104(x0, x1, x2)) 6.55/2.51 proper(plus(x0, x1)) 6.55/2.51 proper(x(x0, x1)) 6.55/2.51 proper(U11(x0, x1, x2)) 6.55/2.51 proper(U12(x0, x1, x2)) 6.55/2.51 proper(U13(x0, x1, x2)) 6.55/2.51 proper(U14(x0, x1, x2)) 6.55/2.51 proper(U15(x0, x1)) 6.55/2.51 proper(U16(x0)) 6.55/2.51 proper(U21(x0, x1)) 6.55/2.51 proper(U22(x0, x1)) 6.55/2.51 proper(U23(x0)) 6.55/2.51 proper(U31(x0, x1, x2)) 6.55/2.51 proper(U32(x0, x1, x2)) 6.55/2.51 proper(U33(x0, x1, x2)) 6.55/2.51 proper(U34(x0, x1, x2)) 6.55/2.51 proper(U35(x0, x1)) 6.55/2.51 proper(U36(x0)) 6.55/2.51 proper(U41(x0, x1)) 6.55/2.51 proper(U42(x0)) 6.55/2.51 proper(U51(x0)) 6.55/2.51 proper(U61(x0, x1)) 6.55/2.51 proper(U62(x0)) 6.55/2.51 proper(U71(x0, x1)) 6.55/2.51 proper(U72(x0, x1)) 6.55/2.51 proper(U81(x0, x1, x2)) 6.55/2.51 proper(U82(x0, x1, x2)) 6.55/2.51 proper(U83(x0, x1, x2)) 6.55/2.51 proper(U84(x0, x1, x2)) 6.55/2.51 proper(s(x0)) 6.55/2.51 proper(U91(x0, x1)) 6.55/2.51 proper(U92(x0)) 6.55/2.51 proper(0) 6.55/2.51 U101(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U102(ok(x0), ok(x1), ok(x2)) 6.55/2.51 isNatKind(ok(x0)) 6.55/2.51 U103(ok(x0), ok(x1), ok(x2)) 6.55/2.51 isNat(ok(x0)) 6.55/2.51 U104(ok(x0), ok(x1), ok(x2)) 6.55/2.51 plus(ok(x0), ok(x1)) 6.55/2.51 x(ok(x0), ok(x1)) 6.55/2.51 U11(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U12(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U13(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U14(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U15(ok(x0), ok(x1)) 6.55/2.51 U16(ok(x0)) 6.55/2.51 U21(ok(x0), ok(x1)) 6.55/2.51 U22(ok(x0), ok(x1)) 6.55/2.51 U23(ok(x0)) 6.55/2.51 U31(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U32(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U33(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U34(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U35(ok(x0), ok(x1)) 6.55/2.51 U36(ok(x0)) 6.55/2.51 U41(ok(x0), ok(x1)) 6.55/2.51 U42(ok(x0)) 6.55/2.51 U51(ok(x0)) 6.55/2.51 U61(ok(x0), ok(x1)) 6.55/2.51 U62(ok(x0)) 6.55/2.51 U71(ok(x0), ok(x1)) 6.55/2.51 U72(ok(x0), ok(x1)) 6.55/2.51 U81(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U82(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U83(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U84(ok(x0), ok(x1), ok(x2)) 6.55/2.51 s(ok(x0)) 6.55/2.51 U91(ok(x0), ok(x1)) 6.55/2.51 U92(ok(x0)) 6.55/2.51 top(mark(x0)) 6.55/2.51 top(ok(x0)) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (1) QTRSToCSRProof (SOUND) 6.55/2.51 The following Q TRS is given: Q restricted rewrite system: 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 active(U101(tt, M, N)) -> mark(U102(isNatKind(M), M, N)) 6.55/2.51 active(U102(tt, M, N)) -> mark(U103(isNat(N), M, N)) 6.55/2.51 active(U103(tt, M, N)) -> mark(U104(isNatKind(N), M, N)) 6.55/2.51 active(U104(tt, M, N)) -> mark(plus(x(N, M), N)) 6.55/2.51 active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) 6.55/2.51 active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) 6.55/2.51 active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) 6.55/2.51 active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) 6.55/2.51 active(U15(tt, V2)) -> mark(U16(isNat(V2))) 6.55/2.51 active(U16(tt)) -> mark(tt) 6.55/2.51 active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) 6.55/2.51 active(U22(tt, V1)) -> mark(U23(isNat(V1))) 6.55/2.51 active(U23(tt)) -> mark(tt) 6.55/2.51 active(U31(tt, V1, V2)) -> mark(U32(isNatKind(V1), V1, V2)) 6.55/2.51 active(U32(tt, V1, V2)) -> mark(U33(isNatKind(V2), V1, V2)) 6.55/2.51 active(U33(tt, V1, V2)) -> mark(U34(isNatKind(V2), V1, V2)) 6.55/2.51 active(U34(tt, V1, V2)) -> mark(U35(isNat(V1), V2)) 6.55/2.51 active(U35(tt, V2)) -> mark(U36(isNat(V2))) 6.55/2.51 active(U36(tt)) -> mark(tt) 6.55/2.51 active(U41(tt, V2)) -> mark(U42(isNatKind(V2))) 6.55/2.51 active(U42(tt)) -> mark(tt) 6.55/2.51 active(U51(tt)) -> mark(tt) 6.55/2.51 active(U61(tt, V2)) -> mark(U62(isNatKind(V2))) 6.55/2.51 active(U62(tt)) -> mark(tt) 6.55/2.51 active(U71(tt, N)) -> mark(U72(isNatKind(N), N)) 6.55/2.51 active(U72(tt, N)) -> mark(N) 6.55/2.51 active(U81(tt, M, N)) -> mark(U82(isNatKind(M), M, N)) 6.55/2.51 active(U82(tt, M, N)) -> mark(U83(isNat(N), M, N)) 6.55/2.51 active(U83(tt, M, N)) -> mark(U84(isNatKind(N), M, N)) 6.55/2.51 active(U84(tt, M, N)) -> mark(s(plus(N, M))) 6.55/2.51 active(U91(tt, N)) -> mark(U92(isNatKind(N))) 6.55/2.51 active(U92(tt)) -> mark(0) 6.55/2.51 active(isNat(0)) -> mark(tt) 6.55/2.51 active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) 6.55/2.51 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 6.55/2.51 active(isNat(x(V1, V2))) -> mark(U31(isNatKind(V1), V1, V2)) 6.55/2.51 active(isNatKind(0)) -> mark(tt) 6.55/2.51 active(isNatKind(plus(V1, V2))) -> mark(U41(isNatKind(V1), V2)) 6.55/2.51 active(isNatKind(s(V1))) -> mark(U51(isNatKind(V1))) 6.55/2.51 active(isNatKind(x(V1, V2))) -> mark(U61(isNatKind(V1), V2)) 6.55/2.51 active(plus(N, 0)) -> mark(U71(isNat(N), N)) 6.55/2.51 active(plus(N, s(M))) -> mark(U81(isNat(M), M, N)) 6.55/2.51 active(x(N, 0)) -> mark(U91(isNat(N), N)) 6.55/2.51 active(x(N, s(M))) -> mark(U101(isNat(M), M, N)) 6.55/2.51 active(U101(X1, X2, X3)) -> U101(active(X1), X2, X3) 6.55/2.51 active(U102(X1, X2, X3)) -> U102(active(X1), X2, X3) 6.55/2.51 active(U103(X1, X2, X3)) -> U103(active(X1), X2, X3) 6.55/2.51 active(U104(X1, X2, X3)) -> U104(active(X1), X2, X3) 6.55/2.51 active(plus(X1, X2)) -> plus(active(X1), X2) 6.55/2.51 active(plus(X1, X2)) -> plus(X1, active(X2)) 6.55/2.51 active(x(X1, X2)) -> x(active(X1), X2) 6.55/2.51 active(x(X1, X2)) -> x(X1, active(X2)) 6.55/2.51 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 6.55/2.51 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 6.55/2.51 active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) 6.55/2.51 active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) 6.55/2.51 active(U15(X1, X2)) -> U15(active(X1), X2) 6.55/2.51 active(U16(X)) -> U16(active(X)) 6.55/2.51 active(U21(X1, X2)) -> U21(active(X1), X2) 6.55/2.51 active(U22(X1, X2)) -> U22(active(X1), X2) 6.55/2.51 active(U23(X)) -> U23(active(X)) 6.55/2.51 active(U31(X1, X2, X3)) -> U31(active(X1), X2, X3) 6.55/2.51 active(U32(X1, X2, X3)) -> U32(active(X1), X2, X3) 6.55/2.51 active(U33(X1, X2, X3)) -> U33(active(X1), X2, X3) 6.55/2.51 active(U34(X1, X2, X3)) -> U34(active(X1), X2, X3) 6.55/2.51 active(U35(X1, X2)) -> U35(active(X1), X2) 6.55/2.51 active(U36(X)) -> U36(active(X)) 6.55/2.51 active(U41(X1, X2)) -> U41(active(X1), X2) 6.55/2.51 active(U42(X)) -> U42(active(X)) 6.55/2.51 active(U51(X)) -> U51(active(X)) 6.55/2.51 active(U61(X1, X2)) -> U61(active(X1), X2) 6.55/2.51 active(U62(X)) -> U62(active(X)) 6.55/2.51 active(U71(X1, X2)) -> U71(active(X1), X2) 6.55/2.51 active(U72(X1, X2)) -> U72(active(X1), X2) 6.55/2.51 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 6.55/2.51 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 6.55/2.51 active(U83(X1, X2, X3)) -> U83(active(X1), X2, X3) 6.55/2.51 active(U84(X1, X2, X3)) -> U84(active(X1), X2, X3) 6.55/2.51 active(s(X)) -> s(active(X)) 6.55/2.51 active(U91(X1, X2)) -> U91(active(X1), X2) 6.55/2.51 active(U92(X)) -> U92(active(X)) 6.55/2.51 U101(mark(X1), X2, X3) -> mark(U101(X1, X2, X3)) 6.55/2.51 U102(mark(X1), X2, X3) -> mark(U102(X1, X2, X3)) 6.55/2.51 U103(mark(X1), X2, X3) -> mark(U103(X1, X2, X3)) 6.55/2.51 U104(mark(X1), X2, X3) -> mark(U104(X1, X2, X3)) 6.55/2.51 plus(mark(X1), X2) -> mark(plus(X1, X2)) 6.55/2.51 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 6.55/2.51 x(mark(X1), X2) -> mark(x(X1, X2)) 6.55/2.51 x(X1, mark(X2)) -> mark(x(X1, X2)) 6.55/2.51 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 6.55/2.51 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 6.55/2.51 U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) 6.55/2.51 U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) 6.55/2.51 U15(mark(X1), X2) -> mark(U15(X1, X2)) 6.55/2.51 U16(mark(X)) -> mark(U16(X)) 6.55/2.51 U21(mark(X1), X2) -> mark(U21(X1, X2)) 6.55/2.51 U22(mark(X1), X2) -> mark(U22(X1, X2)) 6.55/2.51 U23(mark(X)) -> mark(U23(X)) 6.55/2.51 U31(mark(X1), X2, X3) -> mark(U31(X1, X2, X3)) 6.55/2.51 U32(mark(X1), X2, X3) -> mark(U32(X1, X2, X3)) 6.55/2.51 U33(mark(X1), X2, X3) -> mark(U33(X1, X2, X3)) 6.55/2.51 U34(mark(X1), X2, X3) -> mark(U34(X1, X2, X3)) 6.55/2.51 U35(mark(X1), X2) -> mark(U35(X1, X2)) 6.55/2.51 U36(mark(X)) -> mark(U36(X)) 6.55/2.51 U41(mark(X1), X2) -> mark(U41(X1, X2)) 6.55/2.51 U42(mark(X)) -> mark(U42(X)) 6.55/2.51 U51(mark(X)) -> mark(U51(X)) 6.55/2.51 U61(mark(X1), X2) -> mark(U61(X1, X2)) 6.55/2.51 U62(mark(X)) -> mark(U62(X)) 6.55/2.51 U71(mark(X1), X2) -> mark(U71(X1, X2)) 6.55/2.51 U72(mark(X1), X2) -> mark(U72(X1, X2)) 6.55/2.51 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 6.55/2.51 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 6.55/2.51 U83(mark(X1), X2, X3) -> mark(U83(X1, X2, X3)) 6.55/2.51 U84(mark(X1), X2, X3) -> mark(U84(X1, X2, X3)) 6.55/2.51 s(mark(X)) -> mark(s(X)) 6.55/2.51 U91(mark(X1), X2) -> mark(U91(X1, X2)) 6.55/2.51 U92(mark(X)) -> mark(U92(X)) 6.55/2.51 proper(U101(X1, X2, X3)) -> U101(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(tt) -> ok(tt) 6.55/2.51 proper(U102(X1, X2, X3)) -> U102(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(isNatKind(X)) -> isNatKind(proper(X)) 6.55/2.51 proper(U103(X1, X2, X3)) -> U103(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(isNat(X)) -> isNat(proper(X)) 6.55/2.51 proper(U104(X1, X2, X3)) -> U104(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 6.55/2.51 proper(x(X1, X2)) -> x(proper(X1), proper(X2)) 6.55/2.51 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) 6.55/2.51 proper(U16(X)) -> U16(proper(X)) 6.55/2.51 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 6.55/2.51 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 6.55/2.51 proper(U23(X)) -> U23(proper(X)) 6.55/2.51 proper(U31(X1, X2, X3)) -> U31(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U32(X1, X2, X3)) -> U32(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U33(X1, X2, X3)) -> U33(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U34(X1, X2, X3)) -> U34(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U35(X1, X2)) -> U35(proper(X1), proper(X2)) 6.55/2.51 proper(U36(X)) -> U36(proper(X)) 6.55/2.51 proper(U41(X1, X2)) -> U41(proper(X1), proper(X2)) 6.55/2.51 proper(U42(X)) -> U42(proper(X)) 6.55/2.51 proper(U51(X)) -> U51(proper(X)) 6.55/2.51 proper(U61(X1, X2)) -> U61(proper(X1), proper(X2)) 6.55/2.51 proper(U62(X)) -> U62(proper(X)) 6.55/2.51 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 6.55/2.51 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 6.55/2.51 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U83(X1, X2, X3)) -> U83(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(U84(X1, X2, X3)) -> U84(proper(X1), proper(X2), proper(X3)) 6.55/2.51 proper(s(X)) -> s(proper(X)) 6.55/2.51 proper(U91(X1, X2)) -> U91(proper(X1), proper(X2)) 6.55/2.51 proper(U92(X)) -> U92(proper(X)) 6.55/2.51 proper(0) -> ok(0) 6.55/2.51 U101(ok(X1), ok(X2), ok(X3)) -> ok(U101(X1, X2, X3)) 6.55/2.51 U102(ok(X1), ok(X2), ok(X3)) -> ok(U102(X1, X2, X3)) 6.55/2.51 isNatKind(ok(X)) -> ok(isNatKind(X)) 6.55/2.51 U103(ok(X1), ok(X2), ok(X3)) -> ok(U103(X1, X2, X3)) 6.55/2.51 isNat(ok(X)) -> ok(isNat(X)) 6.55/2.51 U104(ok(X1), ok(X2), ok(X3)) -> ok(U104(X1, X2, X3)) 6.55/2.51 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 6.55/2.51 x(ok(X1), ok(X2)) -> ok(x(X1, X2)) 6.55/2.51 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 6.55/2.51 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 6.55/2.51 U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) 6.55/2.51 U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) 6.55/2.51 U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) 6.55/2.51 U16(ok(X)) -> ok(U16(X)) 6.55/2.51 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 6.55/2.51 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 6.55/2.51 U23(ok(X)) -> ok(U23(X)) 6.55/2.51 U31(ok(X1), ok(X2), ok(X3)) -> ok(U31(X1, X2, X3)) 6.55/2.51 U32(ok(X1), ok(X2), ok(X3)) -> ok(U32(X1, X2, X3)) 6.55/2.51 U33(ok(X1), ok(X2), ok(X3)) -> ok(U33(X1, X2, X3)) 6.55/2.51 U34(ok(X1), ok(X2), ok(X3)) -> ok(U34(X1, X2, X3)) 6.55/2.51 U35(ok(X1), ok(X2)) -> ok(U35(X1, X2)) 6.55/2.51 U36(ok(X)) -> ok(U36(X)) 6.55/2.51 U41(ok(X1), ok(X2)) -> ok(U41(X1, X2)) 6.55/2.51 U42(ok(X)) -> ok(U42(X)) 6.55/2.51 U51(ok(X)) -> ok(U51(X)) 6.55/2.51 U61(ok(X1), ok(X2)) -> ok(U61(X1, X2)) 6.55/2.51 U62(ok(X)) -> ok(U62(X)) 6.55/2.51 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 6.55/2.51 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 6.55/2.51 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 6.55/2.51 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 6.55/2.51 U83(ok(X1), ok(X2), ok(X3)) -> ok(U83(X1, X2, X3)) 6.55/2.51 U84(ok(X1), ok(X2), ok(X3)) -> ok(U84(X1, X2, X3)) 6.55/2.51 s(ok(X)) -> ok(s(X)) 6.55/2.51 U91(ok(X1), ok(X2)) -> ok(U91(X1, X2)) 6.55/2.51 U92(ok(X)) -> ok(U92(X)) 6.55/2.51 top(mark(X)) -> top(proper(X)) 6.55/2.51 top(ok(X)) -> top(active(X)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 active(isNat(0)) 6.55/2.51 active(isNat(plus(x0, x1))) 6.55/2.51 active(isNat(s(x0))) 6.55/2.51 active(isNat(x(x0, x1))) 6.55/2.51 active(isNatKind(0)) 6.55/2.51 active(isNatKind(plus(x0, x1))) 6.55/2.51 active(isNatKind(s(x0))) 6.55/2.51 active(isNatKind(x(x0, x1))) 6.55/2.51 active(U101(x0, x1, x2)) 6.55/2.51 active(U102(x0, x1, x2)) 6.55/2.51 active(U103(x0, x1, x2)) 6.55/2.51 active(U104(x0, x1, x2)) 6.55/2.51 active(plus(x0, x1)) 6.55/2.51 active(x(x0, x1)) 6.55/2.51 active(U11(x0, x1, x2)) 6.55/2.51 active(U12(x0, x1, x2)) 6.55/2.51 active(U13(x0, x1, x2)) 6.55/2.51 active(U14(x0, x1, x2)) 6.55/2.51 active(U15(x0, x1)) 6.55/2.51 active(U16(x0)) 6.55/2.51 active(U21(x0, x1)) 6.55/2.51 active(U22(x0, x1)) 6.55/2.51 active(U23(x0)) 6.55/2.51 active(U31(x0, x1, x2)) 6.55/2.51 active(U32(x0, x1, x2)) 6.55/2.51 active(U33(x0, x1, x2)) 6.55/2.51 active(U34(x0, x1, x2)) 6.55/2.51 active(U35(x0, x1)) 6.55/2.51 active(U36(x0)) 6.55/2.51 active(U41(x0, x1)) 6.55/2.51 active(U42(x0)) 6.55/2.51 active(U51(x0)) 6.55/2.51 active(U61(x0, x1)) 6.55/2.51 active(U62(x0)) 6.55/2.51 active(U71(x0, x1)) 6.55/2.51 active(U72(x0, x1)) 6.55/2.51 active(U81(x0, x1, x2)) 6.55/2.51 active(U82(x0, x1, x2)) 6.55/2.51 active(U83(x0, x1, x2)) 6.55/2.51 active(U84(x0, x1, x2)) 6.55/2.51 active(s(x0)) 6.55/2.51 active(U91(x0, x1)) 6.55/2.51 active(U92(x0)) 6.55/2.51 U101(mark(x0), x1, x2) 6.55/2.51 U102(mark(x0), x1, x2) 6.55/2.51 U103(mark(x0), x1, x2) 6.55/2.51 U104(mark(x0), x1, x2) 6.55/2.51 plus(mark(x0), x1) 6.55/2.51 plus(x0, mark(x1)) 6.55/2.51 x(mark(x0), x1) 6.55/2.51 x(x0, mark(x1)) 6.55/2.51 U11(mark(x0), x1, x2) 6.55/2.51 U12(mark(x0), x1, x2) 6.55/2.51 U13(mark(x0), x1, x2) 6.55/2.51 U14(mark(x0), x1, x2) 6.55/2.51 U15(mark(x0), x1) 6.55/2.51 U16(mark(x0)) 6.55/2.51 U21(mark(x0), x1) 6.55/2.51 U22(mark(x0), x1) 6.55/2.51 U23(mark(x0)) 6.55/2.51 U31(mark(x0), x1, x2) 6.55/2.51 U32(mark(x0), x1, x2) 6.55/2.51 U33(mark(x0), x1, x2) 6.55/2.51 U34(mark(x0), x1, x2) 6.55/2.51 U35(mark(x0), x1) 6.55/2.51 U36(mark(x0)) 6.55/2.51 U41(mark(x0), x1) 6.55/2.51 U42(mark(x0)) 6.55/2.51 U51(mark(x0)) 6.55/2.51 U61(mark(x0), x1) 6.55/2.51 U62(mark(x0)) 6.55/2.51 U71(mark(x0), x1) 6.55/2.51 U72(mark(x0), x1) 6.55/2.51 U81(mark(x0), x1, x2) 6.55/2.51 U82(mark(x0), x1, x2) 6.55/2.51 U83(mark(x0), x1, x2) 6.55/2.51 U84(mark(x0), x1, x2) 6.55/2.51 s(mark(x0)) 6.55/2.51 U91(mark(x0), x1) 6.55/2.51 U92(mark(x0)) 6.55/2.51 proper(U101(x0, x1, x2)) 6.55/2.51 proper(tt) 6.55/2.51 proper(U102(x0, x1, x2)) 6.55/2.51 proper(isNatKind(x0)) 6.55/2.51 proper(U103(x0, x1, x2)) 6.55/2.51 proper(isNat(x0)) 6.55/2.51 proper(U104(x0, x1, x2)) 6.55/2.51 proper(plus(x0, x1)) 6.55/2.51 proper(x(x0, x1)) 6.55/2.51 proper(U11(x0, x1, x2)) 6.55/2.51 proper(U12(x0, x1, x2)) 6.55/2.51 proper(U13(x0, x1, x2)) 6.55/2.51 proper(U14(x0, x1, x2)) 6.55/2.51 proper(U15(x0, x1)) 6.55/2.51 proper(U16(x0)) 6.55/2.51 proper(U21(x0, x1)) 6.55/2.51 proper(U22(x0, x1)) 6.55/2.51 proper(U23(x0)) 6.55/2.51 proper(U31(x0, x1, x2)) 6.55/2.51 proper(U32(x0, x1, x2)) 6.55/2.51 proper(U33(x0, x1, x2)) 6.55/2.51 proper(U34(x0, x1, x2)) 6.55/2.51 proper(U35(x0, x1)) 6.55/2.51 proper(U36(x0)) 6.55/2.51 proper(U41(x0, x1)) 6.55/2.51 proper(U42(x0)) 6.55/2.51 proper(U51(x0)) 6.55/2.51 proper(U61(x0, x1)) 6.55/2.51 proper(U62(x0)) 6.55/2.51 proper(U71(x0, x1)) 6.55/2.51 proper(U72(x0, x1)) 6.55/2.51 proper(U81(x0, x1, x2)) 6.55/2.51 proper(U82(x0, x1, x2)) 6.55/2.51 proper(U83(x0, x1, x2)) 6.55/2.51 proper(U84(x0, x1, x2)) 6.55/2.51 proper(s(x0)) 6.55/2.51 proper(U91(x0, x1)) 6.55/2.51 proper(U92(x0)) 6.55/2.51 proper(0) 6.55/2.51 U101(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U102(ok(x0), ok(x1), ok(x2)) 6.55/2.51 isNatKind(ok(x0)) 6.55/2.51 U103(ok(x0), ok(x1), ok(x2)) 6.55/2.51 isNat(ok(x0)) 6.55/2.51 U104(ok(x0), ok(x1), ok(x2)) 6.55/2.51 plus(ok(x0), ok(x1)) 6.55/2.51 x(ok(x0), ok(x1)) 6.55/2.51 U11(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U12(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U13(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U14(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U15(ok(x0), ok(x1)) 6.55/2.51 U16(ok(x0)) 6.55/2.51 U21(ok(x0), ok(x1)) 6.55/2.51 U22(ok(x0), ok(x1)) 6.55/2.51 U23(ok(x0)) 6.55/2.51 U31(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U32(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U33(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U34(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U35(ok(x0), ok(x1)) 6.55/2.51 U36(ok(x0)) 6.55/2.51 U41(ok(x0), ok(x1)) 6.55/2.51 U42(ok(x0)) 6.55/2.51 U51(ok(x0)) 6.55/2.51 U61(ok(x0), ok(x1)) 6.55/2.51 U62(ok(x0)) 6.55/2.51 U71(ok(x0), ok(x1)) 6.55/2.51 U72(ok(x0), ok(x1)) 6.55/2.51 U81(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U82(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U83(ok(x0), ok(x1), ok(x2)) 6.55/2.51 U84(ok(x0), ok(x1), ok(x2)) 6.55/2.51 s(ok(x0)) 6.55/2.51 U91(ok(x0), ok(x1)) 6.55/2.51 U92(ok(x0)) 6.55/2.51 top(mark(x0)) 6.55/2.51 top(ok(x0)) 6.55/2.51 6.55/2.51 Special symbols used for the transformation (see [GM04]): 6.55/2.51 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 6.55/2.51 The replacement map contains the following entries: 6.55/2.51 6.55/2.51 U101: {1} 6.55/2.51 tt: empty set 6.55/2.51 U102: {1} 6.55/2.51 isNatKind: empty set 6.55/2.51 U103: {1} 6.55/2.51 isNat: empty set 6.55/2.51 U104: {1} 6.55/2.51 plus: {1, 2} 6.55/2.51 x: {1, 2} 6.55/2.51 U11: {1} 6.55/2.51 U12: {1} 6.55/2.51 U13: {1} 6.55/2.51 U14: {1} 6.55/2.51 U15: {1} 6.55/2.51 U16: {1} 6.55/2.51 U21: {1} 6.55/2.51 U22: {1} 6.55/2.51 U23: {1} 6.55/2.51 U31: {1} 6.55/2.51 U32: {1} 6.55/2.51 U33: {1} 6.55/2.51 U34: {1} 6.55/2.51 U35: {1} 6.55/2.51 U36: {1} 6.55/2.51 U41: {1} 6.55/2.51 U42: {1} 6.55/2.51 U51: {1} 6.55/2.51 U61: {1} 6.55/2.51 U62: {1} 6.55/2.51 U71: {1} 6.55/2.51 U72: {1} 6.55/2.51 U81: {1} 6.55/2.51 U82: {1} 6.55/2.51 U83: {1} 6.55/2.51 U84: {1} 6.55/2.51 s: {1} 6.55/2.51 U91: {1} 6.55/2.51 U92: {1} 6.55/2.51 0: empty set 6.55/2.51 The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (2) 6.55/2.51 Obligation: 6.55/2.51 Context-sensitive rewrite system: 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.51 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.52 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.52 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.52 U72(tt, N) -> N 6.55/2.52 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.52 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.52 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.52 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.52 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 plus(N, 0) -> U71(isNat(N), N) 6.55/2.52 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.52 x(N, 0) -> U91(isNat(N), N) 6.55/2.52 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.52 6.55/2.52 The replacement map contains the following entries: 6.55/2.52 6.55/2.52 U101: {1} 6.55/2.52 tt: empty set 6.55/2.52 U102: {1} 6.55/2.52 isNatKind: empty set 6.55/2.52 U103: {1} 6.55/2.52 isNat: empty set 6.55/2.52 U104: {1} 6.55/2.52 plus: {1, 2} 6.55/2.52 x: {1, 2} 6.55/2.52 U11: {1} 6.55/2.52 U12: {1} 6.55/2.52 U13: {1} 6.55/2.52 U14: {1} 6.55/2.52 U15: {1} 6.55/2.52 U16: {1} 6.55/2.52 U21: {1} 6.55/2.52 U22: {1} 6.55/2.52 U23: {1} 6.55/2.52 U31: {1} 6.55/2.52 U32: {1} 6.55/2.52 U33: {1} 6.55/2.52 U34: {1} 6.55/2.52 U35: {1} 6.55/2.52 U36: {1} 6.55/2.52 U41: {1} 6.55/2.52 U42: {1} 6.55/2.52 U51: {1} 6.55/2.52 U61: {1} 6.55/2.52 U62: {1} 6.55/2.52 U71: {1} 6.55/2.52 U72: {1} 6.55/2.52 U81: {1} 6.55/2.52 U82: {1} 6.55/2.52 U83: {1} 6.55/2.52 U84: {1} 6.55/2.52 s: {1} 6.55/2.52 U91: {1} 6.55/2.52 U92: {1} 6.55/2.52 0: empty set 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (3) CSDependencyPairsProof (EQUIVALENT) 6.55/2.52 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (4) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, PLUS_2, X_2, U16'_1, U23'_1, U36'_1, U42'_1, U62'_1, U92'_1, U51'_1} are replacing on all positions. 6.55/2.52 For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U102'_3, U101'_3, U103'_3, U104'_3, U12'_3, U11'_3, U13'_3, U14'_3, U15'_2, U22'_2, U21'_2, U32'_3, U31'_3, U33'_3, U34'_3, U35'_2, U41'_2, U61'_2, U72'_2, U71'_2, U82'_3, U81'_3, U83'_3, U84'_3, U91'_2} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1, ISNATKIND_1, ISNAT_1, U_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The ordinary context-sensitive dependency pairs DP_o are: 6.55/2.52 U101'(tt, M, N) -> U102'(isNatKind(M), M, N) 6.55/2.52 U101'(tt, M, N) -> ISNATKIND(M) 6.55/2.52 U102'(tt, M, N) -> U103'(isNat(N), M, N) 6.55/2.52 U102'(tt, M, N) -> ISNAT(N) 6.55/2.52 U103'(tt, M, N) -> U104'(isNatKind(N), M, N) 6.55/2.52 U103'(tt, M, N) -> ISNATKIND(N) 6.55/2.52 U104'(tt, M, N) -> PLUS(x(N, M), N) 6.55/2.52 U104'(tt, M, N) -> X(N, M) 6.55/2.52 U11'(tt, V1, V2) -> U12'(isNatKind(V1), V1, V2) 6.55/2.52 U11'(tt, V1, V2) -> ISNATKIND(V1) 6.55/2.52 U12'(tt, V1, V2) -> U13'(isNatKind(V2), V1, V2) 6.55/2.52 U12'(tt, V1, V2) -> ISNATKIND(V2) 6.55/2.52 U13'(tt, V1, V2) -> U14'(isNatKind(V2), V1, V2) 6.55/2.52 U13'(tt, V1, V2) -> ISNATKIND(V2) 6.55/2.52 U14'(tt, V1, V2) -> U15'(isNat(V1), V2) 6.55/2.52 U14'(tt, V1, V2) -> ISNAT(V1) 6.55/2.52 U15'(tt, V2) -> U16'(isNat(V2)) 6.55/2.52 U15'(tt, V2) -> ISNAT(V2) 6.55/2.52 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 6.55/2.52 U21'(tt, V1) -> ISNATKIND(V1) 6.55/2.52 U22'(tt, V1) -> U23'(isNat(V1)) 6.55/2.52 U22'(tt, V1) -> ISNAT(V1) 6.55/2.52 U31'(tt, V1, V2) -> U32'(isNatKind(V1), V1, V2) 6.55/2.52 U31'(tt, V1, V2) -> ISNATKIND(V1) 6.55/2.52 U32'(tt, V1, V2) -> U33'(isNatKind(V2), V1, V2) 6.55/2.52 U32'(tt, V1, V2) -> ISNATKIND(V2) 6.55/2.52 U33'(tt, V1, V2) -> U34'(isNatKind(V2), V1, V2) 6.55/2.52 U33'(tt, V1, V2) -> ISNATKIND(V2) 6.55/2.52 U34'(tt, V1, V2) -> U35'(isNat(V1), V2) 6.55/2.52 U34'(tt, V1, V2) -> ISNAT(V1) 6.55/2.52 U35'(tt, V2) -> U36'(isNat(V2)) 6.55/2.52 U35'(tt, V2) -> ISNAT(V2) 6.55/2.52 U41'(tt, V2) -> U42'(isNatKind(V2)) 6.55/2.52 U41'(tt, V2) -> ISNATKIND(V2) 6.55/2.52 U61'(tt, V2) -> U62'(isNatKind(V2)) 6.55/2.52 U61'(tt, V2) -> ISNATKIND(V2) 6.55/2.52 U71'(tt, N) -> U72'(isNatKind(N), N) 6.55/2.52 U71'(tt, N) -> ISNATKIND(N) 6.55/2.52 U81'(tt, M, N) -> U82'(isNatKind(M), M, N) 6.55/2.52 U81'(tt, M, N) -> ISNATKIND(M) 6.55/2.52 U82'(tt, M, N) -> U83'(isNat(N), M, N) 6.55/2.52 U82'(tt, M, N) -> ISNAT(N) 6.55/2.52 U83'(tt, M, N) -> U84'(isNatKind(N), M, N) 6.55/2.52 U83'(tt, M, N) -> ISNATKIND(N) 6.55/2.52 U84'(tt, M, N) -> PLUS(N, M) 6.55/2.52 U91'(tt, N) -> U92'(isNatKind(N)) 6.55/2.52 U91'(tt, N) -> ISNATKIND(N) 6.55/2.52 ISNAT(plus(V1, V2)) -> U11'(isNatKind(V1), V1, V2) 6.55/2.52 ISNAT(plus(V1, V2)) -> ISNATKIND(V1) 6.55/2.52 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 6.55/2.52 ISNAT(s(V1)) -> ISNATKIND(V1) 6.55/2.52 ISNAT(x(V1, V2)) -> U31'(isNatKind(V1), V1, V2) 6.55/2.52 ISNAT(x(V1, V2)) -> ISNATKIND(V1) 6.55/2.52 ISNATKIND(plus(V1, V2)) -> U41'(isNatKind(V1), V2) 6.55/2.52 ISNATKIND(plus(V1, V2)) -> ISNATKIND(V1) 6.55/2.52 ISNATKIND(s(V1)) -> U51'(isNatKind(V1)) 6.55/2.52 ISNATKIND(s(V1)) -> ISNATKIND(V1) 6.55/2.52 ISNATKIND(x(V1, V2)) -> U61'(isNatKind(V1), V2) 6.55/2.52 ISNATKIND(x(V1, V2)) -> ISNATKIND(V1) 6.55/2.52 PLUS(N, 0) -> U71'(isNat(N), N) 6.55/2.52 PLUS(N, 0) -> ISNAT(N) 6.55/2.52 PLUS(N, s(M)) -> U81'(isNat(M), M, N) 6.55/2.52 PLUS(N, s(M)) -> ISNAT(M) 6.55/2.52 X(N, 0) -> U91'(isNat(N), N) 6.55/2.52 X(N, 0) -> ISNAT(N) 6.55/2.52 X(N, s(M)) -> U101'(isNat(M), M, N) 6.55/2.52 X(N, s(M)) -> ISNAT(M) 6.55/2.52 6.55/2.52 The collapsing dependency pairs are DP_c: 6.55/2.52 U104'(tt, M, N) -> N 6.55/2.52 U104'(tt, M, N) -> M 6.55/2.52 U72'(tt, N) -> N 6.55/2.52 U84'(tt, M, N) -> N 6.55/2.52 U84'(tt, M, N) -> M 6.55/2.52 6.55/2.52 6.55/2.52 The hidden terms of R are: 6.55/2.52 none 6.55/2.52 6.55/2.52 Every hiding context is built from:none 6.55/2.52 6.55/2.52 Hence, the new unhiding pairs DP_u are : 6.55/2.52 U104'(tt, M, N) -> U(N) 6.55/2.52 U104'(tt, M, N) -> U(M) 6.55/2.52 U72'(tt, N) -> U(N) 6.55/2.52 U84'(tt, M, N) -> U(N) 6.55/2.52 U84'(tt, M, N) -> U(M) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.52 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.52 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.52 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.52 U72(tt, N) -> N 6.55/2.52 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.52 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.52 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.52 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.52 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 plus(N, 0) -> U71(isNat(N), N) 6.55/2.52 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.52 x(N, 0) -> U91(isNat(N), N) 6.55/2.52 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (5) QCSDependencyGraphProof (EQUIVALENT) 6.55/2.52 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 4 SCCs with 38 less nodes. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (6) 6.55/2.52 Complex Obligation (AND) 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (7) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1} are replacing on all positions. 6.55/2.52 For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U41'_2, U61'_2} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1, ISNATKIND_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 U41'(tt, V2) -> ISNATKIND(V2) 6.55/2.52 ISNATKIND(plus(V1, V2)) -> U41'(isNatKind(V1), V2) 6.55/2.52 ISNATKIND(plus(V1, V2)) -> ISNATKIND(V1) 6.55/2.52 ISNATKIND(s(V1)) -> ISNATKIND(V1) 6.55/2.52 ISNATKIND(x(V1, V2)) -> U61'(isNatKind(V1), V2) 6.55/2.52 U61'(tt, V2) -> ISNATKIND(V2) 6.55/2.52 ISNATKIND(x(V1, V2)) -> ISNATKIND(V1) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.52 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.52 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.52 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.52 U72(tt, N) -> N 6.55/2.52 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.52 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.52 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.52 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.52 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 plus(N, 0) -> U71(isNat(N), N) 6.55/2.52 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.52 x(N, 0) -> U91(isNat(N), N) 6.55/2.52 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (8) QCSDPSubtermProof (EQUIVALENT) 6.55/2.52 We use the subterm processor [DA_EMMES]. 6.55/2.52 6.55/2.52 6.55/2.52 The following pairs can be oriented strictly and are deleted. 6.55/2.52 6.55/2.52 ISNATKIND(plus(V1, V2)) -> U41'(isNatKind(V1), V2) 6.55/2.52 ISNATKIND(plus(V1, V2)) -> ISNATKIND(V1) 6.55/2.52 ISNATKIND(s(V1)) -> ISNATKIND(V1) 6.55/2.52 ISNATKIND(x(V1, V2)) -> U61'(isNatKind(V1), V2) 6.55/2.52 ISNATKIND(x(V1, V2)) -> ISNATKIND(V1) 6.55/2.52 The remaining pairs can at least be oriented weakly. 6.55/2.52 6.55/2.52 U41'(tt, V2) -> ISNATKIND(V2) 6.55/2.52 U61'(tt, V2) -> ISNATKIND(V2) 6.55/2.52 Used ordering: Combined order from the following AFS and order. 6.55/2.52 ISNATKIND(x1) = x1 6.55/2.52 6.55/2.52 U41'(x1, x2) = x2 6.55/2.52 6.55/2.52 U61'(x1, x2) = x2 6.55/2.52 6.55/2.52 6.55/2.52 Subterm Order 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (9) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1} are replacing on all positions. 6.55/2.52 For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U41'_2, U61'_2} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1, ISNATKIND_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 U41'(tt, V2) -> ISNATKIND(V2) 6.55/2.52 U61'(tt, V2) -> ISNATKIND(V2) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.52 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.52 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.52 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.52 U72(tt, N) -> N 6.55/2.52 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.52 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.52 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.52 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.52 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 plus(N, 0) -> U71(isNat(N), N) 6.55/2.52 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.52 x(N, 0) -> U91(isNat(N), N) 6.55/2.52 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (10) QCSDependencyGraphProof (EQUIVALENT) 6.55/2.52 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (11) 6.55/2.52 TRUE 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (12) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1} are replacing on all positions. 6.55/2.52 For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U12'_3, U11'_3, U13'_3, U14'_3, U15'_2, U21'_2, U22'_2, U31'_3, U32'_3, U33'_3, U34'_3, U35'_2} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1, ISNAT_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 U11'(tt, V1, V2) -> U12'(isNatKind(V1), V1, V2) 6.55/2.52 U12'(tt, V1, V2) -> U13'(isNatKind(V2), V1, V2) 6.55/2.52 U13'(tt, V1, V2) -> U14'(isNatKind(V2), V1, V2) 6.55/2.52 U14'(tt, V1, V2) -> U15'(isNat(V1), V2) 6.55/2.52 U15'(tt, V2) -> ISNAT(V2) 6.55/2.52 ISNAT(plus(V1, V2)) -> U11'(isNatKind(V1), V1, V2) 6.55/2.52 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 6.55/2.52 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 6.55/2.52 U22'(tt, V1) -> ISNAT(V1) 6.55/2.52 ISNAT(x(V1, V2)) -> U31'(isNatKind(V1), V1, V2) 6.55/2.52 U31'(tt, V1, V2) -> U32'(isNatKind(V1), V1, V2) 6.55/2.52 U32'(tt, V1, V2) -> U33'(isNatKind(V2), V1, V2) 6.55/2.52 U33'(tt, V1, V2) -> U34'(isNatKind(V2), V1, V2) 6.55/2.52 U34'(tt, V1, V2) -> U35'(isNat(V1), V2) 6.55/2.52 U35'(tt, V2) -> ISNAT(V2) 6.55/2.52 U34'(tt, V1, V2) -> ISNAT(V1) 6.55/2.52 U14'(tt, V1, V2) -> ISNAT(V1) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.52 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.52 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.52 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.52 U72(tt, N) -> N 6.55/2.52 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.52 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.52 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.52 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.52 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 plus(N, 0) -> U71(isNat(N), N) 6.55/2.52 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.52 x(N, 0) -> U91(isNat(N), N) 6.55/2.52 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (13) QCSUsableRulesProof (EQUIVALENT) 6.55/2.52 The following rules are not useable [DA_EMMES] and can be deleted: 6.55/2.52 6.55/2.52 U101(tt, x0, x1) -> U102(isNatKind(x0), x0, x1) 6.55/2.52 U102(tt, x0, x1) -> U103(isNat(x1), x0, x1) 6.55/2.52 U103(tt, x0, x1) -> U104(isNatKind(x1), x0, x1) 6.55/2.52 U104(tt, x0, x1) -> plus(x(x1, x0), x1) 6.55/2.52 U71(tt, x0) -> U72(isNatKind(x0), x0) 6.55/2.52 U72(tt, x0) -> x0 6.55/2.52 U81(tt, x0, x1) -> U82(isNatKind(x0), x0, x1) 6.55/2.52 U82(tt, x0, x1) -> U83(isNat(x1), x0, x1) 6.55/2.52 U83(tt, x0, x1) -> U84(isNatKind(x1), x0, x1) 6.55/2.52 U84(tt, x0, x1) -> s(plus(x1, x0)) 6.55/2.52 U91(tt, x0) -> U92(isNatKind(x0)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 plus(x0, 0) -> U71(isNat(x0), x0) 6.55/2.52 plus(x0, s(x1)) -> U81(isNat(x1), x1, x0) 6.55/2.52 x(x0, 0) -> U91(isNat(x0), x0) 6.55/2.52 x(x0, s(x1)) -> U101(isNat(x1), x1, x0) 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (14) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, s_1, U51_1, x_2, U62_1, U42_1, U23_1, U36_1, U16_1} are replacing on all positions. 6.55/2.52 For all symbols f in {U41_2, U61_2, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U12'_3, U11'_3, U13'_3, U14'_3, U15'_2, U21'_2, U22'_2, U31'_3, U32'_3, U33'_3, U34'_3, U35'_2} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1, ISNAT_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 U11'(tt, V1, V2) -> U12'(isNatKind(V1), V1, V2) 6.55/2.52 U12'(tt, V1, V2) -> U13'(isNatKind(V2), V1, V2) 6.55/2.52 U13'(tt, V1, V2) -> U14'(isNatKind(V2), V1, V2) 6.55/2.52 U14'(tt, V1, V2) -> U15'(isNat(V1), V2) 6.55/2.52 U15'(tt, V2) -> ISNAT(V2) 6.55/2.52 ISNAT(plus(V1, V2)) -> U11'(isNatKind(V1), V1, V2) 6.55/2.52 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 6.55/2.52 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 6.55/2.52 U22'(tt, V1) -> ISNAT(V1) 6.55/2.52 ISNAT(x(V1, V2)) -> U31'(isNatKind(V1), V1, V2) 6.55/2.52 U31'(tt, V1, V2) -> U32'(isNatKind(V1), V1, V2) 6.55/2.52 U32'(tt, V1, V2) -> U33'(isNatKind(V2), V1, V2) 6.55/2.52 U33'(tt, V1, V2) -> U34'(isNatKind(V2), V1, V2) 6.55/2.52 U34'(tt, V1, V2) -> U35'(isNat(V1), V2) 6.55/2.52 U35'(tt, V2) -> ISNAT(V2) 6.55/2.52 U34'(tt, V1, V2) -> ISNAT(V1) 6.55/2.52 U14'(tt, V1, V2) -> ISNAT(V1) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U23(tt) -> tt 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (15) QCSDPMuMonotonicPoloProof (EQUIVALENT) 6.55/2.52 By using the following mu-monotonic polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this Q-CSDP problem can be strictly oriented and thus deleted. 6.55/2.52 6.55/2.52 Strictly oriented dependency pairs: 6.55/2.52 6.55/2.52 U14'(tt, V1, V2) -> U15'(isNat(V1), V2) 6.55/2.52 U15'(tt, V2) -> ISNAT(V2) 6.55/2.52 ISNAT(plus(V1, V2)) -> U11'(isNatKind(V1), V1, V2) 6.55/2.52 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 6.55/2.52 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 6.55/2.52 U22'(tt, V1) -> ISNAT(V1) 6.55/2.52 ISNAT(x(V1, V2)) -> U31'(isNatKind(V1), V1, V2) 6.55/2.52 U34'(tt, V1, V2) -> U35'(isNat(V1), V2) 6.55/2.52 U35'(tt, V2) -> ISNAT(V2) 6.55/2.52 U34'(tt, V1, V2) -> ISNAT(V1) 6.55/2.52 U14'(tt, V1, V2) -> ISNAT(V1) 6.55/2.52 6.55/2.52 Strictly oriented rules of the TRS R: 6.55/2.52 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 6.55/2.52 Used ordering: POLO with Polynomial interpretation [POLO]: 6.55/2.52 6.55/2.52 POL(0) = 2 6.55/2.52 POL(ISNAT(x_1)) = 2 + 2*x_1 6.55/2.52 POL(U11(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U11'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U12(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U12'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U13(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U13'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U14(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U14'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U15(x_1, x_2)) = x_1 + 2*x_2 6.55/2.52 POL(U15'(x_1, x_2)) = 1 + x_1 + 2*x_2 6.55/2.52 POL(U16(x_1)) = 2*x_1 6.55/2.52 POL(U21(x_1, x_2)) = x_1 + 2*x_2 6.55/2.52 POL(U21'(x_1, x_2)) = 2*x_1 + 2*x_2 6.55/2.52 POL(U22(x_1, x_2)) = x_1 + 2*x_2 6.55/2.52 POL(U22'(x_1, x_2)) = 1 + x_1 + 2*x_2 6.55/2.52 POL(U23(x_1)) = 1 + 2*x_1 6.55/2.52 POL(U31(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U31'(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U32(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 6.55/2.52 POL(U32'(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U33(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 6.55/2.52 POL(U33'(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U34(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 6.55/2.52 POL(U34'(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 6.55/2.52 POL(U35(x_1, x_2)) = 1 + 2*x_1 + x_2 6.55/2.52 POL(U35'(x_1, x_2)) = 2*x_1 + 2*x_2 6.55/2.52 POL(U36(x_1)) = x_1 6.55/2.52 POL(U41(x_1, x_2)) = x_1 6.55/2.52 POL(U42(x_1)) = x_1 6.55/2.52 POL(U51(x_1)) = x_1 6.55/2.52 POL(U61(x_1, x_2)) = x_1 6.55/2.52 POL(U62(x_1)) = x_1 6.55/2.52 POL(isNat(x_1)) = x_1 6.55/2.52 POL(isNatKind(x_1)) = 2 6.55/2.52 POL(plus(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 6.55/2.52 POL(s(x_1)) = 2 + 2*x_1 6.55/2.52 POL(tt) = 2 6.55/2.52 POL(x(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 6.55/2.52 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (16) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, s_1, U51_1, x_2, U62_1, U42_1, U36_1} are replacing on all positions. 6.55/2.52 For all symbols f in {U41_2, U61_2, U11_3, U12_3, U13_3, U14_3, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U12'_3, U11'_3, U13'_3, U14'_3, U32'_3, U31'_3, U33'_3, U34'_3} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 U11'(tt, V1, V2) -> U12'(isNatKind(V1), V1, V2) 6.55/2.52 U12'(tt, V1, V2) -> U13'(isNatKind(V2), V1, V2) 6.55/2.52 U13'(tt, V1, V2) -> U14'(isNatKind(V2), V1, V2) 6.55/2.52 U31'(tt, V1, V2) -> U32'(isNatKind(V1), V1, V2) 6.55/2.52 U32'(tt, V1, V2) -> U33'(isNatKind(V2), V1, V2) 6.55/2.52 U33'(tt, V1, V2) -> U34'(isNatKind(V2), V1, V2) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U36(tt) -> tt 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (17) QCSDependencyGraphProof (EQUIVALENT) 6.55/2.52 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 6 less nodes. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (18) 6.55/2.52 TRUE 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (19) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, PLUS_2} are replacing on all positions. 6.55/2.52 For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U83'_3, U82'_3, U84'_3, U81'_3} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 U82'(tt, M, N) -> U83'(isNat(N), M, N) 6.55/2.52 U83'(tt, M, N) -> U84'(isNatKind(N), M, N) 6.55/2.52 U84'(tt, M, N) -> PLUS(N, M) 6.55/2.52 PLUS(N, s(M)) -> U81'(isNat(M), M, N) 6.55/2.52 U81'(tt, M, N) -> U82'(isNatKind(M), M, N) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.52 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.52 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.52 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.52 U72(tt, N) -> N 6.55/2.52 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.52 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.52 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.52 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.52 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 plus(N, 0) -> U71(isNat(N), N) 6.55/2.52 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.52 x(N, 0) -> U91(isNat(N), N) 6.55/2.52 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (20) QCSDPSubtermProof (EQUIVALENT) 6.55/2.52 We use the subterm processor [DA_EMMES]. 6.55/2.52 6.55/2.52 6.55/2.52 The following pairs can be oriented strictly and are deleted. 6.55/2.52 6.55/2.52 PLUS(N, s(M)) -> U81'(isNat(M), M, N) 6.55/2.52 The remaining pairs can at least be oriented weakly. 6.55/2.52 6.55/2.52 U82'(tt, M, N) -> U83'(isNat(N), M, N) 6.55/2.52 U83'(tt, M, N) -> U84'(isNatKind(N), M, N) 6.55/2.52 U84'(tt, M, N) -> PLUS(N, M) 6.55/2.52 U81'(tt, M, N) -> U82'(isNatKind(M), M, N) 6.55/2.52 Used ordering: Combined order from the following AFS and order. 6.55/2.52 U83'(x1, x2, x3) = x2 6.55/2.52 6.55/2.52 U82'(x1, x2, x3) = x2 6.55/2.52 6.55/2.52 U84'(x1, x2, x3) = x2 6.55/2.52 6.55/2.52 PLUS(x1, x2) = x2 6.55/2.52 6.55/2.52 U81'(x1, x2, x3) = x2 6.55/2.52 6.55/2.52 6.55/2.52 Subterm Order 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (21) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, PLUS_2} are replacing on all positions. 6.55/2.52 For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U83'_3, U82'_3, U84'_3, U81'_3} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 U82'(tt, M, N) -> U83'(isNat(N), M, N) 6.55/2.52 U83'(tt, M, N) -> U84'(isNatKind(N), M, N) 6.55/2.52 U84'(tt, M, N) -> PLUS(N, M) 6.55/2.52 U81'(tt, M, N) -> U82'(isNatKind(M), M, N) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.52 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.52 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.52 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.52 U72(tt, N) -> N 6.55/2.52 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.52 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.52 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.52 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.52 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 plus(N, 0) -> U71(isNat(N), N) 6.55/2.52 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.52 x(N, 0) -> U91(isNat(N), N) 6.55/2.52 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (22) QCSDependencyGraphProof (EQUIVALENT) 6.55/2.52 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 4 less nodes. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (23) 6.55/2.52 TRUE 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (24) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, X_2} are replacing on all positions. 6.55/2.52 For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U103'_3, U102'_3, U104'_3, U101'_3} we have mu(f) = {1}. 6.55/2.52 The symbols in {isNatKind_1, isNat_1} are not replacing on any position. 6.55/2.52 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 U102'(tt, M, N) -> U103'(isNat(N), M, N) 6.55/2.52 U103'(tt, M, N) -> U104'(isNatKind(N), M, N) 6.55/2.52 U104'(tt, M, N) -> X(N, M) 6.55/2.52 X(N, s(M)) -> U101'(isNat(M), M, N) 6.55/2.52 U101'(tt, M, N) -> U102'(isNatKind(M), M, N) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.52 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.52 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.52 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.52 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.52 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.52 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.52 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.52 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.52 U16(tt) -> tt 6.55/2.52 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.52 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.52 U23(tt) -> tt 6.55/2.52 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.52 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.52 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.52 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.52 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.52 U36(tt) -> tt 6.55/2.52 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.52 U42(tt) -> tt 6.55/2.52 U51(tt) -> tt 6.55/2.52 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.52 U62(tt) -> tt 6.55/2.52 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.52 U72(tt, N) -> N 6.55/2.52 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.52 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.52 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.52 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.52 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.52 U92(tt) -> 0 6.55/2.52 isNat(0) -> tt 6.55/2.52 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.52 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.52 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.52 isNatKind(0) -> tt 6.55/2.52 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.52 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.52 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.52 plus(N, 0) -> U71(isNat(N), N) 6.55/2.52 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.52 x(N, 0) -> U91(isNat(N), N) 6.55/2.52 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.52 6.55/2.52 Q is empty. 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (25) QCSDPSubtermProof (EQUIVALENT) 6.55/2.52 We use the subterm processor [DA_EMMES]. 6.55/2.52 6.55/2.52 6.55/2.52 The following pairs can be oriented strictly and are deleted. 6.55/2.52 6.55/2.52 X(N, s(M)) -> U101'(isNat(M), M, N) 6.55/2.52 The remaining pairs can at least be oriented weakly. 6.55/2.52 6.55/2.52 U102'(tt, M, N) -> U103'(isNat(N), M, N) 6.55/2.52 U103'(tt, M, N) -> U104'(isNatKind(N), M, N) 6.55/2.52 U104'(tt, M, N) -> X(N, M) 6.55/2.52 U101'(tt, M, N) -> U102'(isNatKind(M), M, N) 6.55/2.52 Used ordering: Combined order from the following AFS and order. 6.55/2.52 U103'(x1, x2, x3) = x2 6.55/2.52 6.55/2.52 U102'(x1, x2, x3) = x2 6.55/2.52 6.55/2.52 U104'(x1, x2, x3) = x2 6.55/2.52 6.55/2.52 X(x1, x2) = x2 6.55/2.52 6.55/2.52 U101'(x1, x2, x3) = x2 6.55/2.52 6.55/2.52 6.55/2.52 Subterm Order 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (26) 6.55/2.52 Obligation: 6.55/2.52 Q-restricted context-sensitive dependency pair problem: 6.55/2.52 The symbols in {plus_2, x_2, U16_1, U23_1, U36_1, U42_1, U51_1, U62_1, s_1, U92_1, X_2} are replacing on all positions. 6.55/2.52 For all symbols f in {U101_3, U102_3, U103_3, U104_3, U11_3, U12_3, U13_3, U14_3, U15_2, U21_2, U22_2, U31_3, U32_3, U33_3, U34_3, U35_2, U41_2, U61_2, U71_2, U72_2, U81_3, U82_3, U83_3, U84_3, U91_2, U103'_3, U102'_3, U104'_3, U101'_3} we have mu(f) = {1}. 6.55/2.53 The symbols in {isNatKind_1, isNat_1} are not replacing on any position. 6.55/2.53 6.55/2.53 The TRS P consists of the following rules: 6.55/2.53 6.55/2.53 U102'(tt, M, N) -> U103'(isNat(N), M, N) 6.55/2.53 U103'(tt, M, N) -> U104'(isNatKind(N), M, N) 6.55/2.53 U104'(tt, M, N) -> X(N, M) 6.55/2.53 U101'(tt, M, N) -> U102'(isNatKind(M), M, N) 6.55/2.53 6.55/2.53 The TRS R consists of the following rules: 6.55/2.53 6.55/2.53 U101(tt, M, N) -> U102(isNatKind(M), M, N) 6.55/2.53 U102(tt, M, N) -> U103(isNat(N), M, N) 6.55/2.53 U103(tt, M, N) -> U104(isNatKind(N), M, N) 6.55/2.53 U104(tt, M, N) -> plus(x(N, M), N) 6.55/2.53 U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) 6.55/2.53 U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) 6.55/2.53 U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) 6.55/2.53 U14(tt, V1, V2) -> U15(isNat(V1), V2) 6.55/2.53 U15(tt, V2) -> U16(isNat(V2)) 6.55/2.53 U16(tt) -> tt 6.55/2.53 U21(tt, V1) -> U22(isNatKind(V1), V1) 6.55/2.53 U22(tt, V1) -> U23(isNat(V1)) 6.55/2.53 U23(tt) -> tt 6.55/2.53 U31(tt, V1, V2) -> U32(isNatKind(V1), V1, V2) 6.55/2.53 U32(tt, V1, V2) -> U33(isNatKind(V2), V1, V2) 6.55/2.53 U33(tt, V1, V2) -> U34(isNatKind(V2), V1, V2) 6.55/2.53 U34(tt, V1, V2) -> U35(isNat(V1), V2) 6.55/2.53 U35(tt, V2) -> U36(isNat(V2)) 6.55/2.53 U36(tt) -> tt 6.55/2.53 U41(tt, V2) -> U42(isNatKind(V2)) 6.55/2.53 U42(tt) -> tt 6.55/2.53 U51(tt) -> tt 6.55/2.53 U61(tt, V2) -> U62(isNatKind(V2)) 6.55/2.53 U62(tt) -> tt 6.55/2.53 U71(tt, N) -> U72(isNatKind(N), N) 6.55/2.53 U72(tt, N) -> N 6.55/2.53 U81(tt, M, N) -> U82(isNatKind(M), M, N) 6.55/2.53 U82(tt, M, N) -> U83(isNat(N), M, N) 6.55/2.53 U83(tt, M, N) -> U84(isNatKind(N), M, N) 6.55/2.53 U84(tt, M, N) -> s(plus(N, M)) 6.55/2.53 U91(tt, N) -> U92(isNatKind(N)) 6.55/2.53 U92(tt) -> 0 6.55/2.53 isNat(0) -> tt 6.55/2.53 isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) 6.55/2.53 isNat(s(V1)) -> U21(isNatKind(V1), V1) 6.55/2.53 isNat(x(V1, V2)) -> U31(isNatKind(V1), V1, V2) 6.55/2.53 isNatKind(0) -> tt 6.55/2.53 isNatKind(plus(V1, V2)) -> U41(isNatKind(V1), V2) 6.55/2.53 isNatKind(s(V1)) -> U51(isNatKind(V1)) 6.55/2.53 isNatKind(x(V1, V2)) -> U61(isNatKind(V1), V2) 6.55/2.53 plus(N, 0) -> U71(isNat(N), N) 6.55/2.53 plus(N, s(M)) -> U81(isNat(M), M, N) 6.55/2.53 x(N, 0) -> U91(isNat(N), N) 6.55/2.53 x(N, s(M)) -> U101(isNat(M), M, N) 6.55/2.53 6.55/2.53 Q is empty. 6.55/2.53 6.55/2.53 ---------------------------------------- 6.55/2.53 6.55/2.53 (27) QCSDependencyGraphProof (EQUIVALENT) 6.55/2.53 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 4 less nodes. 6.55/2.53 6.55/2.53 ---------------------------------------- 6.55/2.53 6.55/2.53 (28) 6.55/2.53 TRUE 6.55/2.54 EOF