Please use this identifier to cite or link to this item: http://elar.urfu.ru/handle/10995/112091
Title: Lower Bounds for the Length of Reset words in Eulerian Automata
Authors: Gusev, V. V.
Issue Date: 2011
Publisher: Springer Berlin Heidelberg
Citation: Gusev V. V. Lower Bounds for the Length of Reset words in Eulerian Automata / V. V. Gusev // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2011. — Vol. 6945 LNCS. — P. 180-190.
Abstract: For each odd n ≥ 5 we present a synchronizing Eulerian automaton with n states for which the minimum length of reset words is equal to n 2-3n+4/2. We also discuss various connections between the reset threshold of a synchronizing automaton and a sequence of reachability properties in its underlying graph. © 2011 Springer-Verlag.
Keywords: EULERIAN
LOWER BOUNDS
REACHABILITY
RESET WORDS
SYNCHRONIZING AUTOMATA
underLYING GRAPHS
AUTOMATA THEORY
URI: http://elar.urfu.ru/handle/10995/112091
Access: info:eu-repo/semantics/openAccess
Conference name: 5th International Workshop on Reachability Problems, RP 2011
Conference date: 28 September 2011 through 30 September 2011
SCOPUS ID: 80053330436
WOS ID: 000306294400016
PURE ID: 37903127
ISSN: 0302-9743
ISBN: 9783642242878
metadata.dc.description.sponsorship: Supported by the Russian Foundation for Basic Research, grant 10-01-00524, and by the Federal Education Agency of Russia, grant 2.1.1/13995.
Appears in Collections:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-80053330436.pdf208,37 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.