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[1]^,[2] et par Gao 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), 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[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 : $\Theta (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 {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 : ${\binom {2n}{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^{n2^{n}}$ états[15]
De 2AFA en AFN : $2^{\Theta (n\log n)}$ états[16]

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[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: $mn$ é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 $mn+m+n$ et $O(n2^{0.79m})$ états[23]
SVFA: $mn$ états[24]
2AFD: entre $m+n$ et $4m+n+4$ états[25]
2AFN: $m+n$ états[26]

Intersection

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

AFD: $mn$ états[20]^,[21].
AFN: $mn$ états[22].
UFA: $mn$ états[23].
SVFA: $mn$ é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 $4n$ états[30].

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 [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: $\Theta (3^{n/3}2^{m})$ états[24].
2AFD: au moins ${\frac {2^{\Omega (n)}}{\log m}}$ et au plus $2m^{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: $2n+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	$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[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^{\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[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^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ états[41].
De AFN en UFA: $g(n)+O(n^{2})$ états[41].

Union

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

Intersection

AFD: $mn$ états, par Yu, Zhuang et Salomaa[21].
AFN: $mn$ é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^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}$ états[41].
2AFD: au moins $n$ et au plus $2n+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: $mn$ états[21].
AFN: entre $m+n-1$ et $m+n$ états[22].
2AFD: $e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}$ états[25].
2AFN: $e^{\Theta ({\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: $\Theta ((g(n))^{2})$ états[25].
2AFN: $\Theta (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	$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[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 à $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}$ [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]^,[51]^,[52].

Recherches en cours

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.

Articles liés

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « State complexity » (voir la liste des auteurs).

(en) Markus Holzer et Martin Kutrib, « Nondeterministic finite automata — recent results on the descriptional and computational complexity », International Journal of Foundations of Computer Science, vol. 20, n^o 4,‎ 2009, p. 563–580 (ISSN 0129-0541, DOI 10.1142/S0129054109006747)
(en) Markus Holzer et Martin Kutrib, « Descriptional and computational complexity of finite automata—A survey », Information and Computation, vol. 209, n^o 3,‎ 2011, p. 456–470 (ISSN 0890-5401, DOI 10.1016/j.ic.2010.11.013)
(en) Yuan Gao, Nelma Moreira, Rogério Reis et Sheng Yu « A Survey on Operational State Complexity », 2015.
(en) M. O. Rabin et D. Scott, « Finite Automata and Their Decision Problems », IBM Journal of Research and Development, vol. 3, n^o 2,‎ 1959, p. 114–125 (ISSN 0018-8646, DOI 10.1147/rd.32.0114)
(en) Oleg B. Lupanov, « A comparison of two types of finite sources », Problemy Kibernetiki, vol. 9,‎ 1963, p. 321–326
(en) Hing Leung, « Descriptional complexity of NFA of different ambiguity », International Journal of Foundations of Computer Science, vol. 16, n^o 5,‎ 2005, p. 975–984 (ISSN 0129-0541, DOI 10.1142/S0129054105003418)
Erik M. Schmidt, Succinctness of Description of Context-Free, Regular and Unambiguous Languages, Cornell University, 1978
(en) Galina Jirásková et Giovanni Pighizzini, « Optimal simulation of self-verifying automata by deterministic automata », Information and Computation, vol. 209, n^o 3,‎ 2011, p. 528–535 (ISSN 0890-5401, DOI 10.1016/j.ic.2010.11.017)
(en) Christos Kapoutsis, « Removing Bidirectionality from Nondeterministic Finite Automata », Mathematical Foundations of Computer Science 2005, vol. 3618,‎ 2005, p. 544–555 (ISBN 978-3-540-28702-5, ISSN 0302-9743, DOI 10.1007/11549345_47)
(en) J. C. Shepherdson, « The Reduction of Two-Way Automata to One-Way Automata », IBM Journal of Research and Development, vol. 3, n^o 2,‎ 1959, p. 198–200 (ISSN 0018-8646, DOI 10.1147/rd.32.0198)
(en) Frank R. Moore, « On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata », IEEE Transactions on Computers, vol. C-20, n^o 10,‎ 1971, p. 1211–1214 (ISSN 0018-9340, DOI 10.1109/T-C.1971.223108)
(en) Jean-Camille Birget, « State-complexity of finite-state devices, state compressibility and incompressibility », Mathematical Systems Theory, vol. 26, n^o 3,‎ 1993, p. 237–269 (ISSN 0025-5661, DOI 10.1007/BF01371727)
(en) Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, n^o 1,‎ 1981, p. 114–133 (ISSN 0004-5411, DOI 10.1145/322234.322243)
(en) Abdelaziz Fellah, Helmut Jürgensen et Sheng Yu, « Constructions for alternating finite automata », International Journal of Computer Mathematics, vol. 35, n^os 1–4,‎ 1990, p. 117–132 (ISSN 0020-7160, DOI 10.1080/00207169008803893)
(en) Richard E. Ladner, Richard J. Lipton et Larry J. Stockmeyer, « Alternating Pushdown and Stack Automata », SIAM Journal on Computing, vol. 13, n^o 1,‎ 1984, p. 135–155 (ISSN 0097-5397, DOI 10.1137/0213010)
(en) Viliam Geffert et Alexander Okhotin, « Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata », Mathematical Foundations of Computer Science 2014, vol. 8634,‎ 2014, p. 291–302 (ISBN 978-3-662-44521-1, ISSN 0302-9743, DOI 10.1007/978-3-662-44522-8_25)
William J. Sakoda et Michael Sipser, « Nondeterminism and the Size of Two Way Finite Automata », ACM,‎ 1978, p. 275–286 (DOI 10.1145/800133.804357)
Piotr Berman et Andrzej Lingas, « On the complexity of regular languages in terms of finite automata », Report 304, Polish Academy of Sciences,‎ 1977
(en) Christos A. Kapoutsis, « Two-Way Automata Versus Logarithmic Space », Theory of Computing Systems, vol. 55, n^o 2,‎ 2014, p. 421–447 (DOI 10.1007/s00224-013-9465-0)
(en) A. N. Maslov, « Estimates of the number of states of finite automata », Soviet Mathematics Doklady, vol. 11,‎ 1970, p. 1373–1375
(en) Sheng Yu, Qingyu Zhuang et Kai Salomaa, « The state complexities of some basic operations on regular languages », Theoretical Computer Science, vol. 125, n^o 2,‎ 1994, p. 315–328 (ISSN 0304-3975, DOI 10.1016/0304-3975(92)00011-F)
(en) Markus Holzer et Martin Kutrib, « Nondeterministic descriptional complexity of regular languages », International Journal of Foundations of Computer Science, vol. 14, n^o 6,‎ 2003, p. 1087–1102 (ISSN 0129-0541, DOI 10.1142/S0129054103002199)
(en) Jozef Jirásek, Galina Jirásková et Juraj Šebej, « Operations on Unambiguous Finite Automata », Developments in Language Theory 2016, vol. 9840,‎ 2016, p. 243–255 (ISBN 978-3-662-53131-0, ISSN 0302-9743, DOI 10.1007/978-3-662-53132-7_20)
(en) Jozef Štefan Jirásek, Galina Jirásková et Alexander Szabari, « Operations on Self-Verifying Finite Automata », International Computer Science Symposium in Russia (CSR), vol. 9139,‎ 2015, p. 231–261 (ISSN 0302-9743, DOI 10.1007/978-3-319-20297-6_16)
(en) Michal Kunc et Alexander Okhotin, « State complexity of operations on two-way finite automata over a unary alphabet », Theoretical Computer Science, vol. 449,‎ 2012, p. 106–118 (ISSN 0304-3975, DOI 10.1016/j.tcs.2012.04.010)
(en) Michal Kunc et Alexander Okhotin, « State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata », Fundamenta Informaticae, vol. 110,‎ 2011, p. 231–239 (DOI 10.3233/FI-2011-540)
(en) Jean-Camille Birget, « Partial orders on words, minimal elements of regular languages, and state complexity », Theoretical Computer Science, vol. 119, n^o 2,‎ 1993, p. 267–291 (ISSN 0304-3975, DOI 10.1016/0304-3975(93)90160-U)
Mikhail Raskin, « A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton », Arxiv,‎ 14 février 2018 (arXiv 1711.03993). Accepté pour ICALP 2018 à Prague.
Emil Indzhev et Stefan Kiefer, « On complementing unambiguous automata and graphs with many cliques and cocliques », Information Processing Letters, vol. 177,‎ août 2022, article n^o 106270 (DOI 10.1016/j.ipl.2022.106270, arXiv 2105.07470).
(en) Viliam Geffert, Carlo Mereghetti et Giovanni Pighizzini, « Complementing two-way finite automata », Information and Computation, vol. 205, n^o 8,‎ 2007, p. 1173–1187 (ISSN 0890-5401, DOI 10.1016/j.ic.2007.01.008)
(en) Galina Jirásková et Alexander Okhotin, « On the State Complexity of Operations on Two-Way Finite Automata », Developments in Language Theory DLT, vol. 5257,‎ 2008, p. 443–454 (ISBN 978-3-540-85779-2, ISSN 0302-9743, DOI 10.1007/978-3-540-85780-8_35)
Henning Bordihn, Michal Hospodár, Galina Jirásková, Benedek Nagy et György Vaszil, « The complexity of concatenation on deterministic and alternating finite automata », RAIRO - Theoretical Informatics and Applications, vol. 52, n^os 2-3-4,‎ 2019, p. 153–168 (ISSN 0988-3754, DOI 10.1051/ita/2018011).
(en) Boris G. Mirkin, « On dual automata », Cybernetics, vol. 2,‎ 1966, p. 6–9
(en) Ernst Leiss, « Succinct representation of regular languages by boolean automata II », Theoretical Computer Science, vol. 38,‎ 1985, p. 133–136 (ISSN 0304-3975, DOI 10.1016/0304-3975(85)90215-4)
(en) Alexander Okhotin et Kai Salomaa, « State complexity of operations on input-driven pushdown automata », Journal of Computer and System Sciences, vol. 86,‎ 2017, p. 207–228 (ISSN 0022-0000, DOI 10.1016/j.jcss.2017.02.001)
Galina Jirásková et Alexander Okhotin, « State complexity of unambiguous operations on finite automata », Theoretical Computer Science, vol. 798,‎ 2019, p. 52–64 (DOI 10.1016/j.tcs.2019.04.008).
(en) Marek Chrobak, « Finite automata and unary languages », Theoretical Computer Science, vol. 47,‎ 1986, p. 149–158 (ISSN 0304-3975, DOI 10.1016/0304-3975(86)90142-8).
(en) Michal Kunc et Alexander Okhotin, « Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups », Springer Lecture Notes in Computer Science, vol. 6795,‎ 2011, p. 324–336 (ISSN 0302-9743, DOI 10.1007/978-3-642-22321-1_28).
(en) Carlo Mereghetti et Giovanni Pighizzini, « Optimal Simulations between Unary Automata », SIAM Journal on Computing, vol. 30, n^o 6,‎ 2001, p. 1976–1992 (ISSN 0097-5397, DOI 10.1137/S009753979935431X).
(en) Viliam Geffert, Carlo Mereghetti et Giovanni Pighizzini, « Converting two-way nondeterministic unary automata into simpler automata », Theoretical Computer Science, vol. 295, n^os 1-3,‎ 2003, p. 189–203 (ISSN 0304-3975, DOI 10.1016/S0304-3975(02)00403-6).
(en) Alexander Okhotin, « Unambiguous finite automata over a unary alphabet », Information and Computation, vol. 212,‎ 2012, p. 15–36 (ISSN 0890-5401, DOI 10.1016/j.ic.2012.01.003)
Par exemple Janusz A. Brzozowski, « In the search of most complex regular languages », Int. J. Found. Comput. Sci., vol. 24 numéro = 6,‎ 2013, p. 691–708.
Pascal Caron, Jean-Gabriel Luque, Ludovic Mignot et Bruno Patrou, « State complexity of catenation combined with a boolean operation : a unified approach », International Journal of Foundations of Computer Science, vol. 27, n^o 6,‎ 2016, p. 675-703 (DOI 10.1142/S0129054116500234)
Bo Cui, Yuan Gao, Lila Kari et Sheng Yu, « State complexity of two combined operations: Catenation-union and catenation-intersection », Int. J. Found. Comput. Sci., vol. 22, n^o 8,‎ 2011, p. 1797–1812
Yuan Gao et Sheng Yu, « State Complexity of Combined Operations with Union, Intersection, Star and Reversal », Fundamenta Informaticae, vol. 116, n^os 1-4,‎ 2012, p. 79-92
Yuan Gao, Kai Salomaa et Sheng Yu, « The state complexity of two combined operations: Star of catenation and star of reversal », Fundamenta Informaticae, vol. 83, n^os 1-2,‎ 2008, p. 75–89
Jozef Jirásek et Galina Jirásková, « On the boundary of regular languages », Theoretical Computer Science, vol. 578,‎ 2015, p. 42–57 (DOI 10.1016/j.tcs.2015.01.022).
Pascal Caron, Jean-Gabriel Luque et Bruno Patrou, « State complexity of multiple catenation », Arxiv (preprint),‎ 2016 (arXiv 1607.04031)
Pascal Caron, Jean-Gabriel Luque et Bruno Patrou, « State complexity of combined operations involving catenation and binary Boolean operations: Beyond the Brzozowski conjectures », Theoretical Computer Science, vol. 800,‎ 2019, p. 15–30 (ISSN 0304-3975, DOI 10.1016/j.tcs.2019.10.013).
Pascal Caron, Edwin Hamel-De le court, Jean-Gabriel Luque et Bruno Patrou, « New tools for state complexity », Discrete Mathematics & Theoretical Computer Science, vol. 22, n^o 1,‎ mars 2020 (DOI 10.23638/DMTCS-22-1-9, arXiv 1807.00663v6).
Pascal Caron, Jean-Gabriel Luque et Bruno Patrou, « A combinatorial approach for the state complexity of the Shuffle product », Arxiv,‎ 2019 (arXiv 1905.08120)
Pascal Caron, Edwin Hamel-de le Court et Jean-Gabriel Luque, « Algebraic and Combinatorial Tools for State Complexity : Application to the Star-Xor Problem », Electronic Proceedings in Theoretical Computer Science, vol. 305,‎ 2019, p. 154–168 (ISSN 2075-2180, DOI 10.4204/EPTCS.305.11, arXiv 1909.07663).

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[HolzerKutrib2009-1] (en) Markus Holzer et Martin Kutrib, « Nondeterministic finite automata — recent results on the descriptional and computational complexity », International Journal of Foundations of Computer Science, vol. 20, n^o 4,‎ 2009, p. 563–580 (ISSN 0129-0541, DOI 10.1142/S0129054109006747)

[HolzerKutrib2011-2] (en) Markus Holzer et Martin Kutrib, « Descriptional and computational complexity of finite automata—A survey », Information and Computation, vol. 209, n^o 3,‎ 2011, p. 456–470 (ISSN 0890-5401, DOI 10.1016/j.ic.2010.11.013)

[GaoMoreiraReisYu-3] (en) Yuan Gao, Nelma Moreira, Rogério Reis et Sheng Yu « A Survey on Operational State Complexity », 2015.

[RabinScott1959-4] (en) M. O. Rabin et D. Scott, « Finite Automata and Their Decision Problems », IBM Journal of Research and Development, vol. 3, n^o 2,‎ 1959, p. 114–125 (ISSN 0018-8646, DOI 10.1147/rd.32.0114)

[Lupanov-5] (en) Oleg B. Lupanov, « A comparison of two types of finite sources », Problemy Kibernetiki, vol. 9,‎ 1963, p. 321–326

[Leung2005-6] (en) Hing Leung, « Descriptional complexity of NFA of different ambiguity », International Journal of Foundations of Computer Science, vol. 16, n^o 5,‎ 2005, p. 975–984 (ISSN 0129-0541, DOI 10.1142/S0129054105003418)

[Schmidt1978-7] Erik M. Schmidt, Succinctness of Description of Context-Free, Regular and Unambiguous Languages, Cornell University, 1978

[JiráskováPighizzini2011-8] (en) Galina Jirásková et Giovanni Pighizzini, « Optimal simulation of self-verifying automata by deterministic automata », Information and Computation, vol. 209, n^o 3,‎ 2011, p. 528–535 (ISSN 0890-5401, DOI 10.1016/j.ic.2010.11.017)

[Kapoutsis2005-9] (en) Christos Kapoutsis, « Removing Bidirectionality from Nondeterministic Finite Automata », Mathematical Foundations of Computer Science 2005, vol. 3618,‎ 2005, p. 544–555 (ISBN 978-3-540-28702-5, ISSN 0302-9743, DOI 10.1007/11549345_47)

[Shepherdson1959-10] (en) J. C. Shepherdson, « The Reduction of Two-Way Automata to One-Way Automata », IBM Journal of Research and Development, vol. 3, n^o 2,‎ 1959, p. 198–200 (ISSN 0018-8646, DOI 10.1147/rd.32.0198)

[Moore1971-11] (en) Frank R. Moore, « On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata », IEEE Transactions on Computers, vol. C-20, n^o 10,‎ 1971, p. 1211–1214 (ISSN 0018-9340, DOI 10.1109/T-C.1971.223108)

[Birget1993a-12] (en) Jean-Camille Birget, « State-complexity of finite-state devices, state compressibility and incompressibility », Mathematical Systems Theory, vol. 26, n^o 3,‎ 1993, p. 237–269 (ISSN 0025-5661, DOI 10.1007/BF01371727)

[ChandraKozen1981-13] (en) Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, n^o 1,‎ 1981, p. 114–133 (ISSN 0004-5411, DOI 10.1145/322234.322243)

[FellahJürgensen1990-14] (en) Abdelaziz Fellah, Helmut Jürgensen et Sheng Yu, « Constructions for alternating finite automata », International Journal of Computer Mathematics, vol. 35, n^os 1–4,‎ 1990, p. 117–132 (ISSN 0020-7160, DOI 10.1080/00207169008803893)

[LadnerLipton1984-15] (en) Richard E. Ladner, Richard J. Lipton et Larry J. Stockmeyer, « Alternating Pushdown and Stack Automata », SIAM Journal on Computing, vol. 13, n^o 1,‎ 1984, p. 135–155 (ISSN 0097-5397, DOI 10.1137/0213010)

[GeffertOkhotin2014-16] (en) Viliam Geffert et Alexander Okhotin, « Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata », Mathematical Foundations of Computer Science 2014, vol. 8634,‎ 2014, p. 291–302 (ISBN 978-3-662-44521-1, ISSN 0302-9743, DOI 10.1007/978-3-662-44522-8_25)

[17] William J. Sakoda et Michael Sipser, « Nondeterminism and the Size of Two Way Finite Automata », ACM,‎ 1978, p. 275–286 (DOI 10.1145/800133.804357)

[18] Piotr Berman et Andrzej Lingas, « On the complexity of regular languages in terms of finite automata », Report 304, Polish Academy of Sciences,‎ 1977

[19] (en) Christos A. Kapoutsis, « Two-Way Automata Versus Logarithmic Space », Theory of Computing Systems, vol. 55, n^o 2,‎ 2014, p. 421–447 (DOI 10.1007/s00224-013-9465-0)

[Maslov-20] (en) A. N. Maslov, « Estimates of the number of states of finite automata », Soviet Mathematics Doklady, vol. 11,‎ 1970, p. 1373–1375

[YuZhuang1994-21] (en) Sheng Yu, Qingyu Zhuang et Kai Salomaa, « The state complexities of some basic operations on regular languages », Theoretical Computer Science, vol. 125, n^o 2,‎ 1994, p. 315–328 (ISSN 0304-3975, DOI 10.1016/0304-3975(92)00011-F)

[HolzerKutrib2003-22] (en) Markus Holzer et Martin Kutrib, « Nondeterministic descriptional complexity of regular languages », International Journal of Foundations of Computer Science, vol. 14, n^o 6,‎ 2003, p. 1087–1102 (ISSN 0129-0541, DOI 10.1142/S0129054103002199)

[JirásekJirásková2016-23] (en) Jozef Jirásek, Galina Jirásková et Juraj Šebej, « Operations on Unambiguous Finite Automata », Developments in Language Theory 2016, vol. 9840,‎ 2016, p. 243–255 (ISBN 978-3-662-53131-0, ISSN 0302-9743, DOI 10.1007/978-3-662-53132-7_20)

[JirásekJirásková2015-24] (en) Jozef Štefan Jirásek, Galina Jirásková et Alexander Szabari, « Operations on Self-Verifying Finite Automata », International Computer Science Symposium in Russia (CSR), vol. 9139,‎ 2015, p. 231–261 (ISSN 0302-9743, DOI 10.1007/978-3-319-20297-6_16)

[KuncOkhotin2012-25] (en) Michal Kunc et Alexander Okhotin, « State complexity of operations on two-way finite automata over a unary alphabet », Theoretical Computer Science, vol. 449,‎ 2012, p. 106–118 (ISSN 0304-3975, DOI 10.1016/j.tcs.2012.04.010)

[KuncOkhotin2011-26] (en) Michal Kunc et Alexander Okhotin, « State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata », Fundamenta Informaticae, vol. 110,‎ 2011, p. 231–239 (DOI 10.3233/FI-2011-540)

[Birget1993b-27] (en) Jean-Camille Birget, « Partial orders on words, minimal elements of regular languages, and state complexity », Theoretical Computer Science, vol. 119, n^o 2,‎ 1993, p. 267–291 (ISSN 0304-3975, DOI 10.1016/0304-3975(93)90160-U)

[Raskin2018-28] Mikhail Raskin, « A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton », Arxiv,‎ 14 février 2018 (arXiv 1711.03993). Accepté pour ICALP 2018 à Prague.

[IndzhevKiefer2022-29] Emil Indzhev et Stefan Kiefer, « On complementing unambiguous automata and graphs with many cliques and cocliques », Information Processing Letters, vol. 177,‎ août 2022, article n^o 106270 (DOI 10.1016/j.ipl.2022.106270, arXiv 2105.07470).

[GeffertMereghetti2007-30] (en) Viliam Geffert, Carlo Mereghetti et Giovanni Pighizzini, « Complementing two-way finite automata », Information and Computation, vol. 205, n^o 8,‎ 2007, p. 1173–1187 (ISSN 0890-5401, DOI 10.1016/j.ic.2007.01.008)

[JiráskováOkhotin2008-31] (en) Galina Jirásková et Alexander Okhotin, « On the State Complexity of Operations on Two-Way Finite Automata », Developments in Language Theory DLT, vol. 5257,‎ 2008, p. 443–454 (ISBN 978-3-540-85779-2, ISSN 0302-9743, DOI 10.1007/978-3-540-85780-8_35)

[BordihnHospodár2019-32] Henning Bordihn, Michal Hospodár, Galina Jirásková, Benedek Nagy et György Vaszil, « The complexity of concatenation on deterministic and alternating finite automata », RAIRO - Theoretical Informatics and Applications, vol. 52, n^os 2-3-4,‎ 2019, p. 153–168 (ISSN 0988-3754, DOI 10.1051/ita/2018011).

[Mirkin1966-33] (en) Boris G. Mirkin, « On dual automata », Cybernetics, vol. 2,‎ 1966, p. 6–9

[Leiss1985-34] (en) Ernst Leiss, « Succinct representation of regular languages by boolean automata II », Theoretical Computer Science, vol. 38,‎ 1985, p. 133–136 (ISSN 0304-3975, DOI 10.1016/0304-3975(85)90215-4)

[OkhotinSalomaa2017-35] (en) Alexander Okhotin et Kai Salomaa, « State complexity of operations on input-driven pushdown automata », Journal of Computer and System Sciences, vol. 86,‎ 2017, p. 207–228 (ISSN 0022-0000, DOI 10.1016/j.jcss.2017.02.001)

[JiráskováOkhotin2019-36] Galina Jirásková et Alexander Okhotin, « State complexity of unambiguous operations on finite automata », Theoretical Computer Science, vol. 798,‎ 2019, p. 52–64 (DOI 10.1016/j.tcs.2019.04.008).

[Chrobak1986-37] (en) Marek Chrobak, « Finite automata and unary languages », Theoretical Computer Science, vol. 47,‎ 1986, p. 149–158 (ISSN 0304-3975, DOI 10.1016/0304-3975(86)90142-8).

[KuncOkhotin2011b-38] (en) Michal Kunc et Alexander Okhotin, « Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups », Springer Lecture Notes in Computer Science, vol. 6795,‎ 2011, p. 324–336 (ISSN 0302-9743, DOI 10.1007/978-3-642-22321-1_28).

[MereghettiPighizzini2001-39] (en) Carlo Mereghetti et Giovanni Pighizzini, « Optimal Simulations between Unary Automata », SIAM Journal on Computing, vol. 30, n^o 6,‎ 2001, p. 1976–1992 (ISSN 0097-5397, DOI 10.1137/S009753979935431X).

[GeffertMereghetti2003-40] (en) Viliam Geffert, Carlo Mereghetti et Giovanni Pighizzini, « Converting two-way nondeterministic unary automata into simpler automata », Theoretical Computer Science, vol. 295, n^os 1-3,‎ 2003, p. 189–203 (ISSN 0304-3975, DOI 10.1016/S0304-3975(02)00403-6).

[Okhotin2012-41] (en) Alexander Okhotin, « Unambiguous finite automata over a unary alphabet », Information and Computation, vol. 212,‎ 2012, p. 15–36 (ISSN 0890-5401, DOI 10.1016/j.ic.2012.01.003)

[Brzozowski2013-42] Par exemple Janusz A. Brzozowski, « In the search of most complex regular languages », Int. J. Found. Comput. Sci., vol. 24 numéro = 6,‎ 2013, p. 691–708.

[CaronLuque2016-43] Pascal Caron, Jean-Gabriel Luque, Ludovic Mignot et Bruno Patrou, « State complexity of catenation combined with a boolean operation : a unified approach », International Journal of Foundations of Computer Science, vol. 27, n^o 6,‎ 2016, p. 675-703 (DOI 10.1142/S0129054116500234)

[CuiGao2011-44] Bo Cui, Yuan Gao, Lila Kari et Sheng Yu, « State complexity of two combined operations: Catenation-union and catenation-intersection », Int. J. Found. Comput. Sci., vol. 22, n^o 8,‎ 2011, p. 1797–1812

[GaoYu2012-45] Yuan Gao et Sheng Yu, « State Complexity of Combined Operations with Union, Intersection, Star and Reversal », Fundamenta Informaticae, vol. 116, n^os 1-4,‎ 2012, p. 79-92

[GaoSalomaa2008-46] Yuan Gao, Kai Salomaa et Sheng Yu, « The state complexity of two combined operations: Star of catenation and star of reversal », Fundamenta Informaticae, vol. 83, n^os 1-2,‎ 2008, p. 75–89

[JirásekJirásková-2015-47] Jozef Jirásek et Galina Jirásková, « On the boundary of regular languages », Theoretical Computer Science, vol. 578,‎ 2015, p. 42–57 (DOI 10.1016/j.tcs.2015.01.022).

[CaronPatrou2016-48] Pascal Caron, Jean-Gabriel Luque et Bruno Patrou, « State complexity of multiple catenation », Arxiv (preprint),‎ 2016 (arXiv 1607.04031)

[CaronLuque2019-49] Pascal Caron, Jean-Gabriel Luque et Bruno Patrou, « State complexity of combined operations involving catenation and binary Boolean operations: Beyond the Brzozowski conjectures », Theoretical Computer Science, vol. 800,‎ 2019, p. 15–30 (ISSN 0304-3975, DOI 10.1016/j.tcs.2019.10.013).

[50] Pascal Caron, Edwin Hamel-De le court, Jean-Gabriel Luque et Bruno Patrou, « New tools for state complexity », Discrete Mathematics & Theoretical Computer Science, vol. 22, n^o 1,‎ mars 2020 (DOI 10.23638/DMTCS-22-1-9, arXiv 1807.00663v6).

[51] Pascal Caron, Jean-Gabriel Luque et Bruno Patrou, « A combinatorial approach for the state complexity of the Shuffle product », Arxiv,‎ 2019 (arXiv 1905.08120)

[CaronHamel-de_le_Court2019-52] Pascal Caron, Edwin Hamel-de le Court et Jean-Gabriel Luque, « Algebraic and Combinatorial Tools for State Complexity : Application to the Star-Xor Problem », Electronic Proceedings in Theoretical Computer Science, vol. 305,‎ 2019, p. 154–168 (ISSN 2075-2180, DOI 10.4204/EPTCS.305.11, arXiv 1909.07663).