Weak Codings of Trace Monoids
by
Michal Kunc
Masaryk University, Brno, Czech Republic

Let X be a finite alphabet and let I be a symmetric irreflexive binary relation on X. Let \rho be the congruence on X ^* generated by the relation {(ab, ba) | aIb}. The monoid X ^* /\rho is denoted M(X, I) and called a free partially commutative monoid or a trace monoid. The relation I can be extended to M(X, I) in the following way: for u, v in X ^* : (u\rho, v\rho) in [`I] if and only if (a, b) in I for all a in c(u), b in c(v), where c(u) is the set of all letters from X occurring in u.

In 1988 Ochma\' nski proposed the problem of finding an algorithm which decides for given two monoids M=M(X, I) and M'=M(X', I') whether there exists an injective morphism (a coding) f from M to M'. This problem is known as a trace coding problem. Mazurkiewicz (1977) observed that trace monoids can be used as a model for concurrent systems. In this view we can reformulate the above question in the following way: Is the problem whether one concurrent system can simulate the other decidable? In general this is still open. It was completely solved only in the case of so called strong morphisms defined by the condition for all (a, b) in I: (f(a), f(b)) in [`(I')] by Diekert et al. in 1995. Actually they proved that deciding the existence of a strong coding is NP-complete.

We introduce a notion of a weak morphism defined by for all (a, b) in I \cup id_X : (f(a), f(b)) in [`(I' \cup id_X')]. We discuss the existence of a weak coding between trace monoids, the problem of deciding whether a given weak morphism is a coding and connections between weak and standard trace codings.

Date received: May 15, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caec-32.