On extended boundary sequences of morphic and Sturmian words
| Autor: | Rigo, Michel, Stipulanti, Manon, Whiteland, Markus A. |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Formal Languages and Automata Theory (cs.FL) Numeration systems Computer Science - Formal Languages and Automata Theory G.2.1 Sturmian words 68R15 Theory of computation → Regular languages Automata Graph of addition Mathematics of computing → Combinatorics on words FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) Boundary sequences F.1.1 Computer Science::Formal Languages and Automata Theory |
| Popis: | 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. 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|