DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2022.79

On Extended Boundary Sequences of Morphic and Sturmian Words

Authors: Michel Rigo, Manon Stipulanti, and Markus A. Whiteland

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

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.

Cite as

Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. On Extended Boundary Sequences of Morphic and Sturmian Words. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 79:1-79:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rigo_et_al:LIPIcs.MFCS.2022.79,
  author =	{Rigo, Michel and Stipulanti, Manon and Whiteland, Markus A.},
  title =	{{On Extended Boundary Sequences of Morphic and Sturmian Words}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{79:1--79:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.79},
  URN =		{urn:nbn:de:0030-drops-168776},
  doi =		{10.4230/LIPIcs.MFCS.2022.79},
  annote =	{Keywords: Boundary sequences, Sturmian words, Numeration systems, Automata, Graph of addition}
}

Search Results

Documents authored by Stipulanti, Manon

On Extended Boundary Sequences of Morphic and Sturmian Words

Abstract

Cite as

Thanks for your feedback!

Could not send message