¿Quedan problemas abiertos sobre los DFA?

59

Después de estudiar autómatas deterministas de estado finito (DFA) en pregrado, sentí que se los comprende muy bien. Mi pregunta es si hay algo que todavía no entendemos acerca de ellos. No me refiero a generalizaciones de DFA, sino a los DFA originales no modificados que estudiamos en pregrado.

Esta es una pregunta vaga, pero espero que entiendas la idea. Quiero entender si es justo decir que entendemos completamente los DFA. Así que realmente me refiero a preguntas que son inherentemente sobre DFA, no problemas hechos artificialmente para parecer un problema sobre DFA. Permítanme dar un ejemplo de tal problema. Sea L el lenguaje vacío si P = NP y algún lenguaje fijo no regular si P no es NP. ¿Puede L ser aceptado por un DFA? Esta pregunta se trata de DFA, pero no se trata de ellos en espíritu. Espero que mi punto sea claro y no obtengo respuestas pedantes de la gente.

En resumen, es justo decir

Básicamente entendemos completamente los DFA.

Lo siento si resulta que esta es una gran área de investigación de la que no estaba al tanto y acabo de insultar a toda una comunidad de personas.

Ganso canadiense
fuente
16
El primer problema abierto que se me ocurrió es si la conjetura de Černý es cierta. en.wikipedia.org/wiki/Synchronizing_word y liafa.jussieu.fr/~jep/Problemes/Cerny.html La siguiente publicación de blog también puede ser interesante para usted: rjlipton.wordpress.com/2009/08/17/…
Abuzer Yakaryilmaz
1
¿Cuentan los problemas abiertos sobre NFA y las expresiones regulares?
Hsien-Chih Chang 張顯 之
1
@ Hsien-Chih: seamos lo más restrictivos posible al interpretar la pregunta. Supuse que no quedan problemas abiertos, pero las respuestas muestran que esto no es cierto.
Ganso canadiense
1
Los DFA y las expresiones regulares son equivalentes. Los NFA y DFA son equivalentes en poder expresivo, aunque un NFA puede tener muchos menos estados que su DFA correspondiente.
chepner
66
@chepner Aunque los DFA, NFA y regexen son equivalentes en poder expresivo, eso de ninguna manera indica que saber todo sobre uno implica saber todo sobre el otro. Por ejemplo, saber cómo minimizar un DFA no le dice directamente cómo minimizar un NFA, ¡lo que en realidad es un problema bastante difícil !
Daniel Wagner

Respuestas:

55

Aquí hay un problema descrito en el libro "Un segundo curso en lenguajes formales y teoría de autómatas" de Shallit.

Sean y dos palabras distintas con . ¿Cuál es el tamaño del DFA más pequeño que acepta pero rechaza , o viceversa?v | u | = | v | = n u vuv|u|=|v|=nuv

Robson, en su artículo " Separando cadenas con pequeños autómatas " en 1989 demostró un límite superior . El límite inferior más conocido en .Ω ( log n )O(n2/5(logn)3/5)Ω(logn)

Para una encuesta ver esto .

Hsien-Chih Chang 張顯 之
fuente
12
En mi reciente charla en BCTCS 2014 en la Universidad de Loughborough, ofrezco 100 GBP por cualquier progreso no trivial en este problema. ¡Ah, y también hay otros problemas abiertos enumerados allí! Ver cs.uwaterloo.ca/~shallit/Talks/bc4.pdf .
Jeffrey Shallit
1
Aceptaré esto ya que fue el primero, pero todas son excelentes respuestas. ¡Gracias a todos y sigan viniendo!
Ganso canadiense
Ahora en Wikipedia como en.wikipedia.org/wiki/Separating_words_problem
David Eppstein
40

Aquí hay un problema de decisión muy simple sobre DFA. Dado un DFA M, ¿acepta M la representación en base 2 de al menos un número primo?

Actualmente, ni siquiera sabemos si este problema es solucionable recursivamente.

Si es solucionable recursivamente, y tenemos un algoritmo para ello, podríamos resolver el problema abierto de larga data sobre si hay primos de Fermat (primos de la forma ) más grande que el más grande conocido, 65537. (Porque cualquier primo con representación de base 2 de la forma debe ser un primo de Fermat).1 0 + 122n+110+1

Jeffrey Shallit
fuente
hay varias otras conjeturas en la teoría de números que se relacionan con períodos EG Erdos Discrepancia problema y anudar un poco en formulaciones de DFA parece posible en otros casos también, un posible programa de investigación para alguien ...
VZN
¿Entiendo correctamente que si tuviéramos un algoritmo para este problema, esto también resolvería el problema de Sierpinski y el problema de Riesel? ( en.wikipedia.org/wiki/Sierpinski_number , en.wikipedia.org/wiki/Riesel_number )
sdcvvc
Sí, sdcvvc, ese es el caso.
Jeffrey Shallit
38

La conjetura de Černý sigue abierta e importante. Se trata de DFA que tienen una palabra de sincronización (una palabra con la propiedad de que dos copias del autómata iniciadas en diferentes estados siempre terminan en el mismo estado entre sí después de que ambas procesen la palabra), y pregunta si (para -state autómata) la longitud de la palabra más corta es siempre como máximo . Los mejores límites probados son de la forma .( n - 1 ) 2 O ( n 3 )n(n1)2O(n3)

David Eppstein
fuente
Lo sentimos, Abuzer Yakaryilmaz, no notó su comentario antes de publicar esto como respuesta. Pero sí creo que merece ser una respuesta y no solo un comentario ...
David Eppstein
2
No hay problema :) Creo que el segundo problema abierto que vinculé también parece bastante interesante.
Abuzer Yakaryilmaz
77
Sé que esta es una pregunta famosa, pero ¿hay una explicación rápida de por qué es importante? ¿Qué aprenderíamos si el límite realmente es lugar de ? n 3 / 6(n1)2n3/6
Sasho Nikolov
@SashoNikolov Puede ser de interés práctico poder restablecer un sistema a un estado conocido sin tener que observarlo (un satélite, por ejemplo), utilizando el menor número de acciones.
Denis
Sí, aprendí este problema por primera vez a través del trabajo de Natarajan en el diseño de componentes de líneas de ensamblaje que fuerzan mecánicamente a las partes a que estén en ciertas orientaciones geométricas. Secuencias de reinicio más cortas (en un autómata que representa posibles pasos de reorientación) = líneas de montaje más cortas.
David Eppstein
20

Quiero señalar el otro problema de investigación, que se refiere a la interacción de conceptos muy básicos sobre DFA.

Es bien sabido que cualquier NFA de estado n puede convertirse en un DFA equivalente que tenga como máximo estados. Esto es lo mejor posible en el peor de los casos, en el sentido de que existen lenguajes regulares de complejidad de estado no determinista n (es decir, el número de estados en un NFA mínimo), pero de complejidad de estado determinista . También hay ejemplos de familias de idiomas, donde el no determinismo puede salvar un factor cuadrático, y casos en los que el no determinismo no ayuda a salvar ningún estado. Por lo tanto, una pregunta natural es la siguiente:2 n2n2n

Problema de número mágico

¿Existe, para cada entre y , un lenguaje regular tal que la brecha entre la complejidad del estado no determinista y la complejidad del estado determinista sea exactamente ?n 2 n L n ααn2nLnα

Si entendemos completamente la construcción del conjunto de potencias y la relación Myhill-Nerode desde una perspectiva matemática, entonces esperaré que uno pueda construir dichos lenguajes para cada , o alternativamente especificar los valores de para los que esto es imposible (si existen tales valores, estos se denominan "números mágicos").ααα

Se sabe que hay números mágicos para el tamaño del alfabeto de entrada y, desde 2009, que no hay números mágicos si el tamaño del alfabeto es al menos . Pero si no me equivoco, el caso de los alfabetos binarios aún está abierto.313

Galina Jirásková. Números mágicos y alfabeto ternario. En: 13ª Conferencia Internacional sobre Desarrollos en Teoría del Lenguaje (DLT 2009), volumen 5583 de Lecture Notes in Computer Science, páginas 300–311.

Hermann Gruber
fuente
77
¡Es un gran problema! Pero quien inventó el término "número mágico" debería ser fusilado.
Jeffrey Shallit
19

Título: Intersección no vacío para dos DFA

Descripción: Dados dos de DFA y , ¿existe una cadena tal que y tanto aceptan ?D 2 x D 1 D 2 xD1D2xD1D2x

Problema abierto: ¿Podemos resolver el vacío de intersección para dos DFA en tiempo?o(n2)

Si pudiéramos resolver este problema en tiempo donde <2, entonces la hipótesis del tiempo exponencial fuerte sería refutada.δO(nδ)δ

Explicación: Decidir el vacío de la intersección de los idiomas regulares en el tiempo subcuadratico

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

¡Que tengas un gran día! :)

Michael Wehar
fuente
hola MW me alegra que hayas notado esta pregunta. recientemente ha citado en esta otra pregunta re separación P / L . Como ha demostrado recientemente, la pregunta anterior (límites superiores sobre la complejidad de resolver el no vacío de intersección de múltiples DFA) está estrechamente relacionada con (el principal problema abierto de) separar P / NL.
vzn
¡Muchas gracias! ¿Quién eres vzn? Fui a tu blog y miré a mi alrededor, pero no pude entenderlo.
Michael Wehar
1
D1D2Ω(n2)
12

Aquí hay un problema abierto relacionado con DFA y la teoría del aprendizaje automático: ¿son uniformemente aleatorias (transiciones aleatorias y comportamiento de aceptación / rechazo) DFA aprendebles en el modelo PAC?

Nota: creemos que los DFA arbitrarios no se pueden aprender b / c de los resultados de dureza criptográfica . Para DFA aleatorio, solo tenemos límites inferiores de SQ , que no son tan fuertes.

Lev Reyzin
fuente
12

LLLlLlLlO(n2)

Saeed
fuente
5

n

Me parece que debería existir una fórmula de forma cerrada, pero no se conoce ninguna. Se conocen algunos límites asintóticos:

n

mikero
fuente
Esto es realmente genial. El otro día estaba pensando en esto y no sabía que otros habían trabajado en esto. Gracias por compartir. :)
Michael Wehar
44
¿Por qué crees que hay una fórmula cerrada? Creo que es muy poco probable.
domotorp
Consulte también esta pregunta para saber qué se sabe sobre ese problema: ¿Cuál es el número de idiomas aceptados por un DFA de tamaño n?
Hermann Gruber
2

Aquí hay una pregunta relacionada con DFA que había hecho antes, y todavía está abierta hasta donde sé:

nΣ={0,1}DFA(n)n|DFA(n)|=n2n2n

x,yΣKn(x,y)DFA(n) xy

Kn(x,y)Kn(x,y)poly(n,|x|,|y|)

Esta pregunta tiene implicaciones para el aprendizaje automático .

Aria
fuente
¿Cuál es el estado actual de la complejidad del problema?
Ryan
1
Jeremiah Blocki tuvo algunos resultados parciales; Este es el estado del conocimiento hasta donde yo sé: cs.cmu.edu/~jblocki/Slides/ComputationalComplexityofKn.pdf
Aryeh
-3

("pensar fuera de la caja" ...) este es un problema un tanto artificial que involucra DFA (no lo he visto estudiado en otro lugar) pero manifiesta un tema en TCS que incluso muchos objetos computacionales aparentemente "simples" (como DFA) pueden tener propiedades complejas , también un aspecto / tema incorporado en el teorema de Rices. (de alguna manera, la "complejidad" final es la "indecidibilidad", también conocida como integridad de Turing).

nxnxn

DFAnDFADFAnDFAnDFA, también es un RL (y un DFA).

Σ

nDFAnΣ

Σn

ahora, para vincular esto más con la pregunta, aunque esto no es ampliamente observado (considerado trivial por algunos), muchos problemas abiertos en TCS / matemáticas están estrechamente relacionados con la indecidibilidad en que dado un oráculo para el problema de detención, pueden ser " resuelto ".

por lo tanto, en cierto sentido, uniendo todo esto usando este problema básico sobre DFA que es indecidible, siempre habrá problemas abiertos sobre DFA, porque siempre habrá problemas "abiertos" sobre DFA (como este) equivalentes a problemas indecidibles . de hecho, usando el teorema de Rices en reversa como lo hace esta construcción de alguna manera, básicamente cualquier propiedad computacional relativamente "simple" pero no trivial en TCS puede usarse para construir problemas indecidibles.

[1] Problemas verbales que requieren tiempo exponencial / Stockmeyer y Meyer

[2] Meyer, AR y L. Stockmeyer. El problema de equivalencia para expresiones regulares con cuadrado requiere espacio exponencial. 13º Simposio IEEE sobre Conmutación y Teoría de Autómatas, octubre de 1972, págs. 125–129.

[3] Introducción a los idiomas, autómatas y computación / Hopcroft / Ullman.

vzn
fuente
2
Creo que estás confundiendo los conceptos "indecidible" y "abierto".
Lev Reyzin
tal como se reconoce, es una visión poco común y / o poco convencional, por decir lo menos, pero no soy el único que lo ha defendido. ver, por ejemplo, esta cita de Michel en este documento Problemas en la teoría de números de la competencia de castores ocupados . También sentimientos similares expresaron wrt famosas conjeturas de la teoría de números abiertos sobre un problema simple cuya indecidibilidad es desconocida . ver también demostración automática del teorema versus indecidibilidad
vzn
DFAnΣn{1nDFAnΣ}
DFA