Colloquium | March 22 | 4-5 p.m. | 60 Evans Hall
Sam van Gool, Utrecht University
This talk is about joint work with Benjamin Steinberg, in which we apply model theory to study algebraic structures occurring in the theory of regular languages.
Regular languages can both be understood as monadic-second-order-definable classes of finite colored linear orders, and as subsets of the free monoid which induce a certain finite-index congruence, called the syntactic congruence. Definability in fragments of monadic second order logic then corresponds to the finite monoid quotient by the syntactic congruence having special properties. As the first and most famous instance of this correspondence theory, essentially due to Schützenberger, the class of languages definable in first-order logic coincides with the class of languages recognizable by an aperiodic (“subgroup-free”) monoid.
In this setting, questions about definability in logic thus lead to challenges that can often be resolved by studying finite monoids. Within this “finite algebra” approach to regular languages, free profinite objects are a useful tool, as they provide the appropriate notion of “equation”. In particular, the free pro-aperiodic monoid is a crucial algebraic object for studying the class of first-order definable languages.
The starting point of our work is the observation that Stone duality and Schützenberger’s Theorem together imply that elements of the free pro-aperiodic monoid may be viewed as elementary equivalence classes of pseudofinite words. Concretely, this means that one may 'compute' with elements of the free pro-aperiodic monoid as if they were finite words, in a way reminiscent of the methods of non-standard analysis. In particular, model theory provides us with saturated words in each class of pseudofinite words, i.e., words in which all possible factorizations are realized. We prove that such saturated words are stable under algebraic operations, and we give several applications of our new model-theoretic approach to pro-aperiodic monoids, including a solution to the word problem for $\omega$-terms that avoids using McCammond’s normal forms, as well as new proofs and extensions of other structural results concerning pro-aperiodic monoids.
Reference: S. J. v. Gool and B. Steinberg, Pro-aperiodic monoids via saturated models, Israel J. Math., accepted (2019). Preprint: https://arxiv.org/abs/1609.07736