ISSN: 2310-757X
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/111370| Название: | Approximating the Minimum Length of Synchronizing Words is Hard |
| Авторы: | Berlinkov, M. V. |
| Дата публикации: | 2010 |
| Издатель: | Springer Berlin Heidelberg |
| Библиографическое описание: | Berlinkov M. V. Approximating the Minimum Length of Synchronizing Words is Hard / M. V. Berlinkov. — DOI 10.14704/WEB/V18SI04/WEB18172 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2010. — Vol. 6072 LNCS. — P. 37-47. |
| Аннотация: | We prove that, unless P = NP, no polynomial-time algorithm can approximate the minimum length of synchronizing words for a given synchronizing automaton within a constant factor. © 2010 Springer-Verlag. |
| Ключевые слова: | CONSTANT FACTORS POLYNOMIAL-TIME ALGORITHMS SYNCHRONIZING AUTOMATA COMPUTATION THEORY |
| URI: | http://elar.urfu.ru/handle/10995/111370 |
| Условия доступа: | info:eu-repo/semantics/openAccess |
| Конференция/семинар: | 5th International Computer Science Symposium in Russia, CSR 2010 |
| Дата конференции/семинара: | 16 June 2010 through 20 June 2010 |
| Идентификатор SCOPUS: | 77954618795 |
| Идентификатор PURE: | 37847485 |
| ISSN: | 0302-9743 |
| ISBN: | 3642131816 9783642131813 |
| DOI: | 10.14704/WEB/V18SI04/WEB18172 |
| Сведения о поддержке: | The author acknowledges support from the Federal Education Agency of Russia, grant 2.1.1/3537, and from the Russian Foundation for Basic Research, grant 09-01-12142. |
| Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 2-s2.0-77954618795.pdf | 197,3 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.