Equivalence of Symbolic Tree Transducers

Hugot, Vincent; Boiret, Adrien; Niehren, Joachim

Type de document :

Communication dans un congrès avec actes

DOI :

10.1007/978-3-642-29709-0_32

Titre :

Equivalence of Symbolic Tree Transducers

Auteur(s) :

Hugot, Vincent [Auteur]
Université de Lille
Linking Dynamic Data [LINKS]
Boiret, Adrien [Auteur]
Université de Lille
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]

Linking Dynamic Data [LINKS]

Titre de la manifestation scientifique :

DLT 2017 - Developments in Language Theory

Ville :

Liege

Pays :

Belgique

Date de début de la manifestation scientifique :

2017-08-07

Date de publication :

2017-04-22

Mot(s)-clé(s) en anglais :

semi-structured data
formal languages
tree automata
transducers

Discipline(s) HAL :

Informatique [cs]/Théorie et langage formel [cs.FL]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Correction de scripts Linux

Collections :