Les automates d'arborescence non déterministes sont-ils plus forts que les automates déterministes?

10

Mise à jour: Il semble que ce problème ait été étudié et résolu récemment, voir cet article wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton Et aussi cette enquête: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf

Supposons qu'au lieu de l'ensemble habituel de mots, {0,1} *, nos mots ne soient pas linéaires mais plutôt donnés sur une structure arborescente. Pour éviter que nos machines ne "se perdent", définissons nos mots comme l'ensemble d'arborescences binaires intégrées. (Donc, chaque mot est un arbre, où chaque bord est dirigé loin d'une racine donnée qui a le degré deux, chaque autre sommet non-feuille a le degré trois, et chaque bord est étiqueté à gauche ou à droite de sorte que deux bords à partir de la même sommet ont des étiquettes différentes.) Une langue est un ensemble de tels arbres. (Notez qu'il n'est pas nécessaire d'écrire des zéros et des uns sur les sommets car ils peuvent être simulés de toute façon en modifiant localement les arbres.) Lorsqu'une machine "lit un arbre", elle part de la racine, elle peut détecter si une donnée le sommet est la racine,

Est-il vrai dans ce modèle que tout langage qui peut être reconnu par un automate à états finis non déterministe peut également être reconnu par un automate à états finis déterministe?

Notez que lorsque la bande est la bande linéaire habituelle, cela est vrai, car tout 2-NFA peut être simulé avec un 2-DFA (même avec un DFA). Je l' ai déjà demandé à un cas particulier du problème ici qui a été résolu par Kristoffer . La motivation serait de résoudre ce problème .

cc.complexity-theory automata-theory space-bounded dfa domotorp
la source
2
Je suggérerais de modifier le titre pour mentionner "les automates non déterministes de marche dans les arbres ".
Sylvain

Réponses:

6

Pour les automates arborescents, vous obtenez les résultats suivants:

  • Les automates d'arbres ascendants déterministes ont le même pouvoir expressif que les automates d'arbres ascendants non déterministes.

  • Les automates arborescents top-down déterministes sont plus faibles que les automates arborescents top-down non déterministes.

Plus de détails peuvent être trouvés dans le livre Tree Automata .

Il semble que vous soyez intéressé par les automates d'arbre descendants, donc la réponse à votre question est non . Vous devrez bien sûr vérifier si les automates d'arbre descendants sont bien ce qui vous intéresse.

Dave Clarke
la source
1
Non, rien de tout cela, mais l'article wiki avait un lien avec la notion que j'ai définie: en.wikipedia.org/wiki/Tree_walking_automaton
domotorp