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-state no determinista finita por un autómata determinista autómata finito requiere exactamente estados en el peor de los casos.
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 no ambiguos (UFA), autoverificables (SVFA) y alternos (AFA). Estos autómatas también pueden ser bidireccionales (2UFA, 2SVFA, 2AFA).
Todas estas máquinas pueden aceptar exactamente los idiomas regulares . Sin embargo, el tamaño de los 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, la compensación de complejidad de estado entre ellos es una función entera dónde es el menor número de estados en los autómatas del segundo tipo suficiente para reconocer cada lenguaje reconocido por un -estado autómata del primer tipo. Se conocen los siguientes resultados.
- NFA a DFA: estados. Esta es la construcción del subconjunto de Rabin y Scott , [1] que Lupanov demostró ser óptima . [2]
- UFA a DFA: estados, ver Leung , [3] Un límite inferior anterior de Schmidt [4] era más pequeño.
- NFA a UFA: estados, ver Leung. [3] Hubo un límite inferior más pequeño anterior por Schmidt. [4]
- SVFA a DFA: estados, véase Jirásková y Pighizzini [5]
- 2DFA a DFA: estados, ver Kapoutsis . [6] La construcción anterior de Shepherdson [7] usó más estados, y un límite inferior anterior de Moore [8] era más pequeño.
- 2DFA a NFA: , ver Kapoutsis. [6] La construcción anterior de Birget [9] utilizó más estados.
- 2NFA a NFA: , ver Kapoutsis. [6]
- AFA a DFA: estados, ver Chandra , Kozen y Stockmeyer . [11]
- AFA a NFA: estados, ver Fellah, Jürgensen y Yu. [12]
- 2AFA a DFA: , ver Ladner , Lipton y Stockmeyer . [13]
- 2AFA a NFA: , ver Geffert y Okhotin. [14]
El problema 2DFA vs. 2NFA y el espacio logarítmico
¿Cada -el estado 2NFA tiene un equivalente -estado 2DFA?
Es un problema abierto si todos los 2NFA se pueden convertir en 2DFA con polinomialmente muchos estados, es decir, si hay un polinomio tal que por cada -estado 2NFA existe un -estado 2DFA. 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]
Estado de la complejidad de las operaciones para autómatas finitos
Dada una operación binaria de preservación de la regularidad en idiomas y una familia de autómatas X (DFA, NFA, etc.), la complejidad de estado de es una función entera tal que
- para cada autómata X de estado m A y autómata X de estado n B hay un -estado X-autómata para , y
- para todos los enteros m, n hay un autómata X de estado m A y un autómata X de estado n B tal que cada autómata X para debe tener al menos estados.
Se aplica una definición análoga para operaciones con cualquier número de argumentos.
Los primeros resultados sobre la complejidad estatal de las operaciones para los 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 idioma requiere m estados e idioma requiere n estados, cuántos estados requiere?
- DFA: estados, véanse Maslov [18] y Yu, Zhuang y Salomaa. [19]
- NFA: estados, ver Holzer y Kutrib. [20]
- UFA: entre y estados, véanse Jirásek, Jirásková y Šebej. [21]
- SVFA: estados, véanse Jirásek, Jirásková y Szabari. [22]
- 2DFA: entre y estados, véanse Kunc y Okhotin. [23]
- 2NFA: estados, véanse Kunc y Okhotin. [24]
Intersección
Cuantos estados requiere?
- DFA: estados, véanse Maslov [18] y Yu, Zhuang y Salomaa. [19]
- NFA: estados, ver Holzer y Kutrib. [20]
- UFA: estados, véanse Jirásek, Jirásková y Šebej. [21]
- SVFA: estados, véanse Jirásek, Jirásková y Szabari. [22]
- 2DFA: entre y estados, véanse Kunc y Okhotin. [23]
- 2NFA: entre y estados, véanse Kunc y Okhotin. [24]
Complementacion
Si el lenguaje L requiere n estados, ¿cuántos estados requiere su complemento ?
- DFA: estados, intercambiando estados de aceptación y rechazo.
- NFA: estados, ver Birget. [25]
- UFA: al menos y como mucho estados, véase Okhotin [26] para el límite inferior e Indzhev y Kiefer [27] para el límite superior. Raskin [28] demostró recientemente un límite inferior superpolinomial.
- SVFA: estados, intercambiando estados de aceptación y rechazo.
- 2DFA: al menos y como mucho estados, véanse Geffert, Mereghetti y Pighizzini. [29]
Concatenación
Cuantos estados requiere?
- DFA: estados, véanse Maslov [18] y Yu, Zhuang y Salomaa. [19]
- NFA: estados, ver Holzer y Kutrib. [20]
- UFA: estados, véanse Jirásek, Jirásková y Šebej. [21]
- SVFA: estados, véanse Jirásek, Jirásková y Szabari. [22]
- 2DFA: al menos y como mucho estados, véanse Jirásková y Okhotin. [30]
Estrella de Kleene
- DFA: estados, véanse Maslov [18] y Yu, Zhuang y Salomaa. [19]
- NFA: estados, ver Holzer y Kutrib. [20]
- UFA: estados, véanse Jirásek, Jirásková y Šebej. [21]
- SVFA: estados, véanse Jirásek, Jirásková y Szabari. [22]
- 2DFA: al menos y como mucho estados, véanse Jirásková y Okhotin. [30]
Inversión
- DFA: estados, ver Mirkin, [31] Leiss, [32] y Yu, Zhuang y Salomaa. [19]
- NFA: estados, ver Holzer y Kutrib. [20]
- UFA: estados.
- SVFA: estados, véanse Jirásek, Jirásková y Szabari. [22]
- 2DFA: entre y estados, véanse Jirásková y Okhotin. [30]
Autómatas finitos sobre un alfabeto unario
La complejidad de estado de los autómatas finitos con un alfabeto de una letra ( unario ), iniciada por Chrobak , [33] es diferente del caso de varias letras.
Dejar ser la función de Landau .
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. [33]
- 2DFA a DFA: estados, véanse Chrobak [33] y Kunc y Okhotin. [34]
- 2NFA a DFA: estados, véase Mereghetti y Pighizzini . [35] y Geffert , Mereghetti y Pighizzini. [36]
- NFA a 2DFA: como máximo estados, ver Chrobak. [33]
- 2NFA a 2DFA: como máximo estados, demostrados mediante la implementación del método del teorema de Savitch , ver Geffert, Mereghetti y Pighizzini. [36]
- UFA a DFA: , ver Okhotin. [26]
- NFA a UFA: , ver Okhotin. [26]
Unión
- DFA: estados, véanse Yu, Zhuang y Salomaa. [19]
- NFA: estados, ver Holzer y Kutrib. [20]
- 2DFA: entre y estados, véanse Kunc y Okhotin. [23]
- 2NFA: estados, véanse Kunc y Okhotin. [24]
Intersección
- DFA: estados, véanse Yu, Zhuang y Salomaa. [19]
- NFA: estados, ver Holzer y Kutrib. [20]
- 2DFA: entre y estados, véanse Kunc y Okhotin. [23]
- 2NFA: entre y estados, véanse Kunc y Okhotin. [24]
Complementacion
- DFA: estados.
- NFA: estados, Holzer y Kutrib. [20]
- UFA: al menos y como mucho estados, ver Okhotin. [26]
- 2DFA: al menos y como mucho estados, véanse Kunc y Okhotin. [23]
- 2NFA: al menos y como mucho estados. El límite superior es mediante la implementación del método del teorema de Immerman-Szelepcsényi , ver Geffert, Mereghetti y Pighizzini. [29]
Concatenación
- DFA: estados, véanse Yu, Zhuang y Salomaa. [19]
- NFA: entre y estados, ver Holzer y Kutrib. [20]
- 2DFA: estados, véanse Kunc y Okhotin. [23]
- 2NFA: estados, véanse Kunc y Okhotin. [23]
Estrella de Kleene
- DFA: estados, véanse Yu, Zhuang y Salomaa. [19]
- NFA: estados, ver Holzer y Kutrib. [20]
- UFA: estados, ver Okhotin. [26]
- 2DFA: estados, véanse Kunc y Okhotin. [23]
- 2NFA: estados, véanse Kunc y Okhotin. [23]
Otras lecturas
Las encuestas de complejidad estatal fueron escritas por Holzer y Kutrib [37] [38] y por Gao et al. [39]
Las nuevas investigaciones sobre la complejidad del estado se presentan comúnmente en los talleres anuales sobre Complejidad Descripcional 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
- ^ Rabin, MO; Scott, D. (1959). "Autómatas finitos y sus problemas de decisión". Revista de investigación y desarrollo de IBM . 3 (2): 114-125. doi : 10.1147 / rd.32.0114 . ISSN 0018-8646 .
- ^ Lupanov, Oleg B. (1963). "Una comparación de dos tipos de fuentes finitas". Problemy Kibernetiki . 9 : 321–326.
- ^ a b Leung, Hing (2005). "Complejidad descriptiva de NFA de diferente ambigüedad". Revista Internacional de Fundamentos de la Ciencia de la Computación . 16 (5): 975–984. doi : 10.1142 / S0129054105003418 . ISSN 0129-0541 .
- ^ a b Schmidt, Erik M. (1978). Concisión de la descripción de lenguajes libres de contexto, regulares e inequívocos (Ph.D.). Universidad de Cornell.
- ^ Jirásková, Galina; Pighizzini, Giovanni (2011). "Simulación óptima de autómatas autoverificables mediante autómatas deterministas". Información y Computación . 209 (3): 528–535. doi : 10.1016 / j.ic.2010.11.017 . ISSN 0890-5401 .
- ^ a b c Kapoutsis, Christos (2005). "Eliminación de bidireccionalidad de autómatas finitos no deterministas". Fundamentos matemáticos de la informática 2005 . Apuntes de conferencias en Ciencias de la Computación. 3618 . págs. 544–555. doi : 10.1007 / 11549345_47 . ISBN 978-3-540-28702-5. ISSN 0302-9743 .
- ^ Shepherdson, JC (1959). "La reducción de autómatas bidireccionales a autómatas unidireccionales". Revista de investigación y desarrollo de IBM . 3 (2): 198–200. doi : 10.1147 / rd.32.0198 . ISSN 0018-8646 .
- ^ Moore, FR (1971). "En los límites del tamaño del conjunto de estados 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 .
- ^ Birget, Jean-Camille (1993). "Estado-complejidad de los dispositivos de estado finito, compresibilidad e incompresibilidad del estado". Teoría de sistemas matemáticos . 26 (3): 237–269. doi : 10.1007 / BF01371727 . ISSN 0025-5661 .
- ^ 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 .
- ^ 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 .
- ^ 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 .
- ^ Ladner, Richard E .; Lipton, Richard J .; Stockmeyer, Larry J. (1984). "Autómatas de empuje y pila alternos". Revista SIAM de Computación . 13 (1): 135-155. doi : 10.1137 / 0213010 . ISSN 0097-5397 .
- ^ Geffert, Viliam; Okhotin, Alexander (2014). Transformación de autómatas finitos alternos bidireccionales en autómatas no deterministas unidireccionales . Apuntes de conferencias en Ciencias de la Computación. 8634 . págs. 291-302. doi : 10.1007 / 978-3-662-44522-8_25 . ISBN 978-3-662-44521-1. ISSN 0302-9743 .
- ^ Sakoda, William J .; Sipser, Michael (1978). El no determinismo y el tamaño de los autómatas finitos bidireccionales . STOC 1978. ACM. págs. 275-286. doi : 10.1145 / 800133.804357 .
- ^ Berman, Piotr; Lingas, Andrzej (1977). Sobre la complejidad de los lenguajes regulares en términos de autómatas finitos . Informe 304. Academia de Ciencias de Polonia.
- ^ Kapoutsis, Christos A. (2014). "Autómatas bidireccionales versus espacio logarítmico". Teoría de los sistemas informáticos . 55 (2): 421–447. doi : 10.1007 / s00224-013-9465-0 .
- ^ a b c d e Maslov, AN (1970). "Estimaciones del número de estados de autómatas finitos". Matemáticas soviéticas - Doklady . 11 : 1373-1375.
- ^ a b c d e f g h yo j 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 .
- ^ a b c d e f g h yo j k Holzer, Markus; Kutrib, Martin (2003). "Complejidad descriptiva no determinista de lenguajes regulares" . Revista Internacional de Fundamentos de la Ciencia de la Computación (manuscrito enviado). 14 (6): 1087-1102. doi : 10.1142 / S0129054103002199 . ISSN 0129-0541 .
- ^ a b c d Jirásek, Jozef; Jirásková, Galina; Šebej, Juraj (2016). Operaciones en autómatas finitos inequívocos . Apuntes de conferencias en Ciencias de la Computación. 9840 . págs. 243-255. doi : 10.1007 / 978-3-662-53132-7_20 . ISBN 978-3-662-53131-0. ISSN 0302-9743 .
- ^ a b c d e Jirásek, Jozef Štefan; Jirásková, Galina; Szabari, Alexander (2015). Ciencias de la Computación - Teoría y Aplicaciones . Apuntes de conferencias en Ciencias de la Computación. 9139 . págs. 231-261. doi : 10.1007 / 978-3-319-20297-6_16 . ISBN 978-3-319-20296-9. ISSN 0302-9743 .
- ^ a b c d e f g h yo Kunc, Michal; Okhotin, Alexander (2012). "Estado de la 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 .
- ^ a b c d Kunc, Michal; Okhotin, Alexander (2011). "Complejidad estatal de unión e intersección para autómatas finitos no deterministas bidireccionales". Fundamenta Informaticae . 110 (1–4): 231–239. doi : 10.3233 / FI-2011-540 .
- ^ 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 .
- ^ a b c d e Okhotin, Alexander (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 .
- ^ Indzhev, Emil; Kiefer, Stefan (2021). "Sobre la complementación de autómatas y gráficos inequívocos con muchas camarillas y cocliques". arXiv : 2105.07470 [ cs.FL ].
- ^ Raskin, Michael (2018). "Un límite inferior superpolinomial 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 .
- ^ a b Geffert, Viliam; Mereghetti, Carlo; Pighizzini, Giovanni (2007). "Complemento de autómatas finitos bidireccionales". Información y Computación . 205 (8): 1173-1187. doi : 10.1016 / j.ic.2007.01.008 . ISSN 0890-5401 .
- ^ a b c Jirásková, Galina; Okhotin, Alexander (2008). Sobre la complejidad estatal de las operaciones en autómatas finitos bidireccionales . Apuntes de conferencias en Ciencias de la Computación. 5257 . págs. 443–454. doi : 10.1007 / 978-3-540-85780-8_35 . ISBN 978-3-540-85779-2. ISSN 0302-9743 .
- ^ Mirkin, Boris G. (1966). "Sobre autómatas duales". Cibernética . 2 : 6-9. doi : 10.1007 / bf01072247 .
- ^ Leiss, Ernst (1985). "Representación sucinta de lenguajes regulares por autómatas booleanos II". Informática Teórica . 38 : 133-136. doi : 10.1016 / 0304-3975 (85) 90215-4 . ISSN 0304-3975 .
- ^ a b c d 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 .
- ^ Kunc, Michal; Okhotin, Alexander (2011). Desarrollos en la teoría del lenguaje . Apuntes de conferencias en Ciencias de la Computación. 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 .
- ^ 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 .
- ^ a b 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 .
- ^ Holzer, Markus; Kutrib, Martin (2009). "Autómatas finitos no deterministas - resultados recientes sobre la complejidad descriptiva y computacional". Revista Internacional de Fundamentos de la Ciencia de la Computación . 20 (4): 563–580. doi : 10.1142 / S0129054109006747 . ISSN 0129-0541 .
- ^ Holzer, Markus; Kutrib, Martin (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 .
- ^ Gao, Yuan; Moreira, Nelma; Reis, Rogério; Yu, Sheng (2015). "Una encuesta sobre la complejidad operacional del Estado". arXiv : 1509.03254v1 [ cs.FL ].