ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS

DOI10.1142/S012905411240014XzbMath1251.68174MaRDI QIDQ2909197

Marcin Piątkowski, Wojciech Rytter

Publication date: 30 August 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

data compression; Sturmian words; repetitions

Mathematics Subject Classification ID

68R15: Combinatorics on words

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Related Items

Computing the number of cubic runs in standard Sturmian words, On the maximum number of cubic subwords in a word

Cites Work

• Maximal repetitions in strings
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• How many squares can a string contain?
• The exact number of squares in Fibonacci words
• A characterization of the squares in a Fibonacci string
• Detecting leftmost maximal periodicities
• Powers in Sturmian sequences
• Squares, cubes, and time-space efficient string searching
• A note on the number of squares in a word
• The number of runs in a string
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• An O(n log n) algorithm for finding all repetitions in a string
• Towards a Solution to the “Runs” Conjecture
• USEFULNESS OF DIRECTED ACYCLIC SUBWORD GRAPHS IN PROBLEMS RELATED TO STANDARD STURMIAN WORDS
• Automatic Sequences
• Jewels of Stringology
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound