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.