Fall 2016

The Power of Two Variables

Monday, November 7th, 2016 11:00 am11:30 am

Add to Calendar

This is a survey of results on the expressive power of first-order logic interpreted in words, where the formulas are restricted to have only two variables. (It is known that formulas with three variables have the same expressive power as arbitrary first-order sentences.) We begin with the original results of Therien and Wilke giving an effective characterization of the languages definable in this logic, consider the connection to temporal logic and results on alternation depth, and the most recent work on two-variable logic enriched by a relation that allows one to talk about the letters appearing between two positions.

PDF icon The Power of Two Variables257.56 KB