In 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.

ASYNCHRONOUS AUTOMATA VERSUS ASYNCHRONOUS CELLULAR-AUTOMATA / G. PIGHIZZINI. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 132:1-2(1994), pp. 179-207.

ASYNCHRONOUS AUTOMATA VERSUS ASYNCHRONOUS CELLULAR-AUTOMATA

G. PIGHIZZINI
Primo
1994

Abstract

In 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.
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/179484
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 9
social impact