کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334257 | 690355 | 2005 | 26 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Unresolved systems of language equations: Expressive power and decision problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Unresolved language equations and inequalities with various sets of operations are considered. It is proved that systems of unresolved equations with linear concatenation and union only, as well as systems with linear concatenation and intersection only, are as expressive as the more general unresolved inequalities with all Boolean operations and unrestricted concatenation: the class of languages defined by unique (least, greatest) solutions of these systems is shown to coincide with the families of recursive (RE, co-RE, resp.) sets, which result extends even to individual equations of the form âujXijvj=wâªâyjXtjzj. On the other hand, unresolved equations with different sets of operations are shown to differ in the hardness of their decision problems, and it is demonstrated that several types of unresolved equations cannot effectively simulate each other in spite of the equality of the language families they define.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 349, Issue 3, 16 December 2005, Pages 283-308
Journal: Theoretical Computer Science - Volume 349, Issue 3, 16 December 2005, Pages 283-308
نویسندگان
Alexander Okhotin,