Complejidad del estado

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

Los autómatas finitos pueden ser deterministas o no deterministas , unidireccionales (DFA, NFA) o bidireccionales (2DFA, 2NFA). Otras clases relacionadas son los autómatas finitos no ambiguos (UFA), autoverificables (SVFA) y alternantes (AFA). Estos autómatas también pueden ser bidireccionales (2UFA, 2SVFA, 2AFA).

Todas estas máquinas pueden aceptar exactamente los lenguajes regulares . Sin embargo, el tamaño de los diferentes tipos de autómatas necesarios para aceptar el mismo lenguaje (medido en el número de sus estados) puede ser diferente. Para cualesquiera dos tipos de autómatas finitos, la compensación de complejidad de estados entre ellos es una función entera donde es el número mínimo de estados en autómatas del segundo tipo suficiente para reconocer cada lenguaje reconocido por un autómata de estados 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 ]} demostrada como óptima por Lupanov . ^{[ 2 ]}${\displaystyle 2^{n}}$

• UFA a DFA: estados, ver Leung , ^{[ 3 ]} Un límite inferior anterior de Schmidt ^{[ 4 ]} era menor.${\displaystyle 2^{n}}$
• De NFA a UFA: estados, véase Leung. ^{[ 3 ]} Hubo un límite inferior menor anterior por Schmidt. ^{[ 4 ]}${\displaystyle 2^{n}-1}$
• SVFA a DFA: estados, véase Jirásková y Pighizzini ^{[ 5 ]}${\displaystyle \Theta (3^{n/3})}$
• 2DFA a DFA: estados, véase Kapoutsis . ^{[ 6 ]} La construcción anterior de Shepherdson ^{[ 7 ]} utilizó más estados, y una cota inferior anterior de Moore ^{[ 8 ]} fue menor.${\displaystyle n(n^{n}-(n-1)^{n})}$
• 2DFA a NFA: , véase 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 que acepta el complemento: estados, véase Vardi . ^{[ 10 ]}${\displaystyle O(4^{n})}$
• AFA a DFA: estados, ver 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)}}$

Problema sin resolver 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 pueden convertirse en 2DFA con un número polinomial de estados, es decir, si existe un polinomio tal que para cada 2NFA de -estados existe un 2DFA de -estados. 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 desarrollada posteriormente por Kapoutsis ^{[ 17 ]} .${\displaystyle p(n)}$${\displaystyle n}$${\displaystyle p(n)}$

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

• para cada autómata X de m estados A y autómata X de n estados B existe un autómata X de -estados para , y${\displaystyle f(m,n)}$${\displaystyle L(A)\circ L(B)}$
• Para todos los enteros m, n existe un autómata X de m estados A y un autómata X de n estados B tales que todo autómata X debe tener al menos estados.${\displaystyle L(A)\circ L(B)}$${\displaystyle f(m,n)}$

Se aplica una definición análoga para operaciones con cualquier número de argumentos.

Los primeros resultados sobre la complejidad de estados de las operaciones para autómatas finitos deterministas (AFD) fueron publicados por Maslov ^{[ 18 ]} y por Yu, Zhuang y Salomaa ^{[ 19 ]} . Holzer y Kutrib ^{[ 20 ]} fueron pioneros en el estudio de la complejidad de estados de las operaciones en autómatas finitos no deterministas (AFND). Los resultados conocidos para las operaciones básicas se enumeran a continuación.

Si un lenguaje requiere m estados y otro lenguaje requiere n estados, ¿cuántos estados requiere el segundo? ${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\ Displaystyle L_ {1} \ taza L_ {2}}$

• DFA: estados, ver Maslov ^{[ 18 ]} y Yu, Zhuang y Salomaa. ^{[ 19 ]}${\displaystyle mn}$
• NFA: estados, véase 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 estados y , ver Kunc y Okhotin. ^{[ 24 ]}${\displaystyle m+n}$${\displaystyle 4m+n+4}$
• 2NFA: estados, ver Kunc y Okhotin. ^{[ 25 ]}${\displaystyle m+n}$

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

• DFA: estados, ver Maslov ^{[ 18 ]} y Yu, Zhuang y Salomaa. ^{[ 19 ]}${\displaystyle mn}$
• NFA: estados, véase 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 estados y , ver Kunc y Okhotin. ^{[ 24 ]}${\displaystyle m+n}$${\displaystyle m+n+1}$
• 2NFA: entre estados , véase Kunc y Okhotin. ^{[ 25 ]}${\displaystyle m+n}$${\displaystyle m+n+1}$

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

• DFA: estados, mediante el intercambio de estados de aceptación y rechazo.${\displaystyle n}$
• NFA: estados, ver Birget. ^{[ 26 ]} o Jirásková ^{[ 27 ]}${\displaystyle 2^{n}}$
• UFA: al menos estados, véase Göös, Kiefer y Yuan, ^{[ 21 ]} (esto sigue una cota anterior de Raskin ^{[ 28 ]} ); y como máximo estados, véase 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 como máximo estados, véase Geffert, Mereghetti y Pighizzini. ^{[ 30 ]}${\displaystyle n}$${\displaystyle 4n}$

¿Cuántos estados se requieren? ${\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, véase 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}}}$

• DFA: estados, ver Maslov ^{[ 18 ]} y Yu, Zhuang y Salomaa. ^{[ 19 ]}${\displaystyle {\frac {3}{4}}2^{n}}$
• NFA: estados, véase 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})}}$

• DFA: estados, ver Mirkin, ^{[ 32 ]} Leiss, ^{[ 33 ]} y Yu, Zhuang y Salomaa. ^{[ 19 ]}${\displaystyle 2^{n}}$
• NFA: estados, véase 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}$

La complejidad de estado de los autómatas finitos con un alfabeto de una letra ( unario ), desarrollado por Chrobak , ^{[ 34 ]} es diferente del caso de múltiples letras.

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

Para un alfabeto de una sola letra, las transformaciones entre diferentes tipos de autómatas finitos a veces son 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 mediante la implementación del método del teorema de Savitch , véase 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})}$

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

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

• DFA: estados.${\displaystyle n}$
• NFA: estados, véase Holzer y Kutrib. ^{[ 20 ]}${\displaystyle g(n)+O(n^{2})}$
• UFA: al menos estados, véase Raskin, ^{[ 39 ]} y en la mayoría de los estados, véase Okhotin. ^{[ 38 ]}${\displaystyle n^{(\log \log \log n)^{\Theta (1)}}}$${\displaystyle e^{\Theta ({\sqrt[{3}]{n(\ln n)^{2}}})}}$
• 2DFA: al menos y como máximo estados, véase Kunc y Okhotin. ^{[ 24 ]}${\displaystyle n}$${\displaystyle 2n+3}$
• 2NFA: al menos y como máximo estados. La cota 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})}$

• DFA: estados, ver Yu, Zhuang y Salomaa. ^{[ 19 ]}${\displaystyle mn}$
• NFA: entre estados y , véase 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)}})}}$

• DFA: estados, ver Yu, Zhuang y Salomaa. ^{[ 19 ]}${\displaystyle (n-1)^{2}+1}$
• NFA: estados, véase 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))}$

^{Holzer y Kutrib [ 40 ] [ 41 ]} y Gao et al. ^{[ 42 ]} realizaron estudios sobre la complejidad de los estados.

Las nuevas investigaciones sobre la complejidad de los estados se presentan habitualmente 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 diversas conferencias sobre informática teórica en general.