TY  - JOUR
AU  - Intrigila, Benedetto
AU  - Salvo, Ivano
AU  - Sorgi, Stefano
PY  - 2001
DA  - 2001//
TI  - A characterization of weakly Church-Rosser abstract reduction systems that are not Church-Rosser
JO  - Information and Computation
SP  - 137
EP  - 155
VL  - 171
IS  - 2
PB  - Academic Press, Inc.
CY  - Duluth, MN, USA
AB  - Basic properties of rewriting systems can be stated in the framework of abstract reduction systems (ARS). Properties like confluence (or Church-Rosser, CR) and weak confluence (or weak Church-Rosser, WCR) and their relationships can be studied in this setting: as a matter of fact, well-known counterexamples to the implication WCR CR have been formulated as ARS. In this paper, starting from the observation that such counterexamples are structurally similar, we set out a graph-theoretic characterization of WCR ARS that is not CR in terms of a suitable class of reduction graphs, such that in every WCR not CR ARS, we can embed at least one element of this class. Moreover, we give a tighter characterization for a restricted class of ARS enjoying a suitable regularity condition. Finally, as a consequence of our approach, we prove some interesting results about ARS using the mathematical tools developed. In particular, we prove an extension of the Newman’s lemma and we find out conditions that, once assumed together with WCR property, ensure the unique normal form property. The Appendix treats two interesting examples, both generated by graph-rewriting rules, with specific combinatorial properties.
SN  - 0890-5401
L1  - http://mclab.di.uniroma1.it/publications/papers/papers/Intrigila2001.pdf
UR  - https://doi.org/10.1006/inco.2001.2945
DO  - 10.1006/inco.2001.2945
N1  - exported from refbase (http://mclab.di.uniroma1.it/publications/show.php?record=68), last updated on Thu, 22 Nov 2012 14:59:18 +0100
ID  - Intrigila_etal2001
ER  -