Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Algebraic Synchronization Criterion and Computing Reset Words
verfasst von : Mikhail Berlinkov, Marek Szykuła
Erschienen in: Mathematical Foundations of Computer Science 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 \log ^3 n)\). Also, we prove the Černý conjecture for n-state automata with a letter of rank at most \(\root 3 \of {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 \(n^{7/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.