Complejidad del estado

La complejidad del estado es un área de la informática teórica que se ocupa del tamaño de los autómatas abstractos, como los diferentes tipos de autómatas finitos . El resultado clásico en el área es que la simulación de un autómata finito no determinista de estado mediante un autómata finito determinista requiere exactamente estados en el peor de los casos. ${\displaystyle n}$ ${\displaystyle 2^{n}}$

Transformación entre variantes de autómatas finitos.

Los autómatas finitos pueden ser deterministas y no deterministas , unidireccionales (DFA, NFA) y bidireccionales (2DFA, 2NFA). Otras clases relacionadas son autómatas finitos inequívocos (UFA), autoverificantes (SVFA) y alternos (AFA). Estos autómatas también pueden ser bidireccionales (2UFA, 2SVFA, 2AFA).

Todas estas máquinas pueden aceptar exactamente los idiomas habituales . Sin embargo, el tamaño de diferentes tipos de autómatas necesarios para aceptar el mismo idioma (medido en el número de sus estados) puede ser diferente. Para dos tipos cualesquiera de autómatas finitos, el equilibrio de complejidad de estado entre ellos es una función entera donde el menor número de estados en autómatas del segundo tipo es suficiente para reconocer todos los idiomas reconocidos por un autómata de estado del primer tipo. Se conocen los siguientes resultados. ${\displaystyle f}$ ${\displaystyle f(n)}$ ${\displaystyle n}$

• NFA a DFA: estados. Esta es la construcción de subconjuntos de Rabin y Scott , ^{[1] que} Lupanov demostró ser óptima . ^[2] ${\displaystyle 2^{n}}$

• De UFA a DFA: estados, ver Leung, ^[3] Un límite inferior anterior de Schmidt ^[4] era más pequeño. ${\displaystyle 2^{n}}$
• NFA a UFA: estados, ver Leung. ^[3] Schmidt ya había establecido un límite inferior más pequeño. ^[4] ${\displaystyle 2^{n}-1}$
• SVFA a DFA: estados, ver Jirásková y Pighizzini ^[5] ${\displaystyle \Theta (3^{n/3})}$
• 2DFA a DFA: estados, ver Kapoutsis. ^[6] La construcción anterior de Shepherdson ^[7] utilizó más estados, y un límite inferior anterior de Moore ^[8] era más pequeño. ${\displaystyle n(n^{n}-(n-1)^{n})}$
• 2DFA a NFA: , ver Kapoutsis. ^[6] La construcción anterior de Birget ^[9] utilizó más estados. ${\displaystyle {\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})}$
• 2NFA a NFA: , ver Kapoutsis. ^[6] ${\displaystyle {\binom {2n}{n+1}}}$
  • 2NFA a NFA aceptando el complemento: estados, ver Vardi . ^[10] ${\displaystyle O(4^{n})}$
• De AFA a DFA: estados, véase Chandra , Kozen y Stockmeyer . ^[11] ${\displaystyle 2^{2^{n}}}$
• De AFA a NFA: estados, véase Fellah, Jürgensen y Yu. ^[12] ${\displaystyle 2^{n}}$
• 2AFA a DFA: , véase Ladner , Lipton y Stockmeyer . ^[13] ${\displaystyle 2^{n2^{n}}}$
• 2AFA a NFA: , véase Geffert y Okhotin. ^[14] ${\displaystyle 2^{\Theta (n\log n)}}$

El problema 2DFA versus 2NFA y el espacio logarítmico

Problema no resuelto en informática :

¿Cada 2NFA de estado tiene un 2DFA de estado equivalente? ${\displaystyle n}$ ${\displaystyle \operatorname {poly} (n)}$

(más problemas sin resolver en informática)

Es un problema abierto si todos los 2NFA se pueden convertir en 2DFA con polinomios de muchos estados, es decir, si existe un polinomio tal que para cada 2NFA de estado exista un 2DFA de estado. El problema fue planteado por Sakoda y Sipser , ^[15] quienes lo compararon con el problema P vs. NP en la teoría de la complejidad computacional . Berman y Lingas ^[16] descubrieron una relación formal entre este problema y el problema abierto L vs. NL . Esta relación fue elaborada con más detalle por Kapoutsis. ^[17] ${\displaystyle p(n)}$ ${\displaystyle n}$ ${\displaystyle p(n)}$

Complejidad estatal de las operaciones para autómatas finitos.

Dada una operación binaria que preserva la regularidad en lenguajes y una familia de autómatas X (DFA, NFA, etc.), la complejidad del estado de es una función entera tal que ${\displaystyle \circ }$ ${\displaystyle \circ }$ ${\displaystyle f(m,n)}$

• para cada autómata X de estado m A y autómata X B de n estado, hay un autómata X de estado para , y ${\displaystyle f(m,n)}$ ${\displaystyle L(A)\circ L(B)}$
• para todos los números enteros m, n hay un autómata X A de estado m y un autómata B B de estado n tal que cada autómata X debe tener al menos estados. ${\displaystyle L(A)\circ L(B)}$ ${\displaystyle f(m,n)}$

Una definición análoga se aplica a operaciones con cualquier número de argumentos.

Los primeros resultados sobre la complejidad estatal de las operaciones de las DFA fueron publicados por Maslov ^[18] y por Yu, Zhuang y Salomaa . ^[19] Holzer y Kutrib ^[20] fueron pioneros en la complejidad estatal de las operaciones en NFA. Los resultados conocidos para operaciones básicas se enumeran a continuación.

Unión

Si el lenguaje requiere m estados y el lenguaje requiere n estados, ¿cuántos estados requiere? ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle L_{1}\cup L_{2}}$

• DFA: estados, ver Maslov ^[18] y Yu, Zhuang y Salomaa. ^[19] ${\displaystyle mn}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle m+n+1}$
• UFA: al menos ; ^[21] entre estados y , véase Jirásek, Jirásková y Šebej. ^[22] ${\displaystyle \min(n,m)^{\Omega (\log(\min(n,m)))}}$ ${\displaystyle mn+m+n}$ ${\displaystyle m+nm2^{0.79m}}$
• SVFA: estados, ver Jirásek, Jirásková y Szabari. ^[23] ${\displaystyle mn}$
• 2DFA: entre y estados, ver Kunc y Okhotin. ^[24] ${\displaystyle m+n}$ ${\displaystyle 4m+n+4}$
• 2NFA: estados, ver Kunc y Okhotin. ^[25] ${\displaystyle m+n}$

Intersección

¿Cuántos estados requiere? ${\displaystyle L_{1}\cap L_{2}}$

• DFA: estados, ver Maslov ^[18] y Yu, Zhuang y Salomaa. ^[19] ${\displaystyle mn}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle mn}$
• UFA: estados, ver Jirásek, Jirásková y Šebej. ^[22] ${\displaystyle mn}$
• SVFA: estados, ver Jirásek, Jirásková y Szabari. ^[23] ${\displaystyle mn}$
• 2DFA: entre y estados, ver Kunc y Okhotin. ^[24] ${\displaystyle m+n}$ ${\displaystyle m+n+1}$
• 2NFA: entre y estados, ver Kunc y Okhotin. ^[25] ${\displaystyle m+n}$ ${\displaystyle m+n+1}$

Complementación

Si el lenguaje L requiere n estados, ¿cuántos estados requiere su complemento ?

• DFA: estados, mediante el intercambio de estados aceptantes y rechazantes. ${\displaystyle n}$
• NFA: estados, ver Birget. ^[26] o Jirásková ^[27] ${\displaystyle 2^{n}}$
• UFA: al menos estados, ver Göös, Kiefer y Yuan, ^[21] (esto sigue un enlace anterior de Raskin ^[28] ); y en la mayoría de los estados, consulte Indzhev y Kiefer. ^[29] ${\displaystyle n^{{\tilde {\Omega }}(\log n)}}$ ${\displaystyle {\sqrt {n+1}}\cdot 2^{0.5n}}$
• SVFA: estados, mediante el intercambio de estados de aceptación y rechazo. ${\displaystyle n}$
• 2DFA: al menos y en la mayoría de los estados, ver Geffert, Mereghetti y Pighizzini. ^[30] ${\displaystyle n}$ ${\displaystyle 4n}$

Concatenación

¿Cuántos estados requiere? ${\displaystyle L_{1}L_{2}=\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\}}$

• DFA: estados, ver Maslov ^[18] y Yu, Zhuang y Salomaa. ^[19] ${\displaystyle m\cdot 2^{n}-2^{n-1}}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle m+n}$
• UFA: estados, ver Jirásek, Jirásková y Šebej. ^[22] ${\displaystyle {\frac {3}{4}}2^{m+n}-1}$
• SVFA: estados, ver Jirásek, Jirásková y Szabari. ^[23] ${\displaystyle \Theta (3^{n/3}2^{m})}$
• 2DFA: al menos y en la mayoría de los estados, ver Jirásková y Okhotin. ^[31] ${\displaystyle {\frac {2^{\Omega (n)}}{\log m}}}$ ${\displaystyle 2m^{m+1}\cdot 2^{n^{n+1}}}$

estrella kleene

• DFA: estados, ver Maslov ^[18] y Yu, Zhuang y Salomaa. ^[19] ${\displaystyle {\frac {3}{4}}2^{n}}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle n+1}$
• UFA: estados, ver Jirásek, Jirásková y Šebej. ^[22] ${\displaystyle {\frac {3}{4}}2^{n}}$
• SVFA: estados, ver Jirásek, Jirásková y Szabari. ^[23] ${\displaystyle {\frac {3}{4}}2^{n}}$
• 2DFA: al menos y en la mayoría de los estados, ver Jirásková y Okhotin. ^[31] ${\displaystyle {\frac {1}{n}}2^{{\frac {n}{2}}-1}}$ ${\displaystyle 2^{O(n^{n+1})}}$

Inversión

• DFA: estados, ver Mirkin, ^[32] Leiss, ^[33] y Yu, Zhuang y Salomaa. ^[19] ${\displaystyle 2^{n}}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle n+1}$
• UFA: estados. ${\displaystyle n}$
• SVFA: estados, ver Jirásek, Jirásková y Szabari. ^[23] ${\displaystyle 2n+1}$
• 2DFA: entre y estados, ver Jirásková y Okhotin. ^[31] ${\displaystyle n+1}$ ${\displaystyle n+2}$

Autómatas finitos sobre un alfabeto unario

La complejidad del estado de los autómatas finitos con un alfabeto de una letra ( unario ), iniciado por Chrobak , ^[34] es diferente del caso de varias letras.

Sea la función de Landau . ${\displaystyle g(n)=e^{\Theta ({\sqrt {n\ln n}})}}$

Transformación entre modelos

Para un alfabeto de una letra, las transformaciones entre diferentes tipos de autómatas finitos son a veces más eficientes que en el caso general.

• NFA a DFA: estados, ver Chrobak. ^[34] ${\displaystyle g(n)+O(n^{2})}$
• 2DFA a DFA: estados, ver Chrobak ^[34] y Kunc y Okhotin. ^[35] ${\displaystyle g(n)+O(n)}$
• 2NFA a DFA: estados, véase Mereghetti y Pighizzini . ^[36] y Geffert , Mereghetti y Pighizzini. ^[37] ${\displaystyle O(g(n))}$
• NFA a 2DFA: en la mayoría de los estados, consulte Chrobak. ^[34] ${\displaystyle O(n^{2})}$
• 2NFA a 2DFA: en la mayoría de los estados, demostrado implementando el método del teorema de Savitch , ver Geffert, Mereghetti y Pighizzini. ^[37] ${\displaystyle n^{O(\log n)}}$
• UFA a DFA: , ver Okhotin. ^[38] ${\displaystyle e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}}$
• NFA a UFA: , ver Okhotin. ^[38] ${\displaystyle g(n)+O(n^{2})}$

Unión

• DFA: estados, ver Yu, Zhuang y Salomaa. ^[19] ${\displaystyle mn}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle m+n+1}$
• 2DFA: entre y estados, ver Kunc y Okhotin. ^[24] ${\displaystyle m+n}$ ${\displaystyle 2m+n+4}$
• 2NFA: estados, ver Kunc y Okhotin. ^[25] ${\displaystyle m+n}$

Intersección

• DFA: estados, ver Yu, Zhuang y Salomaa. ^[19] ${\displaystyle mn}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle mn}$
• 2DFA: entre y estados, ver Kunc y Okhotin. ^[24] ${\displaystyle m+n}$ ${\displaystyle m+n+1}$
• 2NFA: entre y estados, ver Kunc y Okhotin. ^[25] ${\displaystyle m+n}$ ${\displaystyle m+n+1}$

Complementación

• DFA: estados. ${\displaystyle n}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle g(n)+O(n^{2})}$
• UFA: al menos los estados, ver Raskin, ^[39] y en la mayoría de los estados, ver Okhotin. ^[38] ${\displaystyle n^{(\log \log \log n)^{\Theta (1)}}}$ ${\displaystyle e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}}$
• 2DFA: al menos y en la mayoría de los estados, ver Kunc y Okhotin. ^[24] ${\displaystyle n}$ ${\displaystyle 2n+3}$
• 2NFA: al menos y en la mayoría de los estados. El límite superior se obtiene implementando el método del teorema de Immerman-Szelepcsényi , véase Geffert, Mereghetti y Pighizzini. ^[30] ${\displaystyle n}$ ${\displaystyle O(n^{8})}$

Concatenación

• DFA: estados, ver Yu, Zhuang y Salomaa. ^[19] ${\displaystyle mn}$
• NFA: entre y estados, ver Holzer y Kutrib. ^[20] ${\displaystyle m+n-1}$ ${\displaystyle m+n}$
• 2DFA: estados, ver Kunc y Okhotin. ^[24] ${\displaystyle e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}}$
• 2NFA: estados, ver Kunc y Okhotin. ^[24] ${\displaystyle e^{\Theta ({\sqrt {(m+n)\log(m+n)}})}}$

estrella kleene

• DFA: estados, ver Yu, Zhuang y Salomaa. ^[19] ${\displaystyle (n-1)^{2}+1}$
• NFA: estados, ver Holzer y Kutrib. ^[20] ${\displaystyle n+1}$
• UFA: estados, ver Okhotin. ^[38] ${\displaystyle (n-1)^{2}+1}$
• 2DFA: estados, ver Kunc y Okhotin. ^[24] ${\displaystyle \Theta ((g(n))^{2})}$
• 2NFA: estados, ver Kunc y Okhotin. ^[24] ${\displaystyle \Theta (g(n))}$

Otras lecturas

^{Holzer y Kutrib [40] [41]} y Gao et al. escribieron estudios sobre la complejidad del estado. ^[42]

Las nuevas investigaciones sobre la complejidad del estado se presentan comúnmente en los talleres anuales sobre Complejidad Descriptiva de Sistemas Formales (DCFS), en la Conferencia sobre Implementación y Aplicación de Autómatas (CIAA) y en varias conferencias sobre informática teórica en general.

Referencias

1. Rabin, MO; Scott, D. (1959). "Autómatas finitos y sus problemas de decisión". Revista IBM de investigación y desarrollo . 3 (2): 114-125. doi :10.1147/rd.32.0114. ISSN  0018-8646.
2. Lupanov, Oleg B. (1963). "Una comparación de dos tipos de fuentes finitas". Kibernetiki problemático . 9 : 321–326.
3. Leung, Hing (2005). "Complejidad descriptiva de NFA de diferente ambigüedad". Revista Internacional de Fundamentos de la Informática . 16 (5): 975–984. doi :10.1142/S0129054105003418. ISSN  0129-0541.
4. Schmidt, Erik M. (1978). Concisión de la descripción de lenguajes libres de contexto, regulares e inequívocos (Ph.D.). Universidad de Cornell.
5. Jirásková, Galina; Pighizzini, Giovanni (2011). "Simulación óptima de autómatas autoverificantes mediante autómatas deterministas". Información y Computación . 209 (3): 528–535. doi :10.1016/j.ic.2010.11.017. ISSN  0890-5401.
6. Kapoutsis, Christos (2005). "Eliminar la bidireccionalidad de los autómatas finitos no deterministas". Fundamentos matemáticos de la informática 2005 . Apuntes de conferencias sobre informática. vol. 3618. págs. 544–555. doi :10.1007/11549345_47. ISBN 978-3-540-28702-5. ISSN  0302-9743.
7. Shepherdson, JC (1959). "La reducción de autómatas bidireccionales a autómatas unidireccionales". Revista IBM de investigación y desarrollo . 3 (2): 198–200. doi :10.1147/rd.32.0198. ISSN  0018-8646.
8. Moore, FR (1971). "Sobre los límites del tamaño establecido por el estado en las pruebas de equivalencia entre autómatas finitos deterministas, no deterministas y bidireccionales". Transacciones IEEE en computadoras . C-20 (10): 1211–1214. doi :10.1109/TC.1971.223108. ISSN  0018-9340. S2CID  206618275.
9. Birget, Jean-Camille (1993). "Estado-complejidad de dispositivos de estados finitos, compresibilidad e incompresibilidad del estado". Teoría de Sistemas Matemáticos . 26 (3): 237–269. doi :10.1007/BF01371727. ISSN  0025-5661. S2CID  20375279.
10. Vardi, Moshe Y. (1989). "Una nota sobre la reducción de autómatas bidireccionales a autómatas unidireccionales". Cartas de procesamiento de información . 30 (5): 261–264. CiteSeerX 10.1.1.60.464 . doi :10.1016/0020-0190(89)90205-6. ISSN  0020-0190. 
11. Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternancia". Revista de la ACM . 28 (1): 114-133. doi : 10.1145/322234.322243 . ISSN  0004-5411. S2CID  238863413.
12. Fellah, A.; Jürgensen, H.; Yu, S. (1990). "Construcciones para autómatas finitos alternos∗". Revista Internacional de Matemáticas Informáticas . 35 (1–4): 117–132. doi :10.1080/00207169008803893. ISSN  0020-7160.
13. Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Alternancia de pushdown y apilamiento de autómatas". Revista SIAM de Computación . 13 (1): 135-155. doi :10.1137/0213010. ISSN  0097-5397.
14. Geffert, Viliam; Ojotin, Alejandro (2014). Transformación de autómatas finitos alternos bidireccionales en autómatas no deterministas unidireccionales . Apuntes de conferencias sobre informática. vol. 8634, págs. 291–302. doi :10.1007/978-3-662-44522-8_25. ISBN 978-3-662-44521-1. ISSN  0302-9743.
15. Sakoda, William J.; Sipser, Michael (1978). "No determinismo y el tamaño de los autómatas finitos bidireccionales". Actas del décimo simposio anual de ACM sobre teoría de la informática - STOC '78 . STOC 1978. ACM. págs. 275–286. doi : 10.1145/800133.804357 .
16. Berman, Piotr; Lingás, Andrzej (1977). Sobre la complejidad de los lenguajes regulares en términos de autómatas finitos . vol. Informe 304. Academia Polaca de Ciencias.
17. Kapoutsis, Christos A. (2014). "Autómatas bidireccionales versus espacio logarítmico". Teoría de los Sistemas Computacionales . 55 (2): 421–447. doi :10.1007/s00224-013-9465-0. S2CID  14808151.
18. Maslov, AN (1970). "Estimaciones del número de estados de autómatas finitos". Matemáticas soviéticas - Doklady . 11 : 1373-1375.
19. Yu, Sheng; Zhuang, Qingyu; Salomaa, Kai (1994). "Las complejidades estatales de algunas operaciones básicas en lenguajes regulares". Informática Teórica . 125 (2): 315–328. doi :10.1016/0304-3975(92)00011-F. ISSN  0304-3975.
20. Holzer, Markus; Kutrib, Martín (2003). "Complejidad descriptiva no determinista de lenguajes regulares". Revista internacional de fundamentos de la informática (manuscrito enviado). 14 (6): 1087-1102. doi :10.1142/S0129054103002199. ISSN  0129-0541.
21. Göös, Mika; Kiefer, Stefan; Yuan, Weiqiang (12 de febrero de 2022). "Límites inferiores para autómatas inequívocos a través de la complejidad de la comunicación". arXiv : 2109.09155 [cs.FL].
22. Jirásek, Jozef; Jirásková, Galina; Šebej, Juraj (2016). Operaciones sobre autómatas finitos inequívocos . Apuntes de conferencias sobre informática. vol. 9840, págs. 243–255. doi :10.1007/978-3-662-53132-7_20. ISBN 978-3-662-53131-0. ISSN  0302-9743.
23. Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alejandro (2015). Ciencias de la Computación - Teoría y Aplicaciones . Apuntes de conferencias sobre informática. vol. 9139, págs. 231–261. doi :10.1007/978-3-319-20297-6_16. ISBN 978-3-319-20296-9. ISSN  0302-9743.
24. Kunc, Michal; Ojotin, Alejandro (2012). "Estado de complejidad de las operaciones en autómatas finitos bidireccionales sobre un alfabeto unario". Informática Teórica . 449 : 106-118. doi : 10.1016/j.tcs.2012.04.010 . ISSN  0304-3975.
25. Kunc, Michal; Ojotin, Alejandro (2011). "Estado de complejidad de unión e intersección para autómatas finitos no deterministas bidireccionales". Fundamentos de la informática . 110 (1–4): 231–239. doi :10.3233/FI-2011-540.
26. Birget, Jean-Camille (1993). "Órdenes parciales de palabras, elementos mínimos de lenguajes regulares y complejidad del estado". Informática Teórica . 119 (2): 267–291. doi :10.1016/0304-3975(93)90160-U. ISSN  0304-3975.
27. Jirásková, Galina (2005). "Estado de complejidad de algunas operaciones en lenguajes binarios regulares". Informática Teórica . 330 (2): 287–298. doi : 10.1016/j.tcs.2004.04.011., Teorema 5
28. Raskin, Mikhail (2018). "Un límite inferior superpolinomial para el tamaño del complemento no determinista de un autómata inequívoco". DROPS-IDN/V2/Document/10.4230/LIPIcs.ICALP.2018.138 . Schloss-Dagstuhl - Leibniz Zentrum für Informatik. doi : 10.4230/LIPIcs.ICALP.2018.138 .
29. Indzhev, Emil; Kiefer, Stefan (1 de agosto de 2022). "Sobre complementar autómatas y gráficos inequívocos con muchas camarillas y cocliques". Cartas de procesamiento de información . 177 : 106270. arXiv : 2105.07470 . doi : 10.1016/j.ipl.2022.106270 . ISSN  0020-0190. S2CID  234741832 . Consultado el 29 de mayo de 2022 .
30. Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007). "Complementando autómatas finitos bidireccionales". Información y Computación . 205 (8): 1173–1187. doi : 10.1016/j.ic.2007.01.008 . ISSN  0890-5401.
31. Jirásková, Galina; Ojotin, Alejandro (2008). Sobre la complejidad estatal de las operaciones en autómatas finitos bidireccionales . Apuntes de conferencias sobre informática. vol. 5257, págs. 443–454. doi :10.1007/978-3-540-85780-8_35. ISBN 978-3-540-85779-2. ISSN  0302-9743.
32. Mirkin, Boris G. (1966). "Sobre autómatas duales". Cibernética . 2 : 6–9. doi :10.1007/bf01072247. S2CID  123186223.
33. Leiss, Ernst (1985). "Representación sucinta de lenguajes regulares mediante autómatas booleanos II". Informática Teórica . 38 : 133-136. doi :10.1016/0304-3975(85)90215-4. ISSN  0304-3975.
34. Chrobak, Marek (1986). "Autómatas finitos y lenguajes unarios". Informática Teórica . 47 : 149-158. doi :10.1016/0304-3975(86)90142-8. ISSN  0304-3975.
35. Kunc, Michal; Ojotin, Alejandro (2011). Desarrollos en la teoría del lenguaje . Apuntes de conferencias sobre informática. vol. 6795, págs. 324–336. CiteSeerX 10.1.1.616.8835 . doi :10.1007/978-3-642-22321-1_28. ISBN  978-3-642-22320-4. ISSN  0302-9743.
36. Mereghetti, Carlo; Pighizzini, Giovanni (2001). "Simulaciones óptimas entre autómatas unarios". Revista SIAM de Computación . 30 (6): 1976–1992. doi :10.1137/S009753979935431X. hdl : 2434/35121 . ISSN  0097-5397.
37. Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2003). "Conversión de autómatas unarios no deterministas bidireccionales en autómatas más simples". Informática Teórica . 295 (1–3): 189–203. doi :10.1016/S0304-3975(02)00403-6. ISSN  0304-3975.
38. Okhotin, Alejandro (2012). "Autómatas finitos inequívocos sobre un alfabeto unario". Información y Computación . 212 : 15–36. doi : 10.1016/j.ic.2012.01.003 . ISSN  0890-5401.
39. Raskin, Michael (2018). "Un límite inferior superpolinómico para el tamaño del complemento no determinista de un autómata inequívoco". Proc. ICALP 2018 . págs. 138:1–138:11. doi : 10.4230/LIPIcs.ICALP.2018.138 .
40. Holzer, Markus; Kutrib, Martín (2009). "Autómatas finitos no deterministas: resultados recientes sobre la complejidad descriptiva y computacional". Revista Internacional de Fundamentos de la Informática . 20 (4): 563–580. doi :10.1142/S0129054109006747. ISSN  0129-0541.
41. Holzer, Markus; Kutrib, Martín (2011). "Complejidad descriptiva y computacional de autómatas finitos: una encuesta". Información y Computación . 209 (3): 456–470. doi :10.1016/j.ic.2010.11.013. ISSN  0890-5401.
42. Gao, Yuan; Moreira, Nelma; Reis, Rogerio; Yu, Sheng (2015). "Una encuesta sobre la complejidad operativa del estado". arXiv : 1509.03254v1 [cs.FL].