Periodic Partial Words and Random Bipartite Graphs

• Autorzy: Idiatulina L. A. , Shur A. M.

Identyfikatory

DOI

10.3233/FI-2014-1030

• Języki publikacji: EN

Abstrakty

EN

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

EN

random graphs; bipartite graphs; graph theory; multigraph; mathematical analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 15--31
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Idiatulina L. A.

• Ural Federal University Ekaterinburg, Russia

autor

Shur A. M.

• 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