Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/132593
Название: | Approximating the minimum length of synchronizing words is hard |
Авторы: | Berlinkov, M. V. |
Дата публикации: | 2010 |
Издатель: | Springer Berlin Heidelberg |
Библиографическое описание: | Berlinkov, M. V. (2010). Approximating the minimum length of synchronizing words is hard. In Lecture Notes in Computer Science. Computer Science – Theory and Applications (pp. 37–47). doi:10.1007/978-3-642-13182-0_4 |
Аннотация: | 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/132593 |
Условия доступа: | info:eu-repo/semantics/openAccess All Open Access, Green |
Конференция/семинар: | 5th International Computer Science Symposium in Russia, CSR 2010 |
Дата конференции/семинара: | 16 June 2010 through 20 June 2010 |
Идентификатор SCOPUS: | 77954618795 |
Идентификатор WOS: | 000279248300004 |
Идентификатор PURE: | 37847485 |
ISSN: | 0302-9743 |
ISBN: | 978-3-64213181-3 |
DOI: | 10.1007/978-3-642-13182-0_4 |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-77954618795.pdf | 197,3 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.