Normal Form on Linear Tree-to-word Transducers - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Normal Form on Linear Tree-to-word Transducers

Résumé

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.
Fichier principal
Vignette du fichier
0.pdf (365 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01218030 , version 1 (12-04-2017)

Identifiants

  • HAL Id : hal-01218030 , version 1

Citer

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⟩
173 Consultations
165 Téléchargements

Partager

Gmail Facebook X LinkedIn More