کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334326 | 690377 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the descriptional complexity of some rewriting mechanisms regulated by context conditions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We improve the upper bounds of certain descriptional complexity measures of two types of rewriting mechanisms regulated by context conditions. We prove that scattered context grammars having two context sensing productions and five nonterminals are sufficient to generate all recursively enumerable languages and we also show that the same power can be reached by simple semi-conditional grammars having 10 conditional productions with conditions of the length two or eight conditional productions with conditions of length three. The results are based on the common idea of using the so called Geffert normal forms for phrase structure grammars.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 361-373
Journal: Theoretical Computer Science - Volume 330, Issue 2, 2 February 2005, Pages 361-373
نویسندگان
György Vaszil,