کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952042 | 1442007 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
One-way reversible multi-head finite automata
ترجمه فارسی عنوان
اتوماتای محدود چند سر قابل برگشت یک طرفه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
اتوماتای محدود چند سر یک طرفه، محاسبات برگشت پذیر، سوالات تصمیم گیری
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
One-way multi-head finite automata are considered towards their ability to perform reversible computations. It is shown that, for every number kâ¥1 of heads, there are problems which can be solved by one-way k-head finite automata, but not by any one-way reversible k-head finite automaton. Additionally, a proper head hierarchy is obtained for one-way reversible multi-head finite automata. Closure properties and decidability problems are investigated as well. It turns out that one-way reversible finite automata with two heads are still a powerful model, since almost all commonly studied problems are not even semidecidable. Finally, descriptional complexity aspects are studied and non-recursive trade-offs are shown.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 149-164
Journal: Theoretical Computer Science - Volume 682, 19 June 2017, Pages 149-164
نویسندگان
Martin Kutrib, Andreas Malcher,