Transductor de árbol

En la ciencia informática teórica y la teoría del lenguaje formal , un transductor de árbol (TT) es una máquina abstracta que toma como entrada un árbol y genera una salida (generalmente otros árboles, pero existen modelos que producen palabras u otras estructuras). En términos generales, los transductores de árbol extienden autómatas de árbol de la misma manera que los transductores de palabras extienden autómatas de palabras .

La manipulación de estructuras de árbol en lugar de palabras permite a las TT modelar transformaciones dirigidas por la sintaxis de lenguajes formales o naturales. Sin embargo, las TT no se comportan tan bien como sus contrapartes de palabras en términos de complejidad algorítmica , propiedades de cierre , etcétera. En particular, la mayoría de las clases principales no están cerradas bajo composición .

Las principales clases de transductores de árboles son:

Transductores de árbol de arriba hacia abajo (TOP)

Un TOP T es una tupla ( Q , Σ, Γ, I , δ ) tal que:

• Q es un conjunto finito , el conjunto de estados ;
• Σ es un alfabeto de rango finito , llamado alfabeto de entrada ;
• Γ es un alfabeto de rango finito, llamado alfabeto de salida ;
• I es un subconjunto de Q , el conjunto de estados iniciales ; y
• δ es un conjunto de reglas de la forma , donde f es un símbolo de Σ, n es la aridad de f , q es un estado y u es un árbol en Γ y , siendo dichos pares nularios . ${\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}$ ${\displaystyle Q\times 1..n}$

Ejemplos de reglas e intuiciones sobre semántica

Por ejemplo,

${\displaystyle q(f(x_{1},\dots ,x_{3}))\to g(a,q'(x_{1}),h(q''(x_{3})))}$

es una regla –se escribe habitualmente en lugar del par– y su semántica intuitiva es que, bajo la acción de q , un árbol con f en la raíz y tres hijos se transforma en ${\displaystyle q(x_{i})}$ ${\displaystyle (q,x_{i})}$

${\displaystyle g(a,q'(x_{1}),h(q''(x_{3})))}$

donde, recursivamente, y se reemplazan, respectivamente, con la aplicación de en el primer hijo y con la aplicación de en el tercero. ${\displaystyle q'(x_{1})}$ ${\displaystyle q''(x_{3})}$ ${\displaystyle q'}$ ${\displaystyle q''}$

La semántica comoreescritura de términos

La semántica de cada estado del transductor T , y de T mismo, es una relación binaria entre árboles de entrada (en Σ) y árboles de salida (en Γ).

Una forma de definir la semántica formalmente es verla como un sistema de reescritura de términos , siempre que en los lados derechos las llamadas se escriban en la forma , donde los estados q son símbolos unarios. Entonces la semántica de un estado q está dada por ${\displaystyle \delta }$ ${\displaystyle q(x_{i})}$ ${\displaystyle [\![q]\!]}$

${\displaystyle [\![q]\!]=\{u\mapsto v\mid u{\text{ is a tree on }}\Sigma ,\ v{\text{ is a tree on }}\Gamma {\text{, and }}q(u)\to _{\delta }^{*}v\}.}$

La semántica de T se define entonces como la unión de la semántica de sus estados iniciales:

${\displaystyle [\![T]\!]=\bigcup _{q\in I}[\![q]\!].}$

Determinismo y dominio

Al igual que con los autómatas de árbol, se dice que un TOP es determinista (abreviado como DTOP ) si no hay dos reglas de δ que compartan el mismo lado izquierdo y hay como máximo un estado inicial. En ese caso, la semántica del DTOP es una función parcial de los árboles de entrada (en Σ) a los árboles de salida (en Γ), al igual que la semántica de cada uno de los estados del DTOP.

El dominio de un transductor es el dominio de su semántica. Asimismo, la imagen de un transductor es la imagen de su semántica.

Propiedades de DTOP

• Los DTOP no están cerrados bajo la unión : este ya es el caso de los transductores de palabras deterministas.
• El dominio de un DTOP es un lenguaje de árbol regular . Además, el dominio es reconocible por un autómata de árbol descendente determinista (DTTA) de tamaño como máximo exponencial al del DTOP inicial. ^[1]

Que el dominio sea reconocible mediante DTTA no es sorprendente, considerando que los lados izquierdos de las reglas DTOP son los mismos que para DTTA. En cuanto a la razón de la explosión exponencial en el peor de los casos (que no existe en el caso de las palabras), considere la regla . Para que el cálculo tenga éxito, debe tener éxito para ambos hijos. Eso significa que el hijo derecho debe estar en el dominio de . En cuanto al hijo izquierdo, debe estar en el dominio de ambos y . En general, dado que los subárboles se pueden copiar, un solo subárbol puede evaluarse por múltiples estados durante una ejecución, a pesar del determinismo y a diferencia de DTTA. Por lo tanto, la construcción del DTTA que reconoce el dominio de un DTOP debe tener en cuenta conjuntos de estados y calcular las intersecciones de sus dominios, de ahí el exponencial. En el caso especial de DTOP lineal , es decir, DTOP donde cada uno aparece como máximo una vez en el lado derecho de cada regla, la construcción es lineal en el tiempo y el espacio. ${\displaystyle q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))}$ ${\displaystyle p_{3}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle x_{i}}$

• La imagen de un DTOP no es un lenguaje de árbol regular.

Consideremos el transductor que codifica la transformación ; es decir, duplica el hijo de la entrada. Esto se hace fácilmente mediante una regla , donde p codifica la identidad . Entonces, en ausencia de cualquier restricción en el primer hijo de la entrada, la imagen es un lenguaje clásico de árbol no regular. ${\displaystyle f(x)\to g(x,x)}$ ${\displaystyle q(f(x_{1}))\to g(p(x_{1}),p(x_{1}))}$

• Sin embargo, el dominio de un DTOP no puede restringirse a un lenguaje de árbol regular. Es decir, dado un DTOP T y un lenguaje L , en general no se puede construir un DTOP tal que la semántica de sea la de T , restringida a L . ${\displaystyle T'}$ ${\displaystyle T'}$

Esta propiedad está vinculada a la razón por la que los autómatas de árbol deterministas de arriba hacia abajo son menos expresivos que los autómatas de abajo hacia arriba: una vez que se recorre un camino determinado, la información de otros caminos es inaccesible. Considere el transductor que codifica la transformación ; es decir, genera el hijo derecho de la entrada. Esto se hace fácilmente mediante una regla , donde p codifica la identidad. Ahora digamos que queremos restringir este transductor al dominio finito (y por lo tanto, en particular, regular) . Debemos usar las reglas . Pero en la primera regla, no aparece en absoluto, ya que no se produce nada a partir del hijo izquierdo. Por lo tanto, no es posible probar que el hijo izquierdo sea c . Por el contrario, dado que producimos a partir del hijo derecho, podemos probar que es a o b . En general, el criterio es que DTOP no puede probar propiedades de subárboles a partir de los cuales no producen salida. ${\displaystyle f(x,y)\to y}$ ${\displaystyle q(f(x_{1},x_{2}))\to p(x_{2})}$ ${\displaystyle \{f(c,a),\ f(c,b)\}}$ ${\displaystyle q(f(x_{1},x_{2}))\to p(x_{2}),\ p(a)\to a,\ p(b)\to b}$ ${\displaystyle x_{1}}$

• Los DTOP no están cerrados bajo composición . Sin embargo, este problema se puede resolver mediante la adición de un lookahead: un autómata de árbol, acoplado al transductor, que puede realizar pruebas en el dominio de las que el transductor no es capaz. ^[2]

Esto se desprende del punto sobre la restricción del dominio: componer la identidad de codificación DTOP con la codificación debe producir un transductor con la semántica , que sabemos que no se puede expresar mediante un DTOP. ${\displaystyle \{f(c,a),\ f(c,b)\}}$ ${\displaystyle f(x,y)\to y}$ ${\displaystyle \{f(c,a)\mapsto a,\ f(c,b)\mapsto b\}}$

• El problema de verificación de tipos (probar si la imagen de un lenguaje de árbol regular está incluida en otro lenguaje de árbol regular) es decidible.
• El problema de equivalencia —probar si dos DTOP definen las mismas funciones— es decidible. ^[3]

Transductores de árbol de abajo hacia arriba (BOT)

Al igual que en el caso más simple de los autómatas de árbol, los transductores de árbol de abajo a arriba se definen de manera similar a sus contrapartes de arriba a abajo, pero proceden de las hojas del árbol a la raíz, en lugar de hacerlo de la raíz a las hojas. Por lo tanto, la principal diferencia está en la forma de las reglas, que tienen la forma . ${\displaystyle f(q_{1}(x_{1}),\dots ,q_{n}(x_{n}))\to q(u)}$

Referencias

• Común, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Loding, Christof; Tison, Sophie; Tommasi, Marc (noviembre de 2008). "Capítulo 6: Transductores de árboles". Técnicas y aplicaciones de autómatas de árboles . Consultado el 11 de febrero de 2014 .
• Hosoya, Haruo (4 de noviembre de 2010). Fundamentos del procesamiento XML: el enfoque de árbol-autómata . Cambridge University Press. ISBN 978-1-139-49236-2.

1. Baker, BS: Composición de transducciones de árboles de arriba hacia abajo y de abajo hacia arriba. Inf. Control 41(2), 186–213 (1979)
2. Maneth, Sebastian (diciembre de 2015). "Una encuesta sobre problemas de equivalencia decidible para transductores de árbol" (PDF) . Revista internacional de fundamentos de la ciencia de la computación . 26 (8): 1069–1100. doi :10.1142/S0129054115400134. hdl : 20.500.11820/2f1acef4-1b06-485f-bfd1-88636c9e2fe6 .
3. "Resultados de decidibilidad relativos a los transductores de árbol I". www.inf.u-szeged.hu .