2026-07-23T22:06:56Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:16877 2024-03-06T10:58:34Z ddc:004 open_access
On Extended Boundary Sequences of Morphic and Sturmian Words Rigo, Michel Stipulanti, Manon Whiteland, Markus A. Boundary sequences Sturmian words Numeration systems Automata Graph of addition Generalizing the notion of the boundary sequence introduced by Chen and Wen, the nth term of the 𝓁-boundary sequence of an infinite word is the finite set of pairs (u,v) of prefixes and suffixes of length 𝓁 appearing in factors uyv of length n+𝓁 (n β‰₯ 𝓁 β‰₯ 1). Otherwise stated, for increasing values of n, one looks for all pairs of factors of length 𝓁 separated by n-𝓁 symbols. For the large class of addable numeration systems U, we show that if an infinite word is U-automatic, then the same holds for its 𝓁-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). We also provide examples of numeration systems and U-automatic words with a boundary sequence that is not U-automatic. In the second part of the paper, we study the 𝓁-boundary sequence of a Sturmian word. We show that it is obtained through a sliding block code from the characteristic Sturmian word of the same slope. We also show that it is the image under a morphism of some other characteristic Sturmian word. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Michel Rigo and Manon Stipulanti and Markus A. Whiteland 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.79 urn:nbn:de:0030-drops-168776 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.79 eng https://creativecommons.org/licenses/by/4.0/legalcode