Stone Duality and the Substitution Principle.

Room FC1 004, DMat-FCUP at 14:30
Friday, 5 May, 2017 (All day)

Finite and profinite monoids have proved to be a powerful tool in the study of regular languages. In particular, understanding the interplay between the topological and algebraic structures of these objects has been crucial. However, many of the classes of languages that are of interest to study are not regular, and so, those theories no longer apply. Boolean spaces with biactions of monoids were recently proposed as suitable objects to handle classes of (not necessarily regular) languages. In this talk, we will start by identifying these topo-algebraic recognizers as projective limits of recognizers for finite Boolean algebras, and then use them in the study of first-order fragments of logic through the so-called substitution principle.

Roughly speaking, substitution provides a method for decomposing complex formulas into simpler ones. When the fragment of logic considered defines only regular languages, it is well-known that such decomposition is modeled by the usual block product of finite monoids.

We consider a notion of block product that generalizes the usual one from a logic perspective. More precisely, we study the effect of applying one layer of quantifiers to a formula with free-variables in terms of recognition---this leads to the mentioned block product.

(This is joint work with Silke Czarnetzki, Mai Gehrke, and Andreas Krebs.)


Célia Borlido


IRIF, CNRS, Université Paris Diderot

PDF File: