Stefano SORGI
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 $\Rightarrow$ 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 which are 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 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.
BIBTEX.
@article{Intrigila-Salvo-Sorgi:00,
author = {B. Intrigila and I. Salvo and S. Sorgi},
title = {A Characterization of Weakly Church-Rosser, not Church-Rosser
Abstract Reduction Systems},
year = {To Appear},
journal = {Information and Computation}
publisher = {Springer},
pages = { },
series = {LNCS},
}