Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://hdl.handle.net/10995/102482
Название: Approximating the Minimum Length of Synchronizing Words Is Hard
Авторы: Berlinkov, M. V.
Дата публикации: 2014
Библиографическое описание: Berlinkov M. V. Approximating the Minimum Length of Synchronizing Words Is Hard / M. V. Berlinkov. — DOI 10.1007/s00224-013-9511-y // Theory of Computing Systems. — 2014. — Vol. 54. — Iss. 2. — P. 211-223.
Аннотация: We prove that, unless P=NP, no polynomial-time algorithm can approximate the minimum length of reset words for a given synchronizing automaton within a constant factor. © 2013 Springer Science+Business Media New York.
Ключевые слова: POLYNOMIAL-TIME APPROXIMATION
SYNCHRONIZING AUTOMATA
URI: http://hdl.handle.net/10995/102482
Условия доступа: info:eu-repo/semantics/openAccess
Идентификатор SCOPUS: 84895057541
Идентификатор PURE: 336062
2a1af4f8-c31b-4773-a54e-12357bdc2b1b
ISSN: 14324350
DOI: 10.1007/s00224-013-9511-y
Располагается в коллекциях:Научные публикации, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-84895057541.pdf197,3 kBAdobe PDFПросмотреть/Открыть


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