Complexité en états

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].

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]

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))}$