کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952264 | 1442025 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On incomplete and synchronizing finite sets
ترجمه فارسی عنوان
در مجموعه های ناقص و همگام سازی مجموعه های محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
í í ½ حدس، هماهنگ سازی اتوماتیک، کلمه ناتمام همگام سازی مجموعه، مجموعه کامل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper situates itself in the theory of variable length codes and of finite automata where the concepts of completeness and synchronization play a central role. In this theoretical setting, we investigate the problem of finding upper bounds to the minimal length of synchronizing words and incompletable words of a finite language X in terms of the length of the words of X. This problem is related to two well-known conjectures formulated by Äerný and Restivo, respectively. In particular, if Restivo's conjecture is true, our main result provides a quadratic bound for the minimal length of a synchronizing pair of any finite synchronizing complete code with respect to the maximal length of its words.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 664, 15 February 2017, Pages 67-77
Journal: Theoretical Computer Science - Volume 664, 15 February 2017, Pages 67-77
نویسندگان
Arturo Carpi, Flavio D'Alessandro,