Clusters of Repetition Roots Forming Prefix Chains
Clusters of Repetition Roots Forming Prefix Chains
复制标题
形成前缀链的重复根簇
DOI：
10.1007/978-3-031-13257-5_4
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Mercas Robert
中科院分区：
文献类型：
--
作者：
Fazekas Szilard Zsolt;Mercas Robert
我们研究了由重复根共享的公共前缀的簇（出现的起始位置的集合）大小的下界。这些集合中组成根的下界提供了不同重复次数的上界。在完全按前缀关系排序的不同平方根的情况下，已经证明，公共前缀的出现次数一定多于根的出现次数。在这里，我们进一步发展了理论，提出了将边界扩展到高于2的指数的工具，我们证明了它们是最优的，因为任何满足下界的簇大小序列都可以实现。我们还通过证明由两个重叠的根的前缀链共享的无边界前缀的下界，向任意（仅部分前缀有序）根集的边界迈进了下一步。
We investigate lower bounds on the size of clusters (sets of starting positions of occurrences) of common prefixes shared by repetition roots. Such lower bounds in terms of the constituent roots in the sets provide upper bounds on the number of distinct repetitions. In the case of distinct square roots which are totally ordered by the prefix relation it has been shown that there must be more occurrences of the common prefix than the number of roots. Here we develop the theory further by presenting the tools to extend the bounds to exponents higher than 2 and we show that they are optimal in the sense that any sequence of cluster sizes satisfying the lower bounds can be realized. We also take the next step towards the bounds on arbitrary (only partially prefix-ordered) sets of roots by proving a lower bound on unbordered prefixes shared by two overlapping prefix chains of roots.