Paris Automata and Concurrency Theory Seminar

Venue: LIX, École polytechnique

Speaker 1: (present) Gaspard Reghem

Title: Compositional Reasoning About Randomized Distributed Protocols

► Abstract:

TBA

Speaker 2: (online) Fabian Lenke

Title: Algebraic Language Theory with Effects

► Abstract:

Regular languages -- the languages accepted by deterministic finite automata -- are known to be precisely the languages recognized by finite monoids. This characterization is the origin of algebraic language theory. We show how to generalize the correspondence between automata and monoids to automata with generic computational effects given by a monad, providing the foundations of an effectful algebraic language theory. We will se how, under suitable conditions on the monad, a language is computable by an effectful automaton precisely when it is recognizable by (1) an effectful monoid morphism into an effect-free finite monoid, and (2) a monoid morphism into a finitely based monad-monoid bialgebra. As a prime application, we introduce an algebraic approach to languages computed by probabilistic finite automata. Furthermore, we will derive algebraic characterizations for languages accepted by nondeterministic probabilistic finite automata, and weighted finite automata over unrestricted semirings; the latter generalize previous results on weighted algebraic recognition over commutative rings.