ISSN: 2310-757X
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/111370Полная запись метаданных
| Поле DC | Значение | Язык |
|---|---|---|
| dc.contributor.author | Berlinkov, M. V. | en |
| dc.date.accessioned | 2022-05-12T08:17:08Z | - |
| dc.date.available | 2022-05-12T08:17:08Z | - |
| dc.date.issued | 2010 | - |
| dc.identifier.citation | 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. | en |
| dc.identifier.isbn | 3642131816 | - |
| dc.identifier.isbn | 9783642131813 | - |
| dc.identifier.issn | 0302-9743 | - |
| dc.identifier.other | All Open Access, Green | 3 |
| dc.identifier.uri | http://elar.urfu.ru/handle/10995/111370 | - |
| dc.description.abstract | 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. | en |
| dc.description.sponsorship | 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. | en |
| dc.format.mimetype | application/pdf | en |
| dc.language.iso | en | en |
| dc.publisher | Springer Berlin Heidelberg | en |
| dc.rights | info:eu-repo/semantics/openAccess | en |
| dc.source | Lect. Notes Comput. Sci. | 2 |
| dc.source | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en |
| dc.subject | CONSTANT FACTORS | en |
| dc.subject | POLYNOMIAL-TIME ALGORITHMS | en |
| dc.subject | SYNCHRONIZING AUTOMATA | en |
| dc.subject | COMPUTATION THEORY | en |
| dc.title | Approximating the Minimum Length of Synchronizing Words is Hard | en |
| dc.type | Conference Paper | en |
| dc.type | info:eu-repo/semantics/conferenceObject | en |
| dc.type | info:eu-repo/semantics/publishedVersion | en |
| dc.conference.name | 5th International Computer Science Symposium in Russia, CSR 2010 | en |
| dc.conference.date | 16 June 2010 through 20 June 2010 | - |
| dc.identifier.doi | 10.14704/WEB/V18SI04/WEB18172 | - |
| dc.identifier.scopus | 77954618795 | - |
| local.contributor.employee | Berlinkov, M.V., Department of Algebra and Discrete Mathematics, Ural State University, 620083 Ekaterinburg, Russian Federation | en |
| local.description.firstpage | 37 | - |
| local.description.lastpage | 47 | - |
| local.volume | 6072 LNCS | - |
| local.contributor.department | Department of Algebra and Discrete Mathematics, Ural State University, 620083 Ekaterinburg, Russian Federation | en |
| local.identifier.pure | 37847485 | - |
| local.identifier.eid | 2-s2.0-77954618795 | - |
| local.fund.rffi | 09-01-12142 | - |
| Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC | |
Файлы этого ресурса:
| Файл | Описание | Размер | Формат | |
|---|---|---|---|---|
| 2-s2.0-77954618795.pdf | 197,3 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.