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

Deje que sean dos lenguajes regulares dados por NFA como entrada. $L_1,L_2$ $M_1,M_2$

Supongamos que nos gustaría verificar si . Esto puede hacerse claramente mediante un algoritmo cuadrático que computa el autómata del producto de , pero me preguntaba si se sabe algo más eficiente. $L_1\cap L_2\neq \emptyset$ $M_1,M_2$

¿Existe un algoritmo para decidir si ? ¿Cuál es el algoritmo más rápido conocido? $o(n^2)$ $L_1\cap L_2\neq \emptyset$

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.

2^{\frac{n}{2}}

$2^{\frac{n}{2}}$

Michael Wehar

Creo que todavía está abierto para cualquier subcuadrático. Más información: rjlipton.wordpress.com/2009/08/17/…

Michael Wehar

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

RB: Suponga que puede probar el vacío de dos DFA de tamaño

en el tiempo

con

. Ahora, si tiene

DFA de tamaño

, puede construir el producto de los primeros

DFA y de los

DFA restantes. Luego, pruebe el vacío en el tiempo

n

$n$

n^{1 + ε}

$n^{1+\varepsilon}$

ε < 1

$\varepsilon < 1$

k

$k$

n

$n$

k / 2

$k/2$

k / 2

$k/2$

que es mejor que

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

(n^{k / 2})^{1 + ε} = n^{\frac{1}{2} k + \frac{ε}{2} k}

$(n^{k/2})^{1+\varepsilon} = n^{\frac{1}{2}k + \frac{\varepsilon}{2}k}$

n^{k}

$n^k$

Michael Blondin

@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:

Respuesta simple : si existe un algoritmo más eficiente que se ejecuta en el tiempo durante algún , entonces la hipótesis del tiempo exponencial fuerte sería refutada. $O(n^{\delta})$ $\delta < 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 tiempo. $O(n^{\delta})$ $poly(n)\cdot2^{(\delta 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^{\delta})$

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 de $\frac{n}{2}$ $\frac{n}{2}$ $\frac{n}{2}$ $\frac{n}{2}$

$D_1$ $D_2$

$D_1$ $D_2$ $D_1$ $D_2$ $D_1$ $D_2$

$poly(n) \cdot 2^{n/2}$ $poly(n)$

$poly(n) \cdot 2^{(\delta 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^{\delta})$ $poly(n) \cdot 2^{(\delta k/2)}$

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

Michael Wehar
fuente

Ω (n^{2})

$\Omega(n^2)$

k

$k$

k

$k$

(2 k - 2)

$(2k-2)$

k

$k$

N S p a c e (2 \cdot \log (n)) \subseteq D T i m e (n)

$NSpace(2 \cdot \log(n)) \subseteq DTime(n)$

N S p a c e (2 \cdot \log (n))

$NSpace(2 \cdot \log(n))$

2 \cdot \log (n)

$2\cdot \log(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