Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The Number of Distinct Subpalindromes in Random Words

Rubinchik M., Shur A. M.

Fundamenta Informaticae

2016

Vol. 145, nr 3

371--384

We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation,Θ(√n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit limn→∞ E(n, k)=√n does not exist for any κ ≥ 2, lim infn→∞ E(n; k)=√n =Θ(1), and lim supn→∞ E(n; k)=√n = Θ(√k). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.

Periodic Partial Words and Random Bipartite Graphs

Idiatulina L. A., Shur A. M.

Fundamenta Informaticae

2014

Vol. 132, nr 1

15--31

The interaction property (or the Fine-Wilf property) for periodic partial words is studied. Partial words with two periods are represented by bipartite graphs and the interaction property is related to the edge connectedness property of these graphs. Threshold functions for the edge connectedness of random bipartite graphs and multigraphs are found. As a corollary, the interaction property is described in probabilistic terms.