Generating square-free words efficiently

详细信息    查看全文

• 作者：Arseny M. Shur¹ ; ^{Arseny.Shur@urfu.ru" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Square-free word ; Random word ; String algorithms
• 刊名：Theoretical Computer Science
• 出版年：2015
• 出版时间：11 October 2015
• 年：2015
• 卷：601
• 期：Complete
• 页码：67-72
• 全文大小：236 K

文摘

We study a simple algorithm generating square-free words from a random source. The source produces uniformly distributed random letters from a k  -ary alphabet, and the algorithm outputs a (k+1)$(k+1)$-ary square-free word. We are interested in the “conversion ratio” between the lengths of the input random word and the output square-free word. For any k≥3$k\ge 3$ we prove the expected value of this ratio to be a constant and calculate it up to an O(1/k⁵)$O(1/k^5)$ term. For the extremal case of ternary square-free words, we suggest this ratio to have a constant expectation as well and conjecture its actual value from computer experiments.