کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427449 | 686508 | 2014 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable](/preview/png/427449.png)
چکیده انگلیسی
We prove that any propagating E0L system cannot generate the language {w#w|w∈{0,1}⁎}{w#w|w∈{0,1}⁎}. This result, together with some known ones, enables us to conclude that the flip-pushdown automata with k pushdown reversals, i.e., the pushdown automata with the ability to flip the pushdown, and E0L systems are incomparable. This result solves an open problem stated by Holzer and Kutrib in 2003.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 114, Issue 8, August 2014, Pages 417–420
Journal: Information Processing Letters - Volume 114, Issue 8, August 2014, Pages 417–420
نویسندگان
Pavol Ďuriš, Marek Košta,