Deterministic asynchronous automata for infinite traces (Q1338892)

Infinite traces form a suitable framework for describing non-terminating concurrent systems. Especially interesting are systems which may be observed using finite state devices. From the automata-theoretic viewpoint we are interested in automata with distributed control, more precisely in asynchronous cellular automata. The main result of the present paper provides a positive answer to the main open question in this field and extends McNaughton's Theorem from \(\omega\)-word languages to recognizable real trace languages. Concretely, we show the equivalence between the family of recognizable real trace languages and the family of real trace languages which can be accepted by deterministic asynchronous cellular Muller automata. As a special case we obtain that every closed (w.r.t. the independence relation \(I)\) \(\omega\)-word language is accepted by some \(I\)-diamond deterministic Muller automaton.