Pseudopower Avoidance

• Autorzy: Chiniforooshan E. , Kari L. , Xu Z.
• Języki publikacji: EN

Abstrakty

EN

Repetition avoidance has been intensely studied since Thue’s work in the early 1900's. In this paper, we consider another type of repetition, called pseudopower, inspired by theWatson-Crick complementarity property of DNA sequences. A DNA single strand can be viewed as a string over the four-letter alphabet {A,C,G, T }, whereinA is the complement of T , while C is the complement of G. Such a DNA single strand will bind to a reverse complement DNA single strand, called its Watson-Crick complement, to form a helical double-stranded DNA molecule. The Watson-Crick complement of a DNA strand is deducible from, and thus informationally equivalent to, the original strand. We use this fact to generalize the notion of the power of a word by relaxing the meaning of "sameness" to include the image through an antimorphic involution, the model of DNA Watson- Crick complementarity. Given a finite alphabet &Sigma: an antimorphic involution is a function Θ : Σ*→Σ* which is an involution, i.e., Θ2 equals the identity, and an antimorphism, i.e., Θ(uv) = Θ(v)Θ(u), for all u∈Σ* For a positive integer k, we call a word w a pseudo-kth-power with respect to Θ if it can be written as w = u1 . . . uk, where for 1 ≤ i, j ≤ k we have either ui = uj or ui = Θ(uj). The classical kth-power of a word is a special case of a pseudo-kth-power, where all the repeating units are identical. We first classify the alphabets Σ and the antimorphic involutions . for which there exist arbitrarily long pseudo-kth-power-free words. Then we present efficient algorithms to test whether a finite word w is pseudo-kth-power-free.

Słowa kluczowe

EN

pseudopower; pseudosquare; pseudocube; antimorphic involution; pattern avoidance

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 114, nr 1
• Strony: 55--72
• Opis fizyczny: Bibliogr. 25 poz., tab.

Twórcy

autor

Chiniforooshan E.

autor

Kari L.

autor

Xu Z.

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

Bibliografia

• [1] Anne, V., Zamboni, L., Zorca, I.: Palindromes and pseudo-palindromes in Episturmian and pseudopalindromic infinite words, Publications du LACIM, Proc. of Words 2005 (S. Brlek, C. Reutenauer, Eds.), 36, 2005.
• [2] Aršon, S. E.: Démonstration de l'existence des suites asymétriques infinies, Mat. Sb., (N. S.) 2(3), 1937, 769-779.
• [3] Berstel, J.: Axel Thue's papers on repetitions in words: a translation, Number 20 in Publications du Laboratoire de Combinatoire et d'InformatiqueMathématique, Université du Québec `a Montréal, 1995.
• [4] Crochemore, M.: Recherche linéaire d'un carré dans un mot, Comptes Rendus Acad. Sci. Paris Sér. I, 296, 1983, 781-784.
• [5] Czeizler, E., Kari, L., Seki, S.: On a special class of primitive words, Theoret. Comput. Sci., 411(3), 2010, 617-630.
• [6] de Luca, A., De Luca, A.: Pseudopalindrome closure operators in free monoids, Theoret. Comput. Sci., 362, 2006, 282-300.
• [7] Dekking, F.: Strongly non-repetitive sequences and progression-free sets, J. Combin. Theory Ser. A, 27(2), 1979, 181-185.
• [8] Erdös, P.: Some unsolved problems, Michigan Math. J., 4(3), 1957, 291-300.
• [9] Evdokimov, A. A.: Strongly asymmetric sequences generated by a finite number of symbols, Dokl. Akad. Nauk. SSSR, 179, 1968, 1268-1271.
• [10] Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, 1997.
• [11] Kari, L., Mahalingam, K.: Watson-Crick palindromes in DNA computing, Nat. Comput., 9(2), 2010, 297-316.
• [12] Keränen, V.: Abelian squares are avoidable on 4 letters, Proc. 19th Int'l Conf. on Automata, Lang., and Progr. (ICALP '92) (W. Kuich, Ed.), 1992.
• [13] Keränen, V.: A powerful abelian square-free substitution over 4 letters, Theoret. Comput. Sci., 410, 2009, 38-40.
• [14] Kolpakov, R., Kucherov, G.: Finding maximal repetitions in a word in linear time, Proc. 40th Ann. Symp. Found. Comput. Sci. (FOCS '99), 1999.
• [15] Kosaraju, S. R.: Computation of squares in a string, Proc. 5th Ann. Symp. Combinat. Pattern Matching (CPM 1994) (M. Crochemore, D. Gusfield, Eds.), 1994.
• [16] Leech, J.: A problem on strings of beads, Math. Gaz., 41(338), 1957, 277-278.
• [17] Main, M., Lorentz, R.: Linear time recognition of square free strings, in: Combinat. Algorithms on Words (A. Apostolico, Z. Galil, Eds.), Springer, 1985, 272-278.
• [18] Mirkin, S.: Expandable DNA repeats and human disease, Nature, 447(7147), 2007, 932-940.
• [19] Morse, H.: Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc., 22(1), 1921, 84-100.
• [20] Pleasants, P.: Non-repetitive sequences, Math. Proc. Cambridge Philos. Soc., 68(2), 1970, 267-274.
• [21] Shallit, J.: Simultaneous avoidance of large squares and fractional powers in infinite binary words, Int'l. J. Found. Comput. Sci., 15, 2004, 317-327.
• [22] Thue, A.: ¨Uber unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat.-Nat. Kl., (7), 1906, 1-22.
• [23] Thue, A.: ¨Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat.- Nat. Kl., (1), 1912, 1-67.
• [24] Xu, Z.: A minimal periods algorithm with applications, Proc. 21st Ann. Symp. Combinat. Pattern Matching (CPM 2010) (A. Amir, L. Parida, Eds.), 2010.
• [25] Yu, X.: A new solution for Thue's problem, Inform. Process. Lett., 54, 1995, 187-191