Mikołaj Bojańczyk

Recognisable Languages over Monads


April 9, 2015
  1. Mikołaj Bojańczyk
    Recognisable languages over monads. CoRR, 2015   PDF

There are regular languages for: finite words, finite trees, infinite words, various kinds of infinite trees, queries, tuples of words, tuples of trees, etc etc. This paper shows that monads, a concept from category theory, can be used to unify some of the theory of “regularity”. The idea is that for each setting, like finite words or labelled countable total orders, or infinite trees with countably many branches, one chooses a monad, and then many definitions and some theorems come out for free. Here are some slides.

 

Leave a Reply

Your email address will not be published.