¿Quedan problemas abiertos sobre los DFA?

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.

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 $u$$v$$|u|=|v|=n$$u$$v$

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(n^{2/5}(\log n)^{3/5})$$\Omega(\log n)$

Para una encuesta ver esto .

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 +$2^{2^n} + 1$$1 0^+ 1$

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$$(n-1)^2$$O(n^3)$

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 $2^n$$2^n$

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$\alpha$$n$$2^n$$L_n$$\alpha$

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").$\alpha$$\alpha$

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.$1$$3$

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.

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$D_1$$D_2$$x$$D_1$$D_2$$x$

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

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

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! :)

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.

$L$$L$$L$$l$$L$$l$$L$$l$$O(n^2)$

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

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

$n$$\Sigma=\{0,1\}$$DFA(n)$$n$$|DFA(n)| = n^{2n}2^n$

$x,y\in\Sigma^*$$K_n(x,y)$$DFA(n)$ $x$$y$

$K_n(x,y)$$K_n(x,y)$$poly(n,|x|,|y|)$

Esta pregunta tiene implicaciones para el aprendizaje automático .

("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).

$n$$x$$n$$x↑n$

$DFA_n$$DFA'$$DFA'$$n$$DFA_n$$DFA'$, también es un RL (y un DFA).

$\Sigma$

$n$$DFA_n ≠ \Sigma*$

$\Sigma*$$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.