/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) QTRSToCSRProof [EQUIVALENT, 0 ms] (2) CSR (3) CSRRRRProof [EQUIVALENT, 109 ms] (4) CSR (5) CSRRRRProof [EQUIVALENT, 0 ms] (6) CSR (7) CSRRRRProof [EQUIVALENT, 17 ms] (8) CSR (9) CSRRRRProof [EQUIVALENT, 0 ms] (10) CSR (11) CSRRRRProof [EQUIVALENT, 0 ms] (12) CSR (13) CSRRRRProof [EQUIVALENT, 17 ms] (14) CSR (15) CSRRRRProof [EQUIVALENT, 0 ms] (16) CSR (17) CSRRRRProof [EQUIVALENT, 8 ms] (18) CSR (19) CSRRRRProof [EQUIVALENT, 0 ms] (20) CSR (21) CSRRRRProof [EQUIVALENT, 0 ms] (22) CSR (23) CSRRRRProof [EQUIVALENT, 5 ms] (24) CSR (25) CSRRRRProof [EQUIVALENT, 0 ms] (26) CSR (27) CSRRRRProof [EQUIVALENT, 0 ms] (28) CSR (29) CSRRRRProof [EQUIVALENT, 0 ms] (30) CSR (31) RisEmptyProof [EQUIVALENT, 2 ms] (32) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) active(U15(tt, V2)) -> mark(U16(isNat(V2))) active(U16(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) active(U22(tt, V1)) -> mark(U23(isNat(V1))) active(U23(tt)) -> mark(tt) active(U31(tt, V2)) -> mark(U32(isNatKind(V2))) active(U32(tt)) -> mark(tt) active(U41(tt)) -> mark(tt) active(U51(tt, N)) -> mark(U52(isNatKind(N), N)) active(U52(tt, N)) -> mark(N) active(U61(tt, M, N)) -> mark(U62(isNatKind(M), M, N)) active(U62(tt, M, N)) -> mark(U63(isNat(N), M, N)) active(U63(tt, M, N)) -> mark(U64(isNatKind(N), M, N)) active(U64(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatKind(0)) -> mark(tt) active(isNatKind(plus(V1, V2))) -> mark(U31(isNatKind(V1), V2)) active(isNatKind(s(V1))) -> mark(U41(isNatKind(V1))) active(plus(N, 0)) -> mark(U51(isNat(N), N)) active(plus(N, s(M))) -> mark(U61(isNat(M), M, N)) active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) active(U15(X1, X2)) -> U15(active(X1), X2) active(U16(X)) -> U16(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X1, X2)) -> U22(active(X1), X2) active(U23(X)) -> U23(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X)) -> U41(active(X)) active(U51(X1, X2)) -> U51(active(X1), X2) active(U52(X1, X2)) -> U52(active(X1), X2) active(U61(X1, X2, X3)) -> U61(active(X1), X2, X3) active(U62(X1, X2, X3)) -> U62(active(X1), X2, X3) active(U63(X1, X2, X3)) -> U63(active(X1), X2, X3) active(U64(X1, X2, X3)) -> U64(active(X1), X2, X3) active(s(X)) -> s(active(X)) active(plus(X1, X2)) -> plus(active(X1), X2) active(plus(X1, X2)) -> plus(X1, active(X2)) U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) U15(mark(X1), X2) -> mark(U15(X1, X2)) U16(mark(X)) -> mark(U16(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X1), X2) -> mark(U22(X1, X2)) U23(mark(X)) -> mark(U23(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X)) -> mark(U41(X)) U51(mark(X1), X2) -> mark(U51(X1, X2)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U61(mark(X1), X2, X3) -> mark(U61(X1, X2, X3)) U62(mark(X1), X2, X3) -> mark(U62(X1, X2, X3)) U63(mark(X1), X2, X3) -> mark(U63(X1, X2, X3)) U64(mark(X1), X2, X3) -> mark(U64(X1, X2, X3)) s(mark(X)) -> mark(s(X)) plus(mark(X1), X2) -> mark(plus(X1, X2)) plus(X1, mark(X2)) -> mark(plus(X1, X2)) proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) proper(tt) -> ok(tt) proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) proper(isNat(X)) -> isNat(proper(X)) proper(U16(X)) -> U16(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) proper(U23(X)) -> U23(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X)) -> U41(proper(X)) proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U61(X1, X2, X3)) -> U61(proper(X1), proper(X2), proper(X3)) proper(U62(X1, X2, X3)) -> U62(proper(X1), proper(X2), proper(X3)) proper(U63(X1, X2, X3)) -> U63(proper(X1), proper(X2), proper(X3)) proper(U64(X1, X2, X3)) -> U64(proper(X1), proper(X2), proper(X3)) proper(s(X)) -> s(proper(X)) proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) proper(0) -> ok(0) U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) isNatKind(ok(X)) -> ok(isNatKind(X)) U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) isNat(ok(X)) -> ok(isNat(X)) U16(ok(X)) -> ok(U16(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) U23(ok(X)) -> ok(U23(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X)) -> ok(U41(X)) U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U61(ok(X1), ok(X2), ok(X3)) -> ok(U61(X1, X2, X3)) U62(ok(X1), ok(X2), ok(X3)) -> ok(U62(X1, X2, X3)) U63(ok(X1), ok(X2), ok(X3)) -> ok(U63(X1, X2, X3)) U64(ok(X1), ok(X2), ok(X3)) -> ok(U64(X1, X2, X3)) s(ok(X)) -> ok(s(X)) plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Q is empty. ---------------------------------------- (1) QTRSToCSRProof (EQUIVALENT) The following Q TRS is given: Q restricted rewrite system: The TRS R consists of the following rules: active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) active(U15(tt, V2)) -> mark(U16(isNat(V2))) active(U16(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) active(U22(tt, V1)) -> mark(U23(isNat(V1))) active(U23(tt)) -> mark(tt) active(U31(tt, V2)) -> mark(U32(isNatKind(V2))) active(U32(tt)) -> mark(tt) active(U41(tt)) -> mark(tt) active(U51(tt, N)) -> mark(U52(isNatKind(N), N)) active(U52(tt, N)) -> mark(N) active(U61(tt, M, N)) -> mark(U62(isNatKind(M), M, N)) active(U62(tt, M, N)) -> mark(U63(isNat(N), M, N)) active(U63(tt, M, N)) -> mark(U64(isNatKind(N), M, N)) active(U64(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatKind(0)) -> mark(tt) active(isNatKind(plus(V1, V2))) -> mark(U31(isNatKind(V1), V2)) active(isNatKind(s(V1))) -> mark(U41(isNatKind(V1))) active(plus(N, 0)) -> mark(U51(isNat(N), N)) active(plus(N, s(M))) -> mark(U61(isNat(M), M, N)) active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) active(U15(X1, X2)) -> U15(active(X1), X2) active(U16(X)) -> U16(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X1, X2)) -> U22(active(X1), X2) active(U23(X)) -> U23(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X)) -> U41(active(X)) active(U51(X1, X2)) -> U51(active(X1), X2) active(U52(X1, X2)) -> U52(active(X1), X2) active(U61(X1, X2, X3)) -> U61(active(X1), X2, X3) active(U62(X1, X2, X3)) -> U62(active(X1), X2, X3) active(U63(X1, X2, X3)) -> U63(active(X1), X2, X3) active(U64(X1, X2, X3)) -> U64(active(X1), X2, X3) active(s(X)) -> s(active(X)) active(plus(X1, X2)) -> plus(active(X1), X2) active(plus(X1, X2)) -> plus(X1, active(X2)) U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) U15(mark(X1), X2) -> mark(U15(X1, X2)) U16(mark(X)) -> mark(U16(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X1), X2) -> mark(U22(X1, X2)) U23(mark(X)) -> mark(U23(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X)) -> mark(U41(X)) U51(mark(X1), X2) -> mark(U51(X1, X2)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U61(mark(X1), X2, X3) -> mark(U61(X1, X2, X3)) U62(mark(X1), X2, X3) -> mark(U62(X1, X2, X3)) U63(mark(X1), X2, X3) -> mark(U63(X1, X2, X3)) U64(mark(X1), X2, X3) -> mark(U64(X1, X2, X3)) s(mark(X)) -> mark(s(X)) plus(mark(X1), X2) -> mark(plus(X1, X2)) plus(X1, mark(X2)) -> mark(plus(X1, X2)) proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) proper(tt) -> ok(tt) proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) proper(isNat(X)) -> isNat(proper(X)) proper(U16(X)) -> U16(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) proper(U23(X)) -> U23(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X)) -> U41(proper(X)) proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U61(X1, X2, X3)) -> U61(proper(X1), proper(X2), proper(X3)) proper(U62(X1, X2, X3)) -> U62(proper(X1), proper(X2), proper(X3)) proper(U63(X1, X2, X3)) -> U63(proper(X1), proper(X2), proper(X3)) proper(U64(X1, X2, X3)) -> U64(proper(X1), proper(X2), proper(X3)) proper(s(X)) -> s(proper(X)) proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) proper(0) -> ok(0) U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) isNatKind(ok(X)) -> ok(isNatKind(X)) U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) isNat(ok(X)) -> ok(isNat(X)) U16(ok(X)) -> ok(U16(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) U23(ok(X)) -> ok(U23(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X)) -> ok(U41(X)) U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U61(ok(X1), ok(X2), ok(X3)) -> ok(U61(X1, X2, X3)) U62(ok(X1), ok(X2), ok(X3)) -> ok(U62(X1, X2, X3)) U63(ok(X1), ok(X2), ok(X3)) -> ok(U63(X1, X2, X3)) U64(ok(X1), ok(X2), ok(X3)) -> ok(U64(X1, X2, X3)) s(ok(X)) -> ok(s(X)) plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Q is empty. Special symbols used for the transformation (see [GM04]): top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U51: {1} U52: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set The QTRS contained all rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is complete (and sound). ---------------------------------------- (2) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U51(tt, N) -> U52(isNatKind(N), N) U52(tt, N) -> N U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) plus(N, 0) -> U51(isNat(N), N) plus(N, s(M)) -> U61(isNat(M), M, N) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U51: {1} U52: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (3) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U51(tt, N) -> U52(isNatKind(N), N) U52(tt, N) -> N U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) plus(N, 0) -> U51(isNat(N), N) plus(N, s(M)) -> U61(isNat(M), M, N) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U51: {1} U52: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U11(x_1, x_2, x_3)) = x_1 POL(U12(x_1, x_2, x_3)) = x_1 POL(U13(x_1, x_2, x_3)) = x_1 POL(U14(x_1, x_2, x_3)) = x_1 POL(U15(x_1, x_2)) = x_1 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = x_1 POL(U22(x_1, x_2)) = x_1 POL(U23(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(U51(x_1, x_2)) = x_1 + x_2 POL(U52(x_1, x_2)) = x_1 + x_2 POL(U61(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U62(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U63(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U64(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(isNat(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: plus(N, 0) -> U51(isNat(N), N) ---------------------------------------- (4) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U51(tt, N) -> U52(isNatKind(N), N) U52(tt, N) -> N U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) plus(N, s(M)) -> U61(isNat(M), M, N) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U51: {1} U52: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (5) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U51(tt, N) -> U52(isNatKind(N), N) U52(tt, N) -> N U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) plus(N, s(M)) -> U61(isNat(M), M, N) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U51: {1} U52: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U11(x_1, x_2, x_3)) = x_1 POL(U12(x_1, x_2, x_3)) = x_1 POL(U13(x_1, x_2, x_3)) = x_1 POL(U14(x_1, x_2, x_3)) = x_1 POL(U15(x_1, x_2)) = x_1 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = x_1 POL(U22(x_1, x_2)) = x_1 POL(U23(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(U51(x_1, x_2)) = 1 + x_1 + x_2 POL(U52(x_1, x_2)) = x_1 + x_2 POL(U61(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U62(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U63(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U64(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(isNat(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U51(tt, N) -> U52(isNatKind(N), N) ---------------------------------------- (6) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U52(tt, N) -> N U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) plus(N, s(M)) -> U61(isNat(M), M, N) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U52: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (7) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U52(tt, N) -> N U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) plus(N, s(M)) -> U61(isNat(M), M, N) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U52: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2, x_3)) = x_1 POL(U12(x_1, x_2, x_3)) = 2*x_1 POL(U13(x_1, x_2, x_3)) = 2*x_1 POL(U14(x_1, x_2, x_3)) = 2*x_1 POL(U15(x_1, x_2)) = x_1 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = x_1 POL(U22(x_1, x_2)) = x_1 POL(U23(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(U52(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(U62(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(U63(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(U64(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(isNat(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = x_1 + 2*x_2 POL(s(x_1)) = x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U52(tt, N) -> N ---------------------------------------- (8) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) plus(N, s(M)) -> U61(isNat(M), M, N) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (9) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) plus(N, s(M)) -> U61(isNat(M), M, N) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2, x_3)) = 2*x_1 POL(U12(x_1, x_2, x_3)) = x_1 POL(U13(x_1, x_2, x_3)) = x_1 POL(U14(x_1, x_2, x_3)) = 2*x_1 POL(U15(x_1, x_2)) = 2*x_1 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = 2*x_1 POL(U22(x_1, x_2)) = 2*x_1 POL(U23(x_1)) = x_1 POL(U31(x_1, x_2)) = 2*x_1 POL(U32(x_1)) = 2*x_1 POL(U41(x_1)) = 2*x_1 POL(U61(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 POL(U62(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 POL(U63(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + x_3 POL(U64(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + x_3 POL(isNat(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = x_1 + 2*x_2 POL(s(x_1)) = 2 + x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: plus(N, s(M)) -> U61(isNat(M), M, N) ---------------------------------------- (10) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (11) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U63(tt, M, N) -> U64(isNatKind(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2, x_3)) = 2*x_1 POL(U12(x_1, x_2, x_3)) = 2*x_1 POL(U13(x_1, x_2, x_3)) = 2*x_1 POL(U14(x_1, x_2, x_3)) = x_1 POL(U15(x_1, x_2)) = 2*x_1 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = 2*x_1 POL(U22(x_1, x_2)) = 2*x_1 POL(U23(x_1)) = 2*x_1 POL(U31(x_1, x_2)) = 2*x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = 2*x_1 POL(U61(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2, x_3)) = 1 + 2*x_1 + x_2 + 2*x_3 POL(U63(x_1, x_2, x_3)) = 1 + 2*x_1 + x_2 + 2*x_3 POL(U64(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 POL(isNat(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U63(tt, M, N) -> U64(isNatKind(N), M, N) ---------------------------------------- (12) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (13) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} U61: {1} U62: {1} U63: {1} U64: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U11(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 POL(U12(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U13(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U14(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U15(x_1, x_2)) = x_1 + 2*x_2 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = x_1 + x_2 POL(U22(x_1, x_2)) = x_1 + x_2 POL(U23(x_1)) = x_1 POL(U31(x_1, x_2)) = 2*x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = 2*x_1 POL(U61(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3 POL(U62(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U63(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 POL(U64(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(isNat(x_1)) = x_1 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = 2*x_1 + 2*x_2 POL(s(x_1)) = x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U61(tt, M, N) -> U62(isNatKind(M), M, N) U62(tt, M, N) -> U63(isNat(N), M, N) U64(tt, M, N) -> s(plus(N, M)) isNat(0) -> tt ---------------------------------------- (14) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (15) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U21(tt, V1) -> U22(isNatKind(V1), V1) U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U11(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U14(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U15(x_1, x_2)) = x_1 + x_2 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = 1 + x_1 + x_2 POL(U22(x_1, x_2)) = x_1 + x_2 POL(U23(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(isNat(x_1)) = x_1 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = 1 + x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U21(tt, V1) -> U22(isNatKind(V1), V1) ---------------------------------------- (16) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (17) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U22(tt, V1) -> U23(isNat(V1)) U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U22: {1} U23: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U11(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U14(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U15(x_1, x_2)) = x_1 + x_2 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = x_1 + x_2 POL(U22(x_1, x_2)) = 1 + x_1 + x_2 POL(U23(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(isNat(x_1)) = x_1 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 POL(s(x_1)) = x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U22(tt, V1) -> U23(isNat(V1)) isNat(plus(V1, V2)) -> U11(isNatKind(V1), V1, V2) ---------------------------------------- (18) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U23: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (19) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U23(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: U11: {1} tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U23: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 2 POL(U11(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U12(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 POL(U13(x_1, x_2, x_3)) = x_1 + 2*x_2 POL(U14(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 POL(U15(x_1, x_2)) = x_1 POL(U16(x_1)) = 2*x_1 POL(U21(x_1, x_2)) = 2*x_1 POL(U23(x_1)) = 1 + x_1 POL(U31(x_1, x_2)) = 2*x_1 POL(U32(x_1)) = 2*x_1 POL(U41(x_1)) = 2*x_1 POL(isNat(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(s(x_1)) = x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U11(tt, V1, V2) -> U12(isNatKind(V1), V1, V2) U23(tt) -> tt ---------------------------------------- (20) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (21) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U21: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U14(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U15(x_1, x_2)) = x_1 + x_2 POL(U16(x_1)) = x_1 POL(U21(x_1, x_2)) = x_1 + x_2 POL(U31(x_1, x_2)) = x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(isNat(x_1)) = x_1 POL(isNatKind(x_1)) = 0 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 POL(s(x_1)) = 1 + x_1 POL(tt) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: isNat(s(V1)) -> U21(isNatKind(V1), V1) ---------------------------------------- (22) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (23) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) U16(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U15: {1} isNat: empty set U16: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U12(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U14(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U15(x_1, x_2)) = x_1 + x_2 POL(U16(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(isNat(x_1)) = x_1 POL(isNatKind(x_1)) = 1 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 POL(s(x_1)) = 1 + x_1 POL(tt) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U14(tt, V1, V2) -> U15(isNat(V1), V2) U15(tt, V2) -> U16(isNat(V2)) ---------------------------------------- (24) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U16(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U16: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (25) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U16(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: tt: empty set U12: {1} isNatKind: empty set U13: {1} U14: {1} U16: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(U12(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U14(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U16(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 POL(U32(x_1)) = x_1 POL(U41(x_1)) = x_1 POL(isNatKind(x_1)) = 1 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 POL(s(x_1)) = 1 + x_1 POL(tt) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U12(tt, V1, V2) -> U13(isNatKind(V2), V1, V2) ---------------------------------------- (26) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U16(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: tt: empty set isNatKind: empty set U13: {1} U14: {1} U16: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set ---------------------------------------- (27) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U16(tt) -> tt U31(tt, V2) -> U32(isNatKind(V2)) U32(tt) -> tt U41(tt) -> tt isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) The replacement map contains the following entries: tt: empty set isNatKind: empty set U13: {1} U14: {1} U16: {1} U31: {1} U32: {1} U41: {1} s: {1} plus: {1, 2} 0: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 2 POL(U13(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 POL(U14(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 POL(U16(x_1)) = 1 + 2*x_1 POL(U31(x_1, x_2)) = x_1 + 2*x_2 POL(U32(x_1)) = 1 + x_1 POL(U41(x_1)) = 2*x_1 POL(isNatKind(x_1)) = 1 + 2*x_1 POL(plus(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(s(x_1)) = 2 + 2*x_1 POL(tt) = 2 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U13(tt, V1, V2) -> U14(isNatKind(V2), V1, V2) U16(tt) -> tt U32(tt) -> tt U41(tt) -> tt isNatKind(0) -> tt isNatKind(plus(V1, V2)) -> U31(isNatKind(V1), V2) isNatKind(s(V1)) -> U41(isNatKind(V1)) ---------------------------------------- (28) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: U31(tt, V2) -> U32(isNatKind(V2)) The replacement map contains the following entries: tt: empty set isNatKind: empty set U31: {1} U32: {1} ---------------------------------------- (29) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: U31(tt, V2) -> U32(isNatKind(V2)) The replacement map contains the following entries: tt: empty set isNatKind: empty set U31: {1} U32: {1} Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(U31(x_1, x_2)) = [[1]] + [[1, 1]] * x_1 + [[1, 1]] * x_2 >>> <<< POL(tt) = [[1], [1]] >>> <<< POL(U32(x_1)) = [[1]] + [[1, 1]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [1]] + [[1, 1], [0, 0]] * x_1 >>> With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U31(tt, V2) -> U32(isNatKind(V2)) ---------------------------------------- (30) Obligation: Context-sensitive rewrite system: R is empty. ---------------------------------------- (31) RisEmptyProof (EQUIVALENT) The CSR R is empty. Hence, termination is trivially proven. ---------------------------------------- (32) YES