کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334320 | 690377 | 2005 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
State complexity of some operations on binary regular languages
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: State complexity of some operations on binary regular languages State complexity of some operations on binary regular languages](/preview/png/10334320.png)
چکیده انگلیسی
We investigate the state complexity of some operations on binary regular languages. In particular, we consider the concatenation of languages represented by deterministic finite automata, and the reversal and complementation of languages represented by nondeterministic finite automata. We prove that the upper bounds on the state complexity of these operations, which were known to be tight for larger alphabets, are tight also for binary alphabets.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 287-298
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 287-298
نویسندگان
Galina Jirásková,