2021/07/06 by Jacqueline W. Daykin, Daykin, Jacqueline W., Dominik Köppl +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Arithmetic #Binary number #Circulant matrix #Combinatorics #Combinatorics (math.CO) #Combinatorics on words #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Fibonacci number #Formal Languages and Automata Theory (cs.FL) #Linguistics #Mathematics #Modulo #Permutation (music) #Permutation matrix #String (physics) #Suffix #Unary operation #Word (group theory) #cs.DS #cs.FL #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2107.02503
arxiv created 2021/07/06 · openalex publication_date 2021/07/06 · arxiv updated 2021/07/07 · openalex created_date 2021/07/19 · openalex updated_date 2026/07/28
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.