کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430749 | 688140 | 2008 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Lower bounds for the transition complexity of NFAs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We construct regular languages Ln, n⩾1, such that any NFA recognizing Ln needs transitions. Here nsc(Ln) is the nondeterministic state complexity of Ln. Also, we study trade-offs between the number of states and the number of transitions of an NFA. We show that adding one additional state can result in significant reductions in the number of transitions and that there exist regular languages Ln, n⩾2, where the transition minimal NFA for Ln has more than c⋅nsc(Ln) states, for some constant c>1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 74, Issue 7, November 2008, Pages 1116-1130
Journal: Journal of Computer and System Sciences - Volume 74, Issue 7, November 2008, Pages 1116-1130