<p>Here is a list of several hierarchies of interest, some of which were already mentioned in other answers.</p>

<ol>
<li><strong>Concatenation hierarchies</strong></li>
</ol>

<p>A language $L$ is a <em>marked product</em> 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 <a href="https://www.irif.fr/~jep/PDF/DotDepth.pdf">dot-depth hierarchy</a> (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).</p>

<ol start="2">
<li><strong>Star-height hierarchies</strong></li>
</ol>

<p>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 (<a href="https://en.wikipedia.org/wiki/Star-free_language">star-free languages</a>), 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 <a href="https://www.irif.fr/~jep/PDF/Brzozowski.pdf">this paper</a> for an overview.</p>

<ol start="3">
<li><strong>Logical hierarchies</strong></li>
</ol>

<p>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
<a href="https://i.sstatic.net/l7u8y.gif"><img src="https://i.sstatic.net/l7u8y.gif" alt="enter image description here"></a>
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 $&lt;$ (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 <a href="https://www.irif.fr/~jep/PDF/DotDepth.pdf">paper</a> for an overview.</p>

<ol start="4">
<li><strong>Boolean hierarchies</strong></li>
</ol>

<p>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.</p>

<ol start="5">
<li><strong>Group complexity</strong></li>
</ol>

<p>A result of <a href="https://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory">Krohn-Rhodes</a> (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 <a href="https://en.wikipedia.org/wiki/Star-free_language">star-free languages</a> and there exist languages of any complexity. However, no effective characterisation of the languages of complexity $1$ is known.</p>

<ol start="6">
<li><strong>Hierarchies inherited from circuit complexity</strong></li>
</ol>

<p>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$.</p>

<p>$[1]$ Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Regular languages in $NC^1$. <em>J. Comput. System Sci.</em> <strong>44</strong> (1992)</p>

CC BY-SA 3.0
2016-10-27T13:32:46.157Z
2016-10-27T13:32:46.157Z
J.-E. Pin
<p>Expanding the comment: a natural hierarchy is the one induced by the number of states of the DFA.</p>

<p>We can define $\mathcal{L}_n = \{ L \mid \text{ exists an n-states DFA D s.t. } L(D) = L \}$</p>

<p>($D = \{Q, \Sigma, \delta, q_0, F \}$, $|Q| = n$ )</p>

<p>Clearly $\mathcal{L}_n \subseteq \mathcal{L}_{n+1}$ (simply use dead states)</p>

<p>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}$</p>

<p>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 &lt; n$ which doesn't belong to $L_{n+1}$, so a DFA with $n$ or fewer states cannot accept $L_{n+1}$.</p>

CC BY-SA 3.0
2016-10-18T07:20:54.753Z
2016-10-25T17:25:24.490Z
2016-10-25T17:25:24.490Z
Marzio De Biasi
<p>I recently came across <a href="https://arxiv.org/abs/1301.4981" rel="noreferrer">this paper</a> which may give another relevant example (cf. the last sentence of the abstract):</p>

<p>Guillaume Bonfante, Florian Deloup: The genus of regular languages.</p>

<p><em>From the abstract:</em> 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.</p>

CC BY-SA 3.0
2016-10-19T09:19:56.217Z
2016-10-21T12:40:50.173Z
2016-10-21T12:40:50.173Z
Damiano Mazza
<p>There are several natural hierarchies for regular languages of infinite words, that convey a notion of "complexity of the language", for instance:</p>

<ul>
<li>Number of ranks needed in a deterministic parity automaton</li>
<li>Wadge (or Wagner) hierarchy: topological complexity, $\omega^\omega$ levels.</li>
</ul>

<p>These hierarchies can be generalised for regular languages of infinite trees, for which new hierarchies appear, see for instance <a href="https://cstheory.stackexchange.com/a/20842/8953">this answer</a>.</p>

CC BY-SA 3.0
2016-10-20T16:22:37.863Z
2016-10-20T16:22:37.863Z
2017-04-13T12:32:28.743Z
Denis
<p>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).</p>

<p>Thank you!</p>

CC BY-SA 3.0
2016-10-17T07:23:12.857Z
A natural hierarchy is the one induced by the number of states.
Marzio De Biasi
CC BY-SA 3.0
2016-10-17T08:26:15.640Z
The canonical one is the dot depth hierarchy, characterized by quantifier alternation in FO(<). Basically, (Boolean closure of) quantifier alternation gives you robust classes and hierarchies.
Michaël Cadilhac
CC BY-SA 3.0
2016-10-17T23:36:42.200Z
Those both seems like perfectly good answers to me...
Joshua Grochow
CC BY-SA 3.0
2016-10-18T21:18:27.423Z
There is also *star height*.
reinierpost
CC BY-SA 3.0
2016-10-27T11:02:50.417Z
What do you mean by a "nice" hierarchy versus "the membership of each class is "nicely" demonstrated by some elements"?". Outside regular languages, the polynomial hierarchy seems to be considered a nice hierarchy despite the fact that the membership and even the existence of a real hierarchy is still to be proved.
J.-E. Pin
<automata-theory><regular-language><regular-expressions>
Hierarchies in regular languages
raja.damanik
# Hierarchies in regular languages

(Asked by: username_0 on 2016-10-17)

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!

**Tags:** automata-theory, regular-language, regular-expressions
> **Comments:**
> **username_1**: A natural hierarchy is the one induced by the number of states.  
> **username_2**: The canonical one is the dot depth hierarchy, characterized by quantifier alternation in FO(<). Basically, (Boolean closure of) quantifier alternation gives you robust classes and hierarchies.  
> **username_3**: Those both seems like perfectly good answers to me...  
> **username_4**: There is also *star height*.  
> **username_5**: What do you mean by a "nice" hierarchy versus "the membership of each class is "nicely" demonstrated by some elements"?". Outside regular languages, the polynomial hierarchy seems to be considered a nice hierarchy despite the fact that the membership and even the existence of a real hierarchy is still to be proved.  

---

## 4 answers

### Answer by username_5 on 2016-10-27. Score: 17

Here is a list of several hierarchies of interest, some of which were already mentioned in other answers.

1. **Concatenation hierarchies**

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](https://www.irif.fr/~jep/PDF/DotDepth.pdf) (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).

2. **Star-height hierarchies**

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](https://en.wikipedia.org/wiki/Star-free_language)), 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](https://www.irif.fr/~jep/PDF/Brzozowski.pdf) for an overview.

3. **Logical hierarchies**

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
[![enter image description here](https://i.sstatic.net/l7u8y.gif)](https://i.sstatic.net/l7u8y.gif)
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](https://www.irif.fr/~jep/PDF/DotDepth.pdf) for an overview.

4. **Boolean hierarchies**

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.

5. **Group complexity**

A result of [Krohn-Rhodes](https://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory) (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](https://en.wikipedia.org/wiki/Star-free_language) and there exist languages of any complexity. However, no effective characterisation of the languages of complexity $1$ is known.

6. **Hierarchies inherited from circuit complexity**

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)


---

### Answer by username_1 on 2016-10-18. Score: 12

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}$.


---

### Answer by username_6 on 2016-10-19. Score: 9

I recently came across [this paper](https://arxiv.org/abs/1301.4981) 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.


---

### Answer by username_7 on 2016-10-20. Score: 6

There are several natural hierarchies for regular languages of infinite words, that convey a notion of "complexity of the language", for instance:

* Number of ranks needed in a deterministic parity automaton
* Wadge (or Wagner) hierarchy: topological complexity, $\omega^\omega$ levels.

These hierarchies can be generalised for regular languages of infinite trees, for which new hierarchies appear, see for instance [this answer](https://cstheory.stackexchange.com/a/20842/8953).


---

