ISSN: 2310-757X
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/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://elar.urfu.ru/handle/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.pdf | 197,3 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.