Hiérarchies en langues régulières

14

Y a-t-il une "belle" hiérarchie (peut-être finie) à l'intérieur de la classe des langues régulières ? Par gentil ici, les classes de chaque hiérarchie capturent différentes expressivités / puissance / complexité. De plus, l'appartenance à chaque classe est "joliment" démontrée par certains éléments (contrairement au problème de hauteur d'étoile qui peut être problématique).L0L1L2L

Je vous remercie!

raja.damanik
la source
3
Une hiérarchie naturelle est celle induite par le nombre d'états.
Marzio De Biasi
9
La canonique est la hiérarchie des profondeurs de points, caractérisée par une alternance de quantificateurs dans FO (<). Fondamentalement, (la fermeture booléenne de) l'alternance de quantificateur vous donne des classes et des hiérarchies robustes.
Michaël Cadilhac
Ces deux réponses me semblent parfaitement bonnes ...
Joshua Grochow
4
Il y a aussi la hauteur des étoiles .
reinierpost
Qu'entendez-vous par une "belle" hiérarchie par rapport à "l'appartenance à chaque classe est" joliment "démontrée par certains éléments"? ". En dehors des langages réguliers, la hiérarchie polynomiale semble être considérée comme une belle hiérarchie malgré le fait que l'appartenance et même l'existence d'une véritable hiérarchie reste à prouver
J.-E. Pin

Réponses:

15

Voici une liste de plusieurs hiérarchies d'intérêt, dont certaines ont déjà été mentionnées dans d'autres réponses.

  1. Hiérarchies de concaténation

Une langue L est un produit marqué de L0,L1,,Ln si L=L0a1L1anLn pour certaines lettres a1,,an . Les hiérarchies de concaténation sont définies en alternant les opérations booléennes et les opérations polynomiales (= union et produit marqué). La hiérarchie Straubing-Thérien (point de départ {,A}) et la hiérarchie point-profondeur (point de départ {,{1},A+,A})  sont de ce type, mais vous pouvez prendre d'autres points de départ, notamment les langages de groupe (langages acceptés par un automate à permutation).

  1. Hiérarchies d'étoiles

Le schéma général consiste à compter le nombre minimal d'étoiles imbriquées nécessaires pour exprimer une langue à partir des lettres, mais plusieurs variantes sont possibles, selon les opérateurs de base que vous autorisez. Si vous autorisez uniquement l'union et le produit, vous définissez la hauteur d'étoile restreinte, si vous autorisez l'union, le complément et le produit, vous définissez la hauteur d'étoile (généralisée) et si vous autorisez l'union, l'intersection et le produit, vous définissez la hauteur d'étoile intermédiaire . Il existe des langues d'étoile restreinte n pour chaque n et on peut calculer efficacement la hauteur des étoiles d'une langue régulière donnée. Pour la hauteur des étoiles, la hauteur des étoiles 0 est décidable ( langues sans étoiles ), il existe des langues de hauteur des étoiles 1, mais aucune langue de hauteur d'étoile 2 n'est connue! Aucun résultat n'est connu sur la hauteur d'étoile intermédiaire. Consultez cet article pour un aperçu.

  1. Hiérarchies logiques

Ils sont nombreux, mais l'un des plus importants est la soi-disant hiérarchie . Une formule est dit être un Σ n -formule si elle est équivalente à une formule de la forme Q ( x 1 , . . . , X k ) φφ est quantificateur libre et Q ( x 1 , . . . , X k ) est une séquence de nΣnΣnQ(x1,...,xk)φφQ(x1,...,xk)ndes blocs de quantificateurs de telle sorte que le premier bloc contient uniquement les quantificateurs existentiels (note que ce premier bloc peut être vide), le second bloc quantificateurs universels, etc. De même, si est formée de n en alternant des blocs de quantificateurs commençant par un bloc de quantificateurs universels (qui pourrait encore être vide), on dit que φ est une formule Π n . Notons Σ n (resp. Π n ) la classe de langues qui peut être définie par une formule Σ n (resp. A ΠQ(x1,...,xk)nφΠnΣnΠnΣn -formula) et par B Σ n la fermeture booléenne de Σ n -languages. Soit enfin Δ n = Σ nΠ n . L'image générale ressemble à ceci. Il faut bien sûr spécifier la signature. Il y a généralement un prédicat a pour chaque lettre (et un x signifie qu'il y a une lettre a en position x dans le mot). Ensuiteon peut ajouter un symbole binaire <ΠnBΣnΣnΔn=ΣnΠnenter image description hereaaxax<(la hiérarchie correspondante est la hiérarchie de Straubing-Thérien) et également un symbole successeur (la hiérarchie correspondante est la hiérarchie en profondeur de points). D' autres possibilités incluent un prédicat, à compter modulo n , etc. Revoyez ce papier pour un aperçu.Modn

  1. Hiérarchies booléennes

Le schéma général (qui n'est pas spécifique aux langues régulières) est dû à Hausdorff. Soit une classe de langages contenant l'ensemble vide et l'ensemble complet, et fermée sous intersection finie et union finie. Soit D n ( L ) la classe de toutes les langues de la forme X = X 1 - X 2 + ± X nX iL et X 1X 2X 3X n . PuisqueLDn(L)

X=X1X2+±Xn
XiLX1X2X3Xn, les classes D n ( L ) définissent une hiérarchie et leur union est la fermeture booléenne L . Là encore, différents points de départ sont possibles.Dn(L)Dn+1(L)Dn(L)L
  1. Complexité du groupe

Un résultat de Krohn-Rhodes (1966) indique que chaque DFA peut être simulé par une cascade d'automates réinitialisés (également appelés flip-flop) et d'automates dont les semi-groupes de transitions sont des groupes finis. La complexité de groupe d'une langue est le moins grand nombre de groupes impliqués dans une telle décomposition du DFA minimal de la langue. Les langues de complexité sont exactement les langues sans étoiles et il existe des langues de toute complexité. Cependant, aucune caractérisation efficace des langages de complexité 1 n'est connue.01

  1. Hiérarchies héritées de la complexité des circuits

Le point de départ est le bel article qui montre notamment que la classe A C 0R e g est décidable. Soit A C C ( q ) = { L { 0 , 1 } L A C 0 M O D q } , où M O D q = { u { 0 , 1 }[1]AC0RegACC(q)={L{0,1}LAC0MODq} . Si q divise q , alors A C C ( q ) A C C ( q ) . Une question intéressante est de savoir si A C C ( q ) R e g est décidable pour tout q .MODq={u{0,1}|u|10modq}qqACC(q)ACC(q)ACC(q)Regq

Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Langues régulières en N C 1 . J. Comput. System Sci. 44(1992)[1]NC1

J.-E. Épingle
la source
12

Élargissement du commentaire: une hiérarchie naturelle est celle induite par le nombre d'états du DFA.

On peut définir Ln={L exists an n-states DFA D s.t. L(D)=L}

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

Clairement (utilisez simplement des états morts)LnLn+1

Pour montrer l'inclusion appropriée nous pouvons simplement choisir la langue: L n + 1 = { a ii n } L n + 1LnLn+1Ln+1={aiin}Ln+1

Très informellement: le DFA (minimum) qui reconnaît doit être une "chaîne d'état" de longueur n + 1 : q 0 a q 1 a . . . a q n , F = { q n } et q n a q n ( q n a une boucle automatique). Donc, n + 1 états suffisent pour accepter{aiin}n+1q0aq1a...aqnF={qn}qnaqnqnn+1Ln+1q0qfn+1aii<nLn+1nLn+1

Marzio De Biasi
la source
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
la source
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
la source