Coding with traces

We prove that the existence of a coding between two trace monoids is decidable for some families of trace monoids. Decidability heavily depends on the structure of the dependence graphs. The concept of coding is based on the new notion of strong morphism between trace monoids.

On aperiodic trace languages

Star-free trace languages

Abstract Generalizing a classical result of Schutzenberger to free partially commutative monoids, we prove that the family of star-free trace languages coincides with the family of aperiodic trace languages.