Periods in partial words: an algorithm

DOI10.1016/j.jda.2012.04.001zbMath1279.68279OpenAlexW2148660034MaRDI QIDQ1932359

Francine Blanchet-Sadri, Gautam Sisodia, Travis Mandel

Publication date: 18 January 2013

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.04.001

zbMATH Keywords

graph connectivitycombinatorics on wordsautomata and formal languagespartial wordsFine and Wilf's theoremoptimal lengthsstrong periods

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Border correlations, lattices, and the subgraph component polynomial, A periodicity lemma for partial words

Cites Work

• Generalised fine and Wilf's theorem for arbitrary number of periods
• A new approach to the periodicity lemma on strings with holes
• Graph connectivity, partial words, and a theorem of Fine and Wilf
• On the combinatorics of finite words
• Partial words and a theorem of Fine and Wilf
• Periods in Partial Words: An Algorithm
• Handbook of Graph Theory
• Partial words and the interaction property of periods
• Algorithmic Combinatorics on Partial Words
• Uniqueness Theorems for Periodic Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item