Problema de no vacuidad en intersecciones

El problema de la no vacuidad de la intersección , también conocido como problema de la intersección de autómatas finitos ^{[ 1 ]} o problema de la no vacuidad de la intersección , es un problema de decisión PSPACE-completo del campo de la teoría de autómatas . El problema pregunta si una lista de autómatas finitos deterministas tiene una intersección no vacía.

Un problema de decisión de no vacuidad se define (para un tipo particular de autómata) de la siguiente manera: dado un autómata como entrada, el objetivo es determinar si el lenguaje del autómata no está vacío, es decir, si existe una cadena que el autómata acepte. Los problemas de no vacuidad 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 vacuidad son completos para clases de complejidad que van desde Deterministic Logspace hasta PSPACE . ^{[ 2 ]}

El problema de decisión de intersección no vacía es similar, pero se define sobre una lista de autómatas, en lugar de uno solo. En particular, para los fines de este artículo: dada una lista de autómatas finitos deterministas como entrada, determinar si sus lenguajes regulares asociados tienen o no una intersección no vacía; es decir, determinar si existe una cadena que sea aceptada por todos los autómatas de la lista.

Existe un algoritmo de tiempo exponencial que resuelve el problema de no vacuidad de intersección basado en la construcción de producto cartesiano introducida por Michael O. Rabin y Dana Scott . ^{[ 3 ]} La idea es que todos los autómatas juntos forman un "autómata producto" cuyos estados consisten en tuplas de estados en la lista de autómatas; una cadena es aceptada por el autómata producto si y solo si es aceptada por cada autómata en la lista. Por lo tanto, una búsqueda en amplitud (o en profundidad ) dentro del espacio de estados del autómata producto determinará si existe un camino desde el estado inicial del producto a uno de los estados finales del producto. Si existe o no tal camino es equivalente a determinar si cualquier cadena es aceptada por cada autómata en la lista.

Para esta construcción, no es necesario construir explícitamente el autómata producto; los autómatas proporcionan información suficiente para que las transiciones puedan determinarse según sea necesario.

Dexter Kozen demostró en 1977 que el problema de la no vacuidad de la intersección es PSPACE-completo. ^{[ 1 ]} Es un problema abierto si existen algoritmos más rápidos. ^{[ 4 ]}

• Autómata finito determinista
• Problema del vacío
• PSPACE-completo
• Lista de problemas completos de PSPACE