کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436941 690056 2006 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Low complexity classes of multidimensional cellular automata
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Low complexity classes of multidimensional cellular automata
چکیده انگلیسی

In this paper, multidimensional cellular automaton are considered. We investigate the hierarchy designed by the low complexity classes when the dimensionality is increased. Whether this hierarchy is strict, is an open problem. However, we compare different variants and study their closure properties. We present also a correspondence between a main variant of multidimensional real-time cellular automata and one-way multihead alternating finite automata.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 369, Issues 1–3, 15 December 2006, Pages 142-156