Equivalence of Symbolic Tree Transducers

Vincent Hugot 1, 2 Adrien Boiret 1, 2 Joachim Niehren 1
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
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.
Type de document :
Communication dans un congrès
DLT 2017 - Developments in Language Theory, Aug 2017, Liege, Belgium. 105, pp.12, 2017, 〈10.1007/978-3-642-29709-0_32〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01517919
Contributeur : Inria Links <>
Soumis le : samedi 30 septembre 2017 - 18:19:23
Dernière modification le : vendredi 17 novembre 2017 - 08:50:20

Fichier

symbeq.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Vincent Hugot, Adrien Boiret, Joachim Niehren. Equivalence of Symbolic Tree Transducers. DLT 2017 - Developments in Language Theory, Aug 2017, Liege, Belgium. 105, pp.12, 2017, 〈10.1007/978-3-642-29709-0_32〉. 〈hal-01517919v2〉

Partager

Métriques

Consultations de la notice

66

Téléchargements de fichiers

14