Periodicity algorithms and a conjecture on overlaps in partial words

详细信息	查看全文 | 推荐本文 |

• 作者：F. Blanchet-Sadri^a ; ^{blanchet@uncg.edu} ; Robert Merca艧^b ; ^{robertmercas@gmail.com} ; Abraham Rashin^c ; Elara Willett^d
• 关键词：Combinatorics on words ; Partial words ; Freeness ; Overlaps ; Algorithms ; Periodicity
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：20 July, 2012
• 卷：443
• 期：Complete
• 页码：35-45
• 文件大小：314 K

摘要

We propose an algorithm that given as input a full word of length , and positive integers and , outputs, if any exists, a maximal -periodic partial word contained in with the property that no two holes are within distance (so-called -valid). Our algorithm runs in time and is used for the study of repetition-freeness of partial words. Furthermore, we construct an infinite word over a five-letter alphabet that is overlap-free even after holes are inserted in arbitrary 2-valid positions, answering affirmatively a conjecture from Blanchet-Sadri, Merca艧, and Scott.