A Characterization of Infinite LSP Words

Gwenaël Richomme 1, 2
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : G. Fici proved that a finite word has a minimal suffix automaton if and only if all its left special factors occur as prefixes. He called LSP all finite and infinite words having this latter property. We characterize here infinite LSP words in terms of $S$-adicity. More precisely we provide a finite set of morphisms $S$ and an automaton ${\cal A}$ such that an infinite word is LSP if and only if it is $S$-adic and all its directive words are recognizable by ${\cal A}$.
Type de document :
Communication dans un congrès
DLT: Developments in Language Theory, Aug 2017, Liège, Belgium. Springer, 21st International Conference on Developments in Language Theory (DLT 2017), LNCS (10396), pp.320-331, 2017, 〈http://www.cant.ulg.ac.be/dlt/〉. 〈10.1007/978-3-319-62809-7_24〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01587263
Contributeur : Gwenaël Richomme <>
Soumis le : mercredi 13 septembre 2017 - 22:54:46
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

Collections

Citation

Gwenaël Richomme. A Characterization of Infinite LSP Words. DLT: Developments in Language Theory, Aug 2017, Liège, Belgium. Springer, 21st International Conference on Developments in Language Theory (DLT 2017), LNCS (10396), pp.320-331, 2017, 〈http://www.cant.ulg.ac.be/dlt/〉. 〈10.1007/978-3-319-62809-7_24〉. 〈lirmm-01587263〉

Partager

Métriques

Consultations de la notice

56