Os autômatos multipebble podem decidir todas as linguagens determinísticas sensíveis ao contexto?

12

Um MPA (autômato multipebble) é um 2DFA (autômato finito determinístico de duas vias) que pode usar um número arbitrário de seixos (na verdade, no máximo seixos em uma determinada entrada - a entrada é gravada na fita entre as duas extremidades -markers como ). Durante o cálculo, um MPA pode detectar se o símbolo sob a cabeça tem uma pedra e, em seguida, pode colocar uma pedra (remova a pedra) se não houver pedra (uma pedra).|w|+2w#w#

hk(σ)=σσk times=σk é um homomorfismo, onde é um símbolo e .σk>0

Para qualquer linguagem determinística sensível ao contexto não é difícil mostrar que existe um de modo que possa ser reconhecido por um MPA. Então, falando livremente, podemos dizer queL  (LDSPACE(n)),k>0 hk(L)

qualquer "problema" decidível por um DTM de espaço linear (máquina determinística de Turing) pode ser decidido por um MPA.

Isso também se aplica a qualquer idioma em ? Os MPAs podem decidir todas as linguagens determinísticas sensíveis ao contexto?DSPACE(n)


|w|é o comprimento de .w

wi é o símbolo de , onde.ithw1i|w|

hk(L)={hk(w1)hk(w2)hk(w|w|)wL} .

Abuzer Yakaryilmaz
fonte
pergunta interessante; pretende postar algumas referências pouco relacionadas que possam ser relevantes se ninguém mais apresentar algo melhor / mais próximo. uma pergunta embora. CSLs que estão no DSpace (n) não são necessariamente iguais a todos os DTMs de espaço linear, certo? na verdade, essa é uma pergunta em aberto, certo? ou intimamente relacionado a um? porque as CSLs são comprovadamente iguais ao NSpace (n) e estão abertas se NSpace (n) == DSpace (n).
vzn
@vzn: CSLs que estão no DSPACE (n) são chamadas de CSLs determinísticas e formam exatamente o DSPACE (n).
Abuzer Yakaryilmaz
Está bem. o juiz que eu tinha em mente como "provavelmente relacionado" são os argumentos usados ​​para atacar a questão DTime (n ^ k) =? Ntime (n ^ k), por exemplo, resultados recentes da construção da Santhanam no resultado do PPST. Outro problema que intuituively acho que está relacionado é o problema da compressão de uma sequência TM run
vzn
você pode esclarecer um pouco a pergunta? você não afirmou no texto destacado que as MPAs podem decidir todas as CSLs determinísticas? por exemplo, existe alguma maneira de reformular sua pergunta em termos de h_k (L)?
Vzn 6/05/12
2
O teorema é que, se é um DCSL, existem alguns tais que pode ser calculado por um MPA. A questão é: podemos tomar ? k h k ( σ ) k = 1σkhk(σ)k=1
Ben Standeven

Respostas:

3

Talvez você possa criar uma linguagem no DPSACE (n) que não possa ser reconhecida por um MPA com usando um argumento de diagonalização (provavelmente a ideia é semelhante à da resposta de Ben, mas não a expliquei):k=1

Suponha que no alfabeto você codifique um MPA usando uma lista de transições:Σ={0,1}

s,a,ps,p,L|R;...#

onde é o estado atual, é o símbolo atual, é o status do seixo, é o novo estado, é o novo estado do seixo, é a direção do movimento, é um marcador final).a p s p L | R #sapspL|R#

Uma máquina de Turing na entrada pode verificar se é uma descrição válida de um e simulá-la na entrada para etapas usando células, estendendo a entrada desta maneira:MxMPAxx4|x|6|x|+log|x|

 MPA description # MPA tape # curr_state # counter #

Onde:

  • A descrição do MPA é a sequência de entrada original (possui comprimento );x|x|
  • Fita MPA é a representação da fita MPA: para cada célula, podemos usar 3 bits para armazenar o sinalizador principal, sinalizador de calhau e o conteúdo da fita (fixa) (com comprimento );3|x|
  • curr_state armazena o estado atual do MPA (possui comprimento );log|x|
  • counter é o contador de etapas da simulação que é atualizado após cada etapa da simulação (tem comprimento ).2|x|

Se em etapas, o TM emitirá o oposto (se não interromper emitirá 0).MPAx4|x|MM

Para grande o suficiente , as etapas de simulação de são maiores queque é maior que o comprimento de uma descrição completa da configuração do ; dessa maneira, se o não parar em etapas, temos certeza de que ele fará um loop para sempre.x>x04|x|2|x|+2|x|log|x|MPAxMPAx4|x|

Suponha que exista um que decida o mesmo idioma de ; ele sempre será interrompido e você poderá criar um "maior" que decida o mesmo idioma com (basta adicionar estados dum).MPAyLMMPAyy>x0

Por construção, temos, que é uma contradição.MPAy(y)=1M(y)=1MPAy(y)

Marzio De Biasi
fonte
Sim, esse é o argumento que eu tinha em mente.
Ben Standeven
3

Não. Contra-exemplo: o problema de parada para MPAs é decidível no espaço linear: se o MPA tiver N estados, precisaremos de | k | +2 bits de espaço para armazenar os locais dos seixos, registrar N bits para armazenar o estado atual e bits para armazenar um contador; se o contador alternar, a máquina simulada nunca será interrompida. Isso é linear em | k | (ignorando o espaço O (N \ log N) necessário para descrever a máquina), conforme necessário.log(N(|k|+2))+|k|+2

Como essa linguagem é decidível no espaço linear, também é expressável como um DCSL.

Ben Standeven
fonte
Talvez esteja faltando alguns pontos simples, mas não consegui entender como o seu contra-exemplo funciona. Você poderia, por favor, ser mais descritivo sobre como seu argumento funciona? Obrigado!!!
Abuzer Yakaryilmaz 5/11