Hierarchie w zwykłych językach

Czy istnieje jakaś znana „ładna” hierarchia $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (może być skończona) w klasie zwykłych języków $L$ ? Przyjemnie tutaj, klasy w każdej hierarchii przechwytują różną ekspresję / siłę / złożoność. Przynależność do każdej klasy jest „ładnie” wykazana przez niektóre elementy (w przeciwieństwie do problemu wysokości gwiazdy, który może być problematyczny).

Dziękuję Ci!

Oto lista kilku hierarchii interesów, z których niektóre zostały już wspomniane w innych odpowiedziach.

1. Hierarchie konkatenacji

Język jest oznaczony produkt z L 0 , L 1 , ... , L n jeśli L = L 0 1 L 1 ⋯ n L n do niektórych liter 1 , ... , n . Hierarchie konkatenacji są definiowane przez naprzemienne operacje boolowskie i operacje wielomianowe (= związek i oznaczony produkt). Hierarchia Straubing-Thérien (punkt początkowy { ∅ , A ∗ } $L$$L_0, L_1, \ldots, L_n$$L = L_0a_1L_1 \cdots a_nL_n$$a_1, \ldots, a_n$$\{\emptyset, A^*\})\ $i hierarchia głębokości kropek (punkt początkowy są tego typu, ale można wziąć inne punkty początkowe, w szczególności języki grupowe (języki akceptowane przez automat permutacyjny).$\{\emptyset, \{1\}, A^+, A^*\})\ $

2. Hierarchie wysokości gwiazd

Ogólny wzór polega na zliczeniu minimalnej liczby zagnieżdżonych gwiazd potrzebnych do wyrażenia języka zaczynającego się od liter, ale możliwych jest kilka wariantów, w zależności od podstawowych operatorów, na które zezwolisz. Jeśli zezwalasz tylko na łączenie i iloczyn, definiujesz ograniczoną wysokość gwiazdy, jeśli zezwalasz na łączenie, dopełnianie i iloczyn, definiujesz (uogólnioną) wysokość gwiazdy, a jeśli zezwalasz na łączenie, przecięcie i iloczyn, definiujesz pośrednią wysokość gwiazdy . Istnieją języki ograniczonej gwiazdy dla każdego n i dalej mogą skutecznie obliczyć wysokość gwiazdy dla danego języka regularnego. Dla wysokości gwiazdy decyduje wysokość gwiazdy 0 ( języki bez gwiazd ), istnieją języki wysokości gwiazdy$n$$n$$0$$1$, ale żaden język o wysokości gwiazdy jest znany! Nie jest znany żaden wynik na pośredniej wysokości gwiazdy. Zobacz ten papier na przegląd.$2$

3. Logiczne hierarchie

Istnieje wiele z nich, ale jednym z najważniejszych z nich jest tzw hierarchia. Wzór mówi się Σ n -formula jeśli jest to równoważne formuły postaci Q ( x 1 , . . . , X K ) φ gdzie φ jest wolny i kwantyfikator Q ( x 1 , . . . , Bloki kwantyfikatorów, tak że pierwszy blok zawiera tylko kwantyfikatory egzystencjalne (zauważ, że ten pierwszy blok może być pusty), kwantyfikatory uniwersalne drugiego bloku itp. Podobnie, jeśli $\Sigma_n$$\Sigma_n$$Q(x_1,...,x_k)\varphi$$\varphi$ jest sekwencją$Q(x_1,...,x_k)$$n$ jest utworzona z n naprzemienne bloki kwantyfikatorów zaczynające się od bloku uniwersalnych kwantyfikatorów (które znów mogą być puste), mówimy, że φ jestformułą Π n . Oznacz przez Σ n (odpowiednio. Π n ) klasę języków, które można zdefiniować za pomocąformuły Σ n (odpowiednio. A$Q(x_1,...,x_k)$$n$$\varphi$$\Pi_n$$\Sigma_n$$\Pi_n$$\Sigma_n$$\Pi_n$ formula) i przez logiczne zamknięcie Σ n- języków. Na koniec niech Δ n = Σ n ∩ Π n . Ogólny obraz wygląda tak : Oczywiście trzeba określić podpis. Zwykle jest orzecznikiem dla każdej litery (i a x środków nie jest list w pozycji x w słowie). Następnie można dodać symbol binarny $\mathcal{B}\Sigma_n$$\Sigma_n$$\Delta_n = \Sigma_n \cap \Pi_n$$\mathbf{a}$$\mathbf{a}x$$a$$x$$<$ (odpowiednią hierarchią jest hierarchia Straubinga-Thériena), a także symbol zastępczy (odpowiednią hierarchią jest hierarchia z głębokością kropek). Inne możliwości obejmują: źródłowe, do zliczania modulo n itp zobaczy tegopapierudla przeglądu.$Mod$$n$

4. Hierarchie logiczne

Ogólny wzorzec (który nie jest specyficzny dla zwykłych języków) wynika z Hausdorffa. Niech będzie klasą języków zawierających pusty zbiór i pełny zbiór i zamkniętych pod skończonym przecięciem i skończonym zjednoczeniem. Niech D n ( L ) będzie klasą wszystkich języków w postaci X = X 1 - X 2 + ⋯ ± X n, gdzie X i ∈ L i X 1 ⊇ X 2 ⊇ X 3 ⊇ ⋯ ⊇ X n D$\mathcal{L}$$\mathcal{D}_n(\mathcal{L})$

$$\begin{equation} X = X_1 - X_2 + \cdots \pm X_n \end{equation}$$ $X_i\in \mathcal{L}$$X_1 \supseteq X_2\supseteq X_3 \supseteq \cdots \supseteq X_n$ . Od, klasy D N ( L ) określenie hierarchii ich suma jest logiczna zamknięcie L . Ponownie możliwe są różne punkty początkowe.$\mathcal{D}_n(\mathcal{L}) \subseteq \mathcal{D}_{n+1}(\mathcal{L})$$\mathcal{D}_n(\mathcal{L})$$\mathcal{L}$

5. Złożoność grupy

Wynik Krohna-Rhodesa (1966) stwierdza, że ​​każdy DFA może być symulowany przez kaskadę automatów resetujących (zwanych także flip-flop) i automatów, których półgrupami przejścia są grupy skończone. Złożoność grupowa języka to najmniejsza liczba grup zaangażowanych w taki rozkład minimalnego DFA języka. Języki złożoności są dokładnie językami bez gwiazd i istnieją języki o dowolnej złożoności. Jednak nie jest znana skuteczna charakterystyka języków złożoności 1 .$0$$1$

6. Hierarchie odziedziczone ze złożoności obwodów

Punktem wyjścia jest ładny artykuł który pokazuje w szczególności, że klasa A C 0 ∩ R e g jest rozstrzygalna. Niech A C C ( q ) = { L ⊆ { 0 , 1 } ∗ ∣ L ⩽ A C 0 M O D q } , gdzie M O D q = { u ∈ { ∣ | u $[1]$$AC^0 \cap Reg$$ACC(q) = \{ L \subseteq \{0,1\}^* \mid L \leqslant_{AC^0} MOD_q\}$ . Jeżeli q dzieli q ′ , to A C C ( q ) ⊆ A C C ( q ′ ) . Interesujące pytanie jest, aby wiedzieć, czy C C ( Q ) ∩ R e g jest rozstrzygalne dla każdego q .$MOD_q = \{u \in \{0,1\}^* \mid |u|_1 \equiv 0 \bmod q\}$$q$$q'$$ACC(q) \subseteq ACC(q')$$ACC(q) \cap Reg$$q$

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

Rozszerzanie komentarza: naturalna hierarchia jest indukowana przez liczbę stanów DFA.

Możemy zdefiniować $\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:

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