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 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.