کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435480 | 689910 | 2016 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Operational state complexity of unary NFAs with finite nondeterminism
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the state complexity of language operations for unary NFAs with limited nondeterminism. We consider the Boolean operations, concatenation, and Kleene star. We give upper bounds for the state complexity of these language operations and lower bounds that are fairly close to the upper bounds. Our constructions rely on the fact that minimal unary NFAs with limited nondeterminism can be found in Chrobak normal form for most measures of nondeterminism. The measures of nondeterminism which are considered here with the above property are tree width, advice, and trace.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 610, Part A, 11 January 2016, Pages 108–120
Journal: Theoretical Computer Science - Volume 610, Part A, 11 January 2016, Pages 108–120
نویسندگان
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl,