کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437654 | 690169 | 2015 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Multipass automata and group word problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We introduce the notion of multipass automata as a generalization of pushdown automata and study the classes of languages accepted by such machines. The class of languages accepted by deterministic multipass automata is exactly the Boolean closure of the class of deterministic context-free languages while the class of languages accepted by nondeterministic multipass automata is exactly the class of poly-context-free languages, that is, languages which are the intersection of finitely many context-free languages. We illustrate the use of these automata by studying groups whose word problems are in the above classes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 600, 4 October 2015, Pages 19–33
Journal: Theoretical Computer Science - Volume 600, 4 October 2015, Pages 19–33
نویسندگان
Tullio Ceccherini-Silberstein, Michel Coornaert, Francesca Fiorenzi, Paul E. Schupp, Nicholas W.M. Touikan,