Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2010

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: optimal bound

Sortuj według:

Ogranicz wyniki do:

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.