Asynchronous Automata versus Asynchronous
Cellular Automata
Giovanni Pighizzini
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
Abstract
In this paper we compare and we 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.