کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435327 689894 2016 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Closure properties and descriptional complexity of deterministic regular expressions
ترجمه فارسی عنوان
خواص بسته شدن و پیچیدگی توصیفی از عبارات منظم قطعی
کلمات کلیدی
عبارات منظم تعیین کننده، زبانهای یکپارچه، عملیات بولین، نظریه اتوماتیک، پیچیدگی توصیفی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We study the descriptional complexity of regular languages that are definable by deterministic regular expressions, i.e., we examine worst-case blow-ups in size when translating between different representations for such languages. As representations of languages, we consider regular expressions, deterministic regular expressions, and deterministic finite automata. Our results show that exponential blow-ups between these representations cannot be avoided. Furthermore, we study the descriptional complexity of these representations when applying boolean operations. Here, we start by investigating the closure properties of such languages under various language-theoretic operations such as union, intersection, concatenation, Kleene star, and reversal. Our results show that languages that are definable by deterministic regular expressions are not closed under any of these operations. Finally, we show that for all these operations except the Kleene star an exponential blow-up in the size of deterministic regular expressions cannot be avoided.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 627, 9 May 2016, Pages 54–70
نویسندگان
, , ,