Philipp Weis, Neil Immerman

It is well-known that every first-order property on words is expressible

using at most three variables. The subclass of properties expressible with

only two variables is also quite interesting and well-studied. We prove

precise structure theorems that characterize the exact expressive power of

first-order logic with two variables on words. ...
more >>>