Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture different expressiveness / power / complexity. Also, the membership of each class is "nicely" demonstrated by some elements (unlike star height problem that may be problematic).
Thank you!
Here is a list of several hierarchies of interest, some of which were already mentioned in other answers.
A language $L$ is a marked product of $L_0, L_1, \ldots, L_n$ if $L = L_0a_1L_1 \cdots a_nL_n$ for some letters $a_1, \ldots, a_n$. Concatenation hierarchies are defined by alternating Boolean operations and polynomial operations (= union and marked product). The Straubing-Thérien hierarchy (starting point $\{\emptyset, A^*\})\ $ and the dot-depth hierarchy (starting point $\{\emptyset, \{1\}, A^+, A^*\})\ $ are of this type, but you can take other starting points, notably the group languages (languages accepted by a permutation automaton).
The general pattern is to count the minimal number of nested stars needed to express a language starting from the letters, but several variants are possible, depending on the basic operators you allow. If you only allow union and product, you define the restricted star-height, if you allow union, complement and product, you define the (generalised) star-height and if you allow union, intersection and product you define the intermediate star-height. There are languages of restricted star $n$ for every $n$ and on can effectively compute the star-height of a given regular language. For the star-height, star-height $0$ is decidable (star-free languages), there exist languages of star-height $1$, but no language of star-height $2$ is known! No result is known on the intermediate star-height. See this paper for an overview.
There are many of them, but one of the most important one is the so-called $\Sigma_n$ hierarchy. A formula is said to be a $\Sigma_n$-formula if it is equivalent to a formula of the form $Q(x_1,...,x_k)\varphi$ where $\varphi$ is quantifier free and $Q(x_1,...,x_k)$ is a sequence of $n$ blocks of quantifiers such that the first block contains only existential quantifiers (note that this first block may be empty), the second block universal quantifiers, etc. Similarly, if $Q(x_1,...,x_k)$ is formed of $n$ alternating blocks of quantifiers beginning with a block of universal quantifiers (which again might be empty), we say that $\varphi$ is a $\Pi_n$-formula. Denote by $\Sigma_n$ (resp. $\Pi_n$) the class of languages which can be defined by a $\Sigma_n$-formula (resp. a $\Pi_n$-formula) and by $\mathcal{B}\Sigma_n$ the Boolean closure of $\Sigma_n$-languages. Finally, let $\Delta_n = \Sigma_n \cap \Pi_n$.
The general picture looks like this
One needs of course to specify the signature. There is usually a predicate $\mathbf{a}$ for each letter (and $\mathbf{a}x$ means there is a letter $a$ in position $x$ in the word). Then one can add a binary symbol $<$ (the corresponding hierarchy is the Straubing-Thérien hierarchy) and also a successor symbol (the corresponding hierarchy is the dot-depth hierarchy). Other possibilities include a $Mod$ predicate, to count modulo $n$, etc. See again this paper for an overview.
The general pattern (which is not specific to regular languages) is due to Hausdorff. Let $\mathcal{L}$ be a class of languages containing the empty set and the full set, and closed under finite intersection and finite union. Let $\mathcal{D}_n(\mathcal{L})$ be the class of all languages of the form \begin{equation} X = X_1 - X_2 + \cdots \pm X_n \end{equation} where $X_i\in \mathcal{L}$ and $X_1 \supseteq X_2\supseteq X_3 \supseteq \cdots \supseteq X_n$. Since $\mathcal{D}_n(\mathcal{L}) \subseteq \mathcal{D}_{n+1}(\mathcal{L})$, the classes $\mathcal{D}_n(\mathcal{L})$ define a hierarchy and their union is the Boolean closure of $\mathcal{L}$. Again, various starting points are possible.
A result of Krohn-Rhodes (1966) states that every DFA can be simulated by a cascade of reset (also called flip-flop) automata and automata whose transitions semigroups are finite groups. The group complexity of a language is the least number of groups involved in such a decomposition of the minimal DFA of the language. Languages of complexity $0$ are exactly the star-free languages and there exist languages of any complexity. However, no effective characterisation of the languages of complexity $1$ is known.
The starting point is the nice article $[1]$ which show in particular that the class $AC^0 \cap Reg$ is decidable. Let $ACC(q) = \{ L \subseteq \{0,1\}^* \mid L \leqslant_{AC^0} MOD_q\}$, where $MOD_q = \{u \in \{0,1\}^* \mid |u|_1 \equiv 0 \bmod q\}$. If $q$ divides $q'$, then $ACC(q) \subseteq ACC(q')$. An interesting question is to know whether $ACC(q) \cap Reg$ is decidable for any $q$.
$[1]$ Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Regular languages in $NC^1$. J. Comput. System Sci. 44 (1992)
Expanding the comment: a natural hierarchy is the one induced by the number of states of the DFA.
We can define $\mathcal{L}_n = \{ L \mid \text{ exists an n-states DFA D s.t. } L(D) = L \}$
($D = \{Q, \Sigma, \delta, q_0, F \}$, $|Q| = n$ )
Clearly $\mathcal{L}_n \subseteq \mathcal{L}_{n+1}$ (simply use dead states)
To show the proper inclusion $\mathcal{L}_n \subsetneq \mathcal{L}_{n+1} $ we can simply pick the language: $L_{n+1} = \{ a^{i} \mid i \geq n \} \in \mathcal{L}_{n+1}$
Very informally: the (minimum) DFA that recognizes $\{ a^{i} \mid i \geq n \}$ must be a "state chain" of length $n+1$ : $q_0 \to^a q_1 \to^a ... \to^a q_n $, $F = \{q_n\}$ and $q_n \to^a q_n$ ($q_n$ has a self-loop). So $n+1$ states are enough to accept $L_{n+1}$. But every accepting path from $q_0$ to a final state $q_f$ which is strictly shorter than $n+1$ must accept some $a^{i}$ with $i < n$ which doesn't belong to $L_{n+1}$, so a DFA with $n$ or fewer states cannot accept $L_{n+1}$.
I recently came across this paper which may give another relevant example (cf. the last sentence of the abstract):
Guillaume Bonfante, Florian Deloup: The genus of regular languages.
From the abstract: The article defines and studies the genus of finite state deterministic automata (FSA) and regular languages. Indeed, a FSA can be seen as a graph for which the notion of genus arises. At the same time, a FSA has a semantics via its underlying language. It is then natural to make a connection between the languages and the notion of genus. After we introduce and justify the the notion of the genus for regular languages, [...] we build regular languages of arbitrary large genus: the notion of genus defines a proper hierarchy of regular languages.
There are several natural hierarchies for regular languages of infinite words, that convey a notion of "complexity of the language", for instance:
These hierarchies can be generalised for regular languages of infinite trees, for which new hierarchies appear, see for instance this answer.
