Machines, Models, Monoids, and Modal logic

A recent theme in my research has been to apply model theory to
theoretical computer science, in particular to the study of regular
languages and their logics. In this talk I will present two results
falling under this common theme.

First, in joint work with Silvio Ghilardi, we show that the well-known
translation of monadic second order logic into automata and back can be
seen as an instance of the notion of 'model companion' from model
theory. The appropriate setting to make this claim precise is provided
by temporal modal logics: a variant of Linear Temporal Logic in the case
of machines that act on strings, and a variant of Computation Tree Logic
in the case of machines that act on trees.

Second, in joint work with Ben Steinberg, we analyze the free
pro-aperiodic monoid as a monoid of elementary equivalence classes of
certain first-order structures. We identify the notion of 'saturated
model' from model theory as a crucial tool. Combining this analysis with
algebraic-topological results, based on Stone duality theory for the
structures involved, we obtain both new proofs of existing results and
new results in the structure theory of pro-aperiodic monoids.


References
S. Ghilardi and S. J. v. Gool, Monadic second order logic as the model
companion of temporal logic, LICS 2016, preprint at
https://arxiv.org/abs/1605.01003

S. J. v. Gool and B. Steinberg, Pro-aperiodic monoids via saturated
models, STACS 2017, technical report at https://arxiv.org/abs/1609.07736