9.04/3.25 YES 9.45/3.26 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 9.45/3.26 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.45/3.26 9.45/3.26 9.45/3.26 Termination w.r.t. Q of the given QTRS could be proven: 9.45/3.26 9.45/3.26 (0) QTRS 9.45/3.26 (1) QTRSToCSRProof [SOUND, 0 ms] 9.45/3.26 (2) CSR 9.45/3.26 (3) CSRRRRProof [EQUIVALENT, 82 ms] 9.45/3.26 (4) CSR 9.45/3.26 (5) CSRRRRProof [EQUIVALENT, 39 ms] 9.45/3.26 (6) CSR 9.45/3.26 (7) CSRRRRProof [EQUIVALENT, 32 ms] 9.45/3.26 (8) CSR 9.45/3.26 (9) CSRRRRProof [EQUIVALENT, 0 ms] 9.45/3.26 (10) CSR 9.45/3.26 (11) CSRRRRProof [EQUIVALENT, 0 ms] 9.45/3.26 (12) CSR 9.45/3.26 (13) CSRRRRProof [EQUIVALENT, 19 ms] 9.45/3.26 (14) CSR 9.45/3.26 (15) CSRRRRProof [EQUIVALENT, 17 ms] 9.45/3.26 (16) CSR 9.45/3.26 (17) CSRRRRProof [EQUIVALENT, 13 ms] 9.45/3.26 (18) CSR 9.45/3.26 (19) CSRRRRProof [EQUIVALENT, 23 ms] 9.45/3.26 (20) CSR 9.45/3.26 (21) CSDependencyPairsProof [EQUIVALENT, 11 ms] 9.45/3.26 (22) QCSDP 9.45/3.26 (23) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.45/3.26 (24) AND 9.45/3.26 (25) QCSDP 9.45/3.26 (26) QCSUsableRulesProof [EQUIVALENT, 0 ms] 9.45/3.26 (27) QCSDP 9.45/3.26 (28) QCSDPMuMonotonicPoloProof [EQUIVALENT, 0 ms] 9.45/3.26 (29) QCSDP 9.45/3.26 (30) QCSDPSubtermProof [EQUIVALENT, 0 ms] 9.45/3.26 (31) QCSDP 9.45/3.26 (32) PIsEmptyProof [EQUIVALENT, 0 ms] 9.45/3.26 (33) YES 9.45/3.26 (34) QCSDP 9.45/3.26 (35) QCSDPSubtermProof [EQUIVALENT, 12 ms] 9.45/3.26 (36) QCSDP 9.45/3.26 (37) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.45/3.26 (38) TRUE 9.45/3.26 (39) QCSDP 9.45/3.26 (40) QCSUsableRulesProof [EQUIVALENT, 0 ms] 9.45/3.26 (41) QCSDP 9.45/3.26 (42) QCSDPMuMonotonicPoloProof [EQUIVALENT, 9 ms] 9.45/3.26 (43) QCSDP 9.45/3.26 (44) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.45/3.26 (45) TRUE 9.45/3.26 (46) QCSDP 9.45/3.26 (47) QCSDPReductionPairProof [EQUIVALENT, 1 ms] 9.45/3.26 (48) QCSDP 9.45/3.26 (49) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.45/3.26 (50) TRUE 9.45/3.26 (51) QCSDP 9.45/3.26 (52) QCSUsableRulesProof [EQUIVALENT, 0 ms] 9.45/3.26 (53) QCSDP 9.45/3.26 (54) QCSDPMuMonotonicPoloProof [EQUIVALENT, 10 ms] 9.45/3.26 (55) QCSDP 9.45/3.26 (56) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.45/3.26 (57) TRUE 9.45/3.26 9.45/3.26 9.45/3.26 ---------------------------------------- 9.45/3.26 9.45/3.26 (0) 9.45/3.26 Obligation: 9.45/3.26 Q restricted rewrite system: 9.45/3.26 The TRS R consists of the following rules: 9.45/3.26 9.45/3.26 active(zeros) -> mark(cons(0, zeros)) 9.45/3.26 active(U11(tt, V1)) -> mark(U12(isNatIListKind(V1), V1)) 9.45/3.26 active(U12(tt, V1)) -> mark(U13(isNatList(V1))) 9.45/3.26 active(U13(tt)) -> mark(tt) 9.45/3.26 active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) 9.45/3.26 active(U22(tt, V1)) -> mark(U23(isNat(V1))) 9.45/3.26 active(U23(tt)) -> mark(tt) 9.45/3.26 active(U31(tt, V)) -> mark(U32(isNatIListKind(V), V)) 9.45/3.26 active(U32(tt, V)) -> mark(U33(isNatList(V))) 9.45/3.26 active(U33(tt)) -> mark(tt) 9.45/3.26 active(U41(tt, V1, V2)) -> mark(U42(isNatKind(V1), V1, V2)) 9.45/3.26 active(U42(tt, V1, V2)) -> mark(U43(isNatIListKind(V2), V1, V2)) 9.45/3.26 active(U43(tt, V1, V2)) -> mark(U44(isNatIListKind(V2), V1, V2)) 9.45/3.26 active(U44(tt, V1, V2)) -> mark(U45(isNat(V1), V2)) 9.45/3.26 active(U45(tt, V2)) -> mark(U46(isNatIList(V2))) 9.45/3.26 active(U46(tt)) -> mark(tt) 9.45/3.26 active(U51(tt, V2)) -> mark(U52(isNatIListKind(V2))) 9.45/3.26 active(U52(tt)) -> mark(tt) 9.45/3.26 active(U61(tt)) -> mark(tt) 9.45/3.26 active(U71(tt)) -> mark(tt) 9.45/3.26 active(U81(tt, V1, V2)) -> mark(U82(isNatKind(V1), V1, V2)) 9.45/3.26 active(U82(tt, V1, V2)) -> mark(U83(isNatIListKind(V2), V1, V2)) 9.45/3.26 active(U83(tt, V1, V2)) -> mark(U84(isNatIListKind(V2), V1, V2)) 9.45/3.26 active(U84(tt, V1, V2)) -> mark(U85(isNat(V1), V2)) 9.45/3.26 active(U85(tt, V2)) -> mark(U86(isNatList(V2))) 9.45/3.26 active(U86(tt)) -> mark(tt) 9.45/3.26 active(U91(tt, L, N)) -> mark(U92(isNatIListKind(L), L, N)) 9.45/3.26 active(U92(tt, L, N)) -> mark(U93(isNat(N), L, N)) 9.45/3.26 active(U93(tt, L, N)) -> mark(U94(isNatKind(N), L)) 9.45/3.26 active(U94(tt, L)) -> mark(s(length(L))) 9.45/3.26 active(isNat(0)) -> mark(tt) 9.45/3.26 active(isNat(length(V1))) -> mark(U11(isNatIListKind(V1), V1)) 9.45/3.26 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 9.45/3.26 active(isNatIList(V)) -> mark(U31(isNatIListKind(V), V)) 9.45/3.26 active(isNatIList(zeros)) -> mark(tt) 9.45/3.26 active(isNatIList(cons(V1, V2))) -> mark(U41(isNatKind(V1), V1, V2)) 9.45/3.26 active(isNatIListKind(nil)) -> mark(tt) 9.45/3.26 active(isNatIListKind(zeros)) -> mark(tt) 9.45/3.26 active(isNatIListKind(cons(V1, V2))) -> mark(U51(isNatKind(V1), V2)) 9.45/3.26 active(isNatKind(0)) -> mark(tt) 9.45/3.26 active(isNatKind(length(V1))) -> mark(U61(isNatIListKind(V1))) 9.45/3.26 active(isNatKind(s(V1))) -> mark(U71(isNatKind(V1))) 9.45/3.26 active(isNatList(nil)) -> mark(tt) 9.45/3.26 active(isNatList(cons(V1, V2))) -> mark(U81(isNatKind(V1), V1, V2)) 9.45/3.26 active(length(nil)) -> mark(0) 9.45/3.26 active(length(cons(N, L))) -> mark(U91(isNatList(L), L, N)) 9.45/3.26 active(cons(X1, X2)) -> cons(active(X1), X2) 9.45/3.26 active(U11(X1, X2)) -> U11(active(X1), X2) 9.45/3.26 active(U12(X1, X2)) -> U12(active(X1), X2) 9.45/3.26 active(U13(X)) -> U13(active(X)) 9.45/3.26 active(U21(X1, X2)) -> U21(active(X1), X2) 9.45/3.26 active(U22(X1, X2)) -> U22(active(X1), X2) 9.45/3.26 active(U23(X)) -> U23(active(X)) 9.45/3.26 active(U31(X1, X2)) -> U31(active(X1), X2) 9.45/3.26 active(U32(X1, X2)) -> U32(active(X1), X2) 9.45/3.26 active(U33(X)) -> U33(active(X)) 9.45/3.26 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 9.45/3.26 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 9.45/3.26 active(U43(X1, X2, X3)) -> U43(active(X1), X2, X3) 9.45/3.26 active(U44(X1, X2, X3)) -> U44(active(X1), X2, X3) 9.45/3.26 active(U45(X1, X2)) -> U45(active(X1), X2) 9.45/3.26 active(U46(X)) -> U46(active(X)) 9.45/3.26 active(U51(X1, X2)) -> U51(active(X1), X2) 9.45/3.26 active(U52(X)) -> U52(active(X)) 9.45/3.26 active(U61(X)) -> U61(active(X)) 9.45/3.26 active(U71(X)) -> U71(active(X)) 9.45/3.26 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 9.45/3.26 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 9.45/3.26 active(U83(X1, X2, X3)) -> U83(active(X1), X2, X3) 9.45/3.26 active(U84(X1, X2, X3)) -> U84(active(X1), X2, X3) 9.45/3.26 active(U85(X1, X2)) -> U85(active(X1), X2) 9.45/3.26 active(U86(X)) -> U86(active(X)) 9.45/3.26 active(U91(X1, X2, X3)) -> U91(active(X1), X2, X3) 9.45/3.26 active(U92(X1, X2, X3)) -> U92(active(X1), X2, X3) 9.45/3.26 active(U93(X1, X2, X3)) -> U93(active(X1), X2, X3) 9.45/3.26 active(U94(X1, X2)) -> U94(active(X1), X2) 9.45/3.26 active(s(X)) -> s(active(X)) 9.45/3.26 active(length(X)) -> length(active(X)) 9.45/3.26 cons(mark(X1), X2) -> mark(cons(X1, X2)) 9.45/3.26 U11(mark(X1), X2) -> mark(U11(X1, X2)) 9.45/3.26 U12(mark(X1), X2) -> mark(U12(X1, X2)) 9.45/3.26 U13(mark(X)) -> mark(U13(X)) 9.45/3.26 U21(mark(X1), X2) -> mark(U21(X1, X2)) 9.45/3.26 U22(mark(X1), X2) -> mark(U22(X1, X2)) 9.45/3.26 U23(mark(X)) -> mark(U23(X)) 9.45/3.26 U31(mark(X1), X2) -> mark(U31(X1, X2)) 9.45/3.26 U32(mark(X1), X2) -> mark(U32(X1, X2)) 9.45/3.26 U33(mark(X)) -> mark(U33(X)) 9.45/3.26 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 9.45/3.26 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 9.45/3.26 U43(mark(X1), X2, X3) -> mark(U43(X1, X2, X3)) 9.45/3.26 U44(mark(X1), X2, X3) -> mark(U44(X1, X2, X3)) 9.45/3.26 U45(mark(X1), X2) -> mark(U45(X1, X2)) 9.45/3.26 U46(mark(X)) -> mark(U46(X)) 9.45/3.26 U51(mark(X1), X2) -> mark(U51(X1, X2)) 9.45/3.26 U52(mark(X)) -> mark(U52(X)) 9.45/3.26 U61(mark(X)) -> mark(U61(X)) 9.45/3.26 U71(mark(X)) -> mark(U71(X)) 9.45/3.26 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 9.45/3.26 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 9.45/3.26 U83(mark(X1), X2, X3) -> mark(U83(X1, X2, X3)) 9.45/3.26 U84(mark(X1), X2, X3) -> mark(U84(X1, X2, X3)) 9.45/3.26 U85(mark(X1), X2) -> mark(U85(X1, X2)) 9.45/3.26 U86(mark(X)) -> mark(U86(X)) 9.45/3.26 U91(mark(X1), X2, X3) -> mark(U91(X1, X2, X3)) 9.45/3.26 U92(mark(X1), X2, X3) -> mark(U92(X1, X2, X3)) 9.45/3.26 U93(mark(X1), X2, X3) -> mark(U93(X1, X2, X3)) 9.45/3.26 U94(mark(X1), X2) -> mark(U94(X1, X2)) 9.45/3.26 s(mark(X)) -> mark(s(X)) 9.45/3.26 length(mark(X)) -> mark(length(X)) 9.45/3.26 proper(zeros) -> ok(zeros) 9.45/3.26 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 9.45/3.26 proper(0) -> ok(0) 9.45/3.26 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 9.45/3.26 proper(tt) -> ok(tt) 9.45/3.26 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 9.45/3.26 proper(isNatIListKind(X)) -> isNatIListKind(proper(X)) 9.45/3.26 proper(U13(X)) -> U13(proper(X)) 9.45/3.26 proper(isNatList(X)) -> isNatList(proper(X)) 9.45/3.26 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 9.45/3.26 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 9.45/3.26 proper(isNatKind(X)) -> isNatKind(proper(X)) 9.45/3.26 proper(U23(X)) -> U23(proper(X)) 9.45/3.26 proper(isNat(X)) -> isNat(proper(X)) 9.45/3.26 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 9.45/3.26 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 9.45/3.26 proper(U33(X)) -> U33(proper(X)) 9.45/3.26 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U43(X1, X2, X3)) -> U43(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U44(X1, X2, X3)) -> U44(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U45(X1, X2)) -> U45(proper(X1), proper(X2)) 9.45/3.26 proper(U46(X)) -> U46(proper(X)) 9.45/3.26 proper(isNatIList(X)) -> isNatIList(proper(X)) 9.45/3.26 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 9.45/3.26 proper(U52(X)) -> U52(proper(X)) 9.45/3.26 proper(U61(X)) -> U61(proper(X)) 9.45/3.26 proper(U71(X)) -> U71(proper(X)) 9.45/3.26 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U83(X1, X2, X3)) -> U83(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U84(X1, X2, X3)) -> U84(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U85(X1, X2)) -> U85(proper(X1), proper(X2)) 9.45/3.26 proper(U86(X)) -> U86(proper(X)) 9.45/3.26 proper(U91(X1, X2, X3)) -> U91(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U92(X1, X2, X3)) -> U92(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U93(X1, X2, X3)) -> U93(proper(X1), proper(X2), proper(X3)) 9.45/3.26 proper(U94(X1, X2)) -> U94(proper(X1), proper(X2)) 9.45/3.26 proper(s(X)) -> s(proper(X)) 9.45/3.26 proper(length(X)) -> length(proper(X)) 9.45/3.26 proper(nil) -> ok(nil) 9.45/3.26 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 9.45/3.26 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 9.45/3.26 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 9.45/3.26 isNatIListKind(ok(X)) -> ok(isNatIListKind(X)) 9.45/3.26 U13(ok(X)) -> ok(U13(X)) 9.45/3.26 isNatList(ok(X)) -> ok(isNatList(X)) 9.45/3.26 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 9.45/3.26 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 9.45/3.26 isNatKind(ok(X)) -> ok(isNatKind(X)) 9.45/3.26 U23(ok(X)) -> ok(U23(X)) 9.45/3.26 isNat(ok(X)) -> ok(isNat(X)) 9.45/3.26 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 9.45/3.26 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 9.45/3.26 U33(ok(X)) -> ok(U33(X)) 9.45/3.26 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 9.45/3.26 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 9.45/3.26 U43(ok(X1), ok(X2), ok(X3)) -> ok(U43(X1, X2, X3)) 9.45/3.26 U44(ok(X1), ok(X2), ok(X3)) -> ok(U44(X1, X2, X3)) 9.45/3.26 U45(ok(X1), ok(X2)) -> ok(U45(X1, X2)) 9.45/3.26 U46(ok(X)) -> ok(U46(X)) 9.45/3.26 isNatIList(ok(X)) -> ok(isNatIList(X)) 9.45/3.26 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 9.45/3.26 U52(ok(X)) -> ok(U52(X)) 9.45/3.26 U61(ok(X)) -> ok(U61(X)) 9.45/3.26 U71(ok(X)) -> ok(U71(X)) 9.45/3.26 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 9.45/3.26 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 9.45/3.26 U83(ok(X1), ok(X2), ok(X3)) -> ok(U83(X1, X2, X3)) 9.45/3.26 U84(ok(X1), ok(X2), ok(X3)) -> ok(U84(X1, X2, X3)) 9.45/3.26 U85(ok(X1), ok(X2)) -> ok(U85(X1, X2)) 9.45/3.26 U86(ok(X)) -> ok(U86(X)) 9.45/3.26 U91(ok(X1), ok(X2), ok(X3)) -> ok(U91(X1, X2, X3)) 9.45/3.26 U92(ok(X1), ok(X2), ok(X3)) -> ok(U92(X1, X2, X3)) 9.45/3.26 U93(ok(X1), ok(X2), ok(X3)) -> ok(U93(X1, X2, X3)) 9.45/3.26 U94(ok(X1), ok(X2)) -> ok(U94(X1, X2)) 9.45/3.26 s(ok(X)) -> ok(s(X)) 9.45/3.26 length(ok(X)) -> ok(length(X)) 9.45/3.26 top(mark(X)) -> top(proper(X)) 9.45/3.26 top(ok(X)) -> top(active(X)) 9.45/3.26 9.45/3.26 The set Q consists of the following terms: 9.45/3.26 9.45/3.26 active(zeros) 9.45/3.26 active(isNat(0)) 9.45/3.26 active(isNat(length(x0))) 9.45/3.26 active(isNat(s(x0))) 9.45/3.26 active(isNatIList(x0)) 9.45/3.26 active(isNatIListKind(nil)) 9.45/3.26 active(isNatIListKind(zeros)) 9.45/3.26 active(isNatIListKind(cons(x0, x1))) 9.45/3.26 active(isNatKind(0)) 9.45/3.26 active(isNatKind(length(x0))) 9.45/3.26 active(isNatKind(s(x0))) 9.45/3.26 active(isNatList(nil)) 9.45/3.26 active(isNatList(cons(x0, x1))) 9.45/3.26 active(cons(x0, x1)) 9.45/3.26 active(U11(x0, x1)) 9.45/3.26 active(U12(x0, x1)) 9.45/3.26 active(U13(x0)) 9.45/3.26 active(U21(x0, x1)) 9.45/3.26 active(U22(x0, x1)) 9.45/3.26 active(U23(x0)) 9.45/3.26 active(U31(x0, x1)) 9.45/3.26 active(U32(x0, x1)) 9.45/3.26 active(U33(x0)) 9.45/3.26 active(U41(x0, x1, x2)) 9.45/3.26 active(U42(x0, x1, x2)) 9.45/3.26 active(U43(x0, x1, x2)) 9.45/3.26 active(U44(x0, x1, x2)) 9.45/3.26 active(U45(x0, x1)) 9.45/3.26 active(U46(x0)) 9.45/3.26 active(U51(x0, x1)) 9.45/3.26 active(U52(x0)) 9.45/3.26 active(U61(x0)) 9.45/3.26 active(U71(x0)) 9.45/3.26 active(U81(x0, x1, x2)) 9.45/3.26 active(U82(x0, x1, x2)) 9.45/3.26 active(U83(x0, x1, x2)) 9.45/3.26 active(U84(x0, x1, x2)) 9.45/3.26 active(U85(x0, x1)) 9.45/3.26 active(U86(x0)) 9.45/3.26 active(U91(x0, x1, x2)) 9.45/3.26 active(U92(x0, x1, x2)) 9.45/3.26 active(U93(x0, x1, x2)) 9.45/3.26 active(U94(x0, x1)) 9.45/3.26 active(s(x0)) 9.45/3.26 active(length(x0)) 9.45/3.26 cons(mark(x0), x1) 9.45/3.26 U11(mark(x0), x1) 9.45/3.26 U12(mark(x0), x1) 9.45/3.26 U13(mark(x0)) 9.45/3.26 U21(mark(x0), x1) 9.45/3.26 U22(mark(x0), x1) 9.45/3.26 U23(mark(x0)) 9.45/3.26 U31(mark(x0), x1) 9.45/3.26 U32(mark(x0), x1) 9.45/3.26 U33(mark(x0)) 9.45/3.26 U41(mark(x0), x1, x2) 9.45/3.26 U42(mark(x0), x1, x2) 9.45/3.26 U43(mark(x0), x1, x2) 9.45/3.26 U44(mark(x0), x1, x2) 9.45/3.26 U45(mark(x0), x1) 9.45/3.26 U46(mark(x0)) 9.45/3.26 U51(mark(x0), x1) 9.45/3.26 U52(mark(x0)) 9.45/3.26 U61(mark(x0)) 9.45/3.26 U71(mark(x0)) 9.45/3.26 U81(mark(x0), x1, x2) 9.45/3.26 U82(mark(x0), x1, x2) 9.45/3.26 U83(mark(x0), x1, x2) 9.45/3.26 U84(mark(x0), x1, x2) 9.45/3.26 U85(mark(x0), x1) 9.45/3.26 U86(mark(x0)) 9.45/3.26 U91(mark(x0), x1, x2) 9.45/3.26 U92(mark(x0), x1, x2) 9.45/3.26 U93(mark(x0), x1, x2) 9.45/3.26 U94(mark(x0), x1) 9.45/3.26 s(mark(x0)) 9.45/3.26 length(mark(x0)) 9.45/3.26 proper(zeros) 9.45/3.26 proper(cons(x0, x1)) 9.45/3.26 proper(0) 9.45/3.26 proper(U11(x0, x1)) 9.45/3.26 proper(tt) 9.45/3.26 proper(U12(x0, x1)) 9.45/3.26 proper(isNatIListKind(x0)) 9.45/3.26 proper(U13(x0)) 9.45/3.26 proper(isNatList(x0)) 9.45/3.26 proper(U21(x0, x1)) 9.45/3.26 proper(U22(x0, x1)) 9.45/3.26 proper(isNatKind(x0)) 9.45/3.26 proper(U23(x0)) 9.45/3.26 proper(isNat(x0)) 9.45/3.26 proper(U31(x0, x1)) 9.45/3.26 proper(U32(x0, x1)) 9.45/3.26 proper(U33(x0)) 9.45/3.26 proper(U41(x0, x1, x2)) 9.45/3.26 proper(U42(x0, x1, x2)) 9.45/3.26 proper(U43(x0, x1, x2)) 9.45/3.26 proper(U44(x0, x1, x2)) 9.45/3.26 proper(U45(x0, x1)) 9.45/3.26 proper(U46(x0)) 9.45/3.26 proper(isNatIList(x0)) 9.45/3.26 proper(U51(x0, x1)) 9.45/3.26 proper(U52(x0)) 9.45/3.26 proper(U61(x0)) 9.45/3.26 proper(U71(x0)) 9.45/3.26 proper(U81(x0, x1, x2)) 9.45/3.26 proper(U82(x0, x1, x2)) 9.45/3.26 proper(U83(x0, x1, x2)) 9.45/3.26 proper(U84(x0, x1, x2)) 9.45/3.26 proper(U85(x0, x1)) 9.45/3.26 proper(U86(x0)) 9.45/3.26 proper(U91(x0, x1, x2)) 9.45/3.26 proper(U92(x0, x1, x2)) 9.45/3.26 proper(U93(x0, x1, x2)) 9.45/3.26 proper(U94(x0, x1)) 9.45/3.26 proper(s(x0)) 9.45/3.26 proper(length(x0)) 9.45/3.26 proper(nil) 9.45/3.26 cons(ok(x0), ok(x1)) 9.45/3.26 U11(ok(x0), ok(x1)) 9.45/3.26 U12(ok(x0), ok(x1)) 9.45/3.26 isNatIListKind(ok(x0)) 9.45/3.26 U13(ok(x0)) 9.45/3.26 isNatList(ok(x0)) 9.45/3.26 U21(ok(x0), ok(x1)) 9.45/3.26 U22(ok(x0), ok(x1)) 9.45/3.26 isNatKind(ok(x0)) 9.45/3.26 U23(ok(x0)) 9.45/3.26 isNat(ok(x0)) 9.45/3.26 U31(ok(x0), ok(x1)) 9.45/3.26 U32(ok(x0), ok(x1)) 9.45/3.26 U33(ok(x0)) 9.45/3.26 U41(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U42(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U43(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U44(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U45(ok(x0), ok(x1)) 9.45/3.26 U46(ok(x0)) 9.45/3.26 isNatIList(ok(x0)) 9.45/3.26 U51(ok(x0), ok(x1)) 9.45/3.26 U52(ok(x0)) 9.45/3.26 U61(ok(x0)) 9.45/3.26 U71(ok(x0)) 9.45/3.26 U81(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U82(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U83(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U84(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U85(ok(x0), ok(x1)) 9.45/3.26 U86(ok(x0)) 9.45/3.26 U91(ok(x0), ok(x1), ok(x2)) 9.45/3.26 U92(ok(x0), ok(x1), ok(x2)) 9.45/3.27 U93(ok(x0), ok(x1), ok(x2)) 9.45/3.27 U94(ok(x0), ok(x1)) 9.45/3.27 s(ok(x0)) 9.45/3.27 length(ok(x0)) 9.45/3.27 top(mark(x0)) 9.45/3.27 top(ok(x0)) 9.45/3.27 9.45/3.27 9.45/3.27 ---------------------------------------- 9.45/3.27 9.45/3.27 (1) QTRSToCSRProof (SOUND) 9.45/3.27 The following Q TRS is given: Q restricted rewrite system: 9.45/3.27 The TRS R consists of the following rules: 9.45/3.27 9.45/3.27 active(zeros) -> mark(cons(0, zeros)) 9.45/3.27 active(U11(tt, V1)) -> mark(U12(isNatIListKind(V1), V1)) 9.45/3.27 active(U12(tt, V1)) -> mark(U13(isNatList(V1))) 9.45/3.27 active(U13(tt)) -> mark(tt) 9.45/3.27 active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) 9.45/3.27 active(U22(tt, V1)) -> mark(U23(isNat(V1))) 9.45/3.27 active(U23(tt)) -> mark(tt) 9.45/3.27 active(U31(tt, V)) -> mark(U32(isNatIListKind(V), V)) 9.45/3.27 active(U32(tt, V)) -> mark(U33(isNatList(V))) 9.45/3.27 active(U33(tt)) -> mark(tt) 9.45/3.27 active(U41(tt, V1, V2)) -> mark(U42(isNatKind(V1), V1, V2)) 9.45/3.27 active(U42(tt, V1, V2)) -> mark(U43(isNatIListKind(V2), V1, V2)) 9.45/3.27 active(U43(tt, V1, V2)) -> mark(U44(isNatIListKind(V2), V1, V2)) 9.45/3.27 active(U44(tt, V1, V2)) -> mark(U45(isNat(V1), V2)) 9.45/3.27 active(U45(tt, V2)) -> mark(U46(isNatIList(V2))) 9.45/3.27 active(U46(tt)) -> mark(tt) 9.45/3.27 active(U51(tt, V2)) -> mark(U52(isNatIListKind(V2))) 9.45/3.27 active(U52(tt)) -> mark(tt) 9.45/3.27 active(U61(tt)) -> mark(tt) 9.45/3.27 active(U71(tt)) -> mark(tt) 9.45/3.27 active(U81(tt, V1, V2)) -> mark(U82(isNatKind(V1), V1, V2)) 9.45/3.27 active(U82(tt, V1, V2)) -> mark(U83(isNatIListKind(V2), V1, V2)) 9.45/3.27 active(U83(tt, V1, V2)) -> mark(U84(isNatIListKind(V2), V1, V2)) 9.45/3.27 active(U84(tt, V1, V2)) -> mark(U85(isNat(V1), V2)) 9.45/3.27 active(U85(tt, V2)) -> mark(U86(isNatList(V2))) 9.45/3.27 active(U86(tt)) -> mark(tt) 9.45/3.27 active(U91(tt, L, N)) -> mark(U92(isNatIListKind(L), L, N)) 9.45/3.27 active(U92(tt, L, N)) -> mark(U93(isNat(N), L, N)) 9.45/3.27 active(U93(tt, L, N)) -> mark(U94(isNatKind(N), L)) 9.45/3.27 active(U94(tt, L)) -> mark(s(length(L))) 9.45/3.27 active(isNat(0)) -> mark(tt) 9.45/3.27 active(isNat(length(V1))) -> mark(U11(isNatIListKind(V1), V1)) 9.45/3.27 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 9.45/3.27 active(isNatIList(V)) -> mark(U31(isNatIListKind(V), V)) 9.45/3.27 active(isNatIList(zeros)) -> mark(tt) 9.45/3.28 active(isNatIList(cons(V1, V2))) -> mark(U41(isNatKind(V1), V1, V2)) 9.45/3.28 active(isNatIListKind(nil)) -> mark(tt) 9.45/3.28 active(isNatIListKind(zeros)) -> mark(tt) 9.45/3.28 active(isNatIListKind(cons(V1, V2))) -> mark(U51(isNatKind(V1), V2)) 9.45/3.28 active(isNatKind(0)) -> mark(tt) 9.45/3.28 active(isNatKind(length(V1))) -> mark(U61(isNatIListKind(V1))) 9.45/3.28 active(isNatKind(s(V1))) -> mark(U71(isNatKind(V1))) 9.45/3.28 active(isNatList(nil)) -> mark(tt) 9.45/3.28 active(isNatList(cons(V1, V2))) -> mark(U81(isNatKind(V1), V1, V2)) 9.45/3.28 active(length(nil)) -> mark(0) 9.45/3.28 active(length(cons(N, L))) -> mark(U91(isNatList(L), L, N)) 9.45/3.28 active(cons(X1, X2)) -> cons(active(X1), X2) 9.45/3.28 active(U11(X1, X2)) -> U11(active(X1), X2) 9.45/3.28 active(U12(X1, X2)) -> U12(active(X1), X2) 9.45/3.28 active(U13(X)) -> U13(active(X)) 9.45/3.28 active(U21(X1, X2)) -> U21(active(X1), X2) 9.45/3.28 active(U22(X1, X2)) -> U22(active(X1), X2) 9.45/3.28 active(U23(X)) -> U23(active(X)) 9.45/3.28 active(U31(X1, X2)) -> U31(active(X1), X2) 9.45/3.28 active(U32(X1, X2)) -> U32(active(X1), X2) 9.45/3.28 active(U33(X)) -> U33(active(X)) 9.45/3.28 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 9.45/3.28 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 9.45/3.28 active(U43(X1, X2, X3)) -> U43(active(X1), X2, X3) 9.45/3.28 active(U44(X1, X2, X3)) -> U44(active(X1), X2, X3) 9.45/3.28 active(U45(X1, X2)) -> U45(active(X1), X2) 9.45/3.28 active(U46(X)) -> U46(active(X)) 9.45/3.28 active(U51(X1, X2)) -> U51(active(X1), X2) 9.45/3.28 active(U52(X)) -> U52(active(X)) 9.45/3.28 active(U61(X)) -> U61(active(X)) 9.45/3.28 active(U71(X)) -> U71(active(X)) 9.45/3.28 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 9.45/3.28 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 9.45/3.28 active(U83(X1, X2, X3)) -> U83(active(X1), X2, X3) 9.45/3.28 active(U84(X1, X2, X3)) -> U84(active(X1), X2, X3) 9.45/3.28 active(U85(X1, X2)) -> U85(active(X1), X2) 9.45/3.28 active(U86(X)) -> U86(active(X)) 9.45/3.28 active(U91(X1, X2, X3)) -> U91(active(X1), X2, X3) 9.45/3.28 active(U92(X1, X2, X3)) -> U92(active(X1), X2, X3) 9.45/3.28 active(U93(X1, X2, X3)) -> U93(active(X1), X2, X3) 9.45/3.28 active(U94(X1, X2)) -> U94(active(X1), X2) 9.45/3.28 active(s(X)) -> s(active(X)) 9.45/3.28 active(length(X)) -> length(active(X)) 9.45/3.28 cons(mark(X1), X2) -> mark(cons(X1, X2)) 9.45/3.28 U11(mark(X1), X2) -> mark(U11(X1, X2)) 9.45/3.28 U12(mark(X1), X2) -> mark(U12(X1, X2)) 9.45/3.28 U13(mark(X)) -> mark(U13(X)) 9.45/3.28 U21(mark(X1), X2) -> mark(U21(X1, X2)) 9.45/3.28 U22(mark(X1), X2) -> mark(U22(X1, X2)) 9.45/3.28 U23(mark(X)) -> mark(U23(X)) 9.45/3.28 U31(mark(X1), X2) -> mark(U31(X1, X2)) 9.45/3.28 U32(mark(X1), X2) -> mark(U32(X1, X2)) 9.45/3.28 U33(mark(X)) -> mark(U33(X)) 9.45/3.28 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 9.45/3.28 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 9.45/3.28 U43(mark(X1), X2, X3) -> mark(U43(X1, X2, X3)) 9.45/3.28 U44(mark(X1), X2, X3) -> mark(U44(X1, X2, X3)) 9.45/3.28 U45(mark(X1), X2) -> mark(U45(X1, X2)) 9.45/3.28 U46(mark(X)) -> mark(U46(X)) 9.45/3.28 U51(mark(X1), X2) -> mark(U51(X1, X2)) 9.45/3.28 U52(mark(X)) -> mark(U52(X)) 9.45/3.28 U61(mark(X)) -> mark(U61(X)) 9.45/3.28 U71(mark(X)) -> mark(U71(X)) 9.45/3.28 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 9.45/3.28 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 9.45/3.28 U83(mark(X1), X2, X3) -> mark(U83(X1, X2, X3)) 9.45/3.28 U84(mark(X1), X2, X3) -> mark(U84(X1, X2, X3)) 9.45/3.28 U85(mark(X1), X2) -> mark(U85(X1, X2)) 9.45/3.28 U86(mark(X)) -> mark(U86(X)) 9.45/3.28 U91(mark(X1), X2, X3) -> mark(U91(X1, X2, X3)) 9.45/3.28 U92(mark(X1), X2, X3) -> mark(U92(X1, X2, X3)) 9.45/3.28 U93(mark(X1), X2, X3) -> mark(U93(X1, X2, X3)) 9.45/3.28 U94(mark(X1), X2) -> mark(U94(X1, X2)) 9.45/3.28 s(mark(X)) -> mark(s(X)) 9.45/3.28 length(mark(X)) -> mark(length(X)) 9.45/3.28 proper(zeros) -> ok(zeros) 9.45/3.28 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 9.45/3.28 proper(0) -> ok(0) 9.45/3.28 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 9.45/3.28 proper(tt) -> ok(tt) 9.45/3.28 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 9.45/3.28 proper(isNatIListKind(X)) -> isNatIListKind(proper(X)) 9.45/3.28 proper(U13(X)) -> U13(proper(X)) 9.45/3.28 proper(isNatList(X)) -> isNatList(proper(X)) 9.45/3.28 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 9.45/3.28 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 9.45/3.28 proper(isNatKind(X)) -> isNatKind(proper(X)) 9.45/3.28 proper(U23(X)) -> U23(proper(X)) 9.45/3.28 proper(isNat(X)) -> isNat(proper(X)) 9.45/3.28 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 9.45/3.28 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 9.45/3.28 proper(U33(X)) -> U33(proper(X)) 9.45/3.28 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U43(X1, X2, X3)) -> U43(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U44(X1, X2, X3)) -> U44(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U45(X1, X2)) -> U45(proper(X1), proper(X2)) 9.45/3.28 proper(U46(X)) -> U46(proper(X)) 9.45/3.28 proper(isNatIList(X)) -> isNatIList(proper(X)) 9.45/3.28 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 9.45/3.28 proper(U52(X)) -> U52(proper(X)) 9.45/3.28 proper(U61(X)) -> U61(proper(X)) 9.45/3.28 proper(U71(X)) -> U71(proper(X)) 9.45/3.28 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U83(X1, X2, X3)) -> U83(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U84(X1, X2, X3)) -> U84(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U85(X1, X2)) -> U85(proper(X1), proper(X2)) 9.45/3.28 proper(U86(X)) -> U86(proper(X)) 9.45/3.28 proper(U91(X1, X2, X3)) -> U91(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U92(X1, X2, X3)) -> U92(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U93(X1, X2, X3)) -> U93(proper(X1), proper(X2), proper(X3)) 9.45/3.28 proper(U94(X1, X2)) -> U94(proper(X1), proper(X2)) 9.45/3.28 proper(s(X)) -> s(proper(X)) 9.45/3.28 proper(length(X)) -> length(proper(X)) 9.45/3.28 proper(nil) -> ok(nil) 9.45/3.28 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 9.45/3.28 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 9.45/3.28 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 9.45/3.28 isNatIListKind(ok(X)) -> ok(isNatIListKind(X)) 9.45/3.28 U13(ok(X)) -> ok(U13(X)) 9.45/3.28 isNatList(ok(X)) -> ok(isNatList(X)) 9.45/3.28 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 9.45/3.28 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 9.45/3.28 isNatKind(ok(X)) -> ok(isNatKind(X)) 9.45/3.28 U23(ok(X)) -> ok(U23(X)) 9.45/3.28 isNat(ok(X)) -> ok(isNat(X)) 9.45/3.28 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 9.45/3.28 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 9.45/3.28 U33(ok(X)) -> ok(U33(X)) 9.45/3.28 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 9.45/3.28 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 9.45/3.28 U43(ok(X1), ok(X2), ok(X3)) -> ok(U43(X1, X2, X3)) 9.45/3.28 U44(ok(X1), ok(X2), ok(X3)) -> ok(U44(X1, X2, X3)) 9.45/3.28 U45(ok(X1), ok(X2)) -> ok(U45(X1, X2)) 9.45/3.28 U46(ok(X)) -> ok(U46(X)) 9.45/3.28 isNatIList(ok(X)) -> ok(isNatIList(X)) 9.45/3.28 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 9.45/3.28 U52(ok(X)) -> ok(U52(X)) 9.45/3.28 U61(ok(X)) -> ok(U61(X)) 9.45/3.28 U71(ok(X)) -> ok(U71(X)) 9.45/3.28 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 9.45/3.28 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 9.45/3.28 U83(ok(X1), ok(X2), ok(X3)) -> ok(U83(X1, X2, X3)) 9.45/3.28 U84(ok(X1), ok(X2), ok(X3)) -> ok(U84(X1, X2, X3)) 9.45/3.28 U85(ok(X1), ok(X2)) -> ok(U85(X1, X2)) 9.45/3.28 U86(ok(X)) -> ok(U86(X)) 9.45/3.28 U91(ok(X1), ok(X2), ok(X3)) -> ok(U91(X1, X2, X3)) 9.45/3.28 U92(ok(X1), ok(X2), ok(X3)) -> ok(U92(X1, X2, X3)) 9.45/3.28 U93(ok(X1), ok(X2), ok(X3)) -> ok(U93(X1, X2, X3)) 9.45/3.28 U94(ok(X1), ok(X2)) -> ok(U94(X1, X2)) 9.45/3.28 s(ok(X)) -> ok(s(X)) 9.45/3.28 length(ok(X)) -> ok(length(X)) 9.45/3.28 top(mark(X)) -> top(proper(X)) 9.45/3.28 top(ok(X)) -> top(active(X)) 9.45/3.28 9.45/3.28 The set Q consists of the following terms: 9.45/3.28 9.45/3.28 active(zeros) 9.45/3.28 active(isNat(0)) 9.45/3.28 active(isNat(length(x0))) 9.45/3.28 active(isNat(s(x0))) 9.45/3.28 active(isNatIList(x0)) 9.45/3.28 active(isNatIListKind(nil)) 9.45/3.28 active(isNatIListKind(zeros)) 9.45/3.28 active(isNatIListKind(cons(x0, x1))) 9.45/3.28 active(isNatKind(0)) 9.45/3.28 active(isNatKind(length(x0))) 9.45/3.28 active(isNatKind(s(x0))) 9.45/3.28 active(isNatList(nil)) 9.45/3.28 active(isNatList(cons(x0, x1))) 9.45/3.28 active(cons(x0, x1)) 9.45/3.28 active(U11(x0, x1)) 9.45/3.28 active(U12(x0, x1)) 9.45/3.28 active(U13(x0)) 9.45/3.28 active(U21(x0, x1)) 9.45/3.28 active(U22(x0, x1)) 9.45/3.28 active(U23(x0)) 9.45/3.28 active(U31(x0, x1)) 9.45/3.28 active(U32(x0, x1)) 9.45/3.28 active(U33(x0)) 9.45/3.28 active(U41(x0, x1, x2)) 9.45/3.28 active(U42(x0, x1, x2)) 9.45/3.28 active(U43(x0, x1, x2)) 9.45/3.28 active(U44(x0, x1, x2)) 9.45/3.28 active(U45(x0, x1)) 9.45/3.28 active(U46(x0)) 9.45/3.28 active(U51(x0, x1)) 9.45/3.28 active(U52(x0)) 9.45/3.28 active(U61(x0)) 9.45/3.28 active(U71(x0)) 9.45/3.28 active(U81(x0, x1, x2)) 9.45/3.28 active(U82(x0, x1, x2)) 9.45/3.28 active(U83(x0, x1, x2)) 9.45/3.28 active(U84(x0, x1, x2)) 9.45/3.28 active(U85(x0, x1)) 9.45/3.28 active(U86(x0)) 9.45/3.28 active(U91(x0, x1, x2)) 9.45/3.28 active(U92(x0, x1, x2)) 9.45/3.28 active(U93(x0, x1, x2)) 9.45/3.28 active(U94(x0, x1)) 9.45/3.28 active(s(x0)) 9.45/3.28 active(length(x0)) 9.45/3.28 cons(mark(x0), x1) 9.45/3.28 U11(mark(x0), x1) 9.45/3.28 U12(mark(x0), x1) 9.45/3.28 U13(mark(x0)) 9.45/3.28 U21(mark(x0), x1) 9.45/3.28 U22(mark(x0), x1) 9.45/3.28 U23(mark(x0)) 9.45/3.28 U31(mark(x0), x1) 9.45/3.28 U32(mark(x0), x1) 9.45/3.28 U33(mark(x0)) 9.45/3.28 U41(mark(x0), x1, x2) 9.45/3.28 U42(mark(x0), x1, x2) 9.45/3.28 U43(mark(x0), x1, x2) 9.45/3.28 U44(mark(x0), x1, x2) 9.45/3.28 U45(mark(x0), x1) 9.45/3.28 U46(mark(x0)) 9.45/3.28 U51(mark(x0), x1) 9.45/3.28 U52(mark(x0)) 9.45/3.28 U61(mark(x0)) 9.45/3.28 U71(mark(x0)) 9.45/3.28 U81(mark(x0), x1, x2) 9.45/3.28 U82(mark(x0), x1, x2) 9.45/3.28 U83(mark(x0), x1, x2) 9.45/3.28 U84(mark(x0), x1, x2) 9.45/3.28 U85(mark(x0), x1) 9.45/3.28 U86(mark(x0)) 9.45/3.28 U91(mark(x0), x1, x2) 9.45/3.28 U92(mark(x0), x1, x2) 9.45/3.28 U93(mark(x0), x1, x2) 9.45/3.28 U94(mark(x0), x1) 9.45/3.28 s(mark(x0)) 9.45/3.28 length(mark(x0)) 9.45/3.28 proper(zeros) 9.45/3.28 proper(cons(x0, x1)) 9.45/3.28 proper(0) 9.45/3.28 proper(U11(x0, x1)) 9.45/3.28 proper(tt) 9.45/3.28 proper(U12(x0, x1)) 9.45/3.28 proper(isNatIListKind(x0)) 9.45/3.28 proper(U13(x0)) 9.45/3.28 proper(isNatList(x0)) 9.45/3.28 proper(U21(x0, x1)) 9.45/3.28 proper(U22(x0, x1)) 9.45/3.28 proper(isNatKind(x0)) 9.45/3.28 proper(U23(x0)) 9.45/3.28 proper(isNat(x0)) 9.45/3.28 proper(U31(x0, x1)) 9.45/3.28 proper(U32(x0, x1)) 9.45/3.28 proper(U33(x0)) 9.45/3.28 proper(U41(x0, x1, x2)) 9.45/3.28 proper(U42(x0, x1, x2)) 9.45/3.28 proper(U43(x0, x1, x2)) 9.45/3.28 proper(U44(x0, x1, x2)) 9.45/3.28 proper(U45(x0, x1)) 9.45/3.28 proper(U46(x0)) 9.45/3.28 proper(isNatIList(x0)) 9.45/3.28 proper(U51(x0, x1)) 9.45/3.28 proper(U52(x0)) 9.45/3.28 proper(U61(x0)) 9.45/3.28 proper(U71(x0)) 9.45/3.28 proper(U81(x0, x1, x2)) 9.45/3.28 proper(U82(x0, x1, x2)) 9.45/3.28 proper(U83(x0, x1, x2)) 9.45/3.28 proper(U84(x0, x1, x2)) 9.45/3.28 proper(U85(x0, x1)) 9.45/3.28 proper(U86(x0)) 9.45/3.28 proper(U91(x0, x1, x2)) 9.45/3.28 proper(U92(x0, x1, x2)) 9.45/3.28 proper(U93(x0, x1, x2)) 9.45/3.28 proper(U94(x0, x1)) 9.45/3.28 proper(s(x0)) 9.45/3.28 proper(length(x0)) 9.45/3.28 proper(nil) 9.45/3.28 cons(ok(x0), ok(x1)) 9.45/3.28 U11(ok(x0), ok(x1)) 9.45/3.28 U12(ok(x0), ok(x1)) 9.45/3.28 isNatIListKind(ok(x0)) 9.45/3.28 U13(ok(x0)) 9.45/3.28 isNatList(ok(x0)) 9.45/3.28 U21(ok(x0), ok(x1)) 9.45/3.28 U22(ok(x0), ok(x1)) 9.45/3.28 isNatKind(ok(x0)) 9.45/3.28 U23(ok(x0)) 9.45/3.28 isNat(ok(x0)) 9.45/3.28 U31(ok(x0), ok(x1)) 9.45/3.28 U32(ok(x0), ok(x1)) 9.45/3.28 U33(ok(x0)) 9.45/3.28 U41(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U42(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U43(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U44(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U45(ok(x0), ok(x1)) 9.45/3.28 U46(ok(x0)) 9.45/3.28 isNatIList(ok(x0)) 9.45/3.28 U51(ok(x0), ok(x1)) 9.45/3.28 U52(ok(x0)) 9.45/3.28 U61(ok(x0)) 9.45/3.28 U71(ok(x0)) 9.45/3.28 U81(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U82(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U83(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U84(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U85(ok(x0), ok(x1)) 9.45/3.28 U86(ok(x0)) 9.45/3.28 U91(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U92(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U93(ok(x0), ok(x1), ok(x2)) 9.45/3.28 U94(ok(x0), ok(x1)) 9.45/3.28 s(ok(x0)) 9.45/3.28 length(ok(x0)) 9.45/3.28 top(mark(x0)) 9.45/3.28 top(ok(x0)) 9.45/3.28 9.45/3.28 Special symbols used for the transformation (see [GM04]): 9.45/3.28 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U33: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 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. 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (2) 9.45/3.28 Obligation: 9.45/3.28 Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U32(tt, V) -> U33(isNatList(V)) 9.45/3.28 U33(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 isNatIList(zeros) -> tt 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(nil) -> 0 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U33: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (3) CSRRRRProof (EQUIVALENT) 9.45/3.28 The following CSR is given: Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U32(tt, V) -> U33(isNatList(V)) 9.45/3.28 U33(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 isNatIList(zeros) -> tt 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(nil) -> 0 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U33: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 Used ordering: 9.45/3.28 Polynomial interpretation [POLO]: 9.45/3.28 9.45/3.28 POL(0) = 0 9.45/3.28 POL(U11(x_1, x_2)) = x_1 9.45/3.28 POL(U12(x_1, x_2)) = x_1 9.45/3.28 POL(U13(x_1)) = x_1 9.45/3.28 POL(U21(x_1, x_2)) = x_1 9.45/3.28 POL(U22(x_1, x_2)) = x_1 9.45/3.28 POL(U23(x_1)) = x_1 9.45/3.28 POL(U31(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(U32(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(U33(x_1)) = x_1 9.45/3.28 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U45(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(U46(x_1)) = x_1 9.45/3.28 POL(U51(x_1, x_2)) = x_1 9.45/3.28 POL(U52(x_1)) = x_1 9.45/3.28 POL(U61(x_1)) = x_1 9.45/3.28 POL(U71(x_1)) = x_1 9.45/3.28 POL(U81(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U82(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U83(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U84(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U85(x_1, x_2)) = x_1 9.45/3.28 POL(U86(x_1)) = x_1 9.45/3.28 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U94(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(cons(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(isNat(x_1)) = 1 9.45/3.28 POL(isNatIList(x_1)) = 1 + x_1 9.45/3.28 POL(isNatIListKind(x_1)) = 1 9.45/3.28 POL(isNatKind(x_1)) = 1 9.45/3.28 POL(isNatList(x_1)) = 1 9.45/3.28 POL(length(x_1)) = 1 + x_1 9.45/3.28 POL(nil) = 1 9.45/3.28 POL(s(x_1)) = x_1 9.45/3.28 POL(tt) = 1 9.45/3.28 POL(zeros) = 1 9.45/3.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.28 9.45/3.28 isNatIList(zeros) -> tt 9.45/3.28 length(nil) -> 0 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (4) 9.45/3.28 Obligation: 9.45/3.28 Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U32(tt, V) -> U33(isNatList(V)) 9.45/3.28 U33(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U33: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (5) CSRRRRProof (EQUIVALENT) 9.45/3.28 The following CSR is given: Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U32(tt, V) -> U33(isNatList(V)) 9.45/3.28 U33(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U33: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 Used ordering: 9.45/3.28 Polynomial interpretation [POLO]: 9.45/3.28 9.45/3.28 POL(0) = 0 9.45/3.28 POL(U11(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U12(x_1, x_2)) = x_1 9.45/3.28 POL(U13(x_1)) = x_1 9.45/3.28 POL(U21(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U22(x_1, x_2)) = x_1 9.45/3.28 POL(U23(x_1)) = 2*x_1 9.45/3.28 POL(U31(x_1, x_2)) = 1 + x_1 9.45/3.28 POL(U32(x_1, x_2)) = 1 + x_1 9.45/3.28 POL(U33(x_1)) = 2*x_1 9.45/3.28 POL(U41(x_1, x_2, x_3)) = 1 + 2*x_1 9.45/3.28 POL(U42(x_1, x_2, x_3)) = 1 + x_1 9.45/3.28 POL(U43(x_1, x_2, x_3)) = 1 + x_1 9.45/3.28 POL(U44(x_1, x_2, x_3)) = 1 + x_1 9.45/3.28 POL(U45(x_1, x_2)) = 1 + 2*x_1 9.45/3.28 POL(U46(x_1)) = x_1 9.45/3.28 POL(U51(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U52(x_1)) = 2*x_1 9.45/3.28 POL(U61(x_1)) = 2*x_1 9.45/3.28 POL(U71(x_1)) = 2*x_1 9.45/3.28 POL(U81(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U82(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U83(x_1, x_2, x_3)) = 2*x_1 9.45/3.28 POL(U84(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U85(x_1, x_2)) = x_1 9.45/3.28 POL(U86(x_1)) = 2*x_1 9.45/3.28 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U92(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 9.45/3.28 POL(U93(x_1, x_2, x_3)) = 2*x_1 + x_2 9.45/3.28 POL(U94(x_1, x_2)) = 2*x_1 + x_2 9.45/3.28 POL(cons(x_1, x_2)) = 2*x_1 + x_2 9.45/3.28 POL(isNat(x_1)) = 0 9.45/3.28 POL(isNatIList(x_1)) = 1 9.45/3.28 POL(isNatIListKind(x_1)) = 0 9.45/3.28 POL(isNatKind(x_1)) = 0 9.45/3.28 POL(isNatList(x_1)) = 0 9.45/3.28 POL(length(x_1)) = x_1 9.45/3.28 POL(nil) = 0 9.45/3.28 POL(s(x_1)) = x_1 9.45/3.28 POL(tt) = 0 9.45/3.28 POL(zeros) = 0 9.45/3.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.28 9.45/3.28 U32(tt, V) -> U33(isNatList(V)) 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (6) 9.45/3.28 Obligation: 9.45/3.28 Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U33(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U33: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (7) CSRRRRProof (EQUIVALENT) 9.45/3.28 The following CSR is given: Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U33(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U33: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 Used ordering: 9.45/3.28 Polynomial interpretation [POLO]: 9.45/3.28 9.45/3.28 POL(0) = 0 9.45/3.28 POL(U11(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U12(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U13(x_1)) = x_1 9.45/3.28 POL(U21(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U22(x_1, x_2)) = x_1 9.45/3.28 POL(U23(x_1)) = 2*x_1 9.45/3.28 POL(U31(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U32(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U33(x_1)) = 1 + x_1 9.45/3.28 POL(U41(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U42(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U43(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U44(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U45(x_1, x_2)) = x_1 9.45/3.28 POL(U46(x_1)) = 2*x_1 9.45/3.28 POL(U51(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U52(x_1)) = x_1 9.45/3.28 POL(U61(x_1)) = x_1 9.45/3.28 POL(U71(x_1)) = x_1 9.45/3.28 POL(U81(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U82(x_1, x_2, x_3)) = 2*x_1 9.45/3.28 POL(U83(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U84(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U85(x_1, x_2)) = x_1 9.45/3.28 POL(U86(x_1)) = x_1 9.45/3.28 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.45/3.28 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 9.45/3.28 POL(U94(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 9.45/3.28 POL(isNat(x_1)) = 0 9.45/3.28 POL(isNatIList(x_1)) = 0 9.45/3.28 POL(isNatIListKind(x_1)) = 0 9.45/3.28 POL(isNatKind(x_1)) = 0 9.45/3.28 POL(isNatList(x_1)) = 0 9.45/3.28 POL(length(x_1)) = x_1 9.45/3.28 POL(nil) = 0 9.45/3.28 POL(s(x_1)) = x_1 9.45/3.28 POL(tt) = 0 9.45/3.28 POL(zeros) = 0 9.45/3.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.28 9.45/3.28 U33(tt) -> tt 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (8) 9.45/3.28 Obligation: 9.45/3.28 Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (9) CSRRRRProof (EQUIVALENT) 9.45/3.28 The following CSR is given: Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 Used ordering: 9.45/3.28 Polynomial interpretation [POLO]: 9.45/3.28 9.45/3.28 POL(0) = 0 9.45/3.28 POL(U11(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U12(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U13(x_1)) = x_1 9.45/3.28 POL(U21(x_1, x_2)) = x_1 9.45/3.28 POL(U22(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U23(x_1)) = 2*x_1 9.45/3.28 POL(U31(x_1, x_2)) = x_1 9.45/3.28 POL(U32(x_1, x_2)) = x_1 9.45/3.28 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 9.45/3.28 POL(U42(x_1, x_2, x_3)) = 1 + x_1 + 2*x_3 9.45/3.28 POL(U43(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.45/3.28 POL(U44(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.45/3.28 POL(U45(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 9.45/3.28 POL(U46(x_1)) = x_1 9.45/3.28 POL(U51(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U52(x_1)) = 2*x_1 9.45/3.28 POL(U61(x_1)) = x_1 9.45/3.28 POL(U71(x_1)) = 2*x_1 9.45/3.28 POL(U81(x_1, x_2, x_3)) = 2*x_1 9.45/3.28 POL(U82(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U83(x_1, x_2, x_3)) = 2*x_1 9.45/3.28 POL(U84(x_1, x_2, x_3)) = 2*x_1 9.45/3.28 POL(U85(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U86(x_1)) = x_1 9.45/3.28 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U92(x_1, x_2, x_3)) = 2*x_1 + x_2 9.45/3.28 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 9.45/3.28 POL(U94(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 9.45/3.28 POL(isNat(x_1)) = 0 9.45/3.28 POL(isNatIList(x_1)) = 1 + 2*x_1 9.45/3.28 POL(isNatIListKind(x_1)) = 0 9.45/3.28 POL(isNatKind(x_1)) = 0 9.45/3.28 POL(isNatList(x_1)) = 0 9.45/3.28 POL(length(x_1)) = x_1 9.45/3.28 POL(nil) = 0 9.45/3.28 POL(s(x_1)) = x_1 9.45/3.28 POL(tt) = 0 9.45/3.28 POL(zeros) = 0 9.45/3.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.28 9.45/3.28 isNatIList(V) -> U31(isNatIListKind(V), V) 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (10) 9.45/3.28 Obligation: 9.45/3.28 Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (11) CSRRRRProof (EQUIVALENT) 9.45/3.28 The following CSR is given: Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U31: {1} 9.45/3.28 U32: {1} 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 Used ordering: 9.45/3.28 Polynomial interpretation [POLO]: 9.45/3.28 9.45/3.28 POL(0) = 0 9.45/3.28 POL(U11(x_1, x_2)) = x_1 9.45/3.28 POL(U12(x_1, x_2)) = x_1 9.45/3.28 POL(U13(x_1)) = x_1 9.45/3.28 POL(U21(x_1, x_2)) = x_1 9.45/3.28 POL(U22(x_1, x_2)) = x_1 9.45/3.28 POL(U23(x_1)) = x_1 9.45/3.28 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 9.45/3.28 POL(U32(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U45(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(U46(x_1)) = x_1 9.45/3.28 POL(U51(x_1, x_2)) = x_1 9.45/3.28 POL(U52(x_1)) = x_1 9.45/3.28 POL(U61(x_1)) = x_1 9.45/3.28 POL(U71(x_1)) = x_1 9.45/3.28 POL(U81(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U82(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U83(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U84(x_1, x_2, x_3)) = x_1 9.45/3.28 POL(U85(x_1, x_2)) = x_1 9.45/3.28 POL(U86(x_1)) = x_1 9.45/3.28 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U94(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(cons(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(isNat(x_1)) = 0 9.45/3.28 POL(isNatIList(x_1)) = x_1 9.45/3.28 POL(isNatIListKind(x_1)) = 0 9.45/3.28 POL(isNatKind(x_1)) = 0 9.45/3.28 POL(isNatList(x_1)) = 0 9.45/3.28 POL(length(x_1)) = x_1 9.45/3.28 POL(nil) = 1 9.45/3.28 POL(s(x_1)) = x_1 9.45/3.28 POL(tt) = 0 9.45/3.28 POL(zeros) = 1 9.45/3.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.28 9.45/3.28 U31(tt, V) -> U32(isNatIListKind(V), V) 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (12) 9.45/3.28 Obligation: 9.45/3.28 Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (13) CSRRRRProof (EQUIVALENT) 9.45/3.28 The following CSR is given: Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 Used ordering: 9.45/3.28 Polynomial interpretation [POLO]: 9.45/3.28 9.45/3.28 POL(0) = 0 9.45/3.28 POL(U11(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(U12(x_1, x_2)) = 2*x_1 + x_2 9.45/3.28 POL(U13(x_1)) = x_1 9.45/3.28 POL(U21(x_1, x_2)) = 2*x_1 + x_2 9.45/3.28 POL(U22(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(U23(x_1)) = x_1 9.45/3.28 POL(U41(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.28 POL(U42(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.28 POL(U43(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.28 POL(U44(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.28 POL(U45(x_1, x_2)) = x_1 + 2*x_2 9.45/3.28 POL(U46(x_1)) = 2*x_1 9.45/3.28 POL(U51(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U52(x_1)) = 2*x_1 9.45/3.28 POL(U61(x_1)) = 2*x_1 9.45/3.28 POL(U71(x_1)) = 2*x_1 9.45/3.28 POL(U81(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.28 POL(U82(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.45/3.28 POL(U83(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.28 POL(U84(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.28 POL(U85(x_1, x_2)) = x_1 + 2*x_2 9.45/3.28 POL(U86(x_1)) = 2*x_1 9.45/3.28 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.45/3.28 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.28 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 9.45/3.28 POL(U94(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 9.45/3.28 POL(isNat(x_1)) = x_1 9.45/3.28 POL(isNatIList(x_1)) = x_1 9.45/3.28 POL(isNatIListKind(x_1)) = 0 9.45/3.28 POL(isNatKind(x_1)) = 0 9.45/3.28 POL(isNatList(x_1)) = x_1 9.45/3.28 POL(length(x_1)) = x_1 9.45/3.28 POL(nil) = 2 9.45/3.28 POL(s(x_1)) = x_1 9.45/3.28 POL(tt) = 0 9.45/3.28 POL(zeros) = 0 9.45/3.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.28 9.45/3.28 isNatList(nil) -> tt 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (14) 9.45/3.28 Obligation: 9.45/3.28 Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (15) CSRRRRProof (EQUIVALENT) 9.45/3.28 The following CSR is given: Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 U12: {1} 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 Used ordering: 9.45/3.28 Polynomial interpretation [POLO]: 9.45/3.28 9.45/3.28 POL(0) = 0 9.45/3.28 POL(U11(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 9.45/3.28 POL(U12(x_1, x_2)) = 1 + x_1 + 2*x_2 9.45/3.28 POL(U13(x_1)) = x_1 9.45/3.28 POL(U21(x_1, x_2)) = 2*x_1 + 2*x_2 9.45/3.28 POL(U22(x_1, x_2)) = 2*x_1 + 2*x_2 9.45/3.28 POL(U23(x_1)) = x_1 9.45/3.28 POL(U41(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.45/3.28 POL(U42(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.45/3.28 POL(U43(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.45/3.28 POL(U44(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.45/3.28 POL(U45(x_1, x_2)) = x_1 + 2*x_2 9.45/3.28 POL(U46(x_1)) = 2*x_1 9.45/3.28 POL(U51(x_1, x_2)) = 2*x_1 9.45/3.28 POL(U52(x_1)) = x_1 9.45/3.28 POL(U61(x_1)) = x_1 9.45/3.28 POL(U71(x_1)) = x_1 9.45/3.28 POL(U81(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.45/3.28 POL(U82(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 9.45/3.28 POL(U83(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 9.45/3.28 POL(U84(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 9.45/3.28 POL(U85(x_1, x_2)) = x_1 + x_2 9.45/3.28 POL(U86(x_1)) = x_1 9.45/3.28 POL(U91(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 9.45/3.28 POL(U92(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 9.45/3.28 POL(U93(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 9.45/3.28 POL(U94(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 9.45/3.28 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 9.45/3.28 POL(isNat(x_1)) = 2*x_1 9.45/3.28 POL(isNatIList(x_1)) = x_1 9.45/3.28 POL(isNatIListKind(x_1)) = 0 9.45/3.28 POL(isNatKind(x_1)) = 0 9.45/3.28 POL(isNatList(x_1)) = x_1 9.45/3.28 POL(length(x_1)) = 1 + 2*x_1 9.45/3.28 POL(nil) = 2 9.45/3.28 POL(s(x_1)) = x_1 9.45/3.28 POL(tt) = 0 9.45/3.28 POL(zeros) = 0 9.45/3.28 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.28 9.45/3.28 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.45/3.28 U12(tt, V1) -> U13(isNatList(V1)) 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (16) 9.45/3.28 Obligation: 9.45/3.28 Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 9.45/3.28 ---------------------------------------- 9.45/3.28 9.45/3.28 (17) CSRRRRProof (EQUIVALENT) 9.45/3.28 The following CSR is given: Context-sensitive rewrite system: 9.45/3.28 The TRS R consists of the following rules: 9.45/3.28 9.45/3.28 zeros -> cons(0, zeros) 9.45/3.28 U13(tt) -> tt 9.45/3.28 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.28 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.28 U23(tt) -> tt 9.45/3.28 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.28 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.28 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.28 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.28 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.28 U46(tt) -> tt 9.45/3.28 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.28 U52(tt) -> tt 9.45/3.28 U61(tt) -> tt 9.45/3.28 U71(tt) -> tt 9.45/3.28 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.28 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.28 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.28 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.28 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.28 U86(tt) -> tt 9.45/3.28 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.28 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.28 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.28 U94(tt, L) -> s(length(L)) 9.45/3.28 isNat(0) -> tt 9.45/3.28 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.28 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.28 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.28 isNatIListKind(nil) -> tt 9.45/3.28 isNatIListKind(zeros) -> tt 9.45/3.28 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.28 isNatKind(0) -> tt 9.45/3.28 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.28 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.28 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.28 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.28 9.45/3.28 The replacement map contains the following entries: 9.45/3.28 9.45/3.28 zeros: empty set 9.45/3.28 cons: {1} 9.45/3.28 0: empty set 9.45/3.28 U11: {1} 9.45/3.28 tt: empty set 9.45/3.28 isNatIListKind: empty set 9.45/3.28 U13: {1} 9.45/3.28 isNatList: empty set 9.45/3.28 U21: {1} 9.45/3.28 U22: {1} 9.45/3.28 isNatKind: empty set 9.45/3.28 U23: {1} 9.45/3.28 isNat: empty set 9.45/3.28 U41: {1} 9.45/3.28 U42: {1} 9.45/3.28 U43: {1} 9.45/3.28 U44: {1} 9.45/3.28 U45: {1} 9.45/3.28 U46: {1} 9.45/3.28 isNatIList: empty set 9.45/3.28 U51: {1} 9.45/3.28 U52: {1} 9.45/3.28 U61: {1} 9.45/3.28 U71: {1} 9.45/3.28 U81: {1} 9.45/3.28 U82: {1} 9.45/3.28 U83: {1} 9.45/3.28 U84: {1} 9.45/3.28 U85: {1} 9.45/3.28 U86: {1} 9.45/3.28 U91: {1} 9.45/3.28 U92: {1} 9.45/3.28 U93: {1} 9.45/3.28 U94: {1} 9.45/3.28 s: {1} 9.45/3.28 length: {1} 9.45/3.28 nil: empty set 9.45/3.28 Used ordering: 9.45/3.28 Polynomial interpretation [POLO]: 9.45/3.28 9.45/3.28 POL(0) = 0 9.45/3.28 POL(U11(x_1, x_2)) = x_1 9.45/3.28 POL(U13(x_1)) = 1 + x_1 9.45/3.29 POL(U21(x_1, x_2)) = x_1 9.45/3.29 POL(U22(x_1, x_2)) = x_1 9.45/3.29 POL(U23(x_1)) = x_1 9.45/3.29 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.29 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.29 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.29 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.29 POL(U45(x_1, x_2)) = x_1 + x_2 9.45/3.29 POL(U46(x_1)) = x_1 9.45/3.29 POL(U51(x_1, x_2)) = x_1 9.45/3.29 POL(U52(x_1)) = x_1 9.45/3.29 POL(U61(x_1)) = x_1 9.45/3.29 POL(U71(x_1)) = x_1 9.45/3.29 POL(U81(x_1, x_2, x_3)) = x_1 9.45/3.29 POL(U82(x_1, x_2, x_3)) = x_1 9.45/3.29 POL(U83(x_1, x_2, x_3)) = x_1 9.45/3.29 POL(U84(x_1, x_2, x_3)) = x_1 9.45/3.29 POL(U85(x_1, x_2)) = x_1 9.45/3.29 POL(U86(x_1)) = x_1 9.45/3.29 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.29 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.29 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.45/3.29 POL(U94(x_1, x_2)) = x_1 + x_2 9.45/3.29 POL(cons(x_1, x_2)) = x_1 + x_2 9.45/3.29 POL(isNat(x_1)) = 1 9.45/3.29 POL(isNatIList(x_1)) = 1 + x_1 9.45/3.29 POL(isNatIListKind(x_1)) = 1 9.45/3.29 POL(isNatKind(x_1)) = 1 9.45/3.29 POL(isNatList(x_1)) = 1 9.45/3.29 POL(length(x_1)) = 1 + x_1 9.45/3.29 POL(nil) = 1 9.45/3.29 POL(s(x_1)) = x_1 9.45/3.29 POL(tt) = 1 9.45/3.29 POL(zeros) = 1 9.45/3.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.29 9.45/3.29 U13(tt) -> tt 9.45/3.29 9.45/3.29 9.45/3.29 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (18) 9.45/3.29 Obligation: 9.45/3.29 Context-sensitive rewrite system: 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 The replacement map contains the following entries: 9.45/3.29 9.45/3.29 zeros: empty set 9.45/3.29 cons: {1} 9.45/3.29 0: empty set 9.45/3.29 U11: {1} 9.45/3.29 tt: empty set 9.45/3.29 isNatIListKind: empty set 9.45/3.29 isNatList: empty set 9.45/3.29 U21: {1} 9.45/3.29 U22: {1} 9.45/3.29 isNatKind: empty set 9.45/3.29 U23: {1} 9.45/3.29 isNat: empty set 9.45/3.29 U41: {1} 9.45/3.29 U42: {1} 9.45/3.29 U43: {1} 9.45/3.29 U44: {1} 9.45/3.29 U45: {1} 9.45/3.29 U46: {1} 9.45/3.29 isNatIList: empty set 9.45/3.29 U51: {1} 9.45/3.29 U52: {1} 9.45/3.29 U61: {1} 9.45/3.29 U71: {1} 9.45/3.29 U81: {1} 9.45/3.29 U82: {1} 9.45/3.29 U83: {1} 9.45/3.29 U84: {1} 9.45/3.29 U85: {1} 9.45/3.29 U86: {1} 9.45/3.29 U91: {1} 9.45/3.29 U92: {1} 9.45/3.29 U93: {1} 9.45/3.29 U94: {1} 9.45/3.29 s: {1} 9.45/3.29 length: {1} 9.45/3.29 nil: empty set 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (19) CSRRRRProof (EQUIVALENT) 9.45/3.29 The following CSR is given: Context-sensitive rewrite system: 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 The replacement map contains the following entries: 9.45/3.29 9.45/3.29 zeros: empty set 9.45/3.29 cons: {1} 9.45/3.29 0: empty set 9.45/3.29 U11: {1} 9.45/3.29 tt: empty set 9.45/3.29 isNatIListKind: empty set 9.45/3.29 isNatList: empty set 9.45/3.29 U21: {1} 9.45/3.29 U22: {1} 9.45/3.29 isNatKind: empty set 9.45/3.29 U23: {1} 9.45/3.29 isNat: empty set 9.45/3.29 U41: {1} 9.45/3.29 U42: {1} 9.45/3.29 U43: {1} 9.45/3.29 U44: {1} 9.45/3.29 U45: {1} 9.45/3.29 U46: {1} 9.45/3.29 isNatIList: empty set 9.45/3.29 U51: {1} 9.45/3.29 U52: {1} 9.45/3.29 U61: {1} 9.45/3.29 U71: {1} 9.45/3.29 U81: {1} 9.45/3.29 U82: {1} 9.45/3.29 U83: {1} 9.45/3.29 U84: {1} 9.45/3.29 U85: {1} 9.45/3.29 U86: {1} 9.45/3.29 U91: {1} 9.45/3.29 U92: {1} 9.45/3.29 U93: {1} 9.45/3.29 U94: {1} 9.45/3.29 s: {1} 9.45/3.29 length: {1} 9.45/3.29 nil: empty set 9.45/3.29 Used ordering: 9.45/3.29 Polynomial interpretation [POLO]: 9.45/3.29 9.45/3.29 POL(0) = 0 9.45/3.29 POL(U11(x_1, x_2)) = 2*x_1 9.45/3.29 POL(U21(x_1, x_2)) = x_1 + x_2 9.45/3.29 POL(U22(x_1, x_2)) = 2*x_1 + x_2 9.45/3.29 POL(U23(x_1)) = x_1 9.45/3.29 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.45/3.29 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.45/3.29 POL(U43(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.29 POL(U44(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.29 POL(U45(x_1, x_2)) = x_1 + 2*x_2 9.45/3.29 POL(U46(x_1)) = 2*x_1 9.45/3.29 POL(U51(x_1, x_2)) = 2*x_1 9.45/3.29 POL(U52(x_1)) = 2*x_1 9.45/3.29 POL(U61(x_1)) = 2*x_1 9.45/3.29 POL(U71(x_1)) = x_1 9.45/3.29 POL(U81(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.45/3.29 POL(U82(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.29 POL(U83(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.29 POL(U84(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.45/3.29 POL(U85(x_1, x_2)) = x_1 + 2*x_2 9.45/3.29 POL(U86(x_1)) = x_1 9.45/3.29 POL(U91(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.45/3.29 POL(U92(x_1, x_2, x_3)) = 1 + 2*x_1 + x_2 + x_3 9.45/3.29 POL(U93(x_1, x_2, x_3)) = 1 + x_1 + x_2 9.45/3.29 POL(U94(x_1, x_2)) = 1 + 2*x_1 + x_2 9.45/3.29 POL(cons(x_1, x_2)) = x_1 + 2*x_2 9.45/3.29 POL(isNat(x_1)) = x_1 9.45/3.29 POL(isNatIList(x_1)) = x_1 9.45/3.29 POL(isNatIListKind(x_1)) = 0 9.45/3.29 POL(isNatKind(x_1)) = 0 9.45/3.29 POL(isNatList(x_1)) = x_1 9.45/3.29 POL(length(x_1)) = 1 + x_1 9.45/3.29 POL(nil) = 2 9.45/3.29 POL(s(x_1)) = x_1 9.45/3.29 POL(tt) = 0 9.45/3.29 POL(zeros) = 0 9.45/3.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.45/3.29 9.45/3.29 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.45/3.29 9.45/3.29 9.45/3.29 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (20) 9.45/3.29 Obligation: 9.45/3.29 Context-sensitive rewrite system: 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 The replacement map contains the following entries: 9.45/3.29 9.45/3.29 zeros: empty set 9.45/3.29 cons: {1} 9.45/3.29 0: empty set 9.45/3.29 tt: empty set 9.45/3.29 isNatIListKind: empty set 9.45/3.29 isNatList: empty set 9.45/3.29 U21: {1} 9.45/3.29 U22: {1} 9.45/3.29 isNatKind: empty set 9.45/3.29 U23: {1} 9.45/3.29 isNat: empty set 9.45/3.29 U41: {1} 9.45/3.29 U42: {1} 9.45/3.29 U43: {1} 9.45/3.29 U44: {1} 9.45/3.29 U45: {1} 9.45/3.29 U46: {1} 9.45/3.29 isNatIList: empty set 9.45/3.29 U51: {1} 9.45/3.29 U52: {1} 9.45/3.29 U61: {1} 9.45/3.29 U71: {1} 9.45/3.29 U81: {1} 9.45/3.29 U82: {1} 9.45/3.29 U83: {1} 9.45/3.29 U84: {1} 9.45/3.29 U85: {1} 9.45/3.29 U86: {1} 9.45/3.29 U91: {1} 9.45/3.29 U92: {1} 9.45/3.29 U93: {1} 9.45/3.29 U94: {1} 9.45/3.29 s: {1} 9.45/3.29 length: {1} 9.45/3.29 nil: empty set 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (21) CSDependencyPairsProof (EQUIVALENT) 9.45/3.29 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (22) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1, U23'_1, U46'_1, U52'_1, U86'_1, LENGTH_1, U61'_1, U71'_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U22'_2, U21'_2, U42'_3, U41'_3, U43'_3, U44'_3, U45'_2, U51'_2, U82'_3, U81'_3, U83'_3, U84'_3, U85'_2, U92'_3, U91'_3, U93'_3, U94'_2} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNATKIND_1, ISNAT_1, ISNATILISTKIND_1, ISNATILIST_1, ISNATLIST_1, U_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The ordinary context-sensitive dependency pairs DP_o are: 9.45/3.29 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 9.45/3.29 U21'(tt, V1) -> ISNATKIND(V1) 9.45/3.29 U22'(tt, V1) -> U23'(isNat(V1)) 9.45/3.29 U22'(tt, V1) -> ISNAT(V1) 9.45/3.29 U41'(tt, V1, V2) -> U42'(isNatKind(V1), V1, V2) 9.45/3.29 U41'(tt, V1, V2) -> ISNATKIND(V1) 9.45/3.29 U42'(tt, V1, V2) -> U43'(isNatIListKind(V2), V1, V2) 9.45/3.29 U42'(tt, V1, V2) -> ISNATILISTKIND(V2) 9.45/3.29 U43'(tt, V1, V2) -> U44'(isNatIListKind(V2), V1, V2) 9.45/3.29 U43'(tt, V1, V2) -> ISNATILISTKIND(V2) 9.45/3.29 U44'(tt, V1, V2) -> U45'(isNat(V1), V2) 9.45/3.29 U44'(tt, V1, V2) -> ISNAT(V1) 9.45/3.29 U45'(tt, V2) -> U46'(isNatIList(V2)) 9.45/3.29 U45'(tt, V2) -> ISNATILIST(V2) 9.45/3.29 U51'(tt, V2) -> U52'(isNatIListKind(V2)) 9.45/3.29 U51'(tt, V2) -> ISNATILISTKIND(V2) 9.45/3.29 U81'(tt, V1, V2) -> U82'(isNatKind(V1), V1, V2) 9.45/3.29 U81'(tt, V1, V2) -> ISNATKIND(V1) 9.45/3.29 U82'(tt, V1, V2) -> U83'(isNatIListKind(V2), V1, V2) 9.45/3.29 U82'(tt, V1, V2) -> ISNATILISTKIND(V2) 9.45/3.29 U83'(tt, V1, V2) -> U84'(isNatIListKind(V2), V1, V2) 9.45/3.29 U83'(tt, V1, V2) -> ISNATILISTKIND(V2) 9.45/3.29 U84'(tt, V1, V2) -> U85'(isNat(V1), V2) 9.45/3.29 U84'(tt, V1, V2) -> ISNAT(V1) 9.45/3.29 U85'(tt, V2) -> U86'(isNatList(V2)) 9.45/3.29 U85'(tt, V2) -> ISNATLIST(V2) 9.45/3.29 U91'(tt, L, N) -> U92'(isNatIListKind(L), L, N) 9.45/3.29 U91'(tt, L, N) -> ISNATILISTKIND(L) 9.45/3.29 U92'(tt, L, N) -> U93'(isNat(N), L, N) 9.45/3.29 U92'(tt, L, N) -> ISNAT(N) 9.45/3.29 U93'(tt, L, N) -> U94'(isNatKind(N), L) 9.45/3.29 U93'(tt, L, N) -> ISNATKIND(N) 9.45/3.29 U94'(tt, L) -> LENGTH(L) 9.45/3.29 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 9.45/3.29 ISNAT(s(V1)) -> ISNATKIND(V1) 9.45/3.29 ISNATILIST(cons(V1, V2)) -> U41'(isNatKind(V1), V1, V2) 9.45/3.29 ISNATILIST(cons(V1, V2)) -> ISNATKIND(V1) 9.45/3.29 ISNATILISTKIND(cons(V1, V2)) -> U51'(isNatKind(V1), V2) 9.45/3.29 ISNATILISTKIND(cons(V1, V2)) -> ISNATKIND(V1) 9.45/3.29 ISNATKIND(length(V1)) -> U61'(isNatIListKind(V1)) 9.45/3.29 ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) 9.45/3.29 ISNATKIND(s(V1)) -> U71'(isNatKind(V1)) 9.45/3.29 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.45/3.29 ISNATLIST(cons(V1, V2)) -> U81'(isNatKind(V1), V1, V2) 9.45/3.29 ISNATLIST(cons(V1, V2)) -> ISNATKIND(V1) 9.45/3.29 LENGTH(cons(N, L)) -> U91'(isNatList(L), L, N) 9.45/3.29 LENGTH(cons(N, L)) -> ISNATLIST(L) 9.45/3.29 9.45/3.29 The collapsing dependency pairs are DP_c: 9.45/3.29 U94'(tt, L) -> L 9.45/3.29 9.45/3.29 9.45/3.29 The hidden terms of R are: 9.45/3.29 9.45/3.29 zeros 9.45/3.29 9.45/3.29 Every hiding context is built from:none 9.45/3.29 9.45/3.29 Hence, the new unhiding pairs DP_u are : 9.45/3.29 U94'(tt, L) -> U(L) 9.45/3.29 U(zeros) -> ZEROS 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (23) QCSDependencyGraphProof (EQUIVALENT) 9.45/3.29 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 5 SCCs with 24 less nodes. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (24) 9.45/3.29 Complex Obligation (AND) 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (25) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U51'_2} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNATILISTKIND_1, ISNATKIND_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) 9.45/3.29 ISNATILISTKIND(cons(V1, V2)) -> U51'(isNatKind(V1), V2) 9.45/3.29 U51'(tt, V2) -> ISNATILISTKIND(V2) 9.45/3.29 ISNATILISTKIND(cons(V1, V2)) -> ISNATKIND(V1) 9.45/3.29 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (26) QCSUsableRulesProof (EQUIVALENT) 9.45/3.29 The following rules are not useable [DA_EMMES] and can be deleted: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, x0) -> U22(isNatKind(x0), x0) 9.45/3.29 U22(tt, x0) -> U23(isNat(x0)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, x0, x1) -> U42(isNatKind(x0), x0, x1) 9.45/3.29 U42(tt, x0, x1) -> U43(isNatIListKind(x1), x0, x1) 9.45/3.29 U43(tt, x0, x1) -> U44(isNatIListKind(x1), x0, x1) 9.45/3.29 U44(tt, x0, x1) -> U45(isNat(x0), x1) 9.45/3.29 U45(tt, x0) -> U46(isNatIList(x0)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U81(tt, x0, x1) -> U82(isNatKind(x0), x0, x1) 9.45/3.29 U82(tt, x0, x1) -> U83(isNatIListKind(x1), x0, x1) 9.45/3.29 U83(tt, x0, x1) -> U84(isNatIListKind(x1), x0, x1) 9.45/3.29 U84(tt, x0, x1) -> U85(isNat(x0), x1) 9.45/3.29 U85(tt, x0) -> U86(isNatList(x0)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, x0, x1) -> U92(isNatIListKind(x0), x0, x1) 9.45/3.29 U92(tt, x0, x1) -> U93(isNat(x1), x0, x1) 9.45/3.29 U93(tt, x0, x1) -> U94(isNatKind(x1), x0) 9.45/3.29 U94(tt, x0) -> s(length(x0)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(x0)) -> U21(isNatKind(x0), x0) 9.45/3.29 isNatIList(cons(x0, x1)) -> U41(isNatKind(x0), x0, x1) 9.45/3.29 isNatList(cons(x0, x1)) -> U81(isNatKind(x0), x0, x1) 9.45/3.29 length(cons(x0, x1)) -> U91(isNatList(x1), x1, x0) 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (27) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {length_1, U61_1, s_1, U71_1, U52_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U51_2, U51'_2} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNatIListKind_1, ISNATILISTKIND_1, ISNATKIND_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) 9.45/3.29 ISNATILISTKIND(cons(V1, V2)) -> U51'(isNatKind(V1), V2) 9.45/3.29 U51'(tt, V2) -> ISNATILISTKIND(V2) 9.45/3.29 ISNATILISTKIND(cons(V1, V2)) -> ISNATKIND(V1) 9.45/3.29 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 U71(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (28) QCSDPMuMonotonicPoloProof (EQUIVALENT) 9.45/3.29 By using the following mu-monotonic polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this Q-CSDP problem can be strictly oriented and thus deleted. 9.45/3.29 9.45/3.29 Strictly oriented dependency pairs: 9.45/3.29 9.45/3.29 ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) 9.45/3.29 ISNATILISTKIND(cons(V1, V2)) -> U51'(isNatKind(V1), V2) 9.45/3.29 U51'(tt, V2) -> ISNATILISTKIND(V2) 9.45/3.29 ISNATILISTKIND(cons(V1, V2)) -> ISNATKIND(V1) 9.45/3.29 9.45/3.29 Strictly oriented rules of the TRS R: 9.45/3.29 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 U71(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 9.45/3.29 Used ordering: POLO with Polynomial interpretation [POLO]: 9.45/3.29 9.45/3.29 POL(0) = 2 9.45/3.29 POL(ISNATILISTKIND(x_1)) = 1 + 2*x_1 9.45/3.29 POL(ISNATKIND(x_1)) = 2 + 2*x_1 9.45/3.29 POL(U51(x_1, x_2)) = x_1 + 2*x_2 9.45/3.29 POL(U51'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 9.45/3.29 POL(U52(x_1)) = x_1 9.45/3.29 POL(U61(x_1)) = x_1 9.45/3.29 POL(U71(x_1)) = 2*x_1 9.45/3.29 POL(cons(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 9.45/3.29 POL(isNatIListKind(x_1)) = 1 + x_1 9.45/3.29 POL(isNatKind(x_1)) = 2*x_1 9.45/3.29 POL(length(x_1)) = 1 + x_1 9.45/3.29 POL(nil) = 2 9.45/3.29 POL(s(x_1)) = 2*x_1 9.45/3.29 POL(tt) = 2 9.45/3.29 POL(zeros) = 2 9.45/3.29 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (29) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {s_1, U71_1, U52_1, U61_1} are replacing on all positions. 9.45/3.29 The symbols in {isNatKind_1, ISNATKIND_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (30) QCSDPSubtermProof (EQUIVALENT) 9.45/3.29 We use the subterm processor [DA_EMMES]. 9.45/3.29 9.45/3.29 9.45/3.29 The following pairs can be oriented strictly and are deleted. 9.45/3.29 9.45/3.29 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.45/3.29 The remaining pairs can at least be oriented weakly. 9.45/3.29 none 9.45/3.29 Used ordering: Combined order from the following AFS and order. 9.45/3.29 ISNATKIND(x1) = x1 9.45/3.29 9.45/3.29 9.45/3.29 Subterm Order 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (31) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {s_1, U71_1, U52_1, U61_1} are replacing on all positions. 9.45/3.29 The symbols in {isNatKind_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 none 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (32) PIsEmptyProof (EQUIVALENT) 9.45/3.29 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (33) 9.45/3.29 YES 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (34) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U22'_2, U21'_2} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNAT_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 U22'(tt, V1) -> ISNAT(V1) 9.45/3.29 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 9.45/3.29 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (35) QCSDPSubtermProof (EQUIVALENT) 9.45/3.29 We use the subterm processor [DA_EMMES]. 9.45/3.29 9.45/3.29 9.45/3.29 The following pairs can be oriented strictly and are deleted. 9.45/3.29 9.45/3.29 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 9.45/3.29 The remaining pairs can at least be oriented weakly. 9.45/3.29 9.45/3.29 U22'(tt, V1) -> ISNAT(V1) 9.45/3.29 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 9.45/3.29 Used ordering: Combined order from the following AFS and order. 9.45/3.29 ISNAT(x1) = x1 9.45/3.29 9.45/3.29 U22'(x1, x2) = x2 9.45/3.29 9.45/3.29 U21'(x1, x2) = x2 9.45/3.29 9.45/3.29 9.45/3.29 Subterm Order 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (36) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U22'_2, U21'_2} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNAT_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 U22'(tt, V1) -> ISNAT(V1) 9.45/3.29 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (37) QCSDependencyGraphProof (EQUIVALENT) 9.45/3.29 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (38) 9.45/3.29 TRUE 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (39) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U85'_2, U84'_3, U81'_3, U82'_3, U83'_3} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNATLIST_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 U84'(tt, V1, V2) -> U85'(isNat(V1), V2) 9.45/3.29 U85'(tt, V2) -> ISNATLIST(V2) 9.45/3.29 ISNATLIST(cons(V1, V2)) -> U81'(isNatKind(V1), V1, V2) 9.45/3.29 U81'(tt, V1, V2) -> U82'(isNatKind(V1), V1, V2) 9.45/3.29 U82'(tt, V1, V2) -> U83'(isNatIListKind(V2), V1, V2) 9.45/3.29 U83'(tt, V1, V2) -> U84'(isNatIListKind(V2), V1, V2) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (40) QCSUsableRulesProof (EQUIVALENT) 9.45/3.29 The following rules are not useable [DA_EMMES] and can be deleted: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U41(tt, x0, x1) -> U42(isNatKind(x0), x0, x1) 9.45/3.29 U42(tt, x0, x1) -> U43(isNatIListKind(x1), x0, x1) 9.45/3.29 U43(tt, x0, x1) -> U44(isNatIListKind(x1), x0, x1) 9.45/3.29 U44(tt, x0, x1) -> U45(isNat(x0), x1) 9.45/3.29 U45(tt, x0) -> U46(isNatIList(x0)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U81(tt, x0, x1) -> U82(isNatKind(x0), x0, x1) 9.45/3.29 U82(tt, x0, x1) -> U83(isNatIListKind(x1), x0, x1) 9.45/3.29 U83(tt, x0, x1) -> U84(isNatIListKind(x1), x0, x1) 9.45/3.29 U84(tt, x0, x1) -> U85(isNat(x0), x1) 9.45/3.29 U85(tt, x0) -> U86(isNatList(x0)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, x0, x1) -> U92(isNatIListKind(x0), x0, x1) 9.45/3.29 U92(tt, x0, x1) -> U93(isNat(x1), x0, x1) 9.45/3.29 U93(tt, x0, x1) -> U94(isNatKind(x1), x0) 9.45/3.29 U94(tt, x0) -> s(length(x0)) 9.45/3.29 isNatIList(cons(x0, x1)) -> U41(isNatKind(x0), x0, x1) 9.45/3.29 isNatList(cons(x0, x1)) -> U81(isNatKind(x0), x0, x1) 9.45/3.29 length(cons(x0, x1)) -> U91(isNatList(x1), x1, x0) 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (41) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {s_1, length_1, U61_1, U71_1, U52_1, U23_1} are replacing on all positions. 9.45/3.29 For all symbols f in {U21_2, cons_2, U51_2, U22_2, U85'_2, U84'_3, U81'_3, U82'_3, U83'_3} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNat_1, isNatKind_1, isNatIListKind_1, ISNATLIST_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 U84'(tt, V1, V2) -> U85'(isNat(V1), V2) 9.45/3.29 U85'(tt, V2) -> ISNATLIST(V2) 9.45/3.29 ISNATLIST(cons(V1, V2)) -> U81'(isNatKind(V1), V1, V2) 9.45/3.29 U81'(tt, V1, V2) -> U82'(isNatKind(V1), V1, V2) 9.45/3.29 U82'(tt, V1, V2) -> U83'(isNatIListKind(V2), V1, V2) 9.45/3.29 U83'(tt, V1, V2) -> U84'(isNatIListKind(V2), V1, V2) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 U71(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (42) QCSDPMuMonotonicPoloProof (EQUIVALENT) 9.45/3.29 By using the following mu-monotonic polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this Q-CSDP problem can be strictly oriented and thus deleted. 9.45/3.29 9.45/3.29 Strictly oriented dependency pairs: 9.45/3.29 9.45/3.29 U85'(tt, V2) -> ISNATLIST(V2) 9.45/3.29 U83'(tt, V1, V2) -> U84'(isNatIListKind(V2), V1, V2) 9.45/3.29 9.45/3.29 9.45/3.29 Used ordering: POLO with Polynomial interpretation [POLO]: 9.45/3.29 9.45/3.29 POL(0) = 0 9.45/3.29 POL(ISNATLIST(x_1)) = 1 + 2*x_1 9.45/3.29 POL(U21(x_1, x_2)) = x_1 9.45/3.29 POL(U22(x_1, x_2)) = x_1 9.45/3.29 POL(U23(x_1)) = x_1 9.45/3.29 POL(U51(x_1, x_2)) = x_1 9.45/3.29 POL(U52(x_1)) = x_1 9.45/3.29 POL(U61(x_1)) = x_1 9.45/3.29 POL(U71(x_1)) = x_1 9.45/3.29 POL(U81'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.45/3.29 POL(U82'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.45/3.29 POL(U83'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.45/3.29 POL(U84'(x_1, x_2, x_3)) = x_1 + 2*x_3 9.45/3.29 POL(U85'(x_1, x_2)) = x_1 + 2*x_2 9.45/3.29 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 9.45/3.29 POL(isNat(x_1)) = 2 9.45/3.29 POL(isNatIListKind(x_1)) = 2 9.45/3.29 POL(isNatKind(x_1)) = 2 9.45/3.29 POL(length(x_1)) = 2 + 2*x_1 9.45/3.29 POL(nil) = 2 9.45/3.29 POL(s(x_1)) = x_1 9.45/3.29 POL(tt) = 2 9.45/3.29 POL(zeros) = 2 9.45/3.29 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (43) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {s_1, length_1, U61_1, U71_1, U52_1, U23_1} are replacing on all positions. 9.45/3.29 For all symbols f in {U21_2, cons_2, U51_2, U22_2, U85'_2, U84'_3, U81'_3, U82'_3, U83'_3} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNat_1, isNatKind_1, isNatIListKind_1, ISNATLIST_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 U84'(tt, V1, V2) -> U85'(isNat(V1), V2) 9.45/3.29 ISNATLIST(cons(V1, V2)) -> U81'(isNatKind(V1), V1, V2) 9.45/3.29 U81'(tt, V1, V2) -> U82'(isNatKind(V1), V1, V2) 9.45/3.29 U82'(tt, V1, V2) -> U83'(isNatIListKind(V2), V1, V2) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 U71(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (44) QCSDependencyGraphProof (EQUIVALENT) 9.45/3.29 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 4 less nodes. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (45) 9.45/3.29 TRUE 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (46) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1, LENGTH_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U91'_3, U92'_3, U93'_3, U94'_2} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 LENGTH(cons(N, L)) -> U91'(isNatList(L), L, N) 9.45/3.29 U91'(tt, L, N) -> U92'(isNatIListKind(L), L, N) 9.45/3.29 U92'(tt, L, N) -> U93'(isNat(N), L, N) 9.45/3.29 U93'(tt, L, N) -> U94'(isNatKind(N), L) 9.45/3.29 U94'(tt, L) -> LENGTH(L) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (47) QCSDPReductionPairProof (EQUIVALENT) 9.45/3.29 Using the order 9.45/3.29 9.45/3.29 Polynomial interpretation [POLO]: 9.45/3.29 9.45/3.29 POL(0) = 2 9.45/3.29 POL(LENGTH(x_1)) = 1 9.45/3.29 POL(U21(x_1, x_2)) = 2 9.45/3.29 POL(U22(x_1, x_2)) = 2 9.45/3.29 POL(U23(x_1)) = 2 9.45/3.29 POL(U51(x_1, x_2)) = 2 9.45/3.29 POL(U52(x_1)) = 2 9.45/3.29 POL(U61(x_1)) = 2 9.45/3.29 POL(U71(x_1)) = 2 9.45/3.29 POL(U81(x_1, x_2, x_3)) = 0 9.45/3.29 POL(U82(x_1, x_2, x_3)) = 0 9.45/3.29 POL(U83(x_1, x_2, x_3)) = 0 9.45/3.29 POL(U84(x_1, x_2, x_3)) = 0 9.45/3.29 POL(U85(x_1, x_2)) = 0 9.45/3.29 POL(U86(x_1)) = 2*x_1 9.45/3.29 POL(U91(x_1, x_2, x_3)) = x_1 9.45/3.29 POL(U91'(x_1, x_2, x_3)) = 1 + 2*x_1 9.45/3.29 POL(U92(x_1, x_2, x_3)) = 1 9.45/3.29 POL(U92'(x_1, x_2, x_3)) = 1 + 2*x_1 9.45/3.29 POL(U93(x_1, x_2, x_3)) = 1 9.45/3.29 POL(U93'(x_1, x_2, x_3)) = 1 + 2*x_1 9.45/3.29 POL(U94(x_1, x_2)) = 1 9.45/3.29 POL(U94'(x_1, x_2)) = 2 9.45/3.29 POL(cons(x_1, x_2)) = 0 9.45/3.29 POL(isNat(x_1)) = 2 9.45/3.29 POL(isNatIListKind(x_1)) = 2 9.45/3.29 POL(isNatKind(x_1)) = 2*x_1 9.45/3.29 POL(isNatList(x_1)) = 0 9.45/3.29 POL(length(x_1)) = 2 9.45/3.29 POL(nil) = 2 9.45/3.29 POL(s(x_1)) = 1 9.45/3.29 POL(tt) = 2 9.45/3.29 POL(zeros) = 0 9.45/3.29 9.45/3.29 9.45/3.29 the following usable rules 9.45/3.29 9.45/3.29 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 9.45/3.29 9.45/3.29 could all be oriented weakly. 9.45/3.29 9.45/3.29 Furthermore, the pairs 9.45/3.29 9.45/3.29 9.45/3.29 U93'(tt, L, N) -> U94'(isNatKind(N), L) 9.45/3.29 U94'(tt, L) -> LENGTH(L) 9.45/3.29 9.45/3.29 9.45/3.29 could be oriented strictly and thus removed by the CS-Reduction Pair Processor [LPAR08,DA_EMMES]. 9.45/3.29 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (48) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1, LENGTH_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U91'_3, U92'_3, U93'_3} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 LENGTH(cons(N, L)) -> U91'(isNatList(L), L, N) 9.45/3.29 U91'(tt, L, N) -> U92'(isNatIListKind(L), L, N) 9.45/3.29 U92'(tt, L, N) -> U93'(isNat(N), L, N) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (49) QCSDependencyGraphProof (EQUIVALENT) 9.45/3.29 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 3 less nodes. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (50) 9.45/3.29 TRUE 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (51) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.45/3.29 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U45'_2, U44'_3, U41'_3, U42'_3, U43'_3} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNATILIST_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 U44'(tt, V1, V2) -> U45'(isNat(V1), V2) 9.45/3.29 U45'(tt, V2) -> ISNATILIST(V2) 9.45/3.29 ISNATILIST(cons(V1, V2)) -> U41'(isNatKind(V1), V1, V2) 9.45/3.29 U41'(tt, V1, V2) -> U42'(isNatKind(V1), V1, V2) 9.45/3.29 U42'(tt, V1, V2) -> U43'(isNatIListKind(V2), V1, V2) 9.45/3.29 U43'(tt, V1, V2) -> U44'(isNatIListKind(V2), V1, V2) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.45/3.29 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.45/3.29 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.45/3.29 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.45/3.29 U45(tt, V2) -> U46(isNatIList(V2)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U71(tt) -> tt 9.45/3.29 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.45/3.29 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.45/3.29 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.45/3.29 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.45/3.29 U85(tt, V2) -> U86(isNatList(V2)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.45/3.29 U92(tt, L, N) -> U93(isNat(N), L, N) 9.45/3.29 U93(tt, L, N) -> U94(isNatKind(N), L) 9.45/3.29 U94(tt, L) -> s(length(L)) 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.45/3.29 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (52) QCSUsableRulesProof (EQUIVALENT) 9.45/3.29 The following rules are not useable [DA_EMMES] and can be deleted: 9.45/3.29 9.45/3.29 zeros -> cons(0, zeros) 9.45/3.29 U41(tt, x0, x1) -> U42(isNatKind(x0), x0, x1) 9.45/3.29 U42(tt, x0, x1) -> U43(isNatIListKind(x1), x0, x1) 9.45/3.29 U43(tt, x0, x1) -> U44(isNatIListKind(x1), x0, x1) 9.45/3.29 U44(tt, x0, x1) -> U45(isNat(x0), x1) 9.45/3.29 U45(tt, x0) -> U46(isNatIList(x0)) 9.45/3.29 U46(tt) -> tt 9.45/3.29 U81(tt, x0, x1) -> U82(isNatKind(x0), x0, x1) 9.45/3.29 U82(tt, x0, x1) -> U83(isNatIListKind(x1), x0, x1) 9.45/3.29 U83(tt, x0, x1) -> U84(isNatIListKind(x1), x0, x1) 9.45/3.29 U84(tt, x0, x1) -> U85(isNat(x0), x1) 9.45/3.29 U85(tt, x0) -> U86(isNatList(x0)) 9.45/3.29 U86(tt) -> tt 9.45/3.29 U91(tt, x0, x1) -> U92(isNatIListKind(x0), x0, x1) 9.45/3.29 U92(tt, x0, x1) -> U93(isNat(x1), x0, x1) 9.45/3.29 U93(tt, x0, x1) -> U94(isNatKind(x1), x0) 9.45/3.29 U94(tt, x0) -> s(length(x0)) 9.45/3.29 isNatIList(cons(x0, x1)) -> U41(isNatKind(x0), x0, x1) 9.45/3.29 isNatList(cons(x0, x1)) -> U81(isNatKind(x0), x0, x1) 9.45/3.29 length(cons(x0, x1)) -> U91(isNatList(x1), x1, x0) 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (53) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {s_1, length_1, U61_1, U71_1, U52_1, U23_1} are replacing on all positions. 9.45/3.29 For all symbols f in {U21_2, cons_2, U51_2, U22_2, U45'_2, U44'_3, U41'_3, U42'_3, U43'_3} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNat_1, isNatKind_1, isNatIListKind_1, ISNATILIST_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 U44'(tt, V1, V2) -> U45'(isNat(V1), V2) 9.45/3.29 U45'(tt, V2) -> ISNATILIST(V2) 9.45/3.29 ISNATILIST(cons(V1, V2)) -> U41'(isNatKind(V1), V1, V2) 9.45/3.29 U41'(tt, V1, V2) -> U42'(isNatKind(V1), V1, V2) 9.45/3.29 U42'(tt, V1, V2) -> U43'(isNatIListKind(V2), V1, V2) 9.45/3.29 U43'(tt, V1, V2) -> U44'(isNatIListKind(V2), V1, V2) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 U71(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (54) QCSDPMuMonotonicPoloProof (EQUIVALENT) 9.45/3.29 By using the following mu-monotonic polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this Q-CSDP problem can be strictly oriented and thus deleted. 9.45/3.29 9.45/3.29 Strictly oriented dependency pairs: 9.45/3.29 9.45/3.29 U45'(tt, V2) -> ISNATILIST(V2) 9.45/3.29 U43'(tt, V1, V2) -> U44'(isNatIListKind(V2), V1, V2) 9.45/3.29 9.45/3.29 9.45/3.29 Used ordering: POLO with Polynomial interpretation [POLO]: 9.45/3.29 9.45/3.29 POL(0) = 0 9.45/3.29 POL(ISNATILIST(x_1)) = 1 + 2*x_1 9.45/3.29 POL(U21(x_1, x_2)) = x_1 9.45/3.29 POL(U22(x_1, x_2)) = x_1 9.45/3.29 POL(U23(x_1)) = x_1 9.45/3.29 POL(U41'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.45/3.29 POL(U42'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.45/3.29 POL(U43'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.45/3.29 POL(U44'(x_1, x_2, x_3)) = x_1 + 2*x_3 9.45/3.29 POL(U45'(x_1, x_2)) = x_1 + 2*x_2 9.45/3.29 POL(U51(x_1, x_2)) = x_1 9.45/3.29 POL(U52(x_1)) = x_1 9.45/3.29 POL(U61(x_1)) = x_1 9.45/3.29 POL(U71(x_1)) = x_1 9.45/3.29 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 9.45/3.29 POL(isNat(x_1)) = 2 9.45/3.29 POL(isNatIListKind(x_1)) = 2 9.45/3.29 POL(isNatKind(x_1)) = 2 9.45/3.29 POL(length(x_1)) = 2 + 2*x_1 9.45/3.29 POL(nil) = 2 9.45/3.29 POL(s(x_1)) = x_1 9.45/3.29 POL(tt) = 2 9.45/3.29 POL(zeros) = 2 9.45/3.29 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (55) 9.45/3.29 Obligation: 9.45/3.29 Q-restricted context-sensitive dependency pair problem: 9.45/3.29 The symbols in {s_1, length_1, U61_1, U71_1, U52_1, U23_1} are replacing on all positions. 9.45/3.29 For all symbols f in {U21_2, cons_2, U51_2, U22_2, U45'_2, U44'_3, U41'_3, U42'_3, U43'_3} we have mu(f) = {1}. 9.45/3.29 The symbols in {isNat_1, isNatKind_1, isNatIListKind_1, ISNATILIST_1} are not replacing on any position. 9.45/3.29 9.45/3.29 The TRS P consists of the following rules: 9.45/3.29 9.45/3.29 U44'(tt, V1, V2) -> U45'(isNat(V1), V2) 9.45/3.29 ISNATILIST(cons(V1, V2)) -> U41'(isNatKind(V1), V1, V2) 9.45/3.29 U41'(tt, V1, V2) -> U42'(isNatKind(V1), V1, V2) 9.45/3.29 U42'(tt, V1, V2) -> U43'(isNatIListKind(V2), V1, V2) 9.45/3.29 9.45/3.29 The TRS R consists of the following rules: 9.45/3.29 9.45/3.29 isNat(0) -> tt 9.45/3.29 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.45/3.29 isNatKind(0) -> tt 9.45/3.29 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.45/3.29 isNatIListKind(nil) -> tt 9.45/3.29 isNatIListKind(zeros) -> tt 9.45/3.29 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.45/3.29 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.45/3.29 U71(tt) -> tt 9.45/3.29 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.45/3.29 U52(tt) -> tt 9.45/3.29 U61(tt) -> tt 9.45/3.29 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.45/3.29 U22(tt, V1) -> U23(isNat(V1)) 9.45/3.29 U23(tt) -> tt 9.45/3.29 9.45/3.29 Q is empty. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (56) QCSDependencyGraphProof (EQUIVALENT) 9.45/3.29 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 4 less nodes. 9.45/3.29 9.45/3.29 ---------------------------------------- 9.45/3.29 9.45/3.29 (57) 9.45/3.29 TRUE 9.55/3.32 EOF