کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427449 686508 2014 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله 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
چکیده انگلیسی

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
نویسندگان
, ,