| Summary: | We consider the class of languages defined in the 2-variable fragment of the
first-order logic of the linear order. Many interesting characterizations of
this class are known, as well as the fact that restricting the number of
quantifier alternations yields an infinite hierarchy whose levels are varieties
of languages (and hence admit an algebraic characterization). Using this
algebraic approach, we show that the quantifier alternation hierarchy inside
FO^{2}[<] is decidable within one unit. For this purpose, we relate each level
of the hierarchy with decidable varieties of languages, which can be defined in
terms of iterated deterministic and co-deterministic products. A crucial notion
in this process is that of condensed rankers, a refinement of the rankers of
Weis and Immerman and the turtle languages of Schwentick, Th\'erien and
Vollmer.
|
|---|