Autómata que camina sobre los árboles

Un autómata de recorrido de árboles (TWA, por sus siglas en inglés) es un tipo de autómata finito que trabaja con estructuras de árbol en lugar de cadenas. El concepto fue propuesto originalmente por Aho y Ullman . ^{[ 1 ]}

El siguiente artículo trata sobre autómatas de recorrido de árboles. Para una noción diferente de autómata de árbol, estrechamente relacionada con los lenguajes de árboles regulares , véase autómata de ramificación .

Se supone que todos los árboles son binarios , con etiquetas de un alfabeto fijo Σ.

De manera informal, un autómata de recorrido de árboles (TWA) A es un dispositivo de estados finitos que recorre un árbol de entrada de forma secuencial. En cada instante, A visita un nodo v en estado q . Dependiendo del estado q , la etiqueta del nodo v y si el nodo es la raíz, un hijo izquierdo, un hijo derecho o una hoja, A cambia su estado de q a q ' y se mueve al padre de v o a su hijo izquierdo o derecho. Un TWA acepta un árbol si entra en un estado de aceptación y lo rechaza si entra en un estado de rechazo o entra en un bucle infinito. Al igual que los autómatas de cadenas, un TWA puede ser determinista o no determinista.

De manera más formal, un autómata de recorrido de árbol (no determinista) sobre un alfabeto Σ es una tupla A = ( Q , Σ, I , F , R , δ ) donde Q es un conjunto finito de estados, sus subconjuntos I , F , y R son los conjuntos de estados inicial, de aceptación y de rechazo, respectivamente, y δ ⊆ ( Q × { raíz , izquierda , derecha , hoja } × Σ × { arriba , izquierda , derecha } × Q ) es la relación de transición.

Un ejemplo sencillo de un autómata de recorrido de árboles es un TWA que realiza una búsqueda en profundidad (DFS) en el árbol de entrada. El autómata${\displaystyle A}$tiene tres estados,${\displaystyle Q=\{q_{0},q_{\mathit {left}},q_{\mathit {right}}\}}$.${\displaystyle A}$comienza en la raíz en estado${\displaystyle q_{0}}$y desciende al subárbol izquierdo. Luego procesa el árbol recursivamente. Siempre que${\displaystyle A}$entra en un nodo${\displaystyle v}$en el estado${\displaystyle q_{\mathit {left}}}$, significa que el subárbol izquierdo de${\displaystyle v}$acaba de ser procesado, por lo que procede al subárbol derecho de${\displaystyle v}$. Si${\displaystyle A}$entra en un nodo${\displaystyle v}$en el estado${\displaystyle q_{\mathit {right}}}$, significa que todo el subárbol con raíz${\displaystyle v}$ha sido procesado y${\displaystyle A}$camina hacia el padre de${\displaystyle v}$y cambia su estado a${\displaystyle q_{\mathit {left}}}$o${\displaystyle q_{\mathit {right}}}$, dependiendo de si${\displaystyle v}$es un niño izquierdo o derecho.

A diferencia de los autómatas ramificados , los autómatas de recorrido de árboles son difíciles de analizar: incluso las propiedades simples son difíciles de demostrar. La siguiente lista resume algunos hechos conocidos relacionados con los autómatas de recorrido de árboles:

• Como demostraron Bojańczyk y Colcombet , ^{[ 2 ]} las TWA deterministas son estrictamente más débiles que las no deterministas (${\displaystyle {\mathit {DTWA}}\subsetneq {\mathit {TWA}}}$)
• Las TWA deterministas son cerradas bajo complementación (pero se desconoce si lo mismo ocurre con las no deterministas ^{[ 3 ]} ).
• El conjunto de lenguajes reconocidos por TWA está estrictamente contenido en lenguajes de árbol regulares (${\displaystyle {\mathit {TWA}}\subsetneq {\mathit {REG}}}$), es decir, existen lenguajes regulares que no son reconocidos por ningún autómata de recorrido de árboles, véase Bojańczyk y Colcombet. ^{[ 4 ]}

• Autómatas de guijarros , una extensión de los autómatas que caminan sobre árboles.

• Mikołaj Bojańczyk: Autómatas que caminan por los árboles . Una breve encuesta.