Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111857
Title: Synchronizing Automata with Finitely Many Minimal Synchronizing Words
Authors: Pribavkina, E. V.
Rodaro, E.
Issue Date: 2011
Publisher: Elsevier BV
Citation: Pribavkina E. V. Synchronizing Automata with Finitely Many Minimal Synchronizing Words / E. V. Pribavkina, E. Rodaro // Information and Computation. — 2011. — Vol. 209. — Iss. 3. — P. 568-579.
Abstract: A synchronizing word for a given synchronizing DFA is called minimal if none of its proper factors is synchronizing. We characterize the class of synchronizing automata having only finitely many minimal synchronizing words (the class of such automata is denoted by FG). Using this characterization we prove that any such automaton possesses a synchronizing word of length at most 3n-5. We also prove that checking whether a given DFA A is in FG is co-NP-hard and provide an algorithm for this problem which is exponential in the number of states A. © 2010 Elsevier Inc. All rights reserved.
Keywords: CO-NP-HARD PROBLEMS
MINIMAL SYNCHRONIZING WORDS
SYNCHRONIZING AUTOMATA
MINIMAL SYNCHRONIZING WORDS
NP-HARD
NP-HARD PROBLEM
NUMBER OF STATE
SYNCHRONIZING AUTOMATA
COMPUTATIONAL COMPLEXITY
FINITE AUTOMATA
SYNCHRONIZATION
URI: http://hdl.handle.net/10995/111857
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 79751533959
ISSN: 0890-5401
metadata.dc.description.sponsorship: Author acknowledges support from the Federal Education Agency of Russia, Grant 2.1.1/3537, and from the Russian Foundation for Basic Research, Grants 09-01-12142 and 10-01-00793. This research was initiated with the partial support of GNSAGA during the visit of the author to the Ural State University, Russia.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-79751533959.pdf537,23 kBAdobe PDFView/Open


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