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

https://hal.inria.fr/hal-01218030
Contributor : Adrien Boiret <>
Submitted on : Wednesday, April 12, 2017 - 3:39:57 PM
Last modification on : Friday, December 11, 2020 - 6:44:06 PM
Long-term archiving on: : Thursday, July 13, 2017 - 2:01:32 PM

File

0.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01218030, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

331

Files downloads

405