کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951206 | 1441194 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of suffix-free regular languages
ترجمه فارسی عنوان
پیچیدگی زبان های منظم پسوند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study various complexity properties of suffix-free regular languages. A sequence (Lk,Lk+1,â¦) of regular languages in some class, where n is the quotient complexity of Ln, is most complex if its languages Ln meet the complexity upper bounds for all basic measures. It is known that there exist such most complex sequences in several classes of regular languages. In contrast to this, we prove that there does not exist a most complex sequence in the class of suffix-free regular languages. However, we do exhibit two such sequences that together meet upper bounds for all basic measures.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 89, November 2017, Pages 270-287
Journal: Journal of Computer and System Sciences - Volume 89, November 2017, Pages 270-287
نویسندگان
Janusz A. Brzozowski, Marek SzykuÅa,