Equivalence of Symbolic Tree Transducers

Hugot, Vincent; Boiret, Adrien; Niehren, Joachim

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]
Université de Lille
Linking Dynamic Data [LINKS]
Boiret, Adrien [Auteur]
Université de Lille
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]

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 :