Complexité en états

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 à états peut être simulé par un automate fini déterministe à au plus é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 jeux 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 états ; la deuxième étape demande de fournir des exemples où cette borne est effectivement atteinte.

Transformation entre variantes d'automates finis[modifier | modifier le code]

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 , qui, pour un automate du premier type à état, associe le nombre minimal 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: é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 : états[6]. Une borne inférieure plus petite est de Schmidt[7].
  • De AFN en UFA : états[6]. Une borne inférieure plus petite est de Schmidt[7].
  • De SVFA en AFD : états[8]
  • De 2AFD en AFD : é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 : états[9]. Une construction antérieure par Jean-Camille Birget|Birget[12] utilise plus d'états.
  • De 2AFN en AFN : [9].
  • De AFA en AFD : états, démonstration par Ashok K. Chandra, Dexter Kozen et Larry Stockmeyer en 1981[13]
  • De AFA en AFN : états[14]
  • De 2AFA en AFD : états[15]
  • De 2AFA en AFN : états[16]

Résumé[modifier | modifier le code]

Complexité de transformation
AFD UFA AFN
AFN -
UFA -
SVFA
2AFD
2AFN
AFA
2AFA

Le problème 2AFD versus 2AFN et l’espace logarithmique[modifier | modifier le code]

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 états pour un automate de départ à et un polynôme . 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[modifier | modifier le code]

Étant donné une opération binaire entre langages formes préservant la la régularité Given a binary regularity-preserving operation on languages et une famille X d'automates (déterministe, non déterministe etc.) la complexité en états de l'opération est une fonction telle que

  • pour toute paire d'automates à états et à états de la famille X, il existe un automate à états de la famille X qui accepte le langage
  • pour toute paire d'entiers , il existe un automate à états et un automate à états dans la famille X telle que tout automate de la famille X acceptant a au moins é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é 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 est accepté par un automate à m états, et par un automate à n états ; on demande le nombre d'états.

Union[modifier | modifier le code]

Nombre d'états nécessaires pour  :

  • AFD: états, démontré par Maslov[20] et Yu, Zhuang et Salomaa[21].
  • AFN: états, établi par Holzer et Kutrib[22].
  • UFA: entre et états[23]
  • SVFA: états[24]
  • 2AFD: entre et états[25]
  • 2AFN: états[26]

Intersection[modifier | modifier le code]

Nombre d'états nécessaires pour  :

  • AFD: états[20],[21].
  • AFN: états[22].
  • UFA: états[23].
  • SVFA: états[24].
  • 2AFD: soit soit états, par Kunc et Okhotin[25].
  • 2AFN: soit soit états[26].

Complémentation[modifier | modifier le code]

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

  • AFD: états, en échangeant les états acceptants et les autres.
  • AFN: états, par Birget[27]
  • UFA: au moins et au plus états, Okhotin[28] pour la borne inférieure et Jirásek, Jirásková et Šebej[23] pour la borne supérieure.
  • SVFA: états, par échange d'états acceptants et non acceptants.
  • 2AFD: au moins et au plus états[29].

Concaténation[modifier | modifier le code]

Nombre d'états requis pour le produit  :

  • AFD: états, déjà Maslov [20] et Yu, Zhuang et Salomaa[21].
  • AFN: états, Holzer et Kutrib[22].
  • UFA: états[23].
  • SVFA: états[24].
  • 2AFD: au moins et au plus états[30].

Étoile de Kleene[modifier | modifier le code]

  • AFD: états, déjà Maslov[20] et Yu, Zhuang et Salomaa[21].
  • AFN: états[22].
  • UFA: états[23].
  • SVFA: états[24].
  • 2AFD: au moins et au plus états[30].

Transposé[modifier | modifier le code]

  • AFD: états, par Boris G. Mirkin[31], Ernst Leiss[32], et Yu, Zhuang et Salomaa[21].
  • AFN: états[22].
  • UFA: états.
  • SVFA: états[24].
  • 2AFD: soit soit états[30].

Résumé[modifier | modifier le code]

La table suivante résume les complexités ; elle figure aussi en partie dans l'article d'Okhotin et Salomaa[33] 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
intersection
complément
concaténation
étoile
transposé

Automates finis sur un alphabet unaire[modifier | modifier le code]

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[34]. 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 la fonction de Landau.

Transformation entre modèles[modifier | modifier le code]

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

  • De AFN en AFD: états[34].
  • De 2AFD en AFD: états[34] et Kunc et Okhotin[35]
  • De 2AFN en AFD: états[35], Mereghetti et Giovanni Pighizzini[36] et Geffert, Mereghetti et Pighizzini[37].
  • De AFN en 2AFD: au plust [34].
  • De 2AFN en 2AFD: au plua états ; majoration établie avec la méthode du théorème de Savitch[37].
  • De UFA en AFD: états[28].
  • De AFN en UFA: états[28].

Union[modifier | modifier le code]

  • AFD: états, par Yu, Zhuang et Salomaa[21].
  • AFN: états, par Holzer et Kutrib[22].
  • 2AFD: entre et états[25].
  • 2AFN: états[26].

Intersection[modifier | modifier le code]

  • AFD: états, par Yu, Zhuang et Salomaa[21].
  • AFN: états, par Holzer et Kutrib[22].
  • 2AFD: entre et états[25].
  • 2AFN: entre et états[26].

Complémentation[modifier | modifier le code]

  • AFD: états.
  • AFN: états[22].
  • UFA: au moins et au plus états[28].
  • 2AFD: au moins et au plus états[25].
  • 2AFN: au moins et au plus états. La majoration est obtenue avec la méthode du théorème d'Immerman-Szelepcsényi[29].

Concaténation[modifier | modifier le code]

  • AFD: états[21].
  • AFN: entre et états[22].
  • 2AFD: états[25].
  • 2AFN: états[25].

Étoile de Kleene[modifier | modifier le code]

  • AFD: états, déjà Yu, Zhuang et Salomaa[21].
  • AFN: états,[22].
  • UFA: états[28].
  • 2AFD: états[25].
  • 2AFN: états[25].

Résumé[modifier | modifier le code]

La table suivante résume ces complexités.

Complexité des opérations binaires
AFD AFN UFA 2AFD 2AFN
union -
intersection -
complémentation
concaténation -
étoile

Opérations combinées[modifier | modifier le code]

Janusz A. Brzozowski a publié des articles[38], 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.[39].


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 [40],[41],[42].

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 à états et d’un AFD à états est  ; la complexité d’une opération booléenne d’un AFD à états et d'un AFD à états est . La combinaison d'une concatéation et d'une intersection (un langage ) est , alors que dans la combinaison avec une union , elle descend à [40].

Une approche plus algébrique du problème est proposée par Pascal Caron et. al.[39]. Ils montrent que les opérations de la forme se ramènent, quitte à remplacer les langages ou par leur complémentaires, aux trois cas où l'opération 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 [43] traite de concaténations multiples ; ils montrent que la borne supérieure est atteinte sur un alphabet à lettres pour concaténations. Ils précisent aussi l'expression de la complexité en états, et utilisent les automates de Brzozowski dans ces développements.

Recherches en cours[modifier | modifier le code]

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[modifier | modifier le code]

Références[modifier | modifier le code]

(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).

  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, no 4,‎ , p. 563–580 (ISSN 0129-0541, DOI 10.1142/S0129054109006747)
  2. (en) Markus Holzer et Martin Kutrib, « Descriptional and computational complexity of finite automata—A survey », Information and Computation, vol. 209, no 3,‎ , p. 456–470 (ISSN 0890-5401, DOI 10.1016/j.ic.2010.11.013)
  3. (en) Yuan Gao, Nelma Moreira, Rogério Reis et Sheng Yu « A Survey on Operational State Complexity », 2015.
  4. (en) M. O. Rabin et D. Scott, « Finite Automata and Their Decision Problems », IBM Journal of Research and Development, vol. 3, no 2,‎ , p. 114–125 (ISSN 0018-8646, DOI 10.1147/rd.32.0114)
  5. (en) Oleg B. Lupanov, « A comparison of two types of finite sources », Problemy Kibernetiki, vol. 9,‎ , p. 321–326
  6. a et b (en) Hing Leung, « Descriptional complexity of NFA of different ambiguity », International Journal of Foundations of Computer Science, vol. 16, no 5,‎ , p. 975–984 (ISSN 0129-0541, DOI 10.1142/S0129054105003418)
  7. a et b Erik M. Schmidt, Succinctness of Description of Context-Free, Regular and Unambiguous Languages, Cornell University,
  8. (en) Galina Jirásková et Giovanni Pighizzini, « Optimal simulation of self-verifying automata by deterministic automata », Information and Computation, vol. 209, no 3,‎ , p. 528–535 (ISSN 0890-5401, DOI 10.1016/j.ic.2010.11.017)
  9. a, b et c (en) Christos Kapoutsis, « Removing Bidirectionality from Nondeterministic Finite Automata », Mathematical Foundations of Computer Science 2005, vol. 3618,‎ , p. 544–555 (ISBN 978-3-540-28702-5, ISSN 0302-9743, DOI 10.1007/11549345_47)
  10. (en) J. C. Shepherdson, « The Reduction of Two-Way Automata to One-Way Automata », IBM Journal of Research and Development, vol. 3, no 2,‎ , p. 198–200 (ISSN 0018-8646, DOI 10.1147/rd.32.0198)
  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, no 10,‎ , p. 1211–1214 (ISSN 0018-9340, DOI 10.1109/T-C.1971.223108)
  12. (en) Jean-Camille Birget, « State-complexity of finite-state devices, state compressibility and incompressibility », Mathematical Systems Theory, vol. 26, no 3,‎ , p. 237–269 (ISSN 0025-5661, DOI 10.1007/BF01371727)
  13. (en) Ashok K. Chandra, Dexter C. Kozen et Larry J. Stockmeyer, « Alternation », Journal of the ACM, vol. 28, no 1,‎ , p. 114–133 (ISSN 0004-5411, DOI 10.1145/322234.322243)
  14. (en) Abdelaziz Fellah, Helmut Jürgensen et Sheng Yu, « Constructions for alternating finite automata », International Journal of Computer Mathematics, vol. 35, no 1–4,‎ , p. 117–132 (ISSN 0020-7160, DOI 10.1080/00207169008803893)
  15. (en) Richard E. Ladner, Richard J. Lipton et Larry J. Stockmeyer, « Alternating Pushdown and Stack Automata », SIAM Journal on Computing, vol. 13, no 1,‎ , p. 135–155 (ISSN 0097-5397, DOI 10.1137/0213010)
  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,‎ , 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,‎ , 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,‎
  19. (en) Christos A. Kapoutsis, « Two-Way Automata Versus Logarithmic Space », Theory of Computing Systems, vol. 55, no 2,‎ , p. 421–447 (DOI 10.1007/s00224-013-9465-0)
  20. a, b, c, d et e (en) A. N. Maslov, « Estimates of the number of states of finite automata », Soviet Mathematics Doklady, vol. 11,‎ , p. 1373–1375
  21. a, b, c, d, e, f, g, h, i et j (en) Sheng Yu, Qingyu Zhuang et Kai Salomaa, « The state complexities of some basic operations on regular languages », Theoretical Computer Science, vol. 125, no 2,‎ , p. 315–328 (ISSN 0304-3975, DOI 10.1016/0304-3975(92)00011-F)
  22. a, b, c, d, e, f, g, h, i, j et k (en) Markus Holzer et Martin Kutrib, « Nondeterministic descriptional complexity of regular languages », International Journal of Foundations of Computer Science, vol. 14, no 6,‎ , p. 1087–1102 (ISSN 0129-0541, DOI 10.1142/S0129054103002199)
  23. a, b, c, d et e (en) Jozef Jirásek, Galina Jirásková et Juraj Šebej, « Operations on Unambiguous Finite Automata », Developments in Language Theory 2016, vol. 9840,‎ , p. 243–255 (ISBN 978-3-662-53131-0, ISSN 0302-9743, DOI 10.1007/978-3-662-53132-7_20)
  24. a, b, c, d et e (en) Jozef Štefan Jirásek, Galina Jirásková et Alexander Szabari, « Operations on Self-Verifying Finite Automata », Computer Science Symposium in Russia (CSR), vol. 9139,‎ , p. 231–261 (ISSN 0302-9743, DOI 10.1007/978-3-319-20297-6_16)
  25. a, b, c, d, e, f, g, h et i (en) Michal Kunc et Alexander Okhotin, « State complexity of operations on two-way finite automata over a unary alphabet », Theoretical Computer Science, vol. 449,‎ , p. 106–118 (ISSN 0304-3975, DOI 10.1016/j.tcs.2012.04.010)
  26. a, b, c et d (en) Michal Kunc et Alexander Okhotin, « State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata », Fundamenta Informaticae, vol. 110,‎ , p. 231–239 (DOI 10.3233/FI-2011-540)
  27. (en) Jean-Camille Birget, « Partial orders on words, minimal elements of regular languages, and state complexity », Theoretical Computer Science, vol. 119, no 2,‎ , p. 267–291 (ISSN 0304-3975, DOI 10.1016/0304-3975(93)90160-U)
  28. a, b, c, d et e (en) Alexander Okhotin, « Unambiguous finite automata over a unary alphabet », Information and Computation, vol. 212,‎ , p. 15–36 (ISSN 0890-5401, DOI 10.1016/j.ic.2012.01.003)
  29. a et b (en) Viliam Geffert, Carlo Mereghetti et Giovanni Pighizzini, « Complementing two-way finite automata », Information and Computation, vol. 205, no 8,‎ , p. 1173–1187 (ISSN 0890-5401, DOI 10.1016/j.ic.2007.01.008)
  30. a, b et c (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,‎ , p. 443–454 (ISBN 978-3-540-85779-2, ISSN 0302-9743, DOI 10.1007/978-3-540-85780-8_35)
  31. (en) Boris G. Mirkin, « On dual automata », Cybernetics, vol. 2,‎ , p. 6–9
  32. (en) Ernst Leiss, « Succinct representation of regular languages by boolean automata II », Theoretical Computer Science, vol. 38,‎ , p. 133–136 (ISSN 0304-3975, DOI 10.1016/0304-3975(85)90215-4)
  33. Alexander Okhotin et Kai Salomaa, « State complexity of operations on input-driven pushdown automata », Journal of Computer and System Sciences, vol. 86,‎ , p. 207–228 (ISSN 0022-0000, DOI 10.1016/j.jcss.2017.02.001)
  34. a, b, c et d (en) Marek Chrobak, « Finite automata and unary languages », Theoretical Computer Science, vol. 47,‎ , p. 149–158 (ISSN 0304-3975, DOI 10.1016/0304-3975(86)90142-8).
  35. a et b (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,‎ , p. 324–336 (ISSN 0302-9743, DOI 10.1007/978-3-642-22321-1_28).
  36. (en) Carlo Mereghetti et Giovanni Pighizzini, « Optimal Simulations between Unary Automata », SIAM Journal on Computing, vol. 30, no 6,‎ , p. 1976–1992 (ISSN 0097-5397, DOI 10.1137/S009753979935431X).
  37. a et b (en) Viliam Geffert, Carlo Mereghetti et Giovanni Pighizzini, « Converting two-way nondeterministic unary automata into simpler automata », Theoretical Computer Science, vol. 295, no 1-3,‎ , p. 189–203 (ISSN 0304-3975, DOI 10.1016/S0304-3975(02)00403-6).
  38. Par exemple Janusz A. Brzozowski, « In the search of most complex regular languages », Int. J. Found. Comput. Sci., vol. 24 numéro = 6,‎ , p. 691–708.
  39. a et b 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, no 6,‎ , p. 675-703 (DOI 10.1142/S0129054116500234)
  40. a et b 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, no 8,‎ , p. 1797–1812
  41. Yuan Gao et Sheng Yu, « State Complexity of Combined Operations with Union, Intersection, Star and Reversal », Fundamenta Informaticae, vol. 116, no 1-4,‎ , p. 79-92
  42. 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, no 1-2,‎ , p. 75–89
  43. Pascal Caron, Jean-Gabriel Luque et Bruno Patrou, « State complexity of multiple catenation », Arxiv (preprint),‎ (arXiv 1607.04031)