Stone duality, logic on words, and profinite monoids

Berkeley-Stanford Circle in Logic and Philosophy, 12 November 2016.

In this interactive tutorial, I will show how Stone duality, when combined with techniques from model theory, can be a powerful tool for studying profinite monoids and logic on words. This recent perspective on profinite monoids also sheds new light on easy-to-state but hard-to-solve problems in theoretical computer science around the definability and decidability for regular languages.

After a short prelude where we will state some of these problems in the field of logic on words, the tutorial will naturally fall into three parts:

(1) what is Stone duality?

(2) how to use Stone duality to understand what profinite monoids and regular languages are?

(3) how to combine model theory with Stone duality to study profinite monoids?

Finally, we will come back to the problems in logic on words from the prelude, and see what we can learn about them from the theory.

Along the way, there will be plenty of opportunities for questions, exercises, (partial) solutions, and other discussion.

Finally, some references. They are intended as good reading material for getting an idea what this research area is all about. As preparation for the tutorial, it will be useful to have read [1] and the 9 pages in [2] that I mention below. If you can/want, also have a look at the introductions of [3] and [4].

[1] M. Gehrke, Duality, inaugural lecture, 2009.
An excellent gentle introduction to duality theory, written for a general audience, by my former adviser Mai Gehrke (CNRS/Paris 7).

[2] S. J. v. Gool, On sheaves and duality, PhD thesis, 2014.
For my own take on Stone duality (or what it was two years ago anyway), read p. 7-9 (less technical) and p. 15-20 (more technical).

[3] M. Gehrke, Stone duality, topological algebra, and recognition, Journal of Pure and Applied Algebra, Volume 220, Issue 7, July 2016, Pages 27112747.
The introduction gives an overview of the application of Stone duality in formal language theory and profinite algebra.

[4] S. J. v. Gool and B. Steinberg, Pro-aperiodic monoids via saturated models, submitted, 2016.
My recent preprint with Ben Steinberg (City College New York) on using model theory for studying pro-aperiodic monoids and logic on words. The introduction explains the gist of the idea without going into technicalities.