کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952040 1442007 2017 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The chop of languages
ترجمه فارسی عنوان
ریز کردن زبان ها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We investigate chop operations, which can be seen as generalized concatenation. For several language families of the Chomsky hierarchy we prove (non)closure properties under chop operations and incomparability to the family of languages that are the chop of two regular languages. We also prove non-closure of that language family under Boolean operations and closure under reversal. Further, the representation of a regular language as the chop of two regular expressions can be exponentially more succinct than its regular expression. By considering the chop of two linear context-free languages we already obtain language families that have non-semi-decidable problems such as emptiness or finiteness.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 122-137
نویسندگان
, , ,