¿Pueden los autómatas multipebble decidir todos los lenguajes deterministas sensibles al contexto?

Un MPA (autómata multipebble) es un 2DFA (autómata finito determinista bidireccional) que puede usar un número arbitrario de guijarros (en realidad, como máximo guijarros en una entrada dada - la entrada está escrita en la cinta entre dos extremos -marcadores como ). Durante el cálculo, un MPA puede detectar si el símbolo debajo de la cabeza tiene un guijarro, y luego puede poner un guijarro (quitar el guijarro) si no hay guijarro (un guijarro). $|w|+2$ $w$ $\# w \#$

$h_k(\sigma) = \underbrace{\sigma \cdots \sigma}_{k \mbox{ times}} = \sigma^k$ es un homomorfismo, donde es un símbolo . $\sigma$ $k>0$

Para cualquier lenguaje determinista sensible al contexto no es difícil demostrar que existe un tal que pueda ser reconocido por un MPA. Entonces, hablando libremente, podemos decir que $\mathtt{L} ~~ \left( \mathtt{L} \in \mathsf{DSPACE(n)} \right),$ $k>0~$ $h_k( \mathtt{L} )$

cualquier "problema" decidible por un DTM de espacio lineal (máquina de Turing determinista) puede ser resuelto por un MPA.

¿También es cierto para cualquier idioma en ? ¿Pueden las AMP decidir todos los lenguajes deterministas sensibles al contexto? $\mathsf{DSPACE(n)}$

$|w|$ es la longitud de . $w$

$w_i$ es el símbolo de , donde. $i^{th}$ $w$ $1 \leq i \leq |w|$

$h_k(\mathtt{L}) = \left\lbrace h_k(w_1) h_k(w_2) \cdots h_k(w_{|w|}) \mid w \in \mathtt{L} \right\rbrace$ .

cc.complexity-theory reference-request automata-theory space-bounded Abuzer Yakaryilmaz
fuente

interesante pregunta; tiene la intención de publicar algunas referencias poco relacionadas que pueden ser relevantes si a nadie más se le ocurre algo mejor / más cercano. una pregunta sin embargo. Las CSL que están en DSpace (n) no son necesariamente las mismas que todas las DTM de espacio lineal, ¿verdad? en realidad esa es una pregunta abierta ¿verdad? o estrechamente relacionado con uno? porque se ha demostrado que las CSL son iguales a NSpace (n) y está abierto si NSpace (n) == DSpace (n).

vzn

@vzn: los CSL que están en DSPACE (n) se denominan CSL deterministas y forman exactamente DSPACE (n).

Abuzer Yakaryilmaz

Okay. La referencia que tenía en mente como "probablemente relacionada" son los argumentos de discusión utilizados para atacar la pregunta DTime (n ^ k) =? Ntime (n ^ k), por ejemplo, resultados recientes de Santhanam construyendo sobre el resultado de PPST. Otro problema que intuitivamente creo que está relacionado es el problema de la compresión de una secuencia de ejecución TM

vzn

¿puedes aclarar un poco la pregunta? ¿no acabas de afirmar en el texto resaltado que las AMP pueden decidir todas las CSL deterministas? Por ejemplo, ¿hay alguna forma de reformular su pregunta en términos de h_k (L)?

vzn

El teorema es que si es un DCSL, hay algunos tales que puede ser calculado por un MPA. La pregunta es, ¿podemos tomar ?

σ

$\sigma$

k

$k$

h_{k} (σ)

$h_k(\sigma)$

k = 1

$k=1$

Ben Standeven el

Respuestas:

Quizás pueda construir un lenguaje en DPSACE (n) que no pueda ser reconocido por un MPA con usando un argumento de diagonalización (probablemente la idea es similar a la de la respuesta de Ben, pero no profundicé en ello): $k=1$

Suponga que sobre el alfabeto codifica un MPA usando una lista de transiciones: $\Sigma = \{0,1\}$

$s,a,p \rightarrow s',p',L|R;...\#$

donde es el estado actual, es el símbolo actual, es el estado del guijarro, es el nuevo estado, es el nuevo estado del guijarro, es la dirección del movimiento, es un marcador final). $s$ $a$ $p$ $s'$ $p'$ $L|R$ $\#$

Una máquina Turing en la entrada puede verificar si es una descripción válida de un y simularla en la entrada para pasos usando celdas, estirando la entrada de esta manera: $M$ $x$ $MPA_x$ $x$ $4^{|x|}$ $6|x|+\log|x|$

 MPA description # MPA tape # curr_state # counter #

Dónde:

La descripción de MPA es la cadena de entrada original (tiene longitud ); $x$ $|x|$
La cinta MPA es la representación de la cinta MPA: para cada celda podemos usar 3 bits para almacenar la bandera principal, la bandera de guijarros y el contenido de la cinta (fija) (tiene una longitud de ); $3|x|$
curr_state almacena el estado actual del MPA (tiene una longitud ); $\log |x|$
counter es el contador de pasos de simulación que se actualiza después de cada paso de simulación (tiene una longitud de ). $2|x|$

Si detiene en pasos, TM genera lo contrario (si no detiene produce 0). $MPA_x$ $4^{|x|}$ $M$ $M$

Para suficientemente grande , los pasos de simulación son mayores queque es mayor que la longitud de una descripción de configuración completa de ; de esta manera, si el no se detiene en pasos, entonces estamos seguros de que se repetirá para siempre. $x > x_0$ $4^{|x|}$ $2^{|x|+2} |x| \log |x|$ $MPA_x$ $MPA_x$ $4^{|x|}$

Suponga que hay un que decide el mismo lenguaje de , entonces siempre se detiene y puede construir un más grande " que decide el mismo idioma, con (solo agregue estados dum). $MPA_y$ $L$ $M$ $MPA_{y'}$ $y'>x_0$

Por construcción tenemos, cual es una contradicción. $MPA_{y'}(y') = 1 - M(y') = 1 - MPA_{y'}(y')$

Marzio De Biasi
fuente

Sí, ese es el argumento que tenía en mente.

Ben Standeven

No. Contraejemplo: el problema de detención de las AMP es decidible en el espacio lineal: si la AMP tiene N estados, necesitamos | k | +2 bits de espacio para almacenar las ubicaciones de los guijarros, registrar N bits para almacenar el estado actual y bits para almacenar un contador; Si el contador realiza ciclos, la máquina simulada nunca se detendrá. Esto es lineal en | k | (ignorando el espacio O (N \ log N) requerido para describir la máquina), según sea necesario. $\log(N(|k|+2))+|k|+2$

Dado que este lenguaje es decidible en el espacio lineal, también se puede expresar como DCSL.

Ben Standeven
fuente

Tal vez me faltan algunos puntos simples, pero no pude entender cómo funciona su contraejemplo. ¿Podría por favor ser más descriptivo sobre cómo funciona su argumento? ¡¡¡Gracias!!!

Abuzer Yakaryilmaz