¿DTIME (O (n)) = REGULAR?

Question

(No creo que este es un buen ajuste en cstheory, ya que me imagino que esta pregunta ya se conoce la respuesta. Sin embargo, si usted piensa que esto sería un mejor ajuste, por favor siéntase libre de migrar)

Puede ser fácilmente demostrado que el uso REGULAR de la clase regular de idiomas), está contenida en DTIME(O(n)), porque para cualquier lenguaje regular L podemos decidir la pertenencia a ese idioma en O(n) tiempo mediante la conversión de un DFA que decide L en un TM que decide L en un solo paso a través de la entrada. Sin embargo, también es cierto que DTIME(O(n)) se encuentra en REGULARES; es decir, que cualquier lenguaje que pueda ser decidido en O(n) tiempo por una sola cinta TM es necesariamente regular?

No tengo idea de cómo abordar este problema, y en todos los idiomas que se me ocurre en DTIME(O(n)) parece ser regular. Intuitivamente, esto tendría sentido, ya que si sólo se permite hacer un número finito pasa por encima de la entrada, sólo podía recordar un número finito de cosas acerca de ella, que parece que podría simular con una lo suficientemente grande DFA. Sin embargo, el hecho de que usted puede escribir a la entrada de la cinta parece que podría complicar las cosas.

Y no, esto no es una tarea problema. Estoy enseñando un curso que cubre la computabilidad y la teoría de la complejidad y pensé que sería interesante presentar la respuesta a esta pregunta en la conferencia. :-)

Gracias!

Answer 1

Para el beneficio de los lectores, aquí es un esquema de la prueba de que un $o(n\log n)$-tiempo TM acepta un lenguaje regular.

Considerar el cálculo de la TM en la entrada $x$. Escribir $x$ como sigue: $$ |x_0|x_1|\cdots|x_n|. $$ Cada una de las $|$ significa que hay un límite entre dos células. El cruce de número en un límite en $x$ es simplemente el número de veces que el equipo cruza la frontera. El cruce de la secuencia es la secuencia de estados que la TM entra inmediatamente después de cruzar el límite (primero de izquierda a derecha y luego de derecha a izquierda, y así sucesivamente).

Reclamación (Kobayashi '85): Si un TM se ejecuta en el tiempo $o(n\log n)$, entonces el cruce de número en cualquier límite en cualquier entrada es $O(1)$.

Prueba de idea: Supongamos que en alguna entrada, el número de cruzar en algún límite de $X$ es grande (por lo menos $A$). Escoge un menor entrada de este tipo. Puesto que la máquina se ejecuta en el tiempo $o(n\log n)$, debe haber muchos límites (al menos $B(n)$) en el que el cruce número es pequeño (en la mayoría de las $c(n)$). Desde $B(n)$ es tan grande en comparación a $c(n)$, por el principio del palomar debe haber cuatro límites con el mismo cruce de la secuencia, de los cuales hay dos en el mismo lado de la $X$. De ello se sigue que, si "impuestos especiales" la subcadena delimitada por estos límites, se obtiene una cadena más pequeña con un límite con el cruce de número, al menos,$A$. Q. E. D.

Un cálculo es, por supuesto, necesario para mostrar que no es una elección apropiada de $A,B(n),c(n)$ cada vez que el tiempo es $o(n\log n)$. Que queda por verificar.

Reclamación (Hennie '65): Si el número de cruzar de un TM es $O(1)$ para cualquier entrada y de cualquier límite, entonces el lenguaje que acepta es regular.

Prueba de idea: Para las cadenas de $x,y$, definir $x \equiv y$ si por cualquier $z$, siempre que la máquina acepta $xz$ a continuación, se acepta $yz$, y viceversa. Nos muestran que $\equiv$ tiene un número finito de clases de equivalencia, por lo que la demanda sigue de Myhill-Nerode.

Para una cadena de caracteres $x$, vamos a $S(x)$ denota el conjunto de cruce de las secuencias en el límite $x|z$ cualquier $z$ de manera tal que el TM acepta $xz$. Supongamos que $S(x) = S(y)$. Vamos a mostrar que el $x \equiv y$. De hecho, ninguna de $z$ de manera tal que el TM acepta $xz$. Desde $S(x) \subseteq S(y)$, $w$ de manera tal que el TM acepta $yw$, y en el cruce de las secuencias de a $x|z$ $y|w$ son los mismos. Esto implica (después de un poco de pensamiento) que, efectivamente, $yz$ es aceptada por el TM. Q. E. D.

Answer 2

Single-tape$o(n \log n)$ Las máquinas Turing sólo pueden reconocer lenguajes regulares. Consulte http://arxiv.org/abs/cs/0310046 para referencia. Recuerdo haber visto la prueba de$O(n)$ sólo (no puedo recordar la fuente ahora), y definitivamente no fue simple.

Answer 3

Al llegar a general polinomio tiempo, usted necesita tener cuidado de que los cálculos del modelo que estamos trabajando con -- un CARNERO puede lograr mucho más en $O(n)$ el tiempo que una máquina de Turing puede.

De todos modos, con un "realista" del modelo, DTIME($O(n)$) puede reconocer mucho más de lo normal idiomas, tales como $\{a^nb^n\mid n\in\mathbb N\}$ en un contador de la máquina.

De manera más general, es fácil ver que una máquina de Turing con una lectura única de entrada de cinta independiente y una cinta virgen puede reconocer, al menos, cada LR($k$) contexto de un lenguaje libre en el tiempo lineal, y más que eso, como $\{a^nb^nc^n\mid n\in\mathbb N\}$ que no es independiente del contexto.

Answer 4

Sí, este es un viejo resultado que en$o(n \lg n)$ tiempo una sola cinta Turing Machine sólo puede decidir idiomas regulares. La prueba es a través de considerar las secuencias de cruce, se puede encontrar una prueba en el segundo volumen del libro de Odifreddi.