Slowly synchronizing automata and digraphs

Ananichev, D.; Gusev, V.; Volkov, M.

doi:10.1007/978-3-642-15155-2_7

Please use this identifier to cite or link to this item: http://elar.urfu.ru/handle/10995/132598

Title:	Slowly synchronizing automata and digraphs
Authors:	Ananichev, D. Gusev, V. Volkov, M.
Issue Date:	2010
Publisher:	Springer Berlin Heidelberg
Citation:	Ananichev, D., Gusev, V., & Volkov, M. (2010). Slowly synchronizing automata and digraphs. In Lecture Notes in Computer Science. Mathematical Foundations of Computer Science 2010 (pp. 55–65). doi:10.1007/978-3-642-15155-2_7
Abstract:	We present several infinite series of synchronizing automatafor which the minimum length of reset words is close to the square of the number of states. These automata are closely related to primitive digraphs with large exponent. © 2010 Springer-Verlag.
Keywords:	INFINITE SERIES NUMBER OF STATE PRIMITIVE DIGRAPHS RESET WORDS SYNCHRONIZING AUTOMATA COMPUTER SCIENCE GRAPH THEORY AUTOMATA THEORY
URI:	http://elar.urfu.ru/handle/10995/132598
Access:	info:eu-repo/semantics/openAccess All Open Access, Green
Conference name:	35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010
Conference date:	23 August 2010 through 27 August 2010
SCOPUS ID:	78349271216
WOS ID:	000285031800007
PURE ID:	7881147
ISSN:	0302-9743
ISBN:	978-3-64215154-5
DOI:	10.1007/978-3-642-15155-2_7
metadata.dc.description.sponsorship:	2.1.1/3537; Russian Foundation for Basic Research, РФФИ: 09-01-12142, 10-01-00524 Supported by the Russian Foundation for Basic Research, grants 09-01-12142 and 10-01-00524, and by the Federal Education Agency of Russia, grant 2.1.1/3537.
Appears in Collections:	Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Files in This Item:

File	Description	Size	Format
2-s2.0-78349271216.pdf		163,39 kB	Adobe PDF	View/Open

Show full item record Google Scholar