Fine and Wilf words for any periods
Fine and Wilf words for any periods
复制标题
适用于任何时期的 Fine 和 Wilf 单词
DOI：
10.1016/s0019-3577(03)90076-0
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
L. Zamboni
中科院分区：
文献类型：
--
作者：
R. Tijdeman;L. Zamboni
设w = w1... wn是一个最大长度为n的单词，在这个长度上有最大数量的不同字母，使得w有周期p1，...，pn但没有周期gcd（p1，...，pr）。我们提供了一个快速算法来计算n和w。我们表明，W是唯一确定的同构之外，它是一个回文。此外，我们给的下限和上限为n作为明确的职能，p1，. pr。对于r = 2的确切价值的n是由于罚款和威尔夫。在案件的数目不同的字母在极端词等于r的一个公式n已给予卡斯泰利，Mestilsi和Restivo的情况下r = 3和贾斯汀如果r > 3。
Let w = w1… wnbe a word of maximal length n, and with a maximal number of distinct letters for this length, such that w has periods p1, …, pnbut not period gcd(p1,…,pr). We provide a fast algorithm to compute n and w. We show that w is uniquely determined apart from isomorphism and that it is a palindrome. Furthermore we give lower and upper bounds for n as explicit functions of p1, …pr. For r = 2 the exact value of n is due to Fine and Wilf. In case the number of distinct letters in the extremal word equals r a formula for n had been given by Castelli, Mignosi and Restivo in case r = 3 and by Justin if r > 3.