The “Runs” Theorem
From MaRDI portal
Publication:5359492
DOI10.1137/15M1011032zbMath1375.68093arXiv1406.0263OpenAlexW2199929370MaRDI QIDQ5359492
Yuto Nakashima, Masayuki Takeda, Hideo Bannai, Kazuya Tsuruta, Shunsuke Inenaga, Tomohiro I.
Publication date: 25 September 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.0263
Related Items
Prefix frequency of lost positions, Efficiently computing runs on a trie, Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes, Clusters of repetition roots: single chains, Upper bounds on distinct maximal (sub-)repetitions in compressed strings, Factorizing strings into repetitions, Universal Reconstruction of a String, A computational substantiation of the \(d\)-step approach to the number of distinct squares problem, Multidimensional period recovery, Lower bounds for the number of repetitions in 2D strings, Can formal languages help pangenomics to represent and analyze multiple genomes?, Longest previous overlapping factor array, Computing longest (common) Lyndon subsequences, Searching of gapped repeats and subrepetitions in a word, Linear construction of a left Lyndon tree, Lyndon partial words and arrays with applications, String rearrangement inequalities and a total order between primitive words, Computing longest Lyndon subsequences and longest common Lyndon subsequences, Finite and infinite closed-rich words, Unnamed Item, Maximal closed substrings, Computing runs on a general alphabet, Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets, Unnamed Item, On the number of gapped repeats with arbitrary gap, Crochemore's partitioning on weighted strings and applications, Dynamic and internal longest common substring, Efficient Computation of 2-Covers of a String., Practical Performance of Space Efficient Data Structures for Longest Common Extensions., Detecting One-Variable Patterns, An abelian periodicity lemma, Fast computation of abelian runs, Square network on a word, Bannai et al. method proves the \(d\)-step conjecture for strings, On \(k\)-abelian palindromes, On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties, String covering with optimal covers, Shortest covers of all cyclic shifts of a string, Unnamed Item, Internal dictionary matching, Some results on the number of periodic factors in words, Computation of the suffix array, Burrows-Wheeler transform and FM-index in \(V\)-order, Repetition Detection in a Dynamic String, Two-dimensional maximal repetitions, Universal reconstruction of a string, Longest property-preserved common factor: a new string-processing framework, Efficient representation and counting of antipower factors in words, Computing runs on a trie, On the size of overlapping Lempel-Ziv and Lyndon factorizations, Computing the Antiperiod(s) of a String, Quasi-Linear-Time Algorithm for Longest Common Circular Factor, Unnamed Item, On the size of the smallest alphabet for Lyndon trees, More properties of the Fibonacci word on an infinite alphabet, Almost linear time computation of maximal repetitions in run length encoded strings, Clusters of repetition roots forming prefix chains, Longest Lyndon Substring After Edit, Three overlapping squares: the general case characterized \& applications, On closed-rich words
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extracting powers and periods in a word from its runs structure
- Deterministic geoleader election in disoriented anonymous systems
- Representations of quiver Hecke algebras via Lyndon bases.
- On the maximal sum of exponents of runs in a string
- A \(d\)-step approach to the maximum number of distinct squares and runs in strings
- The ``runs conjecture
- Lyndon + Christoffel = digitally convex
- Circle formation of weak robots and Lyndon words
- Computing runs on a general alphabet
- On the action of the symmetric group on the free Lie algebra and the partition lattice
- Maximal repetitions in strings
- How many runs can a string contain?
- Computing longest previous factor in linear time and applications
- Repetitions in strings: algorithms and combinatorics
- Asymptotic behavior of the numbers of runs and microruns
- An on-line string superprimitivity test
- Lyndon words, permutations and trees.
- Repetitive perhaps, but certainly not boring
- The maximal number of cubic runs in a word
- Computing regularities in strings: a survey
- Periodic musical sequences and Lyndon words
- The maximal number of runs in standard Sturmian words
- Space efficient linear time construction of suffix arrays
- Large-scale detection of repetitions
- Suffix Arrays: A New Method for On-Line String Searches
- Factorizing words over an ordered alphabet
- An O(n log n) algorithm for finding all repetitions in a string
- Linear work suffix array construction
- Fast and Practical Algorithms for Computing All the Runs in a String
- AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
- Not So Many Runs in Strings
- Linear-Time Construction of Suffix Arrays
- A unifying look at data structures
- A universal algorithm for sequential data compression
- Standard Lyndon Bases of Lie Algebras and Enveloping Algebras
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- Uniqueness Theorems for Periodic Functions
- Internal Pattern Matching Queries in a Text and Applications
- A new characterization of maximal repetitions by Lyndon trees
- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
- Lyndon Words and Short Superstrings
- On Burnside's Problem
- Free differential calculus. IV: The quotient groups of the lower central series
