Counterexamples in Infinitary Rewriting with Non-Fully-Extended Rules

J. Ketema

    Research output: Contribution to journalArticleAcademicpeer-review

    Abstract

    We show counterexamples exist to confluence modulo hypercollapsing subterms, fair normalisation, and the normal form property in orthogonal infinitary higher-order rewriting with non-fully-extended rules. This sets these systems apart from both fully-extended and finite systems, where no such counterexamples are possible.
    Original languageUndefined
    Pages (from-to)642-646
    Number of pages5
    JournalInformation processing letters
    Volume111
    Issue number13
    DOIs
    Publication statusPublished - 1 Jul 2011

    Keywords

    • Programming calculi
    • EWI-20011
    • Higher-order rewriting
    • IR-76651
    • Infinitary Rewriting
    • METIS-277606

    Cite this

    @article{365d9023e1ea4ed1a27ed64d9ccd019e,
    title = "Counterexamples in Infinitary Rewriting with Non-Fully-Extended Rules",
    abstract = "We show counterexamples exist to confluence modulo hypercollapsing subterms, fair normalisation, and the normal form property in orthogonal infinitary higher-order rewriting with non-fully-extended rules. This sets these systems apart from both fully-extended and finite systems, where no such counterexamples are possible.",
    keywords = "Programming calculi, EWI-20011, Higher-order rewriting, IR-76651, Infinitary Rewriting, METIS-277606",
    author = "J. Ketema",
    note = "eemcs-eprint-20011",
    year = "2011",
    month = "7",
    day = "1",
    doi = "10.1016/j.ipl.2011.04.001",
    language = "Undefined",
    volume = "111",
    pages = "642--646",
    journal = "Information processing letters",
    issn = "0020-0190",
    publisher = "Elsevier",
    number = "13",

    }

    Counterexamples in Infinitary Rewriting with Non-Fully-Extended Rules. / Ketema, J.

    In: Information processing letters, Vol. 111, No. 13, 01.07.2011, p. 642-646.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Counterexamples in Infinitary Rewriting with Non-Fully-Extended Rules

    AU - Ketema, J.

    N1 - eemcs-eprint-20011

    PY - 2011/7/1

    Y1 - 2011/7/1

    N2 - We show counterexamples exist to confluence modulo hypercollapsing subterms, fair normalisation, and the normal form property in orthogonal infinitary higher-order rewriting with non-fully-extended rules. This sets these systems apart from both fully-extended and finite systems, where no such counterexamples are possible.

    AB - We show counterexamples exist to confluence modulo hypercollapsing subterms, fair normalisation, and the normal form property in orthogonal infinitary higher-order rewriting with non-fully-extended rules. This sets these systems apart from both fully-extended and finite systems, where no such counterexamples are possible.

    KW - Programming calculi

    KW - EWI-20011

    KW - Higher-order rewriting

    KW - IR-76651

    KW - Infinitary Rewriting

    KW - METIS-277606

    U2 - 10.1016/j.ipl.2011.04.001

    DO - 10.1016/j.ipl.2011.04.001

    M3 - Article

    VL - 111

    SP - 642

    EP - 646

    JO - Information processing letters

    JF - Information processing letters

    SN - 0020-0190

    IS - 13

    ER -