کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437969 | 690211 | 2009 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The Parikh counting functions of sparse context-free languages are quasi-polynomials
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let L be a sparse context-free language over an alphabet of t letters and let fL:Nt→N be its Parikh counting function. We prove the following two results: 1.There exists a partition of Nt into a finite family of polyhedra such that the function fL is a quasi-polynomial on each polyhedron of the partition.2.There exists a partition of Nt into a finite family of rational subsets such that the function fL is a polynomial on each set of the partition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 47–49, 6 November 2009, Pages 5158-5181
Journal: Theoretical Computer Science - Volume 410, Issues 47–49, 6 November 2009, Pages 5158-5181