×

Distributive laws. Applications to stochastic automata. (Lois distributives. Applications aux automates stochastiques.) (French. English summary) Zbl 1166.18301

Summary: 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\).

MSC:

18C15 Monads (= standard construction, triple or triad), algebras for monads, homology and derived functors for monads
18C20 Eilenberg-Moore and Kleisli constructions for monads
60G05 Foundations of stochastic processes
60G07 General theory of stochastic processes
18B20 Categories of machines, automata
PDFBibTeX XMLCite
Full Text: EuDML EMIS