Please use this identifier to cite or link to this item: http://hdl.handle.net/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://hdl.handle.net/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 SizeFormat 
2-s2.0-84943616503.pdf298,55 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.