Complexité en états

La complexité en états (en anglais Modèle:Citation étrangère) est un thème en informatique théorique qui traite de la taille d'automates abstraits, tels que les diverses variantes des automates finis reconnaissant un langage rationnel donné. Un exemple typique dans ce domaine est le résultat selon lequel un automate fini non déterministe à $n$ états peut être simulé par un automate fini déterministe à au plus $2^{n}$ états, et que cette borne peut être atteinte.

La complexité en états d'un langage régulier est la taille, mesurée en nombre d'états, du plus petit automate fini, soit déterministe, soit non déterministe qui reconnaît ce langage. La complexité opérationnelle (en anglais Modèle:Citation étrangère) est la description de la complexité en états des diverses opérations sur les langages qui préservent leur régularité.

On distingue entre plusieurs problèmes dans cette thématique : la transformation d'un modèle d'automate en un autre, et la complexité des opérations sur les langages et leurs automates. Parfois, des résultats existent sur des sous-familles de langages réguliers. Enfin, il apparaît que dans le cas des langages sur un alphabet de taille donnée, et notamment sur un alphabet à une seule lettre (alphabet unaire), des résultats plus précis peuvent être formulés. Plusieurs exposés de synthèse ont été rédigés sur ces problèmes, par Holzer et Kutrib^[1]Modèle:,^[2] et par Gao Modèle:Et al.^[3].

La détermination de la complexité d'un opération ou d'une transformation demande deux informations : d'abord un procédé général dont on sait majorer le coût, en nombre d'états, dans tous les cas ; ensuite un jeu d'exemples qui montrent que la majoration est en fait une borne supérieure, c'est-à-dire effectivement atteinte. L'exemple le plus connu est la déterminisation d'un automate fini non déterministe à n états : l'algorithme de la construction par sous-ensembles fournit un automate qui a toujours au plus $2^{n}$ états ; la deuxième étape demande de fournir des exemples où cette borne est effectivement atteinte.

Transformation entre variantes d'automates finis

Un automate fini peut être déterministe ou non déterministe, unidirectionnel (noté AFD, AFN) ou bidirectionnel (noté alors 2AFD, 2AFN). D'autres types sont les automates inambigus (notés UFA), Modèle:Lien (SVFA) et les automates alternants (AFA). Ces automates peuvent également être bidirectionnels (les classes sont ntées 2UFA, 2SVFA, 2AFA).

Tous ces modèles de machines reconnaissent exactement les langages rationnels. Toutefois, la taille de ces différents types d'automates, mesurée en nombre d'états, peut être différente. Le gain (la perte) de complexité entre deux de ces types d'automates est une fonction $f$ , qui, pour un automate du premier type à $n$ état, associe le nombre minimal $f (n)$ d'état d'un automate du deuxième type qui est reconnaît le même langage.

Voici les résultats de complexité pour les diverses opérations de transformation.

De AFN en AFD: $2^{n}$ états. C'est la construction par sous-ensembles de Rabin et Scott^[4], l'optimalité a été prouvée par Lupanov^[5].
De UFA en AFD : $2^{n}$ états^[6]. Une borne inférieure plus petite est de Schmidt^[7].
De AFN en UFA : $2^{n} - 1$ états^[6]. Une borne inférieure plus petite est de Schmidt^[7].
De SVFA en AFD : $Θ (3^{n / 3})$ états^[8]
De 2AFD en AFD : $n (n^{n} - (n - 1)^{n})$ états^[9]. Une construction plus ancienne par John Cedric Shepherdson^[10] utilise plus d'états, et une borne inférieure par Frank R. Moore ^[11] est moins bonne.
De 2AFD en AFN : $(\binom{2 n}{n + 1}) = O (\frac{4^{n}}{\sqrt{n}})$ états^[9]. Une construction antérieure par Birget^[12] utilise plus d'états.
De 2AFN en AFN : $(\binom{2 n}{n + 1})$ ^[9].
De AFA en AFD : $2^{2^{n}}$ états, démonstration par Ashok K. Chandra, Dexter Kozen et Larry Stockmeyer en 1981^[13]
De AFA en AFN : $2^{n}$ états^[14]
De 2AFA en AFD : $2^{n 2^{n}}$ états^[15]
De 2AFA en AFN : $2^{Θ (n \log n)}$ états^[16]

Résumé

Complexité de transformation
	AFD	UFA	AFN
AFN	$2^{n}$	$2^{n} - 1$	-
UFA	$2^{n}$	-
SVFA	$Θ (3^{n / 3})$
2AFD	$n (n^{n} - (n - 1)^{n})$		$(\binom{2 n}{n + 1})$
2AFN			$(\binom{2 n}{n + 1})$
AFA	$2^{2^{n}}$		$2^{n}$
2AFA	$2^{n 2^{n}}$		$2^{Θ (n \log n)}$

Le problème 2AFD versus 2AFN et l’espace logarithmique

Le problème suivant est ouvert : Peut-on déterminiser un automate bidirectionnel non déterministe (2AFN), c'est-à-dire le convertir en un automate bidirectionnel déterministe (2AFD) ayant un nombre polynomial d'états, en d'autres termes avec $p (n)$ états pour un automate de départ à $n$ et un polynôme $p (n)$ . Ce problème a été posé en 1978 par William J. Sakoda et Michael Sipser^[17]. Piotr Berman et Andrzej Lingas^[18] ont découvert une relation entre ce problème et le problème ouvert du lien etre les classes de complexité L et NL. Cette relation a été apporfondie par Christos Kapoutsis^[19].

Complexité en états d'opérations entre langages

Étant donné une opération binaire $\circ$ entre langages formes préservant la régularité et une famille $X$ d'automates (déterministe, non déterministe etc.) la complexité en états de l'opération $\circ$ est une fonction $f (m, n)$ telle que

pour toute paire d'automates $A$ à $m$ états et $B$ à $n$ états de la famille $X$ , il existe un automate à $f (m, n)$ états de la famille $X$ qui accepte le langage $L (A) \circ L (B)$
pour toute paire d'entiers $m, n$ , il existe un automate $A$ à $m$ états et un automate $B$ à $n$ états dans la famille X telle que tout automate de la famille $X$ acceptant $L (A) \circ L (B)$ a au moins $f (m, n)$ états.

Des définitions analogues valent pour des opérations a plus de deux arguments.

Les premiers résultats sur la complexité des opérations, pour les automates finis déterministes, ont été publiés par A. N. Maslov en 1970^[20], d'autre travaux pionniers, plus récents sont de Sheng Yu, Qingyu Zhuang et Kai Salomaa en 1994^[21] et de Markus Holzer et Martin Kutrib en 2003^[22]

On suppose que $L_{1}$ est accepté par un automate à $m$ états, et $L_{2}$ par un automate à $n$ états ; on demande le nombre d'états.

Union

Nombre d'états nécessaires pour $L_{1} \cup L_{2}$ :

AFD: $m n$ états, démontré par Maslov^[20] et Yu, Zhuang et Salomaa^[21].
AFN: $m + n + 1$ états, établi par Holzer et Kutrib^[22].
UFA: entre $m n + m + n$ et $O (n 2^{0.79 m})$ états^[23]
SVFA: $m n$ états^[24]
2AFD: entre $m + n$ et $4 m + n + 4$ états^[25]
2AFN: $m + n$ états^[26]

Intersection

Nombre d'états nécessaires pour $L_{1} \cap L_{2}$ :

AFD: $m n$ états^[20]Modèle:,^[21].
AFN: $m n$ états^[22].
UFA: $m n$ états^[23].
SVFA: $m n$ états^[24].
2AFD: soit $m + n$ soit $m + n + 1$ états, par Kunc et Okhotin^[25].
2AFN: soit $m + n$ soit $m + n + 1$ états^[26].

Complémentation

Si le langage L requiert $n$ états, le complément demande le nombre d'états suivant :

AFD: $n$ états, en échangeant les états acceptants et les autres.
AFN: $2^{n}$ états, par Birget^[27]
UFA: au moins $n^{d}$ pour tout $d$ et au plus $\sqrt{n + 1} 2^{n / 2}$ états d'après Raskin (2018)^[28] pour la borne inférieure et Indzhev et Kiefer^[29] pour la borne supérieure.
SVFA: $n$ états, par échange d'états acceptants et non acceptants.
2AFD: au moins $n$ et au plus $4 n$ états^[30].

Concaténation

Nombre d'états requis pour le produit $L_{1} L_{2} = {w_{1} w_{2} ∣ w_{1} \in L_{1}, w_{2} \in L_{2}}$ :

AFD: $m \cdot m 2^{n} - 2^{n - 1}$ états, déjà Maslov ^[20] et Yu, Zhuang et Salomaa^[21].
AFN: $m + n$ états, Holzer et Kutrib^[22].
UFA: $\frac{3}{4} 2^{m + n} - 1$ états^[23].
SVFA: $Θ (3^{n / 3} 2^{m})$ états^[24].
2AFD: au moins $\frac{2^{Ω (n)}}{\log m}$ et au plus $2 m^{m + 1} \cdot 2^{n^{n + 1}}$ états^[31].

Voir aussi Bordihn, Hospodár et. al. (2019)^[32].

Étoile de Kleene

AFD: $\frac{3}{4} 2^{n}$ états, déjà Maslov^[20] et Yu, Zhuang et Salomaa^[21].
AFN: $n + 1$ états^[22].
UFA: $\frac{3}{4} 2^{n}$ états^[23].
SVFA: $\frac{3}{4} 2^{n}$ états^[24].
2AFD: au moins $\frac{1}{n} 2^{\frac{n}{2} - 1}$ et au plus $2^{O (n^{n + 1})}$ états^[31].

Transposé

AFD: $2^{n}$ états, par Boris G. Mirkin^[33], Ernst Leiss^[34], et Yu, Zhuang et Salomaa^[21].
AFN: $n + 1$ états^[22].
UFA: $n$ états.
SVFA: $2 n + 1$ états^[24].
2AFD: soit $n + 1$ soit $n + 2$ états^[31].

Résumé

La table suivante résume les complexités ; elle figure aussi en partie dans l'article d'Okhotin et Salomaa^[35] où contient les bornes connues en 2017 pour la complexité des opérations pour les automates finis déterministes (AFD), inambigus (UFA), non déterministes(AFN).

Complexité des opérations binaires
	AFD	AFN	UFA	SVFA	2AFD	2AFN
union	$m n$	$m + n + 1$	$m n + m + n \leq \cdot \leq m + O (n 2^{0.79 m})$	$m n$	$m + n \leq \cdot \leq 4 m + n + 4$	$m + n$
intersection	$m n$	$m n$	$m n$	$m n$	$m + n \leq \cdot \leq m + n + 1$	$m + n \leq \cdot \leq m + n + 1$
complément	$n$	$2^{n}$	$n^{2 - o (1)} \leq \cdot \leq \sqrt{n + 1} 2^{n / 2}$	$n$	$n \leq \cdot \leq 4 n$
concaténation	$m 2^{n} - 2^{n - 1}$	$m + n$	$3 / 4 2^{m + n} - 1$	$Θ (3^{n / 3} 2^{m})$	$\frac{2^{Ω (n)}}{\log m} \leq \cdot \leq 2 m^{m + 1} \cdot 2^{n^{n + 1}}$
étoile	$3 / 4 \cdot 2^{n}$	$n + 1$	$3 / 4 \cdot 2^{n}$	$3 / 4 \cdot 2^{n}$	$\frac{1}{n} 2^{n / 2 - 1} \leq \cdot \leq 2^{O (n^{n + 1})}$
transposé	$2^{n}$	$n + 1$	$n$	$2 n + 1$	$n + O (1)$

Une variante est la complexité en états d'opérations inambigues sur les automates. Des résultats ont été présentés à la International Conference on Descriptional Complexity of Formal Systems (2018) ; l'article détaillé intitulé « State complexity of unambiguous operations on finite automata » de Galina Jirásková et Alexander Okhotin paraît en décembre 2019^[36]. La borne en $\sqrt{n + 1} 2^{n / 2}$ états pour le complémentaire d'un automate fini non ambigu avec $n$ états est d'Emil Indzhev et Stefan Kiefer^[29]

Automates finis sur un alphabet unaire

L'étude de la complexité en états des automates finis sur un alphabet à une seule lettre (alphabet « unaire ») a été initiée par Marek Chrobak en 1986^[37]. Les résultats sont différents car la structure particulière des automates unaires fait naturellement appel à des fonctions de théorie des nombres.

Soit $g (n) = e^{Θ (\sqrt{n \ln n})}$ la fonction de Landau.

Transformation entre modèles

Les transformations sont parfois plus efficaces que dans le cas général.

De AFN en AFD: $g (n) + O (n^{2})$ états^[37].
De 2AFD en AFD: $g (n) + O (n)$ états^[37] et Kunc et Okhotin^[38]
De 2AFN en AFD: $O (g (n))$ états^[38], Mereghetti et Giovanni Pighizzini^[39] et Geffert, Mereghetti et Pighizzini^[40].
De AFN en 2AFD: au plust $O (n^{2})$ ^[37].
De 2AFN en 2AFD: au plua $n^{O (\log n)}$ états ; majoration établie avec la méthode du théorème de Savitch^[40].
De UFA en AFD: $e^{Θ (\sqrt[3]{n (\ln n)^{2}})}$ états^[41].
De AFN en UFA: $g (n) + O (n^{2})$ états^[41].

Union

AFD: $m n$ états, par Yu, Zhuang et Salomaa^[21].
AFN: $m + n + 1$ états, par Holzer et Kutrib^[22].
2AFD: entre $m + n$ et $2 m + n + 4$ états^[25].
2AFN: $m + n$ états^[26].

Intersection

AFD: $m n$ états, par Yu, Zhuang et Salomaa^[21].
AFN: $m n$ états, par Holzer et Kutrib^[22].
2AFD: entre $m + n$ et $m + n + 1$ états^[25].
2AFN: entre $m + n$ et $m + n + 1$ états^[26].

Complémentation

AFD: $n$ états.
AFN: $g (n) + O (n^{2})$ états^[22].
UFA: au moins $n^{2 - o (1)}$ et au plus $e^{Θ (\sqrt[3]{n (\ln n)^{2}})}$ états^[41].
2AFD: au moins $n$ et au plus $2 n + 3$ états^[25].
2AFN: au moins $n$ et au plus $O (n^{8})$ états. La majoration est obtenue avec la méthode du théorème d'Immerman-Szelepcsényi^[30].

Concaténation

AFD: $m n$ états^[21].
AFN: entre $m + n - 1$ et $m + n$ états^[22].
2AFD: $e^{Θ (\sqrt{(m + n) \log (m + n)})}$ états^[25].
2AFN: $e^{Θ (\sqrt{(m + n) \log (m + n)})}$ états^[25].

Étoile de Kleene

AFD: $(n - 1)^{2} + 1$ états, déjà Yu, Zhuang et Salomaa^[21].
AFN: $n + 1$ états^[22].
UFA: $(n - 1)^{2} + 1$ états^[41].
2AFD: $Θ ((g (n))^{2})$ états^[25].
2AFN: $Θ (g (n))$ états^[25].

Résumé

La table suivante résume ces complexités.

Complexité des opérations binaires
	AFD	AFN	UFA	2AFD	2AFN
union	$m n$	$m + n + 1$	-	$m + n \leq \cdot \leq 2 m + n + 4$	$m + n$
intersection	$m n$	$m n$	-	$m + n \leq \cdot \leq m + n + 1$	$m + n \leq \cdot \leq m + n + 1$
complémentation	$n$	$g (n) + O (n^{2})$	$n^{2 - o (1)} \leq \cdot \leq e^{Θ (\sqrt[3]{n (\ln n)^{2}})}$	$n \leq \cdot \leq 2 n + 3$	$n \leq \cdot \leq O (n^{8})$
concaténation	$m n$	$m + n - 1 \leq \cdot \leq m + n$	-	$e^{Θ (\sqrt{(m + n) \log (m + n)})}$	$e^{Θ (\sqrt{(m + n) \log (m + n)})}$
étoile	$(n - 1)^{2} + 1$	$n + 1$	$(n - 1)^{2} + 1$	$Θ ((g (n))^{2})$	$Θ (g (n))$

Opérations combinées

Janusz A. Brzozowski a publié des articles^[42], où il étudie l'influence de divers paramètres sur la complexité en états. Il définit une famille de langages qui pour certaines opérations atteignent les bornes supérieures, à l'aide d'une famille particulière d'automates appelés automates de Brzozowski par Caron et al.^[43].

La complexité pour des opérations combinées a été étudiée par Bo Cui, Yuan Gao, Lila Kari, Kai Salomaa et Sheng Yu et d'autres dans une série d'articles ^[44]Modèle:,^[45]Modèle:,^[46].

La complexité de deux opérations combinées est majorée par la composition des majorations de chacune des opérations, mais les bornes supérieures atteintes dans chacune des opérations peuvent se simplifier dans leur composition, puisque le résultat d'une première opération n'est pas toujours un automate qui peut atteindre la borne pour la deuxième.

Ainsi, la complexité de la concaténation d'un AFD à $m$ états et d’un AFD à $n$ états est $(m - 1) 2^{n} + 2^{n - 1}$ ; la complexité d’une opération booléenne d’un AFD à $n$ états et d'un AFD à $p$ états est $n p$ . La combinaison d'une concatéation et d'une intersection (un langage $L_{1} \dot{(} L_{2} \cap L_{3})$ ) est $(m - 1) 2^{n p} + 2^{n p - 1}$ , alors que dans la combinaison avec une union $L_{1} \dot{(} L_{2} \cup L_{3})$ , elle descend à $(m - 1) (2^{n + p} - 2^{n} - 2^{p} + 2) + 2^{n + p - 2}$ ^[44].

Jozef Jirásek et Galina Jirásková^[47] étudient la complexité du bord d'un langage rationnel. Pour un langage rationnel $L$ donné, le bord est par définition le langage

B (L) = L^{*} \cap (L^{c})^{*}

,

c'est-à-dire l'intersection de l’étoile d'un langage et de l’étoile de son complémentaire. Ici, la complémentation est notée par l'exposant c. Si $n$ est la complexité en état de $L$ , alors la complexité du complémentaire $L^{c}$ est également $n$ , et la complexité en état de $L^{*}$ et de $(L^{c})^{*}$ est au plus $3 / 4 \cdot 2^{n}$ . Les auteurs montrent que la complexité en état du bord $B (L) = L^{*} \cap (L^{c})^{*}$ est en $O (4^{n})$ . La majoration est, plus précisément, $3 / 8 \cdot 4^{n} + 2^{n - 2} - 2 \cdot 3^{n - 2} - (n - 2)$ . Cette borne est atteinte sur alphabet à 5 lettres, sur 4 lettres elle est la même à une unité près^[47].

Une approche plus algébrique du problème est proposée par Pascal Caron et. al.^[43]. Ils montrent que les opérations de la forme $L_{1} \dot{(} L_{2} \circ L_{3})$ se ramènent, quitte à remplacer les langages $L_{2}$ ou $L_{3}$ par leur complémentaires, aux trois cas où l'opération $\circ$ est l’union, l'intersection et la différence symétrique. Ils obtiennent des bornes qui s'expriment à l'aide de fonctions connues en combinatoire algébrique. Un autre article^[48] traite de concaténations multiples ; ils montrent que la borne supérieure est atteinte sur un alphabet à $k + 1$ lettres pour $k$ concaténations. Ils précisent aussi l'expression de la complexité en états, et utilisent les automates de Brzozowski dans ces développements^[49]. Ils systématisent ensuite leur approche et donnent plusieurs applications^[50]Modèle:,^[51]Modèle:,^[52].

Autres travaux

De nouveaux résultats sur la complexité en états sont présentés régulièrement dans des conférences comme Descriptional Complexity of Formal Systems (DCFS) et Conference on Implementation and Application of Automata (CIAA), et dans diverses autres conférences en informatique théorique ou dans des revues spécialisées^[53]Modèle:,^[54]Modèle:,^[55]. Un autre article concerne les opérations sur les langages unaires^[56].

Articles liés

Références

Modèle:Traduction/Référence Modèle:Références

Modèle:Palette Modèle:Portail

↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées HolzerKutrib2009
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées HolzerKutrib2011
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées GaoMoreiraReisYu
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées RabinScott1959
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Lupanov
↑ ^6,0 et ^6,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Leung2005
↑ ^7,0 et ^7,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Schmidt1978
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées JiráskováPighizzini2011
↑ ^9,0 ^9,1 et ^9,2 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Kapoutsis2005
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Shepherdson1959
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Moore1971
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Birget1993a
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées ChandraKozen1981
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées FellahJürgensen1990
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées LadnerLipton1984
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées GeffertOkhotin2014
↑ Modèle:Article
↑ Modèle:Article
↑ Modèle:Article
↑ ^20,0 ^20,1 ^20,2 ^20,3 et ^20,4 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Maslov
↑ ^21,00 ^21,01 ^21,02 ^21,03 ^21,04 ^21,05 ^21,06 ^21,07 ^21,08 et ^21,09 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées YuZhuang1994
↑ ^22,00 ^22,01 ^22,02 ^22,03 ^22,04 ^22,05 ^22,06 ^22,07 ^22,08 ^22,09 et ^22,10 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées HolzerKutrib2003
↑ ^23,0 ^23,1 ^23,2 et ^23,3 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées JirásekJirásková2016
↑ ^24,0 ^24,1 ^24,2 ^24,3 et ^24,4 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées JirásekJirásková2015
↑ ^25,0 ^25,1 ^25,2 ^25,3 ^25,4 ^25,5 ^25,6 ^25,7 et ^25,8 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées KuncOkhotin2012
↑ ^26,0 ^26,1 ^26,2 et ^26,3 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées KuncOkhotin2011
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Birget1993b
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Raskin2018
↑ ^29,0 et ^29,1 Modèle:Article.
↑ ^30,0 et ^30,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées GeffertMereghetti2007
↑ ^31,0 ^31,1 et ^31,2 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées JiráskováOkhotin2008
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées BordihnHospodár2019
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Mirkin1966
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Leiss1985
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées OkhotinSalomaa2017
↑ Modèle:Article.
↑ ^37,0 ^37,1 ^37,2 et ^37,3 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Chrobak1986
↑ ^38,0 et ^38,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées KuncOkhotin2011b
↑ Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées MereghettiPighizzini2001
↑ ^40,0 et ^40,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées GeffertMereghetti2003
↑ ^41,0 ^41,1 ^41,2 et ^41,3 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Okhotin2012
↑ Par exemple Modèle:Article.
↑ ^43,0 et ^43,1 Modèle:Article
↑ ^44,0 et ^44,1 Modèle:Article
↑ Modèle:Article
↑ Modèle:Article
↑ ^47,0 et ^47,1 Modèle:Article.
↑ Modèle:Article
↑ Modèle:Article.
↑ Modèle:Article.
↑ Modèle:Article
↑ Modèle:Article.
↑ Modèle:Article.
↑ Modèle:Article
↑ Modèle:Article.
↑ Modèle:Article

[HolzerKutrib2009-1] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées HolzerKutrib2009

[HolzerKutrib2011-2] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées HolzerKutrib2011

[GaoMoreiraReisYu-3] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées GaoMoreiraReisYu

[RabinScott1959-4] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées RabinScott1959

[Lupanov-5] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Lupanov

[Leung2005-6] 6,0 et ^6,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Leung2005

[Schmidt1978-7] 7,0 et ^7,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Schmidt1978

[JiráskováPighizzini2011-8] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées JiráskováPighizzini2011

[Kapoutsis2005-9] 9,0 ^9,1 et ^9,2 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Kapoutsis2005

[Shepherdson1959-10] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Shepherdson1959

[Moore1971-11] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Moore1971

[Birget1993a-12] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Birget1993a

[ChandraKozen1981-13] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées ChandraKozen1981

[FellahJürgensen1990-14] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées FellahJürgensen1990

[LadnerLipton1984-15] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées LadnerLipton1984

[GeffertOkhotin2014-16] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées GeffertOkhotin2014

[17] Modèle:Article

[18] Modèle:Article

[19] Modèle:Article

[Maslov-20] 20,0 ^20,1 ^20,2 ^20,3 et ^20,4 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Maslov

[YuZhuang1994-21] 21,00 ^21,01 ^21,02 ^21,03 ^21,04 ^21,05 ^21,06 ^21,07 ^21,08 et ^21,09 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées YuZhuang1994

[HolzerKutrib2003-22] 22,00 ^22,01 ^22,02 ^22,03 ^22,04 ^22,05 ^22,06 ^22,07 ^22,08 ^22,09 et ^22,10 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées HolzerKutrib2003

[JirásekJirásková2016-23] 23,0 ^23,1 ^23,2 et ^23,3 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées JirásekJirásková2016

[JirásekJirásková2015-24] 24,0 ^24,1 ^24,2 ^24,3 et ^24,4 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées JirásekJirásková2015

[KuncOkhotin2012-25] 25,0 ^25,1 ^25,2 ^25,3 ^25,4 ^25,5 ^25,6 ^25,7 et ^25,8 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées KuncOkhotin2012

[KuncOkhotin2011-26] 26,0 ^26,1 ^26,2 et ^26,3 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées KuncOkhotin2011

[Birget1993b-27] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Birget1993b

[Raskin2018-28] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Raskin2018

[IndzhevKiefer2022-29] 29,0 et ^29,1 Modèle:Article.

[GeffertMereghetti2007-30] 30,0 et ^30,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées GeffertMereghetti2007

[JiráskováOkhotin2008-31] 31,0 ^31,1 et ^31,2 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées JiráskováOkhotin2008

[BordihnHospodár2019-32] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées BordihnHospodár2019

[Mirkin1966-33] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Mirkin1966

[Leiss1985-34] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Leiss1985

[OkhotinSalomaa2017-35] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées OkhotinSalomaa2017

[JiráskováOkhotin2019-36] Modèle:Article.

[Chrobak1986-37] 37,0 ^37,1 ^37,2 et ^37,3 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Chrobak1986

[KuncOkhotin2011b-38] 38,0 et ^38,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées KuncOkhotin2011b

[MereghettiPighizzini2001-39] Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées MereghettiPighizzini2001

[GeffertMereghetti2003-40] 40,0 et ^40,1 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées GeffertMereghetti2003

[Okhotin2012-41] 41,0 ^41,1 ^41,2 et ^41,3 Erreur de référence : Balise <ref> incorrecte : aucun texte n’a été fourni pour les références nommées Okhotin2012

[Brzozowski2013-42] Par exemple Modèle:Article.

[CaronLuque2016-43] 43,0 et ^43,1 Modèle:Article

[CuiGao2011-44] 44,0 et ^44,1 Modèle:Article

[GaoYu2012-45] Modèle:Article

[GaoSalomaa2008-46] Modèle:Article

[JirásekJirásková-2015-47] 47,0 et ^47,1 Modèle:Article.

[CaronPatrou2016-48] Modèle:Article

[CaronLuque2019-49] Modèle:Article.

[50] Modèle:Article.

[51] Modèle:Article

[CaronHamel-de_le_Court2019-52] Modèle:Article.

[53] Modèle:Article.

[54] Modèle:Article

[55] Modèle:Article.

[56] Modèle:Article

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

Complexité en états

Sommaire

Transformation entre variantes d'automates finis

Résumé

Le problème 2AFD versus 2AFN et l’espace logarithmique

Complexité en états d'opérations entre langages

Union

Intersection

Complémentation

Concaténation

Étoile de Kleene

Transposé

Résumé

Automates finis sur un alphabet unaire

Transformation entre modèles

Union

Intersection

Complémentation

Concaténation

Étoile de Kleene

Résumé

Opérations combinées

Autres travaux

Articles liés

Références

Menu de navigation

Complexité en états

Transformation entre variantes d'automates finis

Résumé

Le problème 2AFD versus 2AFN et l’espace logarithmique

Complexité en états d'opérations entre langages

Union

Intersection

Complémentation

Concaténation

Étoile de Kleene

Transposé

Résumé

Automates finis sur un alphabet unaire

Transformation entre modèles

Union

Intersection

Complémentation

Concaténation

Étoile de Kleene

Résumé

Opérations combinées

Autres travaux

Articles liés

Références

Menu de navigation

Rechercher