1. Электронный научный архив УрФУ
  2. 00. Общеуниверситетские коллекции
  3. Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/111857
Полная запись метаданных
Поле DCЗначениеЯзык
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://elar.urfu.ru/handle/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-
dc.identifier.wos000287382300021-
local.contributor.departmentUral State University, 620083 Ekaterinburg, Russian Federation; Politecnico di Milano, 20133 Milano, Italyen
local.identifier.pure37841531-
local.identifier.eid2-s2.0-79751533959-
local.fund.rffi09-01-12142-
local.fund.rffi10-01-00793-
local.identifier.wosWOS:000287382300021-
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-79751533959.pdf537,23 kBAdobe PDFПросмотреть/Открыть
Показать базовое описание ресурса Статистика


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.