摘要
For a rational number r such that 1<r≤2, an undirected r-power is a word of the form xyx′, where the word x is nonempty, the word x′ is in {x,xR}, and we have |xyx′|/|xy|=r. The undirected repetition threshold for k letters, denoted URT(k), is the infimum of the set of all r such that undirected r-powers are avoidable on k letters. We first demonstrate that URT(3)=74. Then we show that URT(k)≥k−1k−2 for all k≥4. We conjecture that URT(k)=k−1k−2 for all k≥4, and we confirm this conjecture for k∈{4,5,…,21}. We then consider related problems in pattern avoidance; in particular, we find the undirected avoidability index of every binary pattern. This is an extended version of a paper presented at WORDS 2019, and it contains new and improved results.
摘要译文
对于Rational Number R这样1
James D. Currie; Lucas Mol. The undirected repetition threshold and undirected pattern avoidance[J]. Theoretical Computer Science, 2021,866