Pseudopower Avoidance

Article type: Research Article

Authors: Chiniforooshan, Ehsan | Kari, Lila | Xu, Zhi

Affiliations: Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7, [email protected], [email protected], [email protected]

Note: [] The authors wish to thank Shinnosuke Seki and Lucian Ilie for comments on the draft of this paper. This research was supported by Natural Sciences and Engineering Research Council of Canada Discovery Grant R2824A01, and Canada Research Chair Award to Lila Kari.

Note: [] Address for correspondence: Department of Computer Science, The University of Western Ontario, London, Ontario, Canada N6A 5B7 The authors wish to thank Shinnosuke Seki and Lucian Ilie for comments on the draft of this paper. This research was supported by Natural Sciences and Engineering Research Council of Canada Discovery Grant R2824A01, and Canada Research Chair Award to Lila Kari.

Note: [] The authors wish to thank Shinnosuke Seki and Lucian Ilie for comments on the draft of this paper. This research was supported by Natural Sciences and Engineering Research Council of Canada Discovery Grant R2824A01, and Canada Research Chair Award to Lila Kari.

Abstract: 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 the Watson-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}, wherein A 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 Σ, 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.

Keywords: pseudopower, pseudosquare, pseudocube, antimorphic involution, pattern avoidance

DOI: 10.3233/FI-2011-617

Journal: Fundamenta Informaticae, vol. 114, no. 1, pp. 55-72, 2012