Periodicity and repetitions in parameterized strings
Periodicity and repetitions in parameterized strings
复制标题
参数化字符串中的周期性和重复性
DOI：
10.1016/j.dam.2006.11.017
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
R. Giancarlo
中科院分区：
文献类型：
--
作者：
A. Apostolico;R. Giancarlo
弦数学理论中最美丽和最有用的概念之一是周期，即给定弦的初始片段可以通过定期重复自身来生成该弦。周期具有优雅的数学结构和丰富的应用[F. Mignosi 和 A. Restivo，周期性，单词代数组合，见：M. Lothaire（编辑），剑桥大学出版社，剑桥，第 237-274 页，2002 年]。在他们的理论的核心，有两个周期性引理：一个是林登和舒岑伯格提出的[自由群中的方程 aM=bNcP，密歇根数学。 J. 9 (1962) 289–298]，称为弱版本，另一个归因于 Fine 和 Wilf [周期函数的唯一性定理，Proc。阿米尔。数学。苏克。 16（1965）109-114]。在本文中，我们研究了周期性的概念以及与参数化字符串密切相关的重复概念，如 Baker [参数化模式匹配：算法和应用程序，J. Comput。系统科学。 52（1）（1996）28-42；字符串中的参数化重复：算法和软件维护应用，SIAM J. Comput。 26（5）（1997）1343-1362]。在这样的字符串中，符号的成对匹配或“等价”的概念比通常的概念更宽松，因为它依赖于符号的某种映射，而不是同一性。尝试扩展周期和周期性的概念以包含参数化字符串似乎很自然。然而，据我们所知，以前没有在这个方向上进行过尝试。我们的初步调查结果如下。对于周期性，我们得到（a）参数化字符串的周期性引理的弱版本的推广，表明引入周期性的两个映射必须可交换； (b) 证明 Fine 和 Wilf 的引理类似 [周期函数的唯一性定理，Proc.阿米尔。数学。苏克。 16 (1965) 109–114] 不能适用于参数化字符串，即使映射导致周期性“通勤”，在某种意义上将在下面指定； (c) 证明至少由三个字母组成的字母表上的参数化字符串可能具有一组与任何相同长度的二进制字符串不同的句点，从而对 Guibas 和 Odlyzko 的经典结果进行参数化模拟[字符串重叠、模式匹配和非传递游戏，J. Combin。理论系列。 A 30 (1981) 183–208] 不能成立。我们还推导了表征参数化重复的必要和充分条件，这些重复是长度至少是周期长度两倍的模式，并展示了根的概念与标准情况有何不同，并强调了对扩展先前用于字符串搜索、重复检测等的算法标准的一些影响。最后，作为我们主要结果的推论，我们还表明，在周期性和重复性方面，二进制参数化字符串的行为与非参数化字符串的行为大致相同，而字符串与至少三个符号的字母表之间存在显着差异。
One of the most beautiful and useful notions in the Mathematical Theory of Strings is that of a Period, i.e., an initial piece of a given string that can generate that string by repeating itself at regular intervals. Periods have an elegant mathematical structure and a wealth of applications [F. Mignosi and A. Restivo, Periodicity, Algebraic Combinatorics on Words, in: M. Lothaire (Ed.), Cambridge University Press, Cambridge, pp. 237–274, 2002]. At the hearth of their theory, there are two Periodicity Lemmas: one due to Lyndon and Schutzenberger [The equation aM=bNcPin a free group, Michigan Math. J. 9 (1962) 289–298], referred to as the Weak Version, and the other due to Fine and Wilf [Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965) 109–114]. In this paper, we investigate the notion of periodicity and the closely related one of repetition in connection with parameterized strings as introduced by Baker [Parameterized pattern matching: algorithms and applications, J. Comput. System Sci. 52(1) (1996) 28–42; Parameterized duplication in strings: algorithms and an application to software maintenance, SIAM J. Comput. 26(5) (1997) 1343–1362]. In such strings, the notion of pairwise match or “equivalence” of symbols is more relaxed than the usual one, in that it rests on some mapping, rather than identity, of symbols. It seems natural to try and extend notions of periods and periodicities to encompass parameterized strings. However, we know of no previous attempt in this direction. Our preliminary investigation yields results as follows. For periodicity, we get (a) a generalization of the Weak Version of the Periodicity Lemma for parameterized strings, showing that it is essential that the two mappings inducing the periodicity must commute; (b) a proof that an analogous of the Lemma by Fine and Wilf [Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965) 109–114] cannot hold for parameterized strings, even if the mappings inducing the periodicity “commute”, in a sense to be specified below; (c) a proof that parameterized strings over an alphabet of at least three letters may have a set of periods which differ from those of any binary string of the same length—whereby the parameterized analog of a classic result by Guibas and Odlyzko [String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30 (1981) 183–208] cannot hold. We also derive necessary and sufficient conditions characterizing parameterized repetitions, which are patterns of length at least twice that of the period, and show how the notion of root differs from the standard case, and highlight some of the implications on extending algorithmic criteria previously adopted for string searching, detection of repetitions and the likes. Finally, as a corollary of our main results, we also show that binary parameterized strings behave much in the same way as non-parameterized ones with respect to periodicity and repetitions, while there is a substantial difference for strings over alphabets of at least three symbols.