کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426266 | 686021 | 2008 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computational complexity of dynamical systems: The case of cellular automata
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Computational complexity of dynamical systems: The case of cellular automata Computational complexity of dynamical systems: The case of cellular automata](/preview/png/426266.png)
چکیده انگلیسی
Cellular Automata can be considered discrete dynamical systems and at the same time a model of parallel computation. In this paper we investigate the connections between dynamical and computational properties of Cellular Automata. We propose a classification of Cellular Automata according to the language complexities which rise from the basins of attraction of subshift attractors and investigate the intersection classes between our classification and other three topological classifications of Cellular Automata. From the intersection classes we can derive some necessary topological properties for a cellular automaton to be computationally universal according to our model.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 206, Issues 9–10, September–October 2008, Pages 1104-1116
Journal: Information and Computation - Volume 206, Issues 9–10, September–October 2008, Pages 1104-1116