Equivalence of Symbolic Tree Transducers
| Autor: | Hugot, Vincent, Boiret, Adrien, Niehren, Joachim |
|---|---|
| Přispěvatelé: | Linking Dynamic Data (LINKS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Université de Lille, ANR-15-CE25-0001,Colis,Correction de scripts Linux(2015) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | DLT 2017-Developments in Language Theory DLT 2017-Developments in Language Theory, Aug 2017, Liege, Belgium. pp.12, ⟨10.1007/978-3-642-29709-0_32⟩ |
| DOI: | 10.1007/978-3-642-29709-0_32⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|