Vicious Circles in Orthogonal Term Rewriting Systems

J. Ketema; J.W. Klop; V. van Oostrom

doi:10.1016/j.entcs.2004.11.020

Vicious Circles in Orthogonal Term Rewriting Systems

J. Ketema, J.W. Klop, V. van Oostrom

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

Abstract

In this paper we first study the difference between Weak Normalization (WN) and Strong Normalization (SN), in the framework of first order orthogonal rewriting systems. With the help of the Erasure Lemma we establish a Pumping Lemma, yielding information about exceptional terms, defined as terms that are WN but not SN. A corollary is that if an orthogonal TRS is WN, there are no cyclic reductions in finite reduction graphs. This is a stepping stone towards the insight that orthogonal TRSs with the property WN, do not admit cyclic reductions at all. © 2005 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	65-77
Journal	Electronic Notes in Theoretical Computer Science
Volume	124
DOIs	https://doi.org/10.1016/j.entcs.2004.11.020
Publication status	Published - 2005

Bibliographical note

DBLP:journals/entcs/KetemaKO05
Proceedings title: Proceedings of the 4th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2004)
Publisher: Elsevier

Access to Document

10.1016/j.entcs.2004.11.020

Persistent URL (handle)

Persistent link

Cite this

@article{036c600cf4ba44a1b3f11b67dc9f9851,

title = "Vicious Circles in Orthogonal Term Rewriting Systems",

abstract = "In this paper we first study the difference between Weak Normalization (WN) and Strong Normalization (SN), in the framework of first order orthogonal rewriting systems. With the help of the Erasure Lemma we establish a Pumping Lemma, yielding information about exceptional terms, defined as terms that are WN but not SN. A corollary is that if an orthogonal TRS is WN, there are no cyclic reductions in finite reduction graphs. This is a stepping stone towards the insight that orthogonal TRSs with the property WN, do not admit cyclic reductions at all. {\textcopyright} 2005 Elsevier B.V. All rights reserved.",

author = "J. Ketema and J.W. Klop and {van Oostrom}, V.",

note = "DBLP:journals/entcs/KetemaKO05 Proceedings title: Proceedings of the 4th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2004) Publisher: Elsevier",

year = "2005",

doi = "10.1016/j.entcs.2004.11.020",

language = "English",

volume = "124",

pages = "65--77",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Vicious Circles in Orthogonal Term Rewriting Systems

AU - Ketema, J.

AU - Klop, J.W.

AU - van Oostrom, V.

N1 - DBLP:journals/entcs/KetemaKO05 Proceedings title: Proceedings of the 4th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2004) Publisher: Elsevier

PY - 2005

Y1 - 2005

N2 - In this paper we first study the difference between Weak Normalization (WN) and Strong Normalization (SN), in the framework of first order orthogonal rewriting systems. With the help of the Erasure Lemma we establish a Pumping Lemma, yielding information about exceptional terms, defined as terms that are WN but not SN. A corollary is that if an orthogonal TRS is WN, there are no cyclic reductions in finite reduction graphs. This is a stepping stone towards the insight that orthogonal TRSs with the property WN, do not admit cyclic reductions at all. © 2005 Elsevier B.V. All rights reserved.

AB - In this paper we first study the difference between Weak Normalization (WN) and Strong Normalization (SN), in the framework of first order orthogonal rewriting systems. With the help of the Erasure Lemma we establish a Pumping Lemma, yielding information about exceptional terms, defined as terms that are WN but not SN. A corollary is that if an orthogonal TRS is WN, there are no cyclic reductions in finite reduction graphs. This is a stepping stone towards the insight that orthogonal TRSs with the property WN, do not admit cyclic reductions at all. © 2005 Elsevier B.V. All rights reserved.

U2 - 10.1016/j.entcs.2004.11.020

DO - 10.1016/j.entcs.2004.11.020

M3 - Article

SN - 1571-0661

VL - 124

SP - 65

EP - 77

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

ER -

Vicious Circles in Orthogonal Term Rewriting Systems

Abstract

Bibliographical note

Access to Document

Persistent URL (handle)

Fingerprint

Cite this