کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333903 | 689835 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on algebras of languages
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the Boolean algebras R,CS,D of regular languages, context-sensitive languages and decidable languages, respectively, over any alphabet. It is well known that RâCSâD, with proper inclusions. After observing that these Boolean algebras are all isomorphic, we study some immunity properties: for instance we prove that for every coinfinite decidable language L there exists a decidable language Lâ² such that LâLâ², Lâ²âL is infinite, and there is no context-sensitive language Lâ³, with Lâ³âLâ² unless Lâ³âL is finite; similarly, for every coinfinite regular language L there exists a context-sensitive language Lâ² such that LâLâ², Lâ²âL is infinite, and there is no regular language Lâ³ such that Lâ³âLâ², unless Lâ³âL is finite.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 46, 28 October 2011, Pages 6531-6536
Journal: Theoretical Computer Science - Volume 412, Issue 46, 28 October 2011, Pages 6531-6536
نویسندگان
Claudio Marini, Giulia Simi, Andrea Sorbi, Marianna Sorrentino,