# Characterization of infinite LSP words and endomorphisms preserving the LSP property

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.
Keywords :
Document type :
Journal articles

Cited literature [21 references]

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 : Thursday, June 10, 2021 - 5:11:06 PM
Long-term archiving on: : Friday, November 9, 2018 - 12:26:52 PM

### Files

LSP.pdf
Files produced by the author(s)

### 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⟩

Record views