Characterization of infinite LSP words and endomorphisms preserving the LSP property - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles International Journal of Foundations of Computer Science Year : 2019

Characterization of infinite LSP words and endomorphisms preserving the LSP property

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.
Fichier principal
Vignette du fichier
LSP.pdf (325.93 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01855460 , version 1 (08-08-2018)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More