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

Datalogisk Institut

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.

Originalsprog	Engelsk
Artikelnummer	10
Tidsskrift	ACM Transactions on Computational Logic
Vol/bind	16
Udgave nummer	2
Antal sider	9
ISSN	1529-3785
DOI	https://doi.org/10.1145/2699917
Status	Udgivet - 1 feb. 2015

Adgang til dokumentet

10.1145/2699917

Citationsformater

@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

Adgang til dokumentet

Fingeraftryk

Citationsformater