Equivalence of Symbolic Tree Transducers - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Equivalence of Symbolic Tree Transducers

Vincent Hugot
  • Fonction : Auteur
  • PersonId : 958174
Adrien Boiret
  • Fonction : Auteur
  • PersonId : 958173
Joachim Niehren

Résumé

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.
Fichier principal
Vignette du fichier
symbeq.pdf (291.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01517919 , version 1 (09-06-2017)
hal-01517919 , version 2 (30-09-2017)

Identifiants

Citer

Vincent Hugot, Adrien Boiret, Joachim Niehren. Equivalence of Symbolic Tree Transducers. DLT 2017 - Developments in Language Theory, Aug 2017, Liege, Belgium. pp.12, ⟨10.1007/978-3-642-29709-0_32⟩. ⟨hal-01517919v2⟩
460 Consultations
340 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More