کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6873884 | 1440709 | 2018 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Descriptional complexity of limited automata
ترجمه فارسی عنوان
پیچیدگی توصیف اتوماتای محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A k-limited automaton is a linear bounded automaton that may rewrite each tape cell only in the first k visits, where kâ¥0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate the descriptional complexity of limited automata. Since the unary languages accepted are necessarily regular, we first study the cost in the number of states when finite automata simulate a unary k-limited automaton. For the conversion of a 4n-state deterministic 1-limited automaton into one-way or two-way deterministic or nondeterministic finite automata, we show a lower bound of nâ
F(n) states, where F denotes Landau's function. So, even the ability to deterministically rewrite any cell only once gives an enormous descriptional power. For the simulation cost for removing the ability to rewrite each cell kâ¥1 times, more precisely, the cost for the simulation of sweeping unary k-limited automata by deterministic finite automata, we obtain a lower bound of nâ
F(n)k. The upper bound of the cost for the simulation by two-way deterministic finite automata is a polynomial whose degree is quadratic in k. If the k-limited automaton is rotating, the upper bound reduces to O(nk+1) and the lower bound derived is Ω(nk+1) even for nondeterministic two-way finite automata. So, for rotating k-limited automata, the trade-off for the simulation is tight in the order of magnitude. Finally, we consider the simulation of k-limited automata over general alphabets by pushdown automata. It turns out that the cost is an exponential blow-up of the size. Furthermore, an exponential size is also necessary.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 259-276
Journal: Information and Computation - Volume 259, Part 2, April 2018, Pages 259-276
نویسندگان
Martin Kutrib, Giovanni Pighizzini, Matthias Wendlandt,