Asynchronous automata versus asynchronous cellular automata

AbstractIn this paper we compare and study some properties of two mathematical models of concurrent systems, asynchronous automata (Zielonka, 1987) and asynchronous cellular automata (Zielonka, 1989). First, we show that these models are “polynomially” related, exhibiting polynomial-time reductions between them. Subsequently, we prove that, in spite of that, the classes of asynchronous automata and of asynchronous cellular automata recognizing a given trace language are, in general, deeply different. In fact, we exhibit a recognizable trace language T with the following properties: there exists a unique minimum asynchronous automaton accepting T, does not exist a unique minimum asynchronous cellular automaton, but there are infinitely many minimal (i.e., unreducible) nonisomorphic asynchronous cellular automata accepting T. We characterize the class of concurrent alphabets for which every recognizable trace language admits a minimum finite state asynchronous cellular automaton as the class of alphabets with full concurrency relation. Finally, extending a result of (Bruschi et al., 1988), we show that for every concurrent alphabet with nontransitive dependency relation, there exists a trace language accepted by infinitely many minimal nonisomorphic asynchronous automata