Skip to Main content Skip to Navigation
Conference papers

Normal Form on Linear Tree-to-word Transducers

Adrien Boiret 1, 2 
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : We study a subclass of tree-to-word transducers: linear tree-to-word transducers, that cannot use several copies of the input. We aim to study the equivalence problem on this class, by using minimization and normalization techniques. We identify a Myhill-Nerode characterization. It provides a minimal normal form on our class, computable in Exptime. This paper extends an already existing result on tree-to-word transducers without copy or reordering (sequential tree-to-word transducers), by accounting for all the possible reorderings in the output.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Adrien Boiret Connect in order to contact the contributor
Submitted on : Wednesday, April 12, 2017 - 3:39:57 PM
Last modification on : Wednesday, March 23, 2022 - 3:51:22 PM
Long-term archiving on: : Thursday, July 13, 2017 - 2:01:32 PM


Files produced by the author(s)


  • HAL Id : hal-01218030, version 1


Adrien Boiret. Normal Form on Linear Tree-to-word Transducers. 10th International Conference on Language and Automata Theory and Applications, Mar 2016, Prague, Czech Republic. ⟨hal-01218030⟩



Record views


Files downloads