کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435512 689911 2009 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Shortest synchronizing strings for Huffman codes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Shortest synchronizing strings for Huffman codes
چکیده انگلیسی

Most complete binary prefix codes have a synchronizing string, that is a string that resynchronizes the decoder regardless of its previous state. This work presents an upper bound on the length of the shortest synchronizing string for such codes. Two classes of codes with a long shortest synchronizing string are presented. It is known that finding a synchronizing string for a code is equivalent to finding a synchronizing string of some finite automaton. The Černý conjecture for this class of automata is discussed.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 38–40, 6 September 2009, Pages 3925-3941