Hierarchie w zwykłych językach

14

Czy istnieje jakaś znana „ładna” hierarchia L0L1L2 (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!

raja.damanik
źródło
3
Naturalna hierarchia to taka, która wynika z liczby stanów.
Marzio De Biasi
9
Kanoniczna to hierarchia głębokości kropek, charakteryzująca się naprzemiennością kwantyfikatora w FO (<). Zasadniczo, (logiczne zamknięcie) naprzemienność kwantyfikatora daje solidne klasy i hierarchie.
Michaël Cadilhac
Oba wydają mi się idealnie dobrymi odpowiedziami ...
Joshua Grochow
4
Istnieje również wysokość gwiazdy .
reinierpost
Co rozumiesz przez „ładną” hierarchię kontra „przynależność do każdej klasy jest„ ładnie ”wykazana przez niektóre elementy„? ”. Poza zwykłymi językami hierarchia wielomianowa wydaje się uważana za niezłą hierarchię, pomimo faktu, że członkostwo i nawet istnienie prawdziwej hierarchii nie zostało jeszcze udowodnione
J.-E. Pin

Odpowiedzi:

15

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 1n 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,,L.nL=L0a1L1anLna1,,an{,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).{,{1},ZA+,ZA}) 

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

  1. 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 QΣnΣnQ(x1,...,xk)φφ jest sekwencjąQ(x1,...,xk)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(x1,...,xk)nφΠnΣnΠnΣnΠ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 <BΣnΣnΔn=ΣnΠnwprowadź opis zdjęcia tutajaaxax< (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.Modn

  1. 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 iL i X 1X 2X 3X n D nLDn(L)

X=X1X2+±Xn
XiLX1X2X3Xn . Od, klasy D N ( L ) określenie hierarchii ich suma jest logiczna zamknięcie L . Ponownie możliwe są różne punkty początkowe.Dn(L)Dn+1(L)Dn(L)L
  1. 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 .01

  1. 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 0R 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]AC0RegACC(q)={L{0,1}LAC0MODq} . 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 .MODq={u{0,1}|u|10modq}qqACC(q)ACC(q)ACC(q)Regq

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

J.-E. Pin
źródło
12

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

Możemy zdefiniować L.n={L. istnieje n-stany DFA D ul L.(re)=L.}

(D={Q,Σ,δ,q0,F}, |Q|=n )

Clearly LnLn+1 (simply use dead states)

To show the proper inclusion LnLn+1 we can simply pick the language: Ln+1={aiin}Ln+1

Very informally: the (minimum) DFA that recognizes {aiin} must be a "state chain" of length n+1 : q0aq1a...aqn, F={qn} and qnaqn (qn has a self-loop). So n+1 states are enough to accept Ln+1. But every accepting path from q0 to a final state qf which is strictly shorter than n+1 must accept some ai with i<n which doesn't belong to Ln+1, so a DFA with n or fewer states cannot accept Ln+1.

Marzio De Biasi
źródło
8

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.

Damiano Mazza
źródło
5

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, ωω levels.

These hierarchies can be generalised for regular languages of infinite trees, for which new hierarchies appear, see for instance this answer.

Denis
źródło