14
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ A natural hierarchy is the one induced by the number of states. $\endgroup$ – Marzio De Biasi Oct 17 '16 at 7:23
  • 9
    $\begingroup$ 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. $\endgroup$ – Michaël Cadilhac Oct 17 '16 at 8:26
  • $\begingroup$ Those both seems like perfectly good answers to me... $\endgroup$ – Joshua Grochow Oct 17 '16 at 23:36
  • 4
    $\begingroup$ There is also star height. $\endgroup$ – reinierpost Oct 18 '16 at 21:18
  • $\begingroup$ 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. $\endgroup$ – J.-E. Pin Oct 27 '16 at 11:02
14
$\begingroup$

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 (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).

  1. 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), 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.

  1. 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 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.

  1. 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.

  1. Group complexity

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.

  1. 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)

$\endgroup$
11
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.