Paper published in a journal (Scientific congresses and symposiums)
On extended boundary sequences of morphic and Sturmian words
Rigo, Michel; Stipulanti, Manon; Whiteland, Markus
2022 • In Leibniz International Proceedings in Informatics, 241, p. 79
Peer Reviewed verified by ORBi
 

Files


Full Text
arXiv.pdf
Author postprint (757.46 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Combinatorics on words; Boundary sequences; Sturmian words; Numeration systems; Automata; Graph of addition
Abstract :
[en] 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 numeration systems $U$, we show that if an infinite word is $U$-automatic, then the same holds for its $\ell$-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 $\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.
Disciplines :
Mathematics
Author, co-author :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique
Stipulanti, Manon  ;  Université de Liège - ULiège > Mathematics
Whiteland, Markus ;  Université de Liège - ULiège > Mathematics
Language :
English
Title :
On extended boundary sequences of morphic and Sturmian words
Publication date :
2022
Event name :
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Event place :
Vienne, Austria
Event date :
du 22 août au 26 août 2022
Audience :
International
Journal title :
Leibniz International Proceedings in Informatics
ISSN :
1868-8969
Publisher :
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Germany
Volume :
241
Pages :
Paper 79
Peer review/Selection committee :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique
Available on ORBi :
since 23 August 2022

Statistics


Number of views
189 (1 by ULiège)
Number of downloads
198 (1 by ULiège)

Scopus citations®
 
1
Scopus citations®
without self-citations
0
OpenAlex citations
 
1

Bibliography


Similar publications



Contact ORBi