Uniformly Growing k-TH Power-Free Homomorphisms
Uniformly Growing k-TH Power-Free Homomorphisms
复制标题
均匀增长的 k-TH 无幂同态
DOI：
10.1016/0304-3975(88)90009-6
复制
发表时间：
1988
期刊：
影响因子：
--
通讯作者：
F. Brandenburg
中科院分区：
文献类型：
--
作者：
F. Brandenburg
如果一个字符串没有非空子字符串，则称它为无幂的。对所有非负有理数，研究了k次方无幂的弦和k次幂无次同态，并引入了最短一致增长的无平方(k=2)和无立方体(k=3)同态到三个字母和两个字母的最小字母表的映射.结果表明，在这些字母表上存在指数级的每种长度的无平方和无立方体的弦。将n个字母的无幂同态提高到重复阈值RT(N)，证明了各种无幂同态是不存在的。
A string is calledkth power-free, if it does not havexkas a nonempty substring. For all nonnegative rational numbersk,kth power-free strings andkth power-free homomorphisms are investigated and the shortest uniformly growing square-free (k=2) and cube-free (k=3) homomorphisms mapping into least alphabets with three and two-letters are introduced. It is shown that there exist exponentially many square-free and cube-free strings of each length over these alphabets. Sharpening thekth power-freeness to the repetitive threshold RT(n) ofnletter alphabets, we provide arguments for the nonexistence of various RT(n)th power-free homomorphisms.