Les automates multipebble peuvent-ils décider de tous les langages contextuels déterministes?

Un MPA (automate multipebble) est un 2DFA (automate fini déterministe bidirectionnel) qui peut utiliser un nombre arbitraire de cailloux (en fait au plus cailloux sur une entrée donnée w - l'entrée est écrite sur la bande entre deux extrémités -marqueurs comme # w # ). Pendant le calcul, un MPA peut détecter si le symbole sous la tête a un caillou, puis il peut mettre un caillou (retirer le caillou) s'il n'y a pas de caillou (un caillou).$|w|+2$$w$$\# w \#$

est un homomorphisme, où σ est un symbole et k > 0 .$h_k(\sigma) = \underbrace{\sigma \cdots \sigma}_{k \mbox{ times}} = \sigma^k$$\sigma$$k>0$

Pour tout langage déterministe contextuel il n'est pas difficile de montrer qu'il existe un k > 0 tel que h k ( L ) puisse être reconnu par un MPA. Donc, en gros, on peut dire que$\mathtt{L} ~~ \left( \mathtt{L} \in \mathsf{DSPACE(n)} \right),$$k>0~$$h_k( \mathtt{L} )$

tout «problème» décidable par une DTM à espace linéaire (machine de Turing déterministe) peut être résolue par une MPA.

Est-ce également vrai pour n'importe quelle langue en ? Les AMP peuvent-elles décider de tous les langages déterministes contextuels?$\mathsf{DSPACE(n)}$

est la longueur de w .$|w|$$w$

est lesymbole i t h de w , où 1 ≤ i ≤ | w | .$w_i$$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$

Peut-être que vous pouvez construire un langage dans DPSACE (n) qui ne peut pas être reconnu par un MPA avec utilisant un argument de diagonalisation (probablement l'idée est similaire à celle dans la réponse de Ben, mais je n'y ai pas creusé):$k=1$

Supposons que sur l'alphabet vous encodez un MPA en utilisant une liste de transitions:$\Sigma = \{0,1\}$

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

où est l'état actuel, a est le symbole actuel, p est l'état de galet, s ′ est le nouvel état, p ′ est le nouvel état de galet, L | R est la direction du mouvement, $s$$a$$p$$s'$$p'$$L|R$$\#$ est un indicateur de fin).

Une machine de Turing sur l'entrée x peut vérifier s'il s'agit d'une description valide d'un M P A x et la simuler sur l'entrée x pour 4 | x | étapes en utilisant 6 | x | + journal | x | cellules, en étirant l'entrée de cette manière:$M$$x$$MPA_x$$x$$4^{|x|}$$6|x|+\log|x|$

 MPA description # MPA tape # curr_state # counter #

Où:

• La description MPA est la chaîne d'entrée d'origine (a une longueur | x | );$x$$|x|$
• La bande MPA est la représentation de la bande MPA: pour chaque cellule, nous pouvons utiliser 3 bits pour stocker l'indicateur de tête, l'indicateur de galet et le contenu de la bande (fixe) (a une longueur $3|x|$ );
• curr_state stocke l'état actuel du MPA (a une longueur );$\log |x|$
• compteur est le compteur d'étapes de simulation qui est mis à jour après chaque étape de simulation (a une longueur ).$2|x|$

$MPA_x$$4^{|x|}$$M$$M$

$x > x_0$$4^{|x|}$$2^{|x|+2} |x| \log |x|$$MPA_x$$MPA_x$$4^{|x|}$

$MPA_y$$L$$M$$MPA_{y'}$$y'>x_0$ (il suffit d'ajouter états dum).

$MPA_{y'}(y') = 1 - M(y') = 1 - MPA_{y'}(y')$

$\log(N(|k|+2))+|k|+2$

Puisque ce langage est décidable dans l'espace linéaire, il est également exprimable en DCSL.