Poder computacional de autômatos min-heap determinísticos versus não determinísticos

15

Esta é uma questão de acompanhamento deste .

Em uma pergunta anterior sobre máquinas de estado exóticas , Alex ten Brink e Raphael abordaram os recursos computacionais de um tipo peculiar de máquina de estado: autômatos de min-heap. Eles foram capazes de mostrar que o conjunto de idiomas aceitos por essas máquinas ( ) não é um subconjunto nem um superconjunto do conjunto de idiomas sem contexto. Dada a resolução bem-sucedida e o aparente interesse nessa pergunta, prossigo para fazer várias perguntas de acompanhamento.HAL

Sabe-se que autômatos finitos determinísticos e não determinísticos têm capacidades computacionais equivalentes, assim como as máquinas de Turing determinísticas e não determinísticas. No entanto, os recursos computacionais dos autômatos push-down determinísticos são inferiores aos dos autômatos push-down não-determinísticos.

Os recursos computacionais dos autômatos min-heap determinísticos são menores ou iguais aos dos autômatos min-heap não determinísticos?

Patrick87
fonte

Respostas:

3

Parece que, para esse modelo, as máquinas não determinísticas não são equivalentes às determinísticas, basicamente pela mesma razão que os PDAs determinísticos não são equivalentes aos não determinísticos.

Considere o idioma

L=x$y|x|=|y|xy
(onde é um sinal especial não contido em x e y$xy ).

I afirmam que uma máquina não-determinístico - H Uma G pode decidir esta linguagem: Ele executa a mesma que a de PDA por L . A solução PDA padrão usa a pilha apenas para contar as compensações: adivinha não-deterministicamente um deslocamento i , lembra o valor de x i (adicionando um símbolo à pilha a cada etapa), então o PDA ignora a entrada até encontrar o $ e em seguida, ele exibe símbolos da pilha até que ela esteja vazia. Nesta fase, estamos exatamente no y i e ele PDA pode verificar se x iy iNHALLixi$yixiyi. (se algo der errado no meio, o PDA "morre"). Como o alfabeto da pilha é unário, ele pode ser simulado com uma máquina de min-heap. Na verdade: qualquer que é aceito por um PDA com um alfabeto unário pode ser aceito por uma máquina de min-heap. (Talvez eu esteja ignorando outro sinal especial adicionado para identificar uma pilha vazia, mas um sinal equivalente pode ser adicionado ao heap)L

Por outro lado, não tenho a prova formal, mas aqui estão os meus pensamentos:

Afirmo que uma máquina determinística - H A L é incapaz de decidir essa linguagem. Intuitivamente, o conteúdo do heap não pode ser correlacionado com x (caso contrário, permita x . O conteúdo do heap permanece o mesmo ..). Isso sugere que a única coisa que importa é o número de elementos na pilha, mas, se D - H A L pode decidir L , o mesmo pode ser determinístico - P D ADHALxxDHALLPDA .

Edit: mais detalhes sobre a reivindicação "permute ". Supondo que a conjectura de Rafael exista x 1 e x 2 que, após lê-las, o conteúdo da pilha é o mesmo. Em seguida, considere as palavras x 1 $ x 1 e x 2 $ x 1 . O conteúdo do heap é o mesmo quando o HAL chega ao cifrão, portanto, ele deve aceitar os dois ou rejeitar os dois. contradição .xx1x2x1$x1x2$x1

alguém vê uma prova imediata da conjectura?

Tocou.
fonte
x
Qual definição de min-heaps você está usando: a minha original, ou a mais natural sugerida por Raphael? Em qualquer um dos casos, você pode ter mais clareza sobre como uma máquina não determinística aceitaria o idioma que você fornece ... o que ela coloca e tira da pilha e quando?
Patrick87
nn , pois o número total de símbolos na pilha é linear e o número de símbolos diferentes é constante.
Yuval Filmus