Séminaire Lotharingien de Combinatoire, B22c (1989).
[Formerly: Publ. I.R.M.A. Strasbourg, 1990, 414/S-22, p.
37-50.]
Volker Diekert
Combinatorial Rewriting on Traces
Abstract.
There are two main problems in working with replacement systems over free partially commutative monoids: For finite Noetherian
systems confluence is undecidable, in general, and the known algorithms to compute irreducible normal forms need time square in the derivation
length instead of linear. We first give a decidable and sufficient condition on finite Noetherian systems for confluence to be decidable. This
condition is weaker than the ones known previously. Then we give a decidable and sufficient condition for irreducible normal forms to be
computable in time linear in the derivation length. Furthermore, we prove that the first condition is implied by the second. We also present a new
uniform algorithm for computing normal forms using Zielonka's theory of asynchronous automata.
The following version is available:
The paper has been finally published under the same title in
STACS 90 (Rouen, 1990), pp. 138--151,
Lecture Notes in Comput. Sci., 415,
Springer, Berlin, 1990.