Approximating the minimum length of synchronizing words is hard
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Approximating the minimum length of synchronizing words is hard
|
|
| Автор |
Berlinkov, M. V.
|
|
| Тематика |
CONSTANT FACTORS
POLYNOMIAL-TIME ALGORITHMS SYNCHRONIZING AUTOMATA COMPUTATION THEORY |
|
| Описание |
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.
|
|
| Дата |
2024-04-24T12:38:25Z
2024-04-24T12:38:25Z 2010 |
|
| Тип |
book-chapter
Other (info:eu-repo/semantics/other) info:eu-repo/publishedVersion |
|
| Идентификатор |
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
978-3-64213181-3 0302-9743 Final All Open Access, Green https://arxiv.org/pdf/0909.3787 http://elar.urfu.ru/handle/10995/132593 10.1007/978-3-642-13182-0_4 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
|
|
| Формат |
application/pdf
|
|
| Издатель |
Springer Berlin Heidelberg
|
|
| Источник |
Lecture Notes in Computer Science
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|