Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/111871
Полная запись метаданных
Поле DC | Значение | Язык |
---|---|---|
dc.contributor.author | Béal, M. -P. | en |
dc.contributor.author | Berlinkov, M. V. | en |
dc.contributor.author | Perrin, D. | en |
dc.date.accessioned | 2022-05-12T08:24:22Z | - |
dc.date.available | 2022-05-12T08:24:22Z | - |
dc.date.issued | 2011 | - |
dc.identifier.citation | Béal M. -P. A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata / M. -P. Béal, M. V. Berlinkov, D. Perrin // International Journal of Foundations of Computer Science. — 2011. — Vol. 22. — Iss. 2. — P. 277-288. | en |
dc.identifier.issn | 0129-0541 | - |
dc.identifier.other | All Open Access, Green | 3 |
dc.identifier.uri | http://elar.urfu.ru/handle/10995/111871 | - |
dc.description.abstract | Černý's conjecture asserts the existence of a synchronizing word of length at most (n - 1)2 for any synchronized n-state deterministic automaton. We prove a quadratic upper bound on the length of a synchronizing word for any synchronized n-state deterministic automaton satisfying the following additional property: there is a letter a such that for any pair of states p, q, one has p·ar = q·as for some integers r, s (for a state p and a word w, we denote by p·w the state reached from p by the path labeled w). As a consequence, we show that for any finite synchronized prefix code with an n-state decoder, there is a synchronizing word of length O(n2). This applies in particular to Huffman codes. © 2011 World Scientific Publishing Company. | en |
dc.format.mimetype | application/pdf | en |
dc.language.iso | en | en |
dc.publisher | World Scientific Pub Co Pte Lt | en |
dc.rights | info:eu-repo/semantics/openAccess | en |
dc.source | Int. J. Found. Comput. Sci. | 2 |
dc.source | International Journal of Foundations of Computer Science | en |
dc.subject | ČERNÝ'S CONJECTURE | en |
dc.subject | ROAD COLORING PROBLEM | en |
dc.subject | SYNCHRONIZED AUTOMATA | en |
dc.title | A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata | en |
dc.type | Conference Paper | en |
dc.type | info:eu-repo/semantics/conferenceObject | en |
dc.type | info:eu-repo/semantics/submittedVersion | en |
dc.identifier.scopus | 79952131123 | - |
local.contributor.employee | Béal, M.-P., Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, CNRS, 77454 Marne-la-Vallée Cedex 2, France; Berlinkov, M.V., Department of Algebra and Discrete Mathematics, Ural State University, 620083 Ekaterinburg, Russian Federation; Perrin, D., Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, CNRS, 77454 Marne-la-Vallée Cedex 2, France | en |
local.description.firstpage | 277 | - |
local.description.lastpage | 288 | - |
local.issue | 2 | - |
local.volume | 22 | - |
local.contributor.department | Université Paris-Est, Laboratoire d'Informatique Gaspard-Monge, CNRS, 77454 Marne-la-Vallée Cedex 2, France; Department of Algebra and Discrete Mathematics, Ural State University, 620083 Ekaterinburg, Russian Federation | en |
local.identifier.pure | 37846954 | - |
local.identifier.eid | 2-s2.0-79952131123 | - |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-79952131123.pdf | 259,74 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.