06030857

j

06030857 Chiniforooshan, Ehsan Kari, Lila Xu, Zhi Pseudopower avoidance. Fundam. Inform. 114, No. 1, 55-72 (2012). 2012 Polish Mathematical Society, Warsaw; IOS Press, Amsterdam EN pseudopower pseudosquare pseudocube antimorphic involution pattern avoidance

http://iospress.metapress.com/content/h5tn757282135032/fulltext.html

Summary: 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 $\Sigma $, an antimorphic involution is a function $\theta : \Sigma ^{*} \rightarrow \Sigma ^{*}$ which is an involution, i.e., $\theta ^{2}$ equals the identity, and an antimorphism, i.e., $\theta (uv) = \theta (v)\theta (u)$, for all u $\in \Sigma ^{*}$. For a positive integer $k$, we call a word $w$ a pseudo-$k$th-power with respect to $\theta $ if it can be written as $w = u_1 \dots u_k$, where for $1 \leq i, j, \leq k$ we have either $u_i = u_j $ or $u_i = \theta (u_j)$. The classical $k$th-power of a word is a special case of a pseudo-$k$th-power, where all the repeating units are identical. We first classify the alphabets $\Sigma $ and the antimorphic involutions $\theta $ for which there exist arbitrarily long pseudo-$k$th-power-free words. Then we present efficient algorithms to test whether a finite word $w$ is pseudo-$k$th-power-free.