Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111857
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPribavkina, E. V.en
dc.contributor.authorRodaro, E.en
dc.date.accessioned2022-05-12T08:24:07Z-
dc.date.available2022-05-12T08:24:07Z-
dc.date.issued2011-
dc.identifier.citationPribavkina 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.en
dc.identifier.issn0890-5401-
dc.identifier.otherAll Open Access, Bronze3
dc.identifier.urihttp://hdl.handle.net/10995/111857-
dc.description.abstractA 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.en
dc.description.sponsorshipAuthor 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.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherElsevier BVen
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceInf Comput2
dc.sourceInformation and Computationen
dc.subjectCO-NP-HARD PROBLEMSen
dc.subjectMINIMAL SYNCHRONIZING WORDSen
dc.subjectSYNCHRONIZING AUTOMATAen
dc.subjectMINIMAL SYNCHRONIZING WORDSen
dc.subjectNP-HARDen
dc.subjectNP-HARD PROBLEMen
dc.subjectNUMBER OF STATEen
dc.subjectSYNCHRONIZING AUTOMATAen
dc.subjectCOMPUTATIONAL COMPLEXITYen
dc.subjectFINITE AUTOMATAen
dc.subjectSYNCHRONIZATIONen
dc.titleSynchronizing Automata with Finitely Many Minimal Synchronizing Wordsen
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.scopus79751533959-
local.contributor.employeePribavkina, E.V., Ural State University, 620083 Ekaterinburg, Russian Federation; Rodaro, E., Politecnico di Milano, 20133 Milano, Italyen
local.description.firstpage568-
local.description.lastpage579-
local.issue3-
local.volume209-
local.contributor.departmentUral State University, 620083 Ekaterinburg, Russian Federation; Politecnico di Milano, 20133 Milano, Italyen
local.identifier.eid2-s2.0-79751533959-
local.fund.rffi09-01-12142
local.fund.rffi10-01-00793
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.