کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873879 | 1440709 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity and decidability of some problems involving shuffle
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The complexity and decidability of various decision problems involving the shuffle operation (denoted by â§¢) are studied. The following three problems are all shown to be NP-complete: given a nondeterministic finite automaton (NFA) M, and two words u and v, is L(M)âuâ§¢v, is uâ§¢vâL(M), and is L(M)â uâ§¢v? It is also shown that there is a polynomial-time algorithm to determine, for NFAs M1,M2, and a deterministic pushdown automaton M3, whether L(M1)â§¢L(M2)âL(M3). The same is true when M1,M2,M3 are one-way nondeterministic l-reversal-bounded k-counter machines, with M3 being deterministic. Other decidability and complexity results are presented for testing whether given languages L1,L2, and R from various languages families satisfy L1â§¢L2âR, and RâL1â§¢L2. Several closure results on shuffle are also shown.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 214-224
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 214-224
نویسندگان
Joey Eremondi, Oscar H. Ibarra, Ian McQuillan,