¿Los autómatas no deterministas para caminar por los árboles son más fuertes que los deterministas?

10

Actualización: Parece que este problema ha sido estudiado y resuelto recientemente, vea este artículo wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton Y también esta encuesta: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf

Supongamos que, en lugar del conjunto habitual de palabras, {0,1} *, nuestras palabras no son lineales, sino que se dan en alguna estructura de árbol. Para evitar que nuestras máquinas se "pierdan", defina nuestras palabras como el conjunto de arborescencias binarias incrustadas. (Por lo tanto, cada palabra es un árbol, donde cada borde se aleja de una raíz dada que tiene grado dos, todos los demás vértices que no son hojas tienen grado tres, y cada borde se etiqueta a la izquierda o a la derecha de modo que dos bordes que comiencen desde el el mismo vértice tiene diferentes etiquetas.) Un lenguaje es un conjunto de tales árboles. (Tenga en cuenta que no hay necesidad de escribir ceros y unos en los vértices, ya que de todos modos pueden simularse modificando localmente los árboles). Cuando una máquina está "leyendo un árbol", comienza desde la raíz, puede detectar si el vértice es la raíz

¿Es cierto en este modelo que cualquier lenguaje que pueda ser reconocido por un autómata de estado finito no determinista también puede ser reconocido por un autómata de estado finito determinista?

Tenga en cuenta que cuando la cinta es la cinta lineal habitual, esto es cierto, ya que cualquier 2-NFA puede simularse con un 2-DFA (incluso con un DFA). Ya pregunté una instancia especial del problema aquí que fue resuelta por Kristoffer . La motivación sería resolver esto .

cc.complexity-theory automata-theory space-bounded dfa domotorp
fuente
2
Sugeriría modificar el título para mencionar " autómatas no deterministas para caminar por los árboles ".
Sylvain

Respuestas:

6

Para los autómatas de árbol, tiene los siguientes resultados:

  • Los autómatas deterministas de árbol ascendente tienen el mismo poder expresivo que los autómatas de árbol ascendente no deterministas.

  • Los autómatas de árbol descendentes deterministas son más débiles que los autómatas de árbol descendente no deterministas.

Se pueden encontrar más detalles en el libro Tree Automata .

Parece que está interesado en los autómatas de árbol de arriba hacia abajo, por lo que la respuesta a su pregunta es no . Por supuesto, tendrá que verificar si los autómatas de árbol de arriba hacia abajo son de hecho lo que le interesa.

Dave Clarke
fuente
1
No, ninguno de estos, pero el artículo wiki tenía un enlace a la noción que
definí