@Article{Intrigila_etal2001,
author="Intrigila, Benedetto
and Salvo, Ivano
and Sorgi, Stefano",
title="A characterization of weakly Church-Rosser abstract reduction systems that are not Church-Rosser",
journal="Information and Computation",
year="2001",
publisher="Academic Press, Inc.",
address="Duluth, MN, USA",
volume="171",
number="2",
pages="137--155",
abstract="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{\~A}{\textcent}{\^a}‚{\textlnot}{\^a}„{\textcent}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.",
optnote="exported from refbase (http://mclab.di.uniroma1.it/publications/show.php?record=68), last updated on Thu, 22 Nov 2012 14:59:18 +0100",
issn="0890-5401",
doi="10.1006/inco.2001.2945",
opturl="https://doi.org/10.1006/inco.2001.2945",
file=":http://mclab.di.uniroma1.it/publications/papers/papers/Intrigila2001.pdf:PDF"
}