Abelian repetition threshold ART(k) is the number separating fractional Abelian powers which are avoidable and unavoidable over the k-letter alphabet. The exact values of ART(k) are unknown; the lower bounds were proved in [A.V. Samsonov, A.M. Shur. On Abelian repetition threshold. RAIRO ITA, 2012] and conjectured to be tight. We present a method of study of Abelian power-free languages using random walks in prefix trees and some experimental results obtained by this method. On the base of these results, we conjecture that the lower bounds for ART(k) by Samsonov and Shur are not tight for all k except for k=5 and prove this conjecture for k=6,7,8,9,10. Namely, we show that ART(k) > (k-2)/(k-3) in all these cases.
翻译：Abelian 重复阈值 ART (k) 是将可避免和不可避免的分数位别别别别列权力分隔开来的数字。 ART (k) 的确切值未知; 下限在 [A. V. Samsonov, A. M. Shur. Abelian 重复阈值上得到证明。 RAIRO ITA, 2012], 并被推断为很紧。 我们提出了一个方法, 使用前缀树上的随机行走和通过这种方法获得的一些实验结果来研究 Abelian 无权力语言。 根据这些结果, 我们推测Samsonov 和 Shur 的ART (k) 下限除 k=5 外, 对所有 k=6, 7, 8, 9, 10。 也就是说, 我们在所有这些情况中都显示 ART (k) > (k) (k-2)/ (k-3) 。
相关内容
微信扫码咨询专知VIP会员