Являются ли недетерминированные автоматы для ходьбы по деревьям сильнее, чем детерминированные?

10

Обновление: кажется, что эта проблема была недавно изучена и решена, см. Эту статью вики: http://en.wikipedia.org/wiki/Tree_walking_automaton А также этот опрос: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf

Предположим, что вместо обычного набора слов {0,1} * наши слова не линейны, а заданы на некоторой древовидной структуре. Чтобы наши машины не «терялись», определите наши слова как набор двоичных встроенных древовидностей. (Таким образом, каждое слово является деревом, где каждое ребро направлено от заданного корня, имеющего степень два, каждая другая неконечная вершина имеет степень три, и каждое ребро помечено влево или вправо так, что любые два ребра, начинающиеся с одна и та же вершина имеет разные метки.) Язык - это множество таких деревьев. (Обратите внимание, что нет нужды писать нули и единицы в вершинах, так как они в любом случае могут быть смоделированы путем локальной модификации деревьев.) Когда машина «читает дерево», она начинается с корня, она может чувствовать, что вершина является корнем,

Верно ли в этой модели, что любой язык, который может быть распознан недетерминированным автоматом конечного состояния, также может быть распознан детерминированным автоматом конечного состояния?

Обратите внимание, что когда лента является обычной линейной лентой, это действительно так, поскольку любой 2-NFA может быть смоделирован с 2-DFA (даже с DFA). Я уже задавал специальный экземпляр задачи здесь , что было решена Kristoffer . Мотивация должна была бы решить это .

cc.complexity-theory automata-theory space-bounded dfa domotorp
источник
2
Я бы предложил изменить название, чтобы упомянуть «недетерминированные автоматы для ходьбы по дереву ».
Сильвен

Ответы:

6

Для автоматов деревьев у вас есть следующие результаты:

  • Детерминированные восходящие древовидные автоматы обладают той же выразительной силой, что и недетерминированные восходящие древовидные автоматы.

  • Детерминированные нисходящие древовидные автоматы слабее недетерминированных нисходящих древовидных автоматов.

Более подробную информацию можно найти в книге « Дерево автоматов» .

Кажется, вас интересуют нисходящие древовидные автоматы, поэтому ответ на ваш вопрос - нет . Вам, конечно, придется проверить, действительно ли интересующие вас древовидные автоматы дерева действительно интересны.

Дэйв Кларк
источник
1
Нет, ничего из этого, но статья в вики содержала ссылку на понятие, которое я определил: en.wikipedia.org/wiki/Tree_walking_automaton
domotorp