Skip to Main content Skip to Navigation
Journal articles

Characterization of infinite LSP words and endomorphisms preserving the LSP property

Gwenaël Richomme 1, 2
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Answering a question of G. Fici, we give an $S$-adic characterization of the family of infinite LSP words, that is, the family of infinite words having all their left special factors as prefixes. 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 one of its directive words is recognizable by ${\cal A}$. Then we characterize the endomorphisms that preserve the property of being LSP for infinite words. This allows us to prove that there exists no set $S'$ of endomorphisms for which the set of infinite LSP words corresponds to the set of $S'$-adic words. This implies that an automaton is required no matter which set of morphisms is used.
Document type :
Journal articles
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01855460
Contributor : Gwenaël Richomme <>
Submitted on : Wednesday, August 8, 2018 - 10:40:09 AM
Last modification on : Tuesday, May 12, 2020 - 1:46:05 PM
Long-term archiving on: : Friday, November 9, 2018 - 12:26:52 PM

Files

LSP.pdf
Files produced by the author(s)

Identifiers

Citation

Gwenaël Richomme. Characterization of infinite LSP words and endomorphisms preserving the LSP property. International Journal of Foundations of Computer Science, World Scientific Publishing, 2019, 30 (1), pp.171-196. ⟨10.1142/S0129054119400082⟩. ⟨lirmm-01855460⟩

Share

Metrics

Record views

614

Files downloads

91