Trace languages and the variety DA
Manfred Kufleitner
LaBRI, Univ Bordeaux I, France.
08-03-07

---

Abstract

Traces have been introduced by Mazurkiewicz in 1977 as a generalization of words to describe the behavior of concurrent processes. A lot of characterizations for the class of recognizable trace languages and for the class of star-free trace languages are known. These include for example algebraic properties, specialized automata models and logical fragments. For more restricted classes of recognizable trace languages very little research has been done.

A result from the early 90s is that a trace-language is star-free if and only if its syntactic monoid is aperiodic. An important subclass of aperiodic monoids is the variety DA. Over words, many characterizations have been found for languages whose syntactic monoid is in DA. We show which of them also hold for traces and which of them do not hold. For logical fragments, a crucial property is whether one can express concurrency or not.