کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10330788 | 686132 | 2011 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Synchronizing automata with finitely many minimal synchronizing words
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A synchronizing word for a given synchronizing DFA is called minimal if none of its proper factors is synchronizing. We characterize the class of synchronizing automata having only finitely many minimal synchronizing words (the class of such automata is denoted by FG). Using this characterization we prove that any such automaton possesses a synchronizing word of length at most 3n-5. We also prove that checking whether a given DFA A is in FG is co-NP-hard and provide an algorithm for this problem which is exponential in the number of states A.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 209, Issue 3, March 2011, Pages 568-579
Journal: Information and Computation - Volume 209, Issue 3, March 2011, Pages 568-579
نویسندگان
Elena V. Pribavkina, Emanuele Rodaro,