An Improved Bound for an Extension of Fine and Wilf's Theorem and Its Optimality

• Autorzy: Kari L. , Seki S.
• Języki publikacji: EN

Abstrakty

EN

Considering two DNA molecules which are Watson-Crick (WK) complementary to each other "equivalent" with respect to the information they encode enables us to extend the classical notions of repetition, period, and power. WK-complementarity has been modelled mathematically by an antimorphic involution Θ i.e., a function Θ such that Θ(xy) = Θ(y)Θ(x) for any x, y ∈Σ and Θ^2 is the identity. The WK-complementarity being thus modelled, any word which is a repetition of u and Θ(u) such as uu, uΘ(u)u, and uΘ(u)Θ(u)Θ(u) can be regarded repetitive in this sense, and hence, called a -power of u. Taking the notion of Θ-power into account, the Fine and Wilf's theorem was extended as "given an antimorphic involution Θ and words u, v, if aΘ-power of u and a Θ-power of v have a common prefix of length at least b(|u|, |v|) = 2|u| + |v| - gcd(|u|, |v|), then u and v are Θ-powers of a same word." In this paper, we obtain an improved bound b'(|u|, |v|) = b(|u|, |v|) - .gcd(|u|, |v|)/2.. Then we show all the cases when this bound is optimal by providing all the pairs of words (u, v) such that they are not Θ-powers of a same word, but one can construct a Θ-power of u and a Θ-power of v whose maximal common prefix is of length equal to b'(|u|, |v|)-1. Furthermore, we characterize such words in terms of Sturmian words.

Słowa kluczowe

EN

extended Fine and Wilf's theorem; pseudo-primitivity; antimorphic involution; optimal bound; Sturmian word

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 101, nr 3
• Strony: 215--236
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Kari L.

autor

Seki S.

• Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada,

Bibliografia

• [1] Berstel, J., Boasson, L.: Partial Words and a Theorem of Fine and Wilf, Theoretical Computer Science, 218(1), 1999, 135-141.
• [2] Blanchet-Sadri, F., Hegstrom, R. A.: Partial Words and a Theorem of Fine and Wilf revisted, Theoretical Computer Science, 270, 2002, 401-419.
• [3] Castelli, M. G., Mignosi, F., Restivo, A.: Fine andWilf's Theorem for Three Periods and a Generalization of Sturmian Words, Theoretical Computer Science, 218(1), 1999, 83-94.
• [4] Cautis, S., Mignosi, F., Shallit, J.,Wang, M., Yazdani, S.: Periodicity,Morphisms, and Matrices, Theoretical Computer Science, 295, 2003, 107-121.
• [5] Choffrut, C., Karhumäki, J.: Combinatorics of Words, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), vol. 1, Springer-Verlag, Berlin-Heidelberg-New York, 1997, 329-438.
• [6] Constantinescu, S., Ilie, L.: Generalized Fine andWilf's theoremfor arbitrary number of periods, Theoretical Computer Science, 339(1), 2005, 49-60.
• [7] Constantinescu, S., Ilie, L.: Fine and Wilf's Theorem for Abelian Periods, Bulletin of the EATCS, 89, June 2006, 167-170.
• [8] Czeizler, E., Czeizler, E., Kari, L., Seki, S.: An Extension of the Lyndon Sch ützenberger Result to Pseudoperiodic Words, Proc. DLT09 (V. Diekert, D. Nowotka, Eds.), LNCS 5583, Springer-Verlag, Berlin, 2009.
• [9] Czeizler, E., Kari, L., Seki, S.: On a Special Class of PrimitiveWords, Theoretical Computer Science, 411(3), 2010, 617-630.
• [10] Fine, N. J., Wilf, H. S.: Uniqueness Theorem for Periodic Functions, Proceedings of the American Mathematical Society, 16(1), February 1965, 109-114.
• [11] Justin, J.: On a Paper by Castelli, Mignosi, Restivo, RAIRO - Theoretical Informatics and Applications, 34, 2000, 373-377.
• [12] Kari, L., Masson, B., Seki, S.: Properties of Pseudo-PrimitiveWords and Their Applications, 2009, Submitted, available at http://hal.archives-ouvertes.fr/hal-00458695/fr/.
• [13] de Luca, A., De Luca, A.: Pseudopalindrome Closure Operators in Free Monoids, Theoretical Computer Science, 362, 2006, 282-300.
• [14] de Luca, A.,Mignosi, F.: Some Combinatorial Properties of SturmianWords, Theoretical Computer Science, 136, 1994, 361-385.
• [15] Mignosi, F., Restivo, A., Silva, P. V.: On Fine and Wilf's Theorem for Bidimensional Words, Theoretical Computer Science, 292, 2003, 245-262.