Abstract

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.

Attachment

Video Recording