Two-variable Logic with a Between Predicate

Andreas Krebs, Kamal Lodaya, Paritosh Pandya +1

We study an extension of FO^2[<], first-order logic interpreted in finite words, in which formulas are restricted to use only two variables. We adjoin to this language two-variable…