Probabilistic Asynchronous Automata
Sofia Jesi, Giovanni Pighizzini, and Nicoletta Sabadini
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
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 non trivial generalization to
Zielonka's Theorem: we prove that the set of behaviors of
probabilistic automata and of
probabilistic asynchronous automata coincide in the case of
concurrent alphabets with acyclic dependency graph.