transductor de árbol

Por ejemplo,

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

es una regla – uno habitualmente escribe${\displaystyle q(x_{i})}$en lugar del par${\displaystyle (q,x_{i})}$– 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 g(a,q'(x_{1}),h(q''(x_{3})))}$

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

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 ver${\displaystyle \delta }$como un sistema de reescritura de términos , siempre que en los lados derechos las llamadas estén escritas en la forma${\displaystyle q(x_{i})}$, donde los estados q son símbolos unarios. Entonces la semántica${\displaystyle [\![q]\!]}$de un estado q viene dado por

${\displaystyle [\![q]\!]=\{u\mapsto v\mid u{\text{ es un árbol en }}\Sigma ,\ v{\text{ es un árbol en }}\Gamma {\text{, y }}q(u)\to _{\delta }^{*}v\}.}$

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

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

Al igual que con los autómatas de árbol, se dice que un TOP es determinista (abreviado DTOP ) si no hay dos reglas de δ que compartan el mismo lado izquierdo y existe 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. Del mismo modo, la imagen de un transductor es la imagen de su semántica.

• Los DTOP no están cerrados bajo la unión : este ya es el caso para 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 determinista descendente (DTTA) de tamaño como máximo exponencial en el del DTOP inicial. ^{[ 1 ]}

Que el dominio sea reconocible por 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 caso (que no existe en el caso de la palabra), considérese la regla${\displaystyle q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))}$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${\displaystyle p_{3}}$En cuanto al hijo izquierdo, debe estar en el dominio de ambos.${\displaystyle p_{1}}$y${\displaystyle p_{2}}$En general, dado que los subárboles se pueden copiar, un único subárbol puede ser evaluado por múltiples estados durante una ejecución, a pesar del determinismo, y a diferencia de DTTA. Por lo tanto, la construcción de DTTA que reconoce el dominio de un DTOP debe tener en cuenta conjuntos de estados y calcular las intersecciones de sus dominios, de ahí la exponencial. En el caso especial de DTOP lineal , es decir, DTOP donde cada${\displaystyle x_{i}}$Aparece como máximo una vez en el lado derecho de cada regla, la construcción es lineal en el tiempo y el espacio.

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

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

• 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 , no se puede, en general, construir un DTOP${\displaystyle T'}$de tal manera que la semántica de${\displaystyle T'}$es la de T , restringida a L.

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

• Los DTOP no son cerrados bajo composición . Sin embargo, este problema puede resolverse mediante la adición de una anticipación : un autómata de árbol, acoplado al transductor, que puede realizar pruebas en el dominio del que el transductor es incapaz. ^{[ 2 ]}

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

• El problema de la verificación de tipos —que consiste en comprobar 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 ]}