Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/10995/102347
Title: | Algebraic synchronization criterion and computing reset words |
Authors: | Berlinkov, M. SzykuŁa, M. |
Issue Date: | 2015 |
Publisher: | Springer Verlag |
Citation: | Berlinkov M. Algebraic synchronization criterion and computing reset words / M. Berlinkov, M. SzykuŁa. — DOI 10.1007/978-3-662-48057-1_8 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2015. — Vol. 9234. — P. 103-115. |
Abstract: | We refine results about relations between Markov chains and synchronizing automata. We express the condition that an automaton is synchronizing in terms of linear algebra, and obtain upper bounds for the reset thresholds of automata with a short word of a small rank. The results are applied to make several improvements in the area. We improve the best general upper bound for reset thresholds of finite prefix codes (Huffman codes): we show that an n-state synchronizing decoder has a reset word of length at most O(n log3 n). Also, we prove the Černý conjecture for n-state automata with a letter of rank at most 3√6n-6. In another corollary, based on the recent results of Nicaud, we show that the probability that the Čern conjecture does not hold for a random synchronizing binary automaton is exponentially small in terms of the number of states. It follows that the expected value of the reset threshold of an n-state random synchronizing binary automaton is at most n7/4+o(1). Moreover, reset words of the lengths within our bounds are computable in polynomial time. We present suitable algorithms for this task for various classes of automata for which our results can be applied. These include (quasi-)one-cluster and (quasi-)Eulerian automata. © Springer-Verlag Berlin Heidelberg 2015. |
Keywords: | ALGEBRA AUTOMATA THEORY BINS LINEAR ALGEBRA MARKOV PROCESSES POLYNOMIAL APPROXIMATION BINARY AUTOMATON EXPECTED VALUES FINITE PREFIX GENERAL UPPER BOUND HUFFMAN CODE NUMBER OF STATE POLYNOMIAL-TIME SYNCHRONIZING AUTOMATA SYNCHRONIZATION |
URI: | http://elar.urfu.ru/handle/10995/102347 |
Access: | info:eu-repo/semantics/openAccess |
SCOPUS ID: | 84943616503 |
PURE ID: | 290364 46c022bd-027e-4aa7-8a21-5b9fc8a9d24d |
ISSN: | 3029743 |
ISBN: | 9783662480564 |
DOI: | 10.1007/978-3-662-48057-1_8 |
Appears in Collections: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2-s2.0-84943616503.pdf | 298,55 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.