Asynchronous automata versus asynchronous cellular automata (Q1334661)

The investigations of \textit{A. Mazurkiewicz} [Concurrent program schemes and their interpretations, DAIMI-PB-78, Aarhus University (1977)] and \textit{W. Zielonka} [RAIRO Inf. Theor. Appl. 21, 99-135 (1987; Zbl 0623.68055); Lect. Notes Comput. Sci. 38, 278-289 (1989; Zbl 0678.68077)] are continued. It is proved that an asynchronous cellular automaton can be constructed (in polynomial time) accepting the same trace language as a given asynchronous automaton. (The converse construction is obvious.) The question of unicity of minimum asynchronous automata and/or asynchronous cellular automata recognizing a given trace language is studied; both positive and negative results are obtained in this field, depending on which version of the problem is considered. To any (finite or infinite) string \(\gamma\) over \(\{0, 1\}\) an asynchronous automaton \({\mathcal A}\) is associated, the minimality of \({\mathcal A}\) is shown to be equivalent to the non-periodicity (in another terminology, primitivity) of \(\gamma\). It follows from the results that the class of concurrent alphabets for which every recognizable trace language admits a minimum finite state asynchronous automaton becomes narrower when ``asynchronous automaton'' is replaced by ``asynchronous cellular automaton''.