Equivalence of Symbolic Tree TransducersReportar como inadecuado

Equivalence of Symbolic Tree Transducers - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LINKS - Linking Dynamic Data Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 2 Université de Lille

Abstract : Symbolic tree transducers are programs by which to transform data trees with an infinite signature. In this paper, we show that the equivalence problem of symbolic top-down deterministic tree transducers DTops can be reduced to that of classical DTops. As a consequence the equivalence of two symbolic DTops can be decided in NExpTime, when assuming that all operations related to the processing of data values are in PTime. This results can be extended to symbolic DTops with lookahead and thus to symbolic bottom-up deterministic tree transducers.

Keywords : tree automata transducers formal languages semi-structured data

Autor: Vincent Hugot - Adrien Boiret - Joachim Niehren -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados