# Complexité en états

La complexité en états (en anglais « state complexity ») 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 « operational state complexity ») 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$^,$ et par Gao et al..
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), 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 $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, l'optimalité a été prouvée par Lupanov.
* De UFA en AFD : $2^{n}$ états. Une borne inférieure plus petite est de Schmidt.
* De AFN en UFA : $2^{n}-1$ états. Une borne inférieure plus petite est de Schmidt.
* De SVFA en AFD : $\Theta (3^{n/3})$ états
* De 2AFD en AFD : $n(n^{n}-(n-1)^{n})$ états. Une construction plus ancienne par John Cedric Shepherdson utilise plus d'états, et une borne inférieure par Frank R. Moore est moins bonne.
* De 2AFD en AFN : ${\binom {2n}{n+1}}=O\left({\frac {4^{n}}{\sqrt {n}}}\right)$ états. Une construction antérieure par Birget utilise plus d'états.
* De 2AFN en AFN : ${\binom {2n}{n+1}}$.
* De AFA en AFD : $2^{2^{n}}$ états, démonstration par Ashok K. Chandra, Dexter Kozen et Larry Stockmeyer en 1981
* De AFA en AFN : $2^{n}$ états
* De 2AFA en AFD : $2^{n2^{n}}$ états
* De 2AFA en AFN : $2^{\Theta (n\log n)}$ états

### Résumé

    Complexité de transformation AFD UFA AFN AFN$2^{n}$$2^{n}-1$- UFA$2^{n}$- SVFA$\Theta (3^{n/3})$ 2AFD$n(n^{n}-(n-1)^{n})$${\binom {2n}{n+1}}$ 2AFN${\binom {2n}{n+1}}$ AFA$2^{2^{n}}$$2^{n}$ 2AFA$2^{n2^{n}}$$2^{\Theta (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. Piotr Berman et Andrzej Lingas 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.

## 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, d'autre travaux pionniers, plus récents sont de Sheng Yu, Qingyu Zhuang et Kai Salomaa en 1994 et de Markus Holzer et Martin Kutrib en 2003
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: $mn$ états, démontré par Maslov et Yu, Zhuang et Salomaa.
* AFN: $m+n+1$ états, établi par Holzer et Kutrib.
* UFA: entre $mn+m+n$ et $O(n2^{0.79m})$ états
* SVFA: $mn$ états
* 2AFD: entre $m+n$ et $4m+n+4$ états
* 2AFN: $m+n$ états

### Intersection

Nombre d'états nécessaires pour $L_{1}\cap L_{2}$ :
* AFD: $mn$ états$^,$.
* AFN: $mn$ états.
* UFA: $mn$ états.
* SVFA: $mn$ états.
* 2AFD: soit $m+n$ soit $m+n+1$ états, par Kunc et Okhotin.
* 2AFN: soit $m+n$ soit $m+n+1$ états.

### 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
* UFA: au moins $n^{d}$ pour tout $d$ et au plus ${\sqrt {n+1}}\,2^{n/2}$ états d'après Raskin (2018) pour la borne inférieure et Indzhev et Kiefer pour la borne supérieure.
* SVFA: $n$ états, par échange d'états acceptants et non acceptants.
* 2AFD: au moins $n$ et au plus $4n$ états.

### Concaténation

Nombre d'états requis pour le produit $L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}$ :
* AFD: $m\cdot m2^{n}-2^{n-1}$ états, déjà Maslov et Yu, Zhuang et Salomaa.
* AFN: $m+n$ états, Holzer et Kutrib.
* UFA: ${\frac {3}{4}}2^{m+n}-1$ états.
* SVFA: $\Theta (3^{n/3}2^{m})$ états.
* 2AFD: au moins ${\frac {2^{\Omega (n)}}{\log m}}$ et au plus $2m^{m+1}\cdot 2^{n^{n+1}}$ états.
Voir aussi Bordihn, Hospodár et. al. (2019).

### Étoile de Kleene

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

### Transposé

* AFD: $2^{n}$ états, par Boris G. Mirkin, Ernst Leiss, et Yu, Zhuang et Salomaa.
* AFN: $n+1$ états.
* UFA: $n$ états.
* SVFA: $2n+1$ états.
* 2AFD: soit $n+1$ soit $n+2$ états.

### Résumé

La table suivante résume les complexités ; elle figure aussi en partie dans l'article d'Okhotin et Salomaa 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$mn$$m+n+1$$mn+m+n\leq \cdot \leq m+O(n2^{0.79m})$$mn$$m+n\leq \cdot \leq 4m+n+4$$m+n$ intersection$mn$$mn$$mn$$mn$$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 4n$ concaténation$m2^{n}-2^{n-1}$$m+n$$3/42^{m+n}-1$$\Theta (3^{n/3}2^{m})$${\frac {2^{\Omega (n)}}{\log m}}\leq \cdot \leq 2m^{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$$2n+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. 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

## 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. 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^{\Theta ({\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.
* De 2AFD en AFD: $g(n)+O(n)$ états et Kunc et Okhotin
* De 2AFN en AFD: $O(g(n))$ états, Mereghetti et Giovanni Pighizzini et Geffert, Mereghetti et Pighizzini.
* De AFN en 2AFD: au plust $O(n^{2})$.
* De 2AFN en 2AFD: au plua $n^{O(\log n)}$ états ; majoration établie avec la méthode du théorème de Savitch.
* De UFA en AFD: $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ états.
* De AFN en UFA: $g(n)+O(n^{2})$ états.

### Union

* AFD: $mn$ états, par Yu, Zhuang et Salomaa.
* AFN: $m+n+1$ états, par Holzer et Kutrib.
* 2AFD: entre $m+n$ et $2m+n+4$ états.
* 2AFN: $m+n$ états.

### Intersection

* AFD: $mn$ états, par Yu, Zhuang et Salomaa.
* AFN: $mn$ états, par Holzer et Kutrib.
* 2AFD: entre $m+n$ et $m+n+1$ états.
* 2AFN: entre $m+n$ et $m+n+1$ états.

### Complémentation

* AFD: $n$ états.
* AFN: $g(n)+O(n^{2})$ états.
* UFA: au moins $n^{2-o(1)}$ et au plus $e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ états.
* 2AFD: au moins $n$ et au plus $2n+3$ états.
* 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.

### Concaténation

* AFD: $mn$ états.
* AFN: entre $m+n-1$ et $m+n$ états.
* 2AFD: $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ états.
* 2AFN: $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ états.

### Étoile de Kleene

* AFD: $(n-1)^{2}+1$ états, déjà Yu, Zhuang et Salomaa.
* AFN: $n+1$ états.
* UFA: $(n-1)^{2}+1$ états.
* 2AFD: $\Theta ((g(n))^{2})$ états.
* 2AFN: $\Theta (g(n))$ états.

### Résumé

La table suivante résume ces complexités.
    Complexité des opérations binaires AFD AFN UFA 2AFD 2AFN union$mn$$m+n+1$-$m+n\leq \cdot \leq 2m+n+4$$m+n$ intersection$mn$$mn$-$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^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$$n\leq \cdot \leq 2n+3$$n\leq \cdot \leq O(n^{8})$ concaténation$mn$$m+n-1\leq \cdot \leq m+n$-$e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$$e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ étoile$(n-1)^{2}+1$$n+1$$(n-1)^{2}+1$$\Theta ((g(n))^{2})$$\Theta (g(n))$

## Opérations combinées

Janusz A. Brzozowski a publié des articles, 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..
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 $^,$$^,$.
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 $np$. La combinaison d'une concatéation et d'une intersection (un langage $L_{1}{\dot {}L_{2}\cap L_{3})$) est $(m-1)2^{np}+2^{np-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}$.
Jozef Jirásek et Galina Jirásková é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.
Une approche plus algébrique du problème est proposée par Pascal Caron et. al.. 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 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. Ils systématisent ensuite leur approche et donnent plusieurs applications$^,$$^,$.

## 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$^,$$^,$. Un autre article concerne les opérations sur les langages unaires.

## Articles liés

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