Deterministic automata are algebras of the monad $T_M$ associated to a free monoid $M$. To extend to nondeterministic and stochastic automata such a monadic formalism, it is suitable to resort to a notion richer than the one of monad, but equally basic: the notion of distributive law between two monads. The notion of algebra on a monad is then generalized by the one of algebra for a distributive law. The nondeterministic and stochastic automata are precisely algebras for distributive laws whose first monad is $T_M$. If the nondeterministic case involves a distributive law between $T_M$ and the well-known power set monad, the stochastic case involves a distributive law between $T_M$ (where, here, $M$ is a measurable monoid) and the probability monad. This allows presentation of the stochastic automata as algebras for this distributive law. This paper taking place at the confluence of category, automata and probability theories, we have, for the convenience of the reader not aware of each area, made useful reviews about these subjects (in several appendices). We also recall the detailed construction of the probability monad; and we construct precisely the distributive law which links it to the monad $T_M$.
Keywords: category, monad, distributive law, probability. stochastic automata
2000 MSC: 18-02, 18C15, 18C20, 60G05, 60G07
Theory and Applications of Categories,
Vol. 22, 2009,
No. 7, pp 199-221.
http://www.tac.mta.ca/tac/volumes/22/7/22-07.dvi
http://www.tac.mta.ca/tac/volumes/22/7/22-07.ps
http://www.tac.mta.ca/tac/volumes/22/7/22-07.pdf
ftp://ftp.tac.mta.ca/pub/tac/html/volumes/22/7/22-07.dvi
ftp://ftp.tac.mta.ca/pub/tac/html/volumes/22/7/22-07.ps