Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
15--31
Opis fizyczny
Bibliogr. 16 poz., rys., tab.
Twórcy
autor
- Ural Federal University Ekaterinburg, Russia
autor
- Ural Federal University Ekaterinburg, Russia
Bibliografia
- [1] Berstel, J., Boasson, L.: Partial words and a theorem of Fine and Wilf, Theoret. Comput. Sci., 218, 1999, 135–141.
- [2] Blanchet-Sadri, F., Bal, D., Sisodia, G.: Graph connectivity, partial words, and a theorem of Fine and Wilf, Information and Computation, 206, 2008, 676–693.
- [3] Bollobás, B.: Random Graphs, second edition, Cambridge University Press, 2001.
- [4] Erdős, P., Rényi, A.: On the evolution of random graphs, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, Ser. A, 5, 1960, 17–61.
- [5] Fine, N. J., Wilf, H. S.: Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc., 16, 1965, 109–114.
- [6] Fischer, M., Paterson, M.: String matching and other products, SIAM-AMS Proceedings, 7, 1974, 113–125.
- [7] Gamzova, Y. V.: Statistical laws for interaction of periods in partial words, Discrete analysis and operation research. Ser. 1, 11(4), 2004, 20–35, In Russian.
- [8] Halava, V., Harju, T., Kärki, T.: The theorem of Fine andWilf for relational periods, RAIRO Inform. Théor. App., 43, 2009, 209–220.
- [9] Kalugin, I. B.: The number of components of a random bipartite graph, Discrete Math. Appl., 1(3), 1991, 289–299.
- [10] Kolchin, V. F., Sevast’yanov, B. A., Chistyakov, V. P.: Random allocations, Scripta Series in Mathematics, V. H. Winston & Sons, Washington, DC, 1978.
- [11] Kovalenko, I. N.: The structure of random directed graphs, Theory Probab. Math. Statist., 6, 1975, 83–92.
- [12] Muthukrishnan, S., Palem, K.: Non-standard stringology: algorithms and complexity, Proc. 26th Annual ACM Symposium on Theory of Computing (STOC’94), ACM, New York, 1994.
- [13] Ruciński, A.: The r-connectedness of k-partite randomgraph, Bull. Acad. Polon. Sci. Sér. Sci. Math., 29(7-8), 1981, 321–330.
- [14] Saltykov, A. I.: The number of components in a random bipartite graph, Discrete Math. Appl., 5(6), 1995, 515–523.
- [15] Shur, A. M., Gamzova, Y. V.: Partial words and the interaction property of periods, Izv. Ross. Akad. Nauk Ser. Mat., 68(2), 2004, 191–214, In Russian. English translation in Izv. Math. 68 (2004), 405–428.
- [16] Shur, A. M., Konovalova, Y. V.: On the periods of partial words, Proc. 26th Int. Conf. Mathematical foundations of computer science. MFCS 2001, 2136, Springer, Berlin, 2001
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-79bda288-4a4b-4544-8f88-4640375db576