Asynchronous Automata versus Asynchronous Cellular Automata

<TITLE>Asynchronous Automata versus Asynchronous 
Cellular Automata
</TITLE>

<H2 ALIGN="CENTER">Asynchronous Automata versus Asynchronous 
Cellular Automata</H2>

<H4 ALIGN="CENTER">Giovanni Pighizzini</H4>

<H6 ALIGN="CENTER">Dipartimento di  Scienze dell'Informazione<BR>
Universit&agrave; degli Studi di Milano</H6>

<H5 ALIGN="CENTER">Abstract</H5>

In this paper we compare and we study some properties of two mathematical
models of concurrent systems, 
<I>asynchronous automata</I> (Zielonka, 1987) and <I>asynchronous cellular 
automata</I> (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.