تقرير
On extended boundary sequences of morphic and Sturmian words
| العنوان: | On extended boundary sequences of morphic and Sturmian words |
|---|---|
| المؤلفون: | Rigo, Michel, Stipulanti, Manon, Whiteland, Markus A. |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Formal Languages and Automata Theory, 68R15, F.1.1, G.2.1 |
| الوصف: | Generalizing the notion of the boundary sequence introduced by Chen and Wen, the $n$th term of the $\ell$-boundary sequence of an infinite word is the finite set of pairs $(u,v)$ of prefixes and suffixes of length $\ell$ appearing in factors $uyv$ of length $n+\ell$ ($n\ge \ell\ge 1$). Otherwise stated, for increasing values of $n$, one looks for all pairs of factors of length $\ell$ separated by $n-\ell$ symbols. For the large class of addable abstract numeration systems $S$, we show that if an infinite word is $S$-automatic, then the same holds for its $\ell$-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). To precise the limits of this result, we discuss examples of non-addable numeration systems and $S$-automatic words for which the boundary sequence is nevertheless $S$-automatic and conversely, $S$-automatic words with a boundary sequence that is not $S$-automatic. In the second part of the paper, we study the $\ell$-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. Comment: 32 pages, 8 figures. Short version: M. Rigo, M. Stipulanti, M. A. Whiteland, On extended boundary sequences of morphic and Sturmian words, MFCS 2022, Leibniz Int. Proc. Inform. 241 (2022), Paper 79 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2206.15319 |
| رقم الأكسشن: | edsarx.2206.15319 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |