Fall 2016

Operations on Languages and Codensity Monads

Monday, November 7th, 2016 3:00 pm3:30 pm

Add to Calendar

Given some operation on languages, a natural question to ask is what is the corresponding operation at the level of recognisers. For example, the concatenation of two languages  recognized by  monoids M and N, respectively, is recognized by the Schutzenberger product of M and N.

In a recent paper with Mai Gehrke and Luca Reggio, "The Schutzenberger product for syntactic spaces" we introduce a notion of recognition based on Stone spaces with internal monoids, which extends the usual notion for regular languages, but is finer-grained in the non-regular setting.

The focus of that paper is the development of duality based constructions pertinent to the treatment of languages given by logic formulas. We introduce a notion of Schützenberger product for Stone spaces with internal monoids using the  Vietoris construction and we show that the unary Schützenberger product for spaces yields a recogniser for the language of all models of the formula ∃x.Φ(x), when applied to a recogniser for the language of all models of Φ(x).

In this talk, I will also present a framework for dealing with other operations on languages, for example, we can treat languages defined with modular counting quantifiers. This generalises some ideas from our ICALP paper, where one crucial technical ingredient relies on the fact that the  Vietoris monad can be seen as  a codensity monad.