Czy niedeterministyczne automaty do chodzenia po drzewie są silniejsze niż te deterministyczne?

10

Aktualizacja: Wygląda na to, że ten problem został niedawno zbadany i rozwiązany, zobacz ten artykuł wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton A także tę ankietę: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf

Załóżmy, że zamiast zwykłego zestawu słów {0,1} *, nasze słowa nie są liniowe, ale raczej podane na jakiejś strukturze drzewa. Aby zapobiec „zagubieniu się” naszych maszyn, zdefiniuj nasze słowa jako zestaw binarnych osadzonych arborescencji. (Tak więc każde słowo jest drzewem, w którym każda krawędź jest skierowana od danego korzenia, który ma stopień drugi, każdy inny wierzchołek niebędący liściem ma stopień trzeci, a każda krawędź jest oznaczona w lewo lub w prawo tak, że dowolne dwie krawędzie zaczynające się od ten sam wierzchołek ma różne etykiety.) Językiem jest zestaw takich drzew. (Zauważ, że nie ma potrzeby zapisywania zer i jedynek na wierzchołkach, ponieważ można je w każdym razie symulować poprzez lokalną modyfikację drzew.) Gdy maszyna „czyta drzewo”, zaczyna od korzenia, może wyczuć, czy dane wierzchołek jest korzeniem,

Czy prawdą jest w tym modelu, że każdy język, który może być rozpoznany przez niedeterministyczny automat skończony, może być również rozpoznany przez deterministyczny automat skończony?

Zauważ, że gdy taśma jest zwykłą taśmą liniową, jest to prawda, ponieważ każdy 2-NFA może być symulowany za pomocą 2-DFA (nawet z DFA). Zapytałem już o specjalny przykład problemu , który rozwiązał Kristoffer . Motywacją byłoby rozwiązanie tego .

cc.complexity-theory automata-theory space-bounded dfa domotorp
źródło
2
Proponuję zmodyfikować tytuł, aby wspomniał o „niedeterministycznych automatach do chodzenia po drzewach ”.
Sylvain,

Odpowiedzi:

6

W przypadku automatów drzewnych masz następujące wyniki:

  • Deterministyczne automaty drzewa od dołu mają tę samą moc ekspresji, co niedeterministyczne automaty drzewa dołu.

  • Deterministyczne automaty zstępujące z drzewa są słabsze niż niedeterministyczne automaty zstępujące z drzewa.

Więcej informacji można znaleźć w książce Tree Automata .

Wygląda na to, że interesują Cię automatyczne odgórne drzewa, więc odpowiedź na twoje pytanie brzmi „ nie” . Będziesz oczywiście musiał sprawdzić, czy automaty drzewa z góry są tym, czym jesteś zainteresowany.

Dave Clarke
źródło
1
Nie, żaden z nich, ale artykuł wiki zawierał link do pojęcia, które zdefiniowałem: en.wikipedia.org/wiki/Tree_walking_automaton
domotorp