¿Cuántos DFA aceptan dos cadenas dadas?

Arregle un entero $n$ alfabeto $\Sigma=\{0,1\}$ . Defina $DFA(n)$ como la colección de todos los autómatas de estado finito en $n$ estados con estado inicial 1. Estamos considerando todos los DFA (no solo los conectados, mínimos o no degenerados); por lo tanto $|DFA(n)| = n^{2n}2^n$ .

Ahora considere dos cadenas $x,y\in\Sigma^*$ y defina $K(x,y)$ como el número de elementos de $DFA(n)$ que aceptan tanto $x$ como $y$ .

Pregunta: ¿Cuál es la complejidad de calcular $K(x,y)$ ?

Esta pregunta tiene implicaciones para el aprendizaje automático .

Editar: Ahora que hay una recompensa por esta pregunta, supongo que se necesita un poco más de precisión en la formulación. Para $n\ge1$ , deje que $DFA(n)$ sea la colección de $n^{2n}2^n$ autómatas, como se definió anteriormente. Para $x,y\in\{0,1\}^*$ , defina $K_n(x,y)$ como el número de autómatas en $DFA(n)$ que aceptan ambos $x$ e $y$ . Pregunta: ¿sepuede calcular $K_n(x,y)$ en el tiempo $poly(n,|x|,|y|)$ ?

cc.complexity-theory fl.formal-languages automata-theory counting-complexity Aria
fuente

Si arregla un DFA sin fijar los estados finales, entonces asigna x e y al mismo estado, en cuyo caso la única restricción es que el estado tiene que ser final, o los asigna a dos estados diferentes, en cuyo caso La única restricción es que ambos tienen que ser definitivos. Por lo tanto, reformularía su problema como "¿cuántos DFA asignan xey a diferentes estados?".

a3nm

Aryeh, ¿puedes explicar la cuenta

n^{2 n} 2^{n}

$n^{2n} 2^n$ ? No puedo obtener el factor

2^{n}

$2^n$ . Agregado: ¡Vaya! Olvidé especificar los estados finales. De todos modos, por el bien de los demás, así es como va la cuenta. Para cada estado, especifique dónde ir en las entradas

0

$0$ y

1

$1$ ; eso representa

n^{2 n}

$n^{2n}$ . Especifique el conjunto de estados finales; eso es

2^{n}

$2^n$ .

Srivatsan Narayanan

De hecho, no me importa lo que les pase a las cadenas que no sean

. ¿Supongo que uno necesita una cierta cantidad de puntos para comenzar una recompensa?

x

$x$

y

$y$

Aryeh

El autómata más pequeño que acepta

tiene un solo estado, así que no creo que sea terriblemente informativo ...

x

$x$

y

$y$

Aryeh

Aquí hay una idea: solo necesitamos saber el número de DFA

-estatales que terminan en el mismo estado en

. Deje que este número sea

es el número total de DFA, es decir,

. Entonces la respuesta es

n

$n$

x

$x$

y

$y$

m

$m$

M

$M$

M = n^{2 n} 2^{n}

$M=n^{2n}2^{n}$

, esto da límites. Para calcular

otra idea es que podemos olvidarnos del segmento inicial compartido de

y también asumir que wlog

. Solo contamos el número de DAG binarios con

estados y altura como

que

terminan en el mismo lugar y desde allí es fácil calcular

\frac{1}{2} m + \frac{1}{4} (M - m)

$\frac{1}{2}m + \frac{1}{4}(M-m)$

m

$m$

x

$x$

y

$y$

x = 0^{a}

$x=0^a$

b = 1^{b}

$b=1^b$

l

$l$

max {a, b}

$\max\{a,b\}$

0^{a}

$0^a$

1^{b}

$1^b$

m

$m$

Kaveh

Respuestas:

Entonces la pregunta es bastante breve pero muy interesante. Supongo que la entrada es en unario, y e en binario (o tenemos problemas, como lo señala la respuesta de Kai). $n$ $x$ $y$

En primer lugar, si está interesado en conocer aproximadamente, puede generar algunos DFA aleatorios y esto le dará (whp) una buena aproximación. (Me pregunto si esta clase de complejidad tiene un nombre). $K(x,y)$

Entonces saber precisamente parece un problema difícil. Como a cabo en punta en los comentarios por a3_nm y Kaveh, la pregunta es equivalente a determinar el número de autómatas para la que e vaya al mismo estado. Denotaré la probabilidad de que vayan al mismo estado por . $K(x,y)$ $x$ $y$ $p$

Actualización: Algunas de las cosas que escribí aquí no eran ciertas, ahora las arreglé.

Es fácil ver que . Tenemos igualdad, si es todo 0 e es todo cero excepto por su último bit, que es un 1. ¿Hay otros casos? No lo sé. Si, por ejemplo, es la cadena vacía e , entonces $p \ge 1/n$ $x$ $y$ $x$ $y=00$ . $p= \frac{n+1}{(n-1)n}$

Para simplificar el problema, incluso me puse a pensar en lo que sucede si e son unario. Si ambos son al menos y su diferencia es divisible por , entonces . ¿Existe una fórmula simple para la versión unaria? $x$ $y$ $n$ $n!$ $p=1$

domotorp
fuente

He aclarado el problema: se desea un algoritmo

(o una reducción de algún problema difícil conocido). La aproximación de muestreo se emplea en el documento donde se introduce este núcleo: portal.acm.org/citation.cfm?id=1577108

p o l y (n, | x |, | y |)

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

Aryeh

En cuanto a la versión unaria: solo hay polinómicamente muchos autómatas unarios

estados, por lo que apostaría a que hay un algoritmo de poli-tiempo para calcular

en este caso.

n

$n$

K_{n} (x, y)

$K_n(x,y)$

Aryeh

De hecho, tiene toda la razón en que la versión unaria es computable. Todavía me pregunto cuán simple es la fórmula para una x e y dada.

domotorp

La reducción que ha utilizado es defectuosa: x e y pueden ser aceptadas por los mismos autómatas y terminar en estados completamente diferentes, de hecho, pueden compartir solo el estado inicial en sus rutas, lo cual es cierto para todas las cadenas.

amnn

@amnn: Han pasado tres años desde que escribí esto, pero ¿el tercer párrafo de mi respuesta no explica por qué trato solo con terminar en el mismo estado?

domotorp

Es muy posible que me esté perdiendo el punto, pero usted declaró que es fijo, por lo que todos los DFA de ese tamaño podrían considerarse precalculados y almacenados en un formato fácilmente simulable. Calcule siguiente manera: $n$ $K$

En la entrada , donde $x$ $y$ $x,y\in\Sigma^*$

almacenar e $x$ $y$
Inicializar el contador a $c$ $0$
para cada uno de sus DFA $n^{2n} 2^n$
a. simúlelo en ambas palabras (este paso es ) $\mathcal{O}(|xy|)$

si. incremente si ambas ejecuciones de simulación aceptan $c$
salida $c$

En total, el cálculo tiene una complejidad lineal. La respuesta es bastante diferente para . $K(n,x,y)$

Kai
fuente

Claramente, probar todas las máquinas funcionará. Aryeh quiere saber si hay, quizás, un algoritmo de tiempo polinómico o algún otro resultado de dureza.

Lev Reyzin

Hablando estrictamente, este es el tiempo polinómico en la entrada, si n no es parte de la entrada, eso es lo que Kai estaba diciendo. Pero la pregunta es claramente diferente.

domotorp

Oh ya veo. No creo que eso sea lo que él quiere decir con "arreglo

". Creo que la interpretación natural del problema es una que no lo trivializa.

n

$n$

Lev Reyzin

Bien, gracias por señalar la escapatoria, Kai. Se ha solucionado :)

Aryeh