El problema de no vacío de intersección , también conocido como problema de intersección de autómatas finitos [1] o problema de no vacío de intersección , es un problema de decisión PSPACE-completo del campo de la teoría de autómatas .
Un problema de decisión de no vacío se define de la siguiente manera. Dado un autómata como entrada, el objetivo es determinar si el lenguaje del autómata es o no no vacío. En otras palabras, el objetivo es determinar si existe una cadena que sea aceptada por el autómata.
Los problemas de no vacío se han estudiado en el campo de la teoría de autómatas durante muchos años. Se ha demostrado que varios problemas comunes de no vacío son completos para clases de complejidad que van desde el espacio logarítmico determinista hasta el espacio PSPACE . [2]
El problema de decisión de intersección no vacía se ocupa de determinar si la intersección de lenguajes dados no es vacía. En particular, el problema de intersección no vacía se define de la siguiente manera. Dada una lista de autómatas finitos deterministas como entrada, el objetivo es determinar si sus lenguajes regulares asociados tienen o no una intersección no vacía. En otras palabras, el objetivo es determinar si existe una cadena que sea aceptada por todos los autómatas en la lista.
Existe un algoritmo de tiempo exponencial común que resuelve el problema de no vacío de intersección basado en la construcción del producto cartesiano introducida por Michael O. Rabin y Dana Scott . [3] La idea es que todos los autómatas juntos formen un autómata producto de modo que una cadena sea aceptada por todos los autómatas si y solo si es aceptada por el autómata producto. Por lo tanto, una búsqueda en amplitud (o búsqueda en profundidad ) dentro del diagrama de estados del autómata producto determinará si existe una ruta desde el estado inicial del producto hasta uno de los estados finales del producto. Si existe o no dicha ruta es equivalente a determinar si alguna cadena es aceptada por todos los autómatas en la lista.
Nota: No es necesario que el autómata del producto esté completamente construido. Los autómatas juntos proporcionan suficiente información para que se puedan determinar las transiciones según sea necesario.
En un trabajo de Dexter Kozen en 1977 se demostró que el problema de no vacío de intersección es PSPACE-completo . [1] Desde entonces, se han mostrado muchos resultados de dureza adicionales. Sin embargo, sigue siendo un problema abierto determinar si existen algoritmos más rápidos. [4]
* Vea una lista incompleta de publicaciones relacionadas aquí .