Os autômatos não determinísticos para caminhar em árvores são mais fortes que os deterministas?

10

Atualização: Parece que esse problema foi estudado e resolvido recentemente, consulte este artigo da wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton E também esta pesquisa: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf

Suponha que, em vez do conjunto usual de palavras {0,1} *, nossas palavras não sejam lineares, mas sim apresentadas em alguma estrutura de árvore. Para impedir que nossas máquinas "se percam", defina nossas palavras como o conjunto de arborescências binárias incorporadas. (Portanto, toda palavra é uma árvore, em que todas as arestas são direcionadas para longe de uma raiz com grau dois, todos os outros vértices que não sejam folhas têm grau três e todas as arestas são rotuladas à esquerda ou à direita, de modo que quaisquer duas arestas iniciem no mesmo vértice possuem rótulos diferentes.) Um idioma é um conjunto dessas árvores. (Observe que não há necessidade de escrever zeros e zeros nos vértices, pois eles podem ser simulados modificando localmente as árvores.) Quando uma máquina está "lendo uma árvore", ela começa a partir da raiz e pode detectar se um determinado vértice é a raiz,

É verdade neste modelo que qualquer linguagem que possa ser reconhecida por um autômato de estado finito não determinístico também pode ser reconhecida por um autômato de estado finito determinístico?

Observe que quando a fita é a fita linear usual, isso é verdade, pois qualquer 2-NFA pode ser simulado com um 2-DFA (mesmo com um DFA). Eu já perguntei uma instância especial do problema aqui que foi resolvida por Kristoffer . A motivação seria resolver isso .

cc.complexity-theory automata-theory space-bounded dfa domotorp
fonte
2
Eu sugeriria a modificação do título para mencionar " autômatos não determinísticos para caminhar em árvores ".
Sylvain

Respostas:

6

Para autômatos em árvore, você tem os seguintes resultados:

  • Autômatos determinísticos de árvore ascendente têm o mesmo poder expressivo que autômatos não determinísticos de árvore ascendente.

  • Os autómatos de árvores descendentes determinísticos são mais fracos que os autómatos de árvores descendentes não determinísticos.

Mais detalhes podem ser encontrados no livro Tree Automata .

Parece que você está interessado em autômatos de árvores de cima para baixo, então a resposta para sua pergunta é não . É claro que você precisará verificar se os autômatos de árvores de cima para baixo são realmente o que lhe interessa.

Dave Clarke
fonte
11
Não, nada disso, mas a wiki artigo teve um link para a noção de que eu defini: en.wikipedia.org/wiki/Tree_walking_automaton
domotorp