note the change of room

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Dec. 17, 2014, 2:15 p.m.

Room

room 5050

Title in Polish

Monads rulez

Seminar

Seminar Automata Theory

---

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.

---