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.
Classification :
68R15, 11B85, 68V15
Mots-clés :
abstract numeration system, boundary sequence, morphic word, Sturmian word
Affiliations des auteurs :
Michel Rigo
1
;
Manon Stipulanti
1
;
Markus Whiteland
1
1
Université de Liège
Michel Rigo; Manon Stipulanti; Markus Whiteland. On extended boundary sequences of morphic and Sturmian words. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/11728
@article{10_37236_11728,
author = {Michel Rigo and Manon Stipulanti and Markus Whiteland},
title = {On extended boundary sequences of morphic and {Sturmian} words},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {1},
doi = {10.37236/11728},
zbl = {1541.68305},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11728/}
}
TY - JOUR
AU - Michel Rigo
AU - Manon Stipulanti
AU - Markus Whiteland
TI - On extended boundary sequences of morphic and Sturmian words
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/11728/
DO - 10.37236/11728
ID - 10_37236_11728
ER -
%0 Journal Article
%A Michel Rigo
%A Manon Stipulanti
%A Markus Whiteland
%T On extended boundary sequences of morphic and Sturmian words
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11728/
%R 10.37236/11728
%F 10_37236_11728
