Asynchronous automata were introduced by W. Zielonka as an algebraic model of distributed systems, showing that the class of trace languages recognizable by automata over free partially commutative monoids coincides with the class of trace languages recognizable by deterministic asynchronous automata. In this paper we extend the notion of asynchronous automata to the probabilistic case. Our main result is a nontrivial generalization to Zielonka's theorem: we prove that the sets of behaviors of probabilistic automata and of probabilistic asynchronous automata coincide in the case of concurrent alphabets with acyclic dependency graphs.

Probabilistic asynchronous automata / S. Jesi, G. Pighizzini, N. Sabadini. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 29:1(1996), pp. 5-31.

Probabilistic asynchronous automata

G. Pighizzini
Secondo
;
1996

Abstract

Asynchronous automata were introduced by W. Zielonka as an algebraic model of distributed systems, showing that the class of trace languages recognizable by automata over free partially commutative monoids coincides with the class of trace languages recognizable by deterministic asynchronous automata. In this paper we extend the notion of asynchronous automata to the probabilistic case. Our main result is a nontrivial generalization to Zielonka's theorem: we prove that the sets of behaviors of probabilistic automata and of probabilistic asynchronous automata coincide in the case of concurrent alphabets with acyclic dependency graphs.
Settore INF/01 - Informatica
1996
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I metadati presenti in AIR sono rilasciati con licenza CCO mentre i file delle pubblicazioni sono rilasciati con licenza CC BY-SA, salvo diversa indicazione. In caso di violazione di copyright, contattare l'assistenza di AIR

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/178700
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 5
  • OpenAlex ND
social impact