Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102188
Title: Algebraic synchronization criterion and computing reset words
Authors: Berlinkov, M. V.
Szykuła, M.
Issue Date: 2016
Publisher: Elsevier Inc.
Citation: Berlinkov M. V. Algebraic synchronization criterion and computing reset words / M. V. Berlinkov, M. Szykuła. — DOI 10.1016/j.ins.2016.07.049 // Information Sciences. — 2016. — Vol. 369. — P. 718-730.
Abstract: We refine a uniform algebraic approach for deriving upper bounds on reset thresholds of synchronizing automata. We express the condition that an automaton is synchronizing in terms of linear algebra, and obtain new upper bounds for automata with a short word of small rank. The results are applied to make several improvements in the area. In particular, we improve the 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(nlog3n). In addition to that, we prove that the expected reset threshold of a uniformly random synchronizing binary n-state decoder is at most O(nlog n). We prove the Černý conjecture for n-state automata with a letter of rank ≤6n−63. In another corollary, 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, and that the expected value of the reset threshold is at most n3/2+o(1). Moreover, all of our bounds are constructible. We present suitable polynomial algorithms for the task of finding a reset word of length within our bounds. © 2016
Keywords: HUFFMAN CODE
PREFIX CODE
RANDOM AUTOMATON
RESET WORD
SYNCHRONIZING AUTOMATON
ČERNÝ CONJECTURE
ALGEBRA
AUTOMATA THEORY
BINS
CODES (SYMBOLS)
DECODING
LINEAR ALGEBRA
HUFFMAN CODE
PREFIX CODES
RANDOM AUTOMATON
RESET WORDS
SYNCHRONIZING AUTOMATA
SYNCHRONIZATION
URI: http://hdl.handle.net/10995/102188
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84994525822
PURE ID: 1304223
65af5829-b5ef-43c0-bbfb-2406c7886152
ISSN: 200255
DOI: 10.1016/j.ins.2016.07.049
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84994525822.pdf298,56 kBAdobe PDFView/Open


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