  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 atomic formulas that say, `the letter a appears
between positions x and y'. This is, in a sense, the simplest property that is
not expressible using only two variables.
  We present several logics, both first-order and temporal, that have the same
expressive power, and find matching lower and upper bounds for the complexity
of satisfiability for each of these formulations. We also give an effective
necessary condition, in terms of the syntactic monoid of a regular language,
for a property to be expressible in this logic. We show that this condition is
also sufficient for words over a two-letter alphabet. This algebraic analysis
allows us us to prove, among other things, that our new logic has strictly less
expressive power than full first-order logic FO[<].
