کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436144 | 689974 | 2015 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the commutative equivalence of bounded context-free and regular languages: The code case
ترجمه فارسی عنوان
در همگرایی تعاملی زبان محدود و متناهی محدود: پرونده کد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
محدود زبان بدون زمینه، مجموعه نیمه خطی، همبستگی متقابل
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This is the first paper of a group of three where we prove the following result. Let A be an alphabet of t letters and let ψ:A⁎⟶Ntψ:A⁎⟶Nt be the corresponding Parikh morphism. Given two languages L1,L2⊆A⁎L1,L2⊆A⁎, we say that L1L1 is commutatively equivalent to L2L2 if there exists a bijection f:L1⟶L2f:L1⟶L2 from L1L1 onto L2L2 such that, for every u∈L1u∈L1, ψ(u)=ψ(f(u))ψ(u)=ψ(f(u)). Then every bounded context-free language is commutatively equivalent to a regular language.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 562, 11 January 2015, Pages 304–319
Journal: Theoretical Computer Science - Volume 562, 11 January 2015, Pages 304–319
نویسندگان
Flavio D'Alessandro, Benedetto Intrigila,