\title{A note on M{\'e}tivier's construction of asynchronous automata for
  triangulated graphs} 

\author{Volker~Diekert \qquad Anca~Muscholl\\
        {\small Universit\"at Stuttgart} \\[-.8ex]
        {\small Institut f\"ur Informatik} \\[-.8ex]
        {\small Breitwiesenstr.~20-22} \\[-.8ex]
        {\small D-70565 Stuttgart}
}
In the special case of acyclic dependence graphs Y.~M{\'e}tivier
exhibited a surprisingly elegant solution \cite{met87}, providing in
a natural way deterministic asynchronous automata for recognizable
languages.  The drawback is the fact that acyclicity is a strong
restriction on concurrency alphabets. In fact, even the special case of
complete dependence, i.e.\ the free monoid, is not included. We show here
that for a larger class of graphs --the {\em triangulated} graphs--
the main idea of M{\'e}tivier's construction still applies. We are
thus able to generalize this simple construction to triangulated graphs. From
a practical point of view, this means that by adding sufficient
dependence, i.e.\ triangulating in a dependence alphabet, we can
obtain simple deterministic asynchronous automata for every recognizable trace
languages, by loosing some concurrency, only.