\title{Deterministic asynchronous automata for infinite traces}

\institute{Universit\"at Stuttgart\\
Institut f\"ur Informatik\\
Breitwiesenstr.~20-22\\
D-70565 Stuttgart}

\author{Volker~Diekert \qquad  Anca~Muscholl}


\begin{abstract} 
This paper shows the equivalence between the family
of recognizable languages over infinite traces and the family of
languages accepted by deterministic asynchronous cellular Muller
automata.  We thus give a proper generalization of McNaughton's
Theorem from infinite words to infinite traces, thus solving one
of the main open problems in this field.  As a special case we obtain
that every closed (w.r.t.~the independence relation) word language is
accepted by some $I$-diamond deterministic Muller automaton.
\end{abstract}