The maximal number of cubic runs in a word

DOI10.1016/j.jcss.2011.12.005zbMath1250.68217OpenAlexW1973043305WikidataQ61677877 ScholiaQ61677877MaRDI QIDQ1757839

Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Maxime Crochemore, Tomasz Walen, Marcin Kubica

Publication date: 6 November 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.12.005

zbMATH Keywords

Fibonacci wordrun in a wordLyndon word

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items

Efficiently computing runs on a trie ⋮ Clusters of repetition roots: single chains ⋮ Linear construction of a left Lyndon tree ⋮ The “Runs” Theorem ⋮ On the density of Lyndon roots in factors ⋮ Unnamed Item ⋮ Cartesian and Lyndon trees ⋮ Some results on the number of periodic factors in words ⋮ Computing runs on a trie ⋮ Clusters of repetition roots forming prefix chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure of subword graphs and suffix trees of Fibonacci words
• Maximal repetitions in strings
• How many runs can a string contain?
• Repetitions in strings: algorithms and combinatorics
• Squares, cubes, and time-space efficient string searching
• The number of runs in a string
• Towards a Solution to the “Runs” Conjecture
• Analysis of Maximal Repetitions in Strings
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• Not So Many Runs in Strings
• On the Maximal Number of Cubic Runs in a String
• The Number of Runs in Sturmian Words
• On the Maximal Number of Cubic Subwords in a String
• Repetitions in the Fibonacci infinite word
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound