An important question in automata theory concerns the precise characterization of natural classes of regular word languages. These classes are typically defined by refining standard representations of regular languages, such as regular expressions, automata, or monadic second-order logic. However, the notion of "understanding a class" is inherently vague. A common way to formalize this goal is to identify an algorithm that decides membership in the class: given a regular language as input, determine whether it belongs to the class. The significance of this approach lies not in the algorithm itself but in the deep understanding of the class required to develop such a procedure.  

 

A seminal result in this field is Schützenberger's theorem, which provides a membership algorithm for the prominent class of star-free languages. These are the languages that can be expressed using a star-free expression (a regular expression that allows union, concatenation, and complement but not the Kleene star). Equivalently, star-free languages are precisely those definable in first-order logic. Schützenberger's work led to the introduction of a natural parameter for measuring the complexity of a star-free language: the number of alternations between complement and concatenation needed to express it using a star-free expression. From a logical perspective, this corresponds exactly to the number of quantifier alternations required to define the language with a first-order sentence. Brzozowski and Cohen defined an infinite classification, known as the dot-depth hierarchy, which classifies star-free languages according to this complexity measure.  

 

A longstanding open question in automata theory is whether there exists an algorithm that determines the level of a given star-free language within the dot-depth hierarchy. In other words, the challenge is to find a membership algorithm for each level of the hierarchy. In this talk, I will explain why this problem is difficult and outline the known (partial) results. I will focus on recent advances that rely on a new decision problem called separation which is more general than membership. For each class, the associated separation problem takes two regular languages as input and asks whether there exists a third language in the investigated class that includes the first and is disjoint from the second. I will introduce separation and discuss its relevance and usefulness in studying the dot-depth hierarchy.