On the number of squares in partial words

DOI10.1051/ita/2010008zbMath1184.68372OpenAlexW2004920608MaRDI QIDQ5190081

Tomi Kärki, Vesa Halava, Tero J.Harju

Publication date: 12 March 2010

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/44615

zbMATH Keywords

squarepartial wordtheorem of Fraenkel and Simpson

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items

Computing primitively-rooted squares and runs in partial words, Computing Primitively-Rooted Squares and Runs in Partial Words, Constructing Words with High Distinct Square Densities, Squares in partial words, Partial words with a unique position starting a square, A NEW PROOF OF THE THREE-SQUARES LEMMA FOR PARTIAL WORDS WITH ONE HOLE, Squares and primitivity in partial words, Efficient enumeration of non-equivalent squares in partial words with few holes

Cites Work

• Square-free partial words
• Overlap-freeness in infinite partial words
• How many squares can a string contain?
• Partial words and a theorem of Fine and Wilf
• Squares, cubes, and time-space efficient string searching
• A note on the number of squares in a word
• Freeness of partial words
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• Algorithmic Combinatorics on Partial Words
• Unnamed Item
• Unnamed Item
• Unnamed Item