Logic Seminar

Christopher Hawthorne, Department of Pure Mathematics, University of Waterloo

“Model theory and formal languages”

A language is a set of strings over a fixed, finite alphabet. In the study of formal languages, one considers natural classes of languages (typically defined by some model of computation) and studies properties of these classes. In this talk, I will outline my attempts to analyze formal languages using model theory; to do this, we will view languages as subsets of finitely generated free monoids, and consider the model theory of the latter.

We will first see some basic model-theoretic properties of free monoids and their complete theories. We will then consider the computational power of definable and quantifier-free definable sets in one variable: we will see that the quantifier-free definable sets fit nicely into the complexity hierarchy of formal languages, and we will conjecture that the definable sets do not. Finally, we will consider regular languages, a class of great theoretical and practical interest; we will characterize regularity of a language by properties of the type space of an associated structure.

No knowledge of formal languages will be assumed.

MC 5403