5.66/2.19 YES 5.66/2.20 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.66/2.20 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.66/2.20 5.66/2.20 5.66/2.20 Termination w.r.t. Q of the given QTRS could be proven: 5.66/2.20 5.66/2.20 (0) QTRS 5.66/2.20 (1) QTRSToCSRProof [SOUND, 0 ms] 5.66/2.20 (2) CSR 5.66/2.20 (3) CSRRRRProof [EQUIVALENT, 32 ms] 5.66/2.20 (4) CSR 5.66/2.20 (5) CSRRRRProof [EQUIVALENT, 12 ms] 5.66/2.20 (6) CSR 5.66/2.20 (7) CSRRRRProof [EQUIVALENT, 0 ms] 5.66/2.20 (8) CSR 5.66/2.20 (9) CSRRRRProof [EQUIVALENT, 0 ms] 5.66/2.20 (10) CSR 5.66/2.20 (11) CSRRRRProof [EQUIVALENT, 0 ms] 5.66/2.20 (12) CSR 5.66/2.20 (13) CSRRRRProof [EQUIVALENT, 0 ms] 5.66/2.20 (14) CSR 5.66/2.20 (15) CSRRRRProof [EQUIVALENT, 0 ms] 5.66/2.20 (16) CSR 5.66/2.20 (17) CSRRRRProof [EQUIVALENT, 12 ms] 5.66/2.20 (18) CSR 5.66/2.20 (19) CSRRRRProof [EQUIVALENT, 0 ms] 5.66/2.20 (20) CSR 5.66/2.20 (21) CSRRRRProof [EQUIVALENT, 0 ms] 5.66/2.20 (22) CSR 5.66/2.20 (23) CSRRRRProof [EQUIVALENT, 0 ms] 5.66/2.20 (24) CSR 5.66/2.20 (25) RisEmptyProof [EQUIVALENT, 0 ms] 5.66/2.20 (26) YES 5.66/2.20 5.66/2.20 5.66/2.20 ---------------------------------------- 5.66/2.20 5.66/2.20 (0) 5.66/2.20 Obligation: 5.66/2.20 Q restricted rewrite system: 5.66/2.20 The TRS R consists of the following rules: 5.66/2.20 5.66/2.20 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 5.66/2.20 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 5.66/2.20 active(U13(tt)) -> mark(tt) 5.66/2.20 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 5.66/2.20 active(U22(tt)) -> mark(tt) 5.66/2.20 active(U31(tt, N)) -> mark(N) 5.66/2.20 active(U41(tt, M, N)) -> mark(s(plus(N, M))) 5.66/2.20 active(and(tt, X)) -> mark(X) 5.66/2.20 active(isNat(0)) -> mark(tt) 5.66/2.20 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 5.66/2.20 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 5.66/2.20 active(isNatKind(0)) -> mark(tt) 5.66/2.20 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 5.66/2.20 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 5.66/2.20 active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N)) 5.66/2.20 active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 5.66/2.20 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 5.66/2.20 active(U12(X1, X2)) -> U12(active(X1), X2) 5.66/2.20 active(U13(X)) -> U13(active(X)) 5.66/2.20 active(U21(X1, X2)) -> U21(active(X1), X2) 5.66/2.20 active(U22(X)) -> U22(active(X)) 5.66/2.20 active(U31(X1, X2)) -> U31(active(X1), X2) 5.66/2.20 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 5.66/2.20 active(s(X)) -> s(active(X)) 5.66/2.20 active(plus(X1, X2)) -> plus(active(X1), X2) 5.66/2.20 active(plus(X1, X2)) -> plus(X1, active(X2)) 5.66/2.20 active(and(X1, X2)) -> and(active(X1), X2) 5.66/2.20 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 5.66/2.20 U12(mark(X1), X2) -> mark(U12(X1, X2)) 5.66/2.20 U13(mark(X)) -> mark(U13(X)) 5.66/2.20 U21(mark(X1), X2) -> mark(U21(X1, X2)) 5.66/2.20 U22(mark(X)) -> mark(U22(X)) 5.66/2.20 U31(mark(X1), X2) -> mark(U31(X1, X2)) 5.66/2.20 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 5.66/2.20 s(mark(X)) -> mark(s(X)) 5.66/2.20 plus(mark(X1), X2) -> mark(plus(X1, X2)) 5.66/2.20 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 5.66/2.20 and(mark(X1), X2) -> mark(and(X1, X2)) 5.66/2.20 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 5.66/2.20 proper(tt) -> ok(tt) 5.66/2.20 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 5.66/2.20 proper(isNat(X)) -> isNat(proper(X)) 5.66/2.20 proper(U13(X)) -> U13(proper(X)) 5.66/2.20 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 5.66/2.20 proper(U22(X)) -> U22(proper(X)) 5.66/2.20 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 5.66/2.20 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 5.66/2.20 proper(s(X)) -> s(proper(X)) 5.66/2.20 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 5.66/2.20 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 5.66/2.20 proper(0) -> ok(0) 5.66/2.20 proper(isNatKind(X)) -> isNatKind(proper(X)) 5.66/2.20 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 5.66/2.20 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 5.66/2.20 isNat(ok(X)) -> ok(isNat(X)) 5.66/2.20 U13(ok(X)) -> ok(U13(X)) 5.66/2.20 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 5.66/2.20 U22(ok(X)) -> ok(U22(X)) 5.66/2.20 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 5.66/2.20 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 5.66/2.20 s(ok(X)) -> ok(s(X)) 5.66/2.20 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 5.66/2.20 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 5.66/2.20 isNatKind(ok(X)) -> ok(isNatKind(X)) 5.66/2.20 top(mark(X)) -> top(proper(X)) 5.66/2.20 top(ok(X)) -> top(active(X)) 5.66/2.20 5.66/2.20 The set Q consists of the following terms: 5.66/2.20 5.66/2.20 active(isNat(0)) 5.66/2.20 active(isNat(plus(x0, x1))) 5.66/2.20 active(isNat(s(x0))) 5.66/2.20 active(isNatKind(0)) 5.66/2.20 active(isNatKind(plus(x0, x1))) 5.66/2.20 active(isNatKind(s(x0))) 5.66/2.20 active(U11(x0, x1, x2)) 5.66/2.20 active(U12(x0, x1)) 5.66/2.20 active(U13(x0)) 5.66/2.20 active(U21(x0, x1)) 5.66/2.20 active(U22(x0)) 5.66/2.20 active(U31(x0, x1)) 5.66/2.20 active(U41(x0, x1, x2)) 5.66/2.20 active(s(x0)) 5.66/2.20 active(plus(x0, x1)) 5.66/2.20 active(and(x0, x1)) 5.66/2.20 U11(mark(x0), x1, x2) 5.66/2.20 U12(mark(x0), x1) 5.66/2.20 U13(mark(x0)) 5.66/2.20 U21(mark(x0), x1) 5.66/2.20 U22(mark(x0)) 5.66/2.20 U31(mark(x0), x1) 5.66/2.20 U41(mark(x0), x1, x2) 5.66/2.20 s(mark(x0)) 5.66/2.20 plus(mark(x0), x1) 5.66/2.20 plus(x0, mark(x1)) 5.66/2.20 and(mark(x0), x1) 5.66/2.20 proper(U11(x0, x1, x2)) 5.66/2.20 proper(tt) 5.66/2.20 proper(U12(x0, x1)) 5.66/2.20 proper(isNat(x0)) 5.66/2.20 proper(U13(x0)) 5.66/2.20 proper(U21(x0, x1)) 5.66/2.20 proper(U22(x0)) 5.66/2.20 proper(U31(x0, x1)) 5.66/2.20 proper(U41(x0, x1, x2)) 5.66/2.20 proper(s(x0)) 5.66/2.20 proper(plus(x0, x1)) 5.66/2.20 proper(and(x0, x1)) 5.66/2.20 proper(0) 5.66/2.20 proper(isNatKind(x0)) 5.66/2.20 U11(ok(x0), ok(x1), ok(x2)) 5.66/2.20 U12(ok(x0), ok(x1)) 5.66/2.20 isNat(ok(x0)) 5.66/2.20 U13(ok(x0)) 5.66/2.20 U21(ok(x0), ok(x1)) 5.66/2.20 U22(ok(x0)) 5.66/2.20 U31(ok(x0), ok(x1)) 5.66/2.20 U41(ok(x0), ok(x1), ok(x2)) 5.66/2.20 s(ok(x0)) 5.66/2.20 plus(ok(x0), ok(x1)) 5.66/2.20 and(ok(x0), ok(x1)) 5.66/2.20 isNatKind(ok(x0)) 5.66/2.20 top(mark(x0)) 5.66/2.20 top(ok(x0)) 5.66/2.20 5.66/2.20 5.66/2.20 ---------------------------------------- 5.66/2.20 5.66/2.20 (1) QTRSToCSRProof (SOUND) 5.66/2.20 The following Q TRS is given: Q restricted rewrite system: 5.66/2.20 The TRS R consists of the following rules: 5.66/2.20 5.66/2.20 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 5.66/2.20 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 5.66/2.20 active(U13(tt)) -> mark(tt) 5.66/2.20 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 5.66/2.20 active(U22(tt)) -> mark(tt) 5.66/2.20 active(U31(tt, N)) -> mark(N) 5.66/2.20 active(U41(tt, M, N)) -> mark(s(plus(N, M))) 5.66/2.20 active(and(tt, X)) -> mark(X) 5.66/2.20 active(isNat(0)) -> mark(tt) 5.66/2.20 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 5.66/2.20 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 5.66/2.20 active(isNatKind(0)) -> mark(tt) 5.66/2.20 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 5.66/2.20 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 5.66/2.20 active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N)) 5.66/2.20 active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 5.66/2.20 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 5.66/2.20 active(U12(X1, X2)) -> U12(active(X1), X2) 5.66/2.20 active(U13(X)) -> U13(active(X)) 5.66/2.20 active(U21(X1, X2)) -> U21(active(X1), X2) 5.66/2.20 active(U22(X)) -> U22(active(X)) 5.66/2.20 active(U31(X1, X2)) -> U31(active(X1), X2) 5.66/2.20 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 5.66/2.20 active(s(X)) -> s(active(X)) 5.66/2.20 active(plus(X1, X2)) -> plus(active(X1), X2) 5.66/2.20 active(plus(X1, X2)) -> plus(X1, active(X2)) 5.66/2.20 active(and(X1, X2)) -> and(active(X1), X2) 5.66/2.20 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 5.66/2.20 U12(mark(X1), X2) -> mark(U12(X1, X2)) 5.66/2.20 U13(mark(X)) -> mark(U13(X)) 5.66/2.20 U21(mark(X1), X2) -> mark(U21(X1, X2)) 5.66/2.20 U22(mark(X)) -> mark(U22(X)) 5.66/2.20 U31(mark(X1), X2) -> mark(U31(X1, X2)) 5.66/2.20 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 5.66/2.20 s(mark(X)) -> mark(s(X)) 5.66/2.20 plus(mark(X1), X2) -> mark(plus(X1, X2)) 5.66/2.20 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 5.66/2.20 and(mark(X1), X2) -> mark(and(X1, X2)) 5.66/2.20 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 5.66/2.20 proper(tt) -> ok(tt) 5.66/2.20 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 5.66/2.20 proper(isNat(X)) -> isNat(proper(X)) 5.66/2.20 proper(U13(X)) -> U13(proper(X)) 5.66/2.20 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 5.66/2.20 proper(U22(X)) -> U22(proper(X)) 5.66/2.20 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 5.66/2.20 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 5.66/2.20 proper(s(X)) -> s(proper(X)) 5.66/2.20 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 5.66/2.20 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 5.66/2.20 proper(0) -> ok(0) 5.66/2.20 proper(isNatKind(X)) -> isNatKind(proper(X)) 5.66/2.20 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 5.66/2.20 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 5.66/2.20 isNat(ok(X)) -> ok(isNat(X)) 5.66/2.20 U13(ok(X)) -> ok(U13(X)) 5.66/2.20 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 5.66/2.20 U22(ok(X)) -> ok(U22(X)) 5.66/2.20 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 5.66/2.20 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 5.66/2.20 s(ok(X)) -> ok(s(X)) 5.66/2.20 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 5.66/2.20 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 5.66/2.20 isNatKind(ok(X)) -> ok(isNatKind(X)) 5.66/2.20 top(mark(X)) -> top(proper(X)) 5.66/2.20 top(ok(X)) -> top(active(X)) 5.66/2.20 5.66/2.20 The set Q consists of the following terms: 5.66/2.20 5.66/2.20 active(isNat(0)) 5.66/2.20 active(isNat(plus(x0, x1))) 5.66/2.20 active(isNat(s(x0))) 5.66/2.20 active(isNatKind(0)) 5.66/2.20 active(isNatKind(plus(x0, x1))) 5.66/2.20 active(isNatKind(s(x0))) 5.66/2.20 active(U11(x0, x1, x2)) 5.66/2.20 active(U12(x0, x1)) 5.66/2.20 active(U13(x0)) 5.66/2.20 active(U21(x0, x1)) 5.66/2.20 active(U22(x0)) 5.66/2.20 active(U31(x0, x1)) 5.66/2.20 active(U41(x0, x1, x2)) 5.66/2.20 active(s(x0)) 5.66/2.20 active(plus(x0, x1)) 5.66/2.20 active(and(x0, x1)) 5.66/2.20 U11(mark(x0), x1, x2) 5.66/2.20 U12(mark(x0), x1) 5.66/2.20 U13(mark(x0)) 5.66/2.20 U21(mark(x0), x1) 5.66/2.20 U22(mark(x0)) 5.66/2.20 U31(mark(x0), x1) 5.66/2.20 U41(mark(x0), x1, x2) 5.66/2.20 s(mark(x0)) 5.66/2.20 plus(mark(x0), x1) 5.66/2.20 plus(x0, mark(x1)) 5.66/2.20 and(mark(x0), x1) 5.66/2.20 proper(U11(x0, x1, x2)) 5.66/2.20 proper(tt) 5.66/2.20 proper(U12(x0, x1)) 5.66/2.20 proper(isNat(x0)) 5.66/2.20 proper(U13(x0)) 5.66/2.20 proper(U21(x0, x1)) 5.66/2.20 proper(U22(x0)) 5.66/2.20 proper(U31(x0, x1)) 5.66/2.20 proper(U41(x0, x1, x2)) 5.66/2.20 proper(s(x0)) 5.66/2.20 proper(plus(x0, x1)) 5.66/2.20 proper(and(x0, x1)) 5.66/2.20 proper(0) 5.66/2.21 proper(isNatKind(x0)) 5.66/2.21 U11(ok(x0), ok(x1), ok(x2)) 5.66/2.21 U12(ok(x0), ok(x1)) 5.66/2.21 isNat(ok(x0)) 5.66/2.21 U13(ok(x0)) 5.66/2.21 U21(ok(x0), ok(x1)) 5.66/2.21 U22(ok(x0)) 5.66/2.21 U31(ok(x0), ok(x1)) 5.66/2.21 U41(ok(x0), ok(x1), ok(x2)) 5.66/2.21 s(ok(x0)) 5.66/2.21 plus(ok(x0), ok(x1)) 5.66/2.21 and(ok(x0), ok(x1)) 5.66/2.21 isNatKind(ok(x0)) 5.66/2.21 top(mark(x0)) 5.66/2.21 top(ok(x0)) 5.66/2.21 5.66/2.21 Special symbols used for the transformation (see [GM04]): 5.66/2.21 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U31: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 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. 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (2) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U13(tt) -> tt 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U31(tt, N) -> N 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(0) -> tt 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 plus(N, 0) -> U31(and(isNat(N), isNatKind(N)), N) 5.66/2.21 plus(N, s(M)) -> U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U31: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (3) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U13(tt) -> tt 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U31(tt, N) -> N 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(0) -> tt 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 plus(N, 0) -> U31(and(isNat(N), isNatKind(N)), N) 5.66/2.21 plus(N, s(M)) -> U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U31: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(0) = 0 5.66/2.21 POL(U11(x_1, x_2, x_3)) = x_1 5.66/2.21 POL(U12(x_1, x_2)) = x_1 5.66/2.21 POL(U13(x_1)) = x_1 5.66/2.21 POL(U21(x_1, x_2)) = x_1 5.66/2.21 POL(U22(x_1)) = x_1 5.66/2.21 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 5.66/2.21 POL(and(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(isNat(x_1)) = 0 5.66/2.21 POL(isNatKind(x_1)) = 0 5.66/2.21 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(s(x_1)) = x_1 5.66/2.21 POL(tt) = 0 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 U31(tt, N) -> N 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (4) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U13(tt) -> tt 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(0) -> tt 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 plus(N, 0) -> U31(and(isNat(N), isNatKind(N)), N) 5.66/2.21 plus(N, s(M)) -> U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U31: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (5) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U13(tt) -> tt 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(0) -> tt 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 plus(N, 0) -> U31(and(isNat(N), isNatKind(N)), N) 5.66/2.21 plus(N, s(M)) -> U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U31: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(0) = 1 5.66/2.21 POL(U11(x_1, x_2, x_3)) = x_1 5.66/2.21 POL(U12(x_1, x_2)) = x_1 5.66/2.21 POL(U13(x_1)) = x_1 5.66/2.21 POL(U21(x_1, x_2)) = x_1 5.66/2.21 POL(U22(x_1)) = x_1 5.66/2.21 POL(U31(x_1, x_2)) = x_1 5.66/2.21 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 5.66/2.21 POL(and(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(isNat(x_1)) = 0 5.66/2.21 POL(isNatKind(x_1)) = 0 5.66/2.21 POL(plus(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(s(x_1)) = 1 + x_1 5.66/2.21 POL(tt) = 0 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 plus(N, 0) -> U31(and(isNat(N), isNatKind(N)), N) 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (6) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U13(tt) -> tt 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(0) -> tt 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 plus(N, s(M)) -> U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (7) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U13(tt) -> tt 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(0) -> tt 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 plus(N, s(M)) -> U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(0) = 0 5.66/2.21 POL(U11(x_1, x_2, x_3)) = 2*x_1 5.66/2.21 POL(U12(x_1, x_2)) = x_1 5.66/2.21 POL(U13(x_1)) = x_1 5.66/2.21 POL(U21(x_1, x_2)) = x_1 5.66/2.21 POL(U22(x_1)) = x_1 5.66/2.21 POL(U41(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + x_3 5.66/2.21 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 5.66/2.21 POL(isNat(x_1)) = 0 5.66/2.21 POL(isNatKind(x_1)) = 0 5.66/2.21 POL(plus(x_1, x_2)) = x_1 + 2*x_2 5.66/2.21 POL(s(x_1)) = 1 + x_1 5.66/2.21 POL(tt) = 0 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 plus(N, s(M)) -> U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N) 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (8) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U13(tt) -> tt 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(0) -> tt 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (9) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U13(tt) -> tt 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(0) -> tt 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(0) = 1 5.66/2.21 POL(U11(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 5.66/2.21 POL(U12(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(U13(x_1)) = 1 + x_1 5.66/2.21 POL(U21(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(U22(x_1)) = x_1 5.66/2.21 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 5.66/2.21 POL(and(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(isNat(x_1)) = x_1 5.66/2.21 POL(isNatKind(x_1)) = 0 5.66/2.21 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(s(x_1)) = x_1 5.66/2.21 POL(tt) = 0 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 U13(tt) -> tt 5.66/2.21 isNat(0) -> tt 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (10) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (11) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 U41: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(0) = 2 5.66/2.21 POL(U11(x_1, x_2, x_3)) = 2*x_1 5.66/2.21 POL(U12(x_1, x_2)) = 2*x_1 5.66/2.21 POL(U13(x_1)) = 2*x_1 5.66/2.21 POL(U21(x_1, x_2)) = 2*x_1 5.66/2.21 POL(U22(x_1)) = 2*x_1 5.66/2.21 POL(U41(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 5.66/2.21 POL(and(x_1, x_2)) = x_1 + 2*x_2 5.66/2.21 POL(isNat(x_1)) = 0 5.66/2.21 POL(isNatKind(x_1)) = 0 5.66/2.21 POL(plus(x_1, x_2)) = 2*x_1 + x_2 5.66/2.21 POL(s(x_1)) = x_1 5.66/2.21 POL(tt) = 0 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 U41(tt, M, N) -> s(plus(N, M)) 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (12) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (13) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 U22(tt) -> tt 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(0) = 1 5.66/2.21 POL(U11(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 5.66/2.21 POL(U12(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(U13(x_1)) = 1 + x_1 5.66/2.21 POL(U21(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(U22(x_1)) = 1 + x_1 5.66/2.21 POL(and(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(isNat(x_1)) = x_1 5.66/2.21 POL(isNatKind(x_1)) = 0 5.66/2.21 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(s(x_1)) = 1 + x_1 5.66/2.21 POL(tt) = 0 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 U22(tt) -> tt 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (14) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (15) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U13: {1} 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(0) = 1 5.66/2.21 POL(U11(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 5.66/2.21 POL(U12(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(U13(x_1)) = x_1 5.66/2.21 POL(U21(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(U22(x_1)) = 1 + x_1 5.66/2.21 POL(and(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(isNat(x_1)) = x_1 5.66/2.21 POL(isNatKind(x_1)) = 0 5.66/2.21 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(s(x_1)) = 1 + x_1 5.66/2.21 POL(tt) = 0 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 U12(tt, V2) -> U13(isNat(V2)) 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (16) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (17) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 0: empty set 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(U11(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 1], [0, 0]] * x_3 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(tt) = [[0], [0]] 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(U12(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(isNat(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(U21(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(U22(x_1)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(and(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 1], [0, 1]] * x_2 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(plus(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(isNatKind(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(s(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 5.66/2.21 >>> 5.66/2.21 5.66/2.21 <<< 5.66/2.21 POL(0) = [[1], [1]] 5.66/2.21 >>> 5.66/2.21 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 isNatKind(0) -> tt 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (18) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (19) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(U11(x_1, x_2, x_3)) = x_1 + x_2 + x_3 5.66/2.21 POL(U12(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(U21(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(U22(x_1)) = 1 + x_1 5.66/2.21 POL(and(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(isNat(x_1)) = 1 + x_1 5.66/2.21 POL(isNatKind(x_1)) = 0 5.66/2.21 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(s(x_1)) = 1 + x_1 5.66/2.21 POL(tt) = 1 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 and(tt, X) -> X 5.66/2.21 isNat(plus(V1, V2)) -> U11(and(isNatKind(V1), isNatKind(V2)), V1, V2) 5.66/2.21 isNat(s(V1)) -> U21(isNatKind(V1), V1) 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (20) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (21) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 U11: {1} 5.66/2.21 tt: empty set 5.66/2.21 U12: {1} 5.66/2.21 isNat: empty set 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 s: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(U11(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 5.66/2.21 POL(U12(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(U21(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(U22(x_1)) = 1 + x_1 5.66/2.21 POL(and(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(isNat(x_1)) = 1 + x_1 5.66/2.21 POL(isNatKind(x_1)) = 1 + x_1 5.66/2.21 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 5.66/2.21 POL(s(x_1)) = 1 + x_1 5.66/2.21 POL(tt) = 1 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 U11(tt, V1, V2) -> U12(isNat(V1), V2) 5.66/2.21 isNatKind(s(V1)) -> isNatKind(V1) 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (22) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 tt: empty set 5.66/2.21 isNat: empty set 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 isNatKind: empty set 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (23) CSRRRRProof (EQUIVALENT) 5.66/2.21 The following CSR is given: Context-sensitive rewrite system: 5.66/2.21 The TRS R consists of the following rules: 5.66/2.21 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 5.66/2.21 The replacement map contains the following entries: 5.66/2.21 5.66/2.21 tt: empty set 5.66/2.21 isNat: empty set 5.66/2.21 U21: {1} 5.66/2.21 U22: {1} 5.66/2.21 plus: {1, 2} 5.66/2.21 and: {1} 5.66/2.21 isNatKind: empty set 5.66/2.21 Used ordering: 5.66/2.21 Polynomial interpretation [POLO]: 5.66/2.21 5.66/2.21 POL(U21(x_1, x_2)) = 2 + x_1 + 2*x_2 5.66/2.21 POL(U22(x_1)) = 1 + 2*x_1 5.66/2.21 POL(and(x_1, x_2)) = x_1 + x_2 5.66/2.21 POL(isNat(x_1)) = x_1 5.66/2.21 POL(isNatKind(x_1)) = 1 + 2*x_1 5.66/2.21 POL(plus(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.66/2.21 POL(tt) = 0 5.66/2.21 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.66/2.21 5.66/2.21 U21(tt, V1) -> U22(isNat(V1)) 5.66/2.21 isNatKind(plus(V1, V2)) -> and(isNatKind(V1), isNatKind(V2)) 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (24) 5.66/2.21 Obligation: 5.66/2.21 Context-sensitive rewrite system: 5.66/2.21 R is empty. 5.66/2.21 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (25) RisEmptyProof (EQUIVALENT) 5.66/2.21 The CSR R is empty. Hence, termination is trivially proven. 5.66/2.21 ---------------------------------------- 5.66/2.21 5.66/2.21 (26) 5.66/2.21 YES 5.66/2.24 EOF