Skip to Main content Skip to Navigation
Conference papers

Equivalence of Symbolic Tree Transducers

Vincent Hugot 1, 2 Adrien Boiret 1, 2 Joachim Niehren 1
1 LINKS - Linking Dynamic Data
CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189, Inria Lille - Nord Europe
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download
Contributor : Inria Links <>
Submitted on : Saturday, September 30, 2017 - 6:19:23 PM
Last modification on : Friday, December 11, 2020 - 6:44:06 PM
Long-term archiving on: : Sunday, December 31, 2017 - 12:52:46 PM


Files produced by the author(s)




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⟩



Record views


Files downloads