Logic on words
Time and place
1:45 PM on Wednesday, June 12th, 2019; Marshak 418N
Benjamin Steinberg (CCNY and CUNY Graduate Center)
Abstract
The study of formal languages is a classical area in Logic and Theoretical Computer Science. The Chomsky hierarchy classifies languages by how complicated a model of computation is needed to describe the language. At the bottom of the Chomsky hierarchy sits the class of regular languages. Regular languages, while not powerful, are very versatile as they can be described via a number of different formalisms, including regular expressions and finite state automata, and most algorithmic questions about regular languages can be decided (often efficiently).
In this talk I will give a brief introduction to the concept of a regular language and explain how regular languages can be specified using the kind of logic you see in MATH 308, called first order logic, and a slightly stronger logic that lets you quantifying over subsets (called monadic second order logic). Logical specification turns out to be important if program verification. Büchi showed that regular languages are exactly those languages that can be defined by a sentence of monadic second order logic. However, to distinguish those languages definable in first order logic (the MATH 308 sort) and this fancier logic, one needs to use algebra. I’ll also indicate some of the surprisingly simple to state problems about logic on words that are still open and which one hopes to answer using algebraic techniques.
