Mazurkiewicz trace are a model for concurrency. They can be seen as a generalization of words by introducing partial commutation between specific letters. Several logical and language-theoretic characterizations of the variety of monoids DA are known for words. We show which of them also hold for traces and which of them do not hold.
An important tool for this task are Ehrenfeucht-Fraisse games. For several logical fragments, we introduce characterizations in terms of these games. They are used to separate logical fragments over traces that have the same expressive power over words. An essential property is, whether one can express concurrency within a fragment or not.
