Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: antimorphic involution

Sortuj według:

Ogranicz wyniki do:

Pseudopower Avoidance

Chiniforooshan E., Kari L., Xu Z.

Fundamenta Informaticae

2012

Vol. 114, nr 1

55-72

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.

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

Kari L., Seki S.

Fundamenta Informaticae

2010

Vol. 101, nr 3

215-236

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.