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 .