#
Lois distributives. Applications aux automates stochastiques

##
Elisabeth Burroni

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

TAC Home