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. PighizziniSecondo
;
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.