¿Hay una secuencia de reinicio?

Question

Hay una pregunta alguien (estoy nublada como la oms) me dijo años atrás. Me pareció fascinante por un tiempo, pero luego se me olvidó, y estoy fuera de contacto con cualquier evolución posterior. ¿Alguien puede identificar mejor el problema o de relleno en la historia, y decir si está todavía sin resolver? Es una pregunta difícil de contestar si me he metido a la derecha. Aquí está:

Supongamos que usted tiene algún tipo de máquina con dos botones, evidentemente diseñado por personas con mala instinto de la interfaz de usuario. La máquina tiene muchos estados en los que los botones de hacer cosas diferentes. Aquí están los supuestos:

1. No hay ningún periódico cociente del espacio de estado: de ninguna manera a la etiqueta de los estados por un n-ciclo a fin de que tanto los botones de avanzar en la etiqueta por 1 mod n.

2. No es reversible: hay situaciones en las que dos estados se funden en uno.

3. Es ergodic: se puede llegar desde cualquier estado a cualquier otro estado por alguna secuencia de botones.

Ahora supongamos que su dinky poco LCD se desvaneció o roto, por lo que en realidad no se puede decir cuál es el estado en el que esta. Es necesariamente universal restablecer el código, una secuencia que te llevará a un estado conocido no importa dónde empezar? (Formalmente, este es un autómata de estado finito, o una acción de la libre 2-generador de semigroup en un conjunto finito, y se pregunta si algún elemento actúa como un constante mapa).

Answer 1

He jugado con este problema en la vida real con un TiVo, deseando que se vaya a dormir (un bajo consumo de energía del estado) sin tener que encender la pantalla para ver como sus estados cambiado. El TiVo, o cualquier remoto, utiliza un alfabeto de tamaño de, al menos, como muchos botones en el control remoto. Sin embargo, un poco de la caza en la wikipedia muestra que "la Sincronización de Palabra" es donde "reset" secuencia conduce a la.

Para $n$-estado DFAs a través de una $k$-entrada de letras del alfabeto en el que todas las transiciones de estado de preservar el orden cíclico de los estados, un algoritmo por David Eppstein encuentra una sincronización de la palabra en $O(n^3+kn^2)$ tiempo y $O(n^2)$ espacio. El nombre de la publicación es "Restablecer las Secuencias Monótonas Autómata" .

El hallazgo y la estimación de la longitud de la "reset" secuencia para un Autómata Finito Determinista ha sido estudiado desde la década de 1960. El Černý conjetura postula $(n-1)^2$ como el límite superior de la longitud de la menor sincronización de la palabra, para cualquier $n$-estado completo de la DFA (un DFA con la completa transición de estado de la gráfica).

La forma en que ha planteado su pregunta conjuntos de $k=2$, ya que las transiciones sólo puede ser marcadas por los dos botones de la entrada, por lo tanto el Autómata Finito Determinista que subyacen a su pregunta tendrá un grafo dirigido con un máximo de dos arcos salientes en cada estado.

Answer 2

Creo que este papel por Rob Schapire y Ron Rivest en el "homing secuencias" en finito determinista estado de autómatas podría contener la respuesta a su pregunta. A partir de la ponencia:

"De manera informal, una recalada de la secuencia es una secuencia de entradas que, cuando se alimenta a la máquina, está garantizado para 'orientar' el alumno: las salidas producidas en la ejecución de la recalada de la secuencia completamente determinar el estado alcanzado por el autómata al final de la recalada de la secuencia ... Cada máquina de estados finitos tiene una recalada de la secuencia."

Admito que no he leído el papel con cuidado para asegurarse de que el problema de los estudios coincide exactamente con su formulación, pero a un alto nivel parece estrechamente relacionados.

Answer 3

Creo que te estás refiriendo al teorema de coloración del camino . Fue resuelto en este preprint .