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