首页 | 本学科首页   官方微博 | 高级检索  
     


Abelian repetitions in partial words
Authors:F. Blanchet-Sadri  Sean SimmonsDimin Xu
Affiliation:a Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402-6170, USA
b Department of Mathematics, The University of Texas at Austin, 1 University Station C1200, Austin, TX 78712-0233, USA
c Department of Mathematics, Bard College, 30 Campus Road, Annandale-on-Hudson, NY 12504, USA
Abstract:We study abelian repetitions in partial words, or sequences that may contain some unknown positions or holes. First, we look at the avoidance of abelian pth powers in infinite partial words, where p>2, extending recent results regarding the case where p=2. We investigate, for a given p, the smallest alphabet size needed to construct an infinite partial word with finitely or infinitely many holes that avoids abelian pth powers. We construct in particular an infinite binary partial word with infinitely many holes that avoids 6th powers. Then we show, in a number of cases, that the number of abelian p-free partial words of length n with h holes over a given alphabet grows exponentially as n increases. Finally, we prove that we cannot avoid abelian pth powers under arbitrary insertion of holes in an infinite word.
Keywords:68R15   05A05
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号