Periodic Partial Words and Random Bipartite Graphs / Idiatulina Lidia A.,Shur Arseny M. // FUNDAMENTA INFORMATICAE. - 2014. - V. 132, l. 1. - P. 15-31.

ISSN/EISSN:

0169-2968 / 1875-8681

Type:

Article; Proceedings Paper

Abstract:

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.

Author keywords:

THEOREM; FINE; WILF

DOI:

10.3233/FI-2014-1030

Web of Science ID:

ISI:000336407600003

Соавторы в МНС:

—

Другие поля

Поле	Значение
Note	Russian-Finnish Symposium on Discrete Mathematics, Turku, FINLAND, SEP 25-28, 2012
Publisher	IOS PRESS
Address	NIEUWE HEMWEG 6B, 1013 BG AMSTERDAM, NETHERLANDS
Language	English
EISSN	1875-8681
Keywords-Plus	THEOREM; FINE; WILF
Research-Areas	Computer Science; Mathematics
Web-of-Science-Categories	Computer Science, Software Engineering; Mathematics, Applied
Author-Email	lidiatulina@gmail.com arseny.shur@usu.ru
Number-of-Cited-References	17
Journal-ISO	Fundam. Inform.
Doc-Delivery-Number	AH8SD