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.
Domains
Discrete Mathematics [cs.DM]Origin | Files produced by the author(s) |
---|
Loading...