This is a survey about a collection of results about a (double) hierarchy of classes of regular languages, which occurs in a natural fashion in a number of contexts. One of these occurrences is given by an alternated sequence of deterministic and co-deterministic closure operations, starting with the piecewise testable languages. Since these closure operations preserve varieties of languages, this defines a hierarchy of varieties, and through Eilenberg's variety theorem, a hierarchy of pseudo-varieties (classes of finite monoids that are defined by pesudo-identities). The point of this excursion through algebra is that it provides reasonably simple decision algorithms for the membership problem in the corresponding varieties of languages. Another interesting point is that the hierarchy of pseudo-varieties bears a formal resemblance with another hierarchy, the hierarchy of varieties of idempotent monoids, which was much studied in the 1970s and 1980s and is by now well understood. This resemblance provides keys to a combinatorial characterization of the different levels of our hierarchies, which turn out to be closely related with the so-called rankers, a specification mechanism which was introduced to investigate the two-variable fragment of the first-order theory of the linear order. And indeed the union of the varieties of languages which we consider coincides with the languages that can be defined in that fragment. Moreover, the quantifier alternation hierarchy within that logical fragment is exactly captured by our hierarchy of languages, thus establishing the decidability of the alternation hierarchy. There are other combinatorial and algebraic approaches of the same logical hierarchy, and one recently introduced by Krebs and Straubing also establishes decidability. Yet the algebraic operations involved are seemingly very different, an intriguing problem...
展开▼
