Title :

Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time

Author(s) :

Boiret, Adrien [Auteur]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Linking Dynamic Data [LINKS]
Palenta, Raphaela [Auteur]
Technische Universität Munchen - Technical University Munich - Université Technique de Munich [TUM]

Conference title :

20th International Conference on Developments in Language Theory (DLT 2016)

City :

Montreal

Country :

Canada

Start date of the conference :

2016-07-25

Book title :

Lecture Notes in Computer Science

Journal title :

Developments in Language Theory - 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings

Publisher :

Springer

Publication date :

2016-07-21

English keyword(s) :

Tree Transducer
Deciding Equivalence
Partial Normal Form

HAL domain(s) :

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

English abstract : [en]

We show that the equivalence of linear top-down tree-to-word transducers is decidable in polynomial time. Linear tree-to-word transducers are non-copying but not necessarily order-preserving and can be used to express XML ...
Show more >We show that the equivalence of linear top-down tree-to-word transducers is decidable in polynomial time. Linear tree-to-word transducers are non-copying but not necessarily order-preserving and can be used to express XML and other document transformations. The result is based on a partial normal form that provides a basic characterization of the languages produced by linear tree-to-word 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