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 (CRIStAL) - 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.
Type de document :
Communication dans un congrès
Janoušek, Jan; Martín-Vide, Carlos. 10th International Conference on Language and Automata Theory and Applications, Mar 2016, Prague, Czech Republic. 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01218030
Contributeur : Adrien Boiret <>
Soumis le : mercredi 12 avril 2017 - 15:39:57
Dernière modification le : mardi 3 juillet 2018 - 11:23:13
Document(s) archivé(s) le : jeudi 13 juillet 2017 - 14:01:32

Fichier

0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01218030, version 1

Collections

Citation

Adrien Boiret. Normal Form on Linear Tree-to-word Transducers. Janoušek, Jan; Martín-Vide, Carlos. 10th International Conference on Language and Automata Theory and Applications, Mar 2016, Prague, Czech Republic. 10th International Conference, LATA 2016, Prague, Czech Republic, March 14-18, 2016, Proceedings. 〈hal-01218030〉

Partager

Métriques

Consultations de la notice

268

Téléchargements de fichiers

46