کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873879 | 1440709 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity and decidability of some problems involving shuffle
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the complexity and decidability of some problems involving shuffle On the complexity and decidability of some problems involving shuffle](/preview/png/6873879.png)
چکیده انگلیسی
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,