Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435712 | Theoretical Computer Science | 2015 | 6 Pages |
Abstract
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≥3k≥3 we prove the expected value of this ratio to be a constant and calculate it up to an O(1/k5)O(1/k5) 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arseny M. Shur,