Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: pattern avoidance

Sortuj według:

Ogranicz wyniki do:

Pattern 1^j+10^j Avoiding Binary Words

100%

Bilotta S. , Merlini D. , Pergola E. , Pinzani R.

2012

tom Vol. 117, nr 1-4

35-55

In this paper we study the enumeration and the construction of particular binary words avoiding the pattern 1^j=10^j By means of the theory of Riordan arrays, we solve the enumeration problem and we give a particular succession rule, called jumping and marked succession rule, which describes the growth of such words according to their number of ones. Moreover, the problem of associating a word to a path in the generating tree obtained by the succession rule is solved by introducing an algorithm which constructs all binary words and then kills those containing the forbidden pattern.

Pseudopower Avoidance

88%

Chiniforooshan E. , Kari L. , Xu Z.

tom 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.

Pattern avoidance in partial words over a ternary alphabet

75%

Gągol A.

Annales Universitatis Mariae Curie-Skłodowska, sectio A – Mathematica

2015

tom 69

nr 1

Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with \(m\) distinct variables and of length at least \(2^m\) is avoidable over a ternary alphabet and if the length is at least \(3\cdot 2^{m-1}\) it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words – sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words.