Complexité en états

Un automate fini peut êtredéterministe ounon déterministe,unidirectionnel (noté AFD, AFN)ou bidirectionnel(noté alors 2AFD, 2AFN). D'autres types sont les automatesinambigus (notés UFA),automates auto-vérifiant (en) (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 ${\displaystyle f}$ , qui, pour un automate du premier type à ${\displaystyle n}$ état, associe le nombre minimal ${\displaystyle 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: ${\displaystyle 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 : ${\displaystyle 2^{n}}$ états^[6]. Une borne inférieure plus petite est de Schmidt^[7].
• De AFN en UFA : ${\displaystyle 2^{n}-1}$ états^[6]. Une borne inférieure plus petite est de Schmidt^[7].
• De SVFA en AFD : ${\displaystyle \Theta (3^{n/3})}$ états^[8]
• De 2AFD en AFD : ${\displaystyle 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 : ${\displaystyle {\binom {2n}{n+1}}=O\left({\frac {4^{n}}{\sqrt {n}}}\right)}$ états^[9]. Une construction antérieure par Birget^[12] utilise plus d'états.
• De 2AFN en AFN : ${\displaystyle {\binom {2n}{n+1}}}$ ^[9].
• De AFA en AFD : ${\displaystyle 2^{2^{n}}}$ états, démonstration par Ashok K. Chandra, Dexter Kozen et Larry Stockmeyer en 1981^[13]
• De AFA en AFN : ${\displaystyle 2^{n}}$ états^[14]
• De 2AFA en AFD : ${\displaystyle 2^{n2^{n}}}$ états^[15]
• De 2AFA en AFN : ${\displaystyle 2^{\Theta (n\log n)}}$ états^[16]

Complexité de transformation

	AFD	UFA	AFN
AFN	${\displaystyle 2^{n}}$	${\displaystyle 2^{n}-1}$	-
UFA	${\displaystyle 2^{n}}$	-
SVFA	${\displaystyle \Theta (3^{n/3})}$
2AFD	${\displaystyle n(n^{n}-(n-1)^{n})}$		${\displaystyle {\binom {2n}{n+1}}}$
2AFN			${\displaystyle {\binom {2n}{n+1}}}$
AFA	${\displaystyle 2^{2^{n}}}$		${\displaystyle 2^{n}}$
2AFA	${\displaystyle 2^{n2^{n}}}$		${\displaystyle 2^{\Theta (n\log n)}}$

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 ${\displaystyle p(n)}$ états pour un automate de départ à ${\displaystyle n}$ et un polynôme ${\displaystyle 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].

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

• pour toute paire d'automates ${\displaystyle A}$ à ${\displaystyle m}$ états et ${\displaystyle B}$ à ${\displaystyle n}$ états de la famille ${\displaystyle X}$ , il existe un automate à ${\displaystyle f(m,n)}$ états de la famille ${\displaystyle X}$ qui accepte le langage ${\displaystyle L(A)\circ L(B)}$
• pour toute paire d'entiers ${\displaystyle m,n}$ , il existe un automate ${\displaystyle A}$ à ${\displaystyle m}$ états et un automate ${\displaystyle B}$ à ${\displaystyle n}$ états dans la famille X telle que tout automate de la famille ${\displaystyle X}$ acceptant ${\displaystyle L(A)\circ L(B)}$ a au moins ${\displaystyle 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 deMarkus Holzer et Martin Kutrib en 2003^[22]

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

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

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

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

• AFD: ${\displaystyle mn}$ états^[20],[21].
• AFN: ${\displaystyle mn}$ états^[22].
• UFA: ${\displaystyle mn}$ états^[23].
• SVFA: ${\displaystyle mn}$ états^[24].
• 2AFD: soit ${\displaystyle m+n}$ soit ${\displaystyle m+n+1}$ états, par Kunc et Okhotin^[25].
• 2AFN: soit ${\displaystyle m+n}$ soit ${\displaystyle m+n+1}$ états^[26].

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

• AFD: ${\displaystyle n}$ états, en échangeant les états acceptants et les autres.
• AFN: ${\displaystyle 2^{n}}$ états, par Birget^[27]
• UFA: au moins ${\displaystyle n^{d}}$ pour tout ${\displaystyle d}$ et au plus ${\displaystyle {\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: ${\displaystyle n}$ états, par échange d'états acceptants et non acceptants.
• 2AFD: au moins ${\displaystyle n}$ et au plus ${\displaystyle 4n}$ états^[30].

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

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

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

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

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

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	${\displaystyle mn}$	${\displaystyle m+n+1}$	${\displaystyle mn+m+n\leq \cdot \leq m+O(n2^{0.79m})}$	${\displaystyle mn}$	${\displaystyle m+n\leq \cdot \leq 4m+n+4}$	${\displaystyle m+n}$
intersection	${\displaystyle mn}$	${\displaystyle mn}$	${\displaystyle mn}$	${\displaystyle mn}$	${\displaystyle m+n\leq \cdot \leq m+n+1}$	${\displaystyle m+n\leq {\cdot }\leq m+n+1}$
complément	${\displaystyle n}$	${\displaystyle 2^{n}}$	${\displaystyle n^{2-o(1)}\leq \cdot \leq {\sqrt {n+1}}\,2^{n/2}}$	${\displaystyle n}$	${\displaystyle n\leq \cdot \leq 4n}$
concaténation	${\displaystyle m2^{n}-2^{n-1}}$	${\displaystyle m+n}$	${\displaystyle 3/42^{m+n}-1}$	${\displaystyle \Theta (3^{n/3}2^{m})}$	${\displaystyle {\frac {2^{\Omega (n)}}{\log m}}\leq \cdot \leq 2m^{m+1}\cdot 2^{n^{n+1}}}$
étoile	${\displaystyle 3/4\cdot 2^{n}}$	${\displaystyle n+1}$	${\displaystyle 3/4\cdot 2^{n}}$	${\displaystyle 3/4\cdot 2^{n}}$	${\displaystyle {\frac {1}{n}}2^{n/2-1}\leq \cdot \leq 2^{O(n^{n+1})}}$
transposé	${\displaystyle 2^{n}}$	${\displaystyle n+1}$	${\displaystyle n}$	${\displaystyle 2n+1}$	${\displaystyle 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 ${\displaystyle {\sqrt {n+1}}\,2^{n/2}}$ états pour le complémentaire d'un automate fini non ambigu avec ${\displaystyle n}$ états est d'Emil Indzhev et Stefan Kiefer^[29]

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 ${\displaystyle g(n)=e^{\Theta ({\sqrt {n\ln n}})}}$ la fonction de Landau.

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

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

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

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

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

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

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

La table suivante résume ces complexités.

Complexité des opérations binaires

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

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],[45],[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 à ${\displaystyle m}$ états et d’un AFD à ${\displaystyle n}$ états est ${\displaystyle (m-1)2^{n}+2^{n-1}}$  ; la complexité d’une opération booléenne d’un AFD à ${\displaystyle n}$ états et d'un AFD à ${\displaystyle p}$ états est ${\displaystyle np}$ . La combinaison d'une concatéation et d'une intersection (un langage ${\displaystyle L_{1}{\dot {(}}L_{2}\cap L_{3})}$ ) est ${\displaystyle (m-1)2^{np}+2^{np-1}}$ , alors que dans la combinaison avec une union ${\displaystyle L_{1}{\dot {(}}L_{2}\cup L_{3})}$ , elle descend à ${\displaystyle (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 ${\displaystyle L}$ donné, le bord est par définition le langage

${\displaystyle 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 ${\displaystyle n}$ est la complexité en état de ${\displaystyle L}$ , alors la complexité du complémentaire ${\displaystyle L^{c}}$ est également ${\displaystyle n}$ , et la complexité en état de ${\displaystyle L^{*}}$ et de ${\displaystyle (L^{c})^{*}}$ est au plus ${\displaystyle 3/4\cdot 2^{n}}$ . Les auteurs montrent que la complexité en état du bord ${\displaystyle B(L)=L^{*}\cap (L^{c})^{*}}$ est en ${\displaystyle O(4^{n})}$ . La majoration est, plus précisément, ${\displaystyle 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 ${\displaystyle L_{1}{\dot {(}}L_{2}\circ L_{3})}$ se ramènent, quitte à remplacer les langages${\displaystyle L_{2}}$ ou ${\displaystyle L_{3}}$ par leur complémentaires, aux trois cas où l'opération ${\displaystyle \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 à ${\displaystyle k+1}$ lettres pour ${\displaystyle 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],[51],[52]}.

De nouveaux résultats sur la complexité en états sont présentés régulièrement dans des conférences commeDescriptional 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],[54],[55]}.

• Automate fini déterministe
• Automate fini inambigu
• Automate fini non déterministe
• Automate fini déterministe bidirectionnel
• Automate à pile visible