The reflection complexity of sequences over finite alphabets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913821550968832 |
|---|---|
| author | Allouche, Jean-Paul Campbell, John M. Li, Shuo Shallit, Jeffrey Stipulanti, Manon |
| author_facet | Allouche, Jean-Paul Campbell, John M. Li, Shuo Shallit, Jeffrey Stipulanti, Manon |
| contents | In combinatorics on words, the well-studied factor complexity function $ρ_{\infw{x}}$ of a sequence $\infw{x}$ over a finite
alphabet counts, for every nonnegative integer $n$, the number of distinct length-$n$ factors of $\infw{x}$. In this paper, we
introduce the \emph{reflection complexity} function $r_{\infw{x}}$ to enumerate the factors occurring in a sequence $\infw{x}$, up
to reversing the order of symbols in a word. We prove a number of results about the growth properties of $r_{\infw{x}}$
and its relationship with other complexity functions. We also prove a Morse--Hedlund-type result characterizing eventually periodic
sequences in terms of their reflection complexity, and we deduce a characterization of Sturmian sequences. We investigate
the reflection complexity of quasi-Sturmian, episturmian, $(s+1)$-dimensional billiard, complementation-symmetric Rote, and rich
sequences. Furthermore, we prove that if $\infw{x}$ is $k$-automatic, then $r_{\infw{x}}$ is computably $k$-regular, and we use the
software \texttt{Walnut} to evaluate the reflection complexity of some automatic sequences, such as the Thue--Morse sequence. We
note that there are still many unanswered questions about this reflection measure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_09302 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The reflection complexity of sequences over finite alphabets Allouche, Jean-Paul Campbell, John M. Li, Shuo Shallit, Jeffrey Stipulanti, Manon Combinatorics Discrete Mathematics Formal Languages and Automata Theory 68R15 (primary), 11B85 (secondary) In combinatorics on words, the well-studied factor complexity function $ρ_{\infw{x}}$ of a sequence $\infw{x}$ over a finite alphabet counts, for every nonnegative integer $n$, the number of distinct length-$n$ factors of $\infw{x}$. In this paper, we introduce the \emph{reflection complexity} function $r_{\infw{x}}$ to enumerate the factors occurring in a sequence $\infw{x}$, up to reversing the order of symbols in a word. We prove a number of results about the growth properties of $r_{\infw{x}}$ and its relationship with other complexity functions. We also prove a Morse--Hedlund-type result characterizing eventually periodic sequences in terms of their reflection complexity, and we deduce a characterization of Sturmian sequences. We investigate the reflection complexity of quasi-Sturmian, episturmian, $(s+1)$-dimensional billiard, complementation-symmetric Rote, and rich sequences. Furthermore, we prove that if $\infw{x}$ is $k$-automatic, then $r_{\infw{x}}$ is computably $k$-regular, and we use the software \texttt{Walnut} to evaluate the reflection complexity of some automatic sequences, such as the Thue--Morse sequence. We note that there are still many unanswered questions about this reflection measure. |
| title | The reflection complexity of sequences over finite alphabets |
| topic | Combinatorics Discrete Mathematics Formal Languages and Automata Theory 68R15 (primary), 11B85 (secondary) |
| url | https://arxiv.org/abs/2406.09302 |