• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Equivalence of Symbolic Tree Transducers
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Communication dans un congrès avec actes
DOI :
10.1007/978-3-642-29709-0_32
Title :
Equivalence of Symbolic Tree Transducers
Author(s) :
Hugot, Vincent [Auteur]
Linking Dynamic Data [LINKS]
Boiret, Adrien [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur] refId
Linking Dynamic Data [LINKS]
Conference title :
DLT 2017 - Developments in Language Theory
City :
Liege
Country :
Belgique
Start date of the conference :
2017-08-07
Publication date :
2017-04-22
English keyword(s) :
semi-structured data
formal languages
tree automata
transducers
HAL domain(s) :
Informatique [cs]/Théorie et langage formel [cs.FL]
English abstract : [en]
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 ...
Show more >
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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
ANR Project :
Correction de scripts Linux
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://hal.inria.fr/hal-01517919v2/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/hal-01517919v2/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/hal-01517919v2/document
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017