Monads rulez

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

17 grudnia 2014 14:15

Pokój

p. 5050

Tytuł w języku angielskim

note the change of room

Seminarium

Seminarium „Teoria automatów”

---

The algebraic approach to regular languages is to use monoids instead of automata. The algebraic approach has been extended to other settings, such as infinite words, countable total orders, and various kinds of trees. I will show that all of these settings are special cases of  monads, a notion from category theory (also known from programming languages like Haskell). On the general level of monads one can prove several theorems, such as the Myhill-Nerode theorem on the existence of syntactic algebras, or the Eilenberg theorem on the equivalence of pseudovarieties of languages and algebras. One can even prove some of the (less combinatorial) parts of the correspondence between mso and regular languages. Finally, the notion of profinite object can also be defined on the abstract level of monads, yielding some new insights into profiniteness.

---