Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/111871
Название: A Quadratic Upper Bound on the Size of a Synchronizing Word in One-Cluster Automata
Авторы: Béal, M. -P.
Berlinkov, M. V.
Perrin, D.
Дата публикации: 2011
Издатель: World Scientific Pub Co Pte Lt
Библиографическое описание: 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.
Аннотация: Č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.
Ключевые слова: ČERNÝ'S CONJECTURE
ROAD COLORING PROBLEM
SYNCHRONIZED AUTOMATA
URI: http://elar.urfu.ru/handle/10995/111871
Условия доступа: info:eu-repo/semantics/openAccess
Идентификатор SCOPUS: 79952131123
Идентификатор PURE: 37846954
ISSN: 0129-0541
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-79952131123.pdf259,74 kBAdobe PDFПросмотреть/Открыть


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.