کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426660 | 686140 | 2010 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
More concise representation of regular languages by automata and regular expressions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: More concise representation of regular languages by automata and regular expressions More concise representation of regular languages by automata and regular expressions](/preview/png/426660.png)
چکیده انگلیسی
We consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We constructively prove that their sizes are polynomially related. Comparing them with the sizes of finite state automata and regular expressions, we obtain optimal exponential and double exponential gaps, i.e., a more concise representation of regular languages.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 208, Issue 4, April 2010, Pages 385-394
Journal: Information and Computation - Volume 208, Issue 4, April 2010, Pages 385-394