Projects per year
Abstract
We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation P coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given P under which we can find a uniquely defined string over either a binary or ternary alphabet having P as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows–Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions.
Original language | English |
---|---|
Pages (from-to) | 180-199 |
Number of pages | 20 |
Journal | Discrete Applied Mathematics |
Volume | 355 |
Early online date | 17 May 2024 |
DOIs | |
Publication status | Published - 15 Oct 2024 |
Keywords
- Arithmetic progression
- Burrows–Wheeler transform
- Christoffel words
- String combinatorics
- Suffix array
Fingerprint
Dive into the research topics of 'On arithmetically progressed suffix arrays and related Burrows–Wheeler transforms'. Together they form a unique fingerprint.Projects
- 1 Finished
-
SeqInfo : Big Data Stringology Algorithms for 2nd and 3rd Generation Sequencing - Dr Jacqueline Daykin - EU/WG
Clare, A. (PI)
15 Jan 2018 → 07 Jan 2021
Project: Externally funded research