A confluent rewriting system having no computable, one-step, normalizing strategy

Jakob Grue Simonsen

doi:10.1145/2699917

A confluent rewriting system having no computable, one-step, normalizing strategy

Department of Computer Science

Abstract

A full and finitely generated Church-Rosser term rewriting system is presented that has no computable onestep, normalizing strategy; the system is both left- and right-linear. The result provides a negative answer to a question posed by Kennaway in 1989: Number 10 on the List of Open Problems in Rewriting.

Original language	English
Article number	10
Journal	ACM Transactions on Computational Logic
Volume	16
Issue number	2
Number of pages	9
ISSN	1529-3785
DOIs	https://doi.org/10.1145/2699917
Publication status	Published - 1 Feb 2015

Access to Document

10.1145/2699917

Cite this

@article{7e30687c3b5a4c0c9cd2a11524092ade,

title = "A confluent rewriting system having no computable, one-step, normalizing strategy",

abstract = "A full and finitely generated Church-Rosser term rewriting system is presented that has no computable onestep, normalizing strategy; the system is both left- and right-linear. The result provides a negative answer to a question posed by Kennaway in 1989: Number 10 on the List of Open Problems in Rewriting.",

author = "Simonsen, {Jakob Grue}",

year = "2015",

month = feb,

day = "1",

doi = "10.1145/2699917",

language = "English",

volume = "16",

journal = "ACM Transactions on Computational Logic",

issn = "1529-3785",

publisher = "Association for Computing Machinery, Inc.",

number = "2",

}

TY - JOUR

T1 - A confluent rewriting system having no computable, one-step, normalizing strategy

AU - Simonsen, Jakob Grue

PY - 2015/2/1

Y1 - 2015/2/1

N2 - A full and finitely generated Church-Rosser term rewriting system is presented that has no computable onestep, normalizing strategy; the system is both left- and right-linear. The result provides a negative answer to a question posed by Kennaway in 1989: Number 10 on the List of Open Problems in Rewriting.

AB - A full and finitely generated Church-Rosser term rewriting system is presented that has no computable onestep, normalizing strategy; the system is both left- and right-linear. The result provides a negative answer to a question posed by Kennaway in 1989: Number 10 on the List of Open Problems in Rewriting.

U2 - 10.1145/2699917

DO - 10.1145/2699917

M3 - Journal article

SN - 1529-3785

VL - 16

JO - ACM Transactions on Computational Logic

JF - ACM Transactions on Computational Logic

IS - 2

M1 - 10

ER -

A confluent rewriting system having no computable, one-step, normalizing strategy

Abstract

Access to Document

Fingerprint

Cite this