TY - JOUR

T1 - On arithmetically progressed suffix arrays and related Burrows–Wheeler transforms

AU - Daykin, Jacqueline W.

AU - Köppl, Dominik

AU - Kübel, David

AU - Stober, Florian

N1 - Publisher Copyright:
© 2024 The Authors

PY - 2024/5/17

Y1 - 2024/5/17

N2 - 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.

AB - 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.

KW - Arithmetic progression

KW - Burrows–Wheeler transform

KW - Christoffel words

KW - String combinatorics

KW - Suffix array

UR - http://www.scopus.com/inward/record.url?scp=85193448920&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2024.04.009

DO - 10.1016/j.dam.2024.04.009

M3 - Article

AN - SCOPUS:85193448920

SN - 0166-218X

VL - 355

SP - 180

EP - 199

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -