Decidir el vacío de la intersección de las lenguas regulares en el tiempo subcuadrático

23

Deje que sean dos lenguajes regulares dados por NFA M 1 , M 2 como entrada.L1,L2M1,M2

Supongamos que nos gustaría verificar si . Esto puede hacerse claramente mediante un algoritmo cuadrático que computa el autómata del producto de M 1 , M 2 , pero me preguntaba si se sabe algo más eficiente.L1L2M1,M2

¿Existe un algoritmo para decidir si L 1L 2 ? ¿Cuál es el algoritmo más rápido conocido?o(n2)L1L2

RB
fuente
55
Si alguien tiene buenas ideas, hágamelo saber, pero actualmente es un problema abierto. Si pudiera resolver este problema en un tiempo lineal, entonces básicamente cualquier problema solucionable por una máquina no determinista usando solo n bits de memoria podría resolverse de manera determinista en veces. 2n2
Michael Wehar
66
Creo que todavía está abierto para cualquier subcuadrático. Más información: rjlipton.wordpress.com/2009/08/17/…
Michael Wehar
44
Entonces, por ejemplo (basado en el comentario de Michael), la fuerte hipótesis del tiempo exponencial implica que el exponente debería ser 2. Creo que esto también podría resultar de la hipótesis del tiempo exponencial ...
Ryan Williams
44
RB: Suponga que puede probar el vacío de dos DFA de tamaño en el tiempo n 1 + ε con ε < 1 . Ahora, si tiene k DFA de tamaño n , puede construir el producto de los primeros k / 2 DFA y de los k / 2 DFA restantes. Luego, pruebe el vacío en el tiempo ( n k / 2 ) 1 + ε = n 1nn1+εε<1knk/2k/2que es mejor quenk. vzn: Este galardonado artículo fue escrito por @MichaelWehar, quien comentó en este hilo. Michael, tal vez podrías enviar una respuesta, si tienes tiempo. (nk/2)1+ε=n12k+ε2knk
Michael Blondin
44
@RyanWilliams Hola Ryan, ¿qué te lleva a pensar que la hipótesis del tiempo exponencial más débil implica que no podemos resolver el vacío de intersección para dos DFA más rápidamente? Alguien más me sugirió esto una vez también. :)
Michael Wehar

Respuestas:

22

Respuesta simple : si existe un algoritmo más eficiente que se ejecuta en el tiempo durante algún δ < 2 , entonces la hipótesis del tiempo exponencial fuerte sería refutada.O(nδ)δ<2


Vamos a demostrar un teorema más fuerte y luego la respuesta simple seguirá.

Teorema : si podemos resolver el problema de no vacío de intersección para dos DFA en tiempo , entonces cualquier problema que no se pueda resolver determinísticamente utilizando solo n bits de memoria se puede resolver determinísticamente en p o l y ( n ) 2 ( δ n / 2 ) tiempo.O(nδ)poly(n)2(δn/2)

Justificación : Supongamos que podemos resolver el vacío de intersección para dos DFA en el tiempo . Deje una máquina Turing no determinista M con una cinta de entrada de solo lectura y una cinta de trabajo binario de lectura / escritura. Deje una cadena de entrada x de longitud n. Suponga que M no accede a más de n bits de memoria en la cinta de trabajo binaria.O(nδ)

Un cálculo de M en la entrada x puede representarse mediante una lista finita de configuraciones. Cada configuración consta de un estado, una posición en la cinta de entrada, una posición en la cinta de trabajo y hasta n bits de memoria que representan la cinta de trabajo.

Ahora, considere que la cinta de trabajo se dividió por la mitad. En otras palabras, tenemos una sección izquierda de celdas y una sección derecha denn2n2n2n2

D1D2

D1D2D1D2D1D2

poly(n)2n/2poly(n)

poly(n)2(δn/2)

Puede encontrar esto útil: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/


k+O(log(n))O(nδ)poly(n)2(δk/2)

Comentarios, correcciones, sugerencias y preguntas son bienvenidas. :)

Michael Wehar
fuente
1
Ω(n2)
1
kk
1
(2k2)k
1
NSpace(2log(n))DTime(n)NSpace(2log(n))2log(n)espacio para máquinas Turing no deterministas con una cinta de entrada de solo lectura bidireccional y una cinta de trabajo binaria de lectura / escritura bidireccional.
Michael Wehar