Counterexamples in Infinitary Rewriting with Non-Fully-Extended Rules

J. Ketema

doi:10.1016/j.ipl.2011.04.001

Counterexamples in Infinitary Rewriting with Non-Fully-Extended Rules

J. Ketema

Research output: Contribution to journal › Article › Academic › peer-review

7 Downloads (Pure)

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 language	Undefined
Pages (from-to)	642-646
Number of pages	5
Journal	Information processing letters
Volume	111
Issue number	13
DOIs	https://doi.org/10.1016/j.ipl.2011.04.001
Publication status	Published - 1 Jul 2011

Keywords

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

Access to Document

10.1016/j.ipl.2011.04.001

http://eprints.eemcs.utwente.nl/secure2/20011/01/fully.pdf

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 = jul,

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 B.V.",

number = "13",

}

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

SN - 0020-0190

VL - 111

SP - 642

EP - 646

JO - Information processing letters

JF - Information processing letters

IS - 13

ER -