| THE COMPLEXITY OF LIMIT LANGUAGES OF CELLULAR AUTOMATA: AN EXAMPLE |
| |
| 作者姓名： | XIE Huimin |
| |
| 作者单位： | Department of Mathematics，Suzhou University，Suzhou 215006，China |
| |
| 基金项目： | the Special Funds for Major State Basic Research Projects. |
| |
| 摘 要： | 1 IntroductionCellular automata (abbreviated as CA) are typical complex systems that their global behaviors cannot be PrediCted from the Properties of their componellts (i.e. cells or automata)which are identically located on the nodes of a periodic lattice and have the same updatingrules.Historicallys the first cellular automaton was proposed by von Neumann to formalize thereproductivity phenomena in living systemsIJ. Since then cellular automata as mathematicalmodels have been used to si…
|
THE COMPLEXITY OF LIMIT LANGUAGES OF CELLULAR AUTOMATA: AN EXAMPLE |
| |
| XIE Huimin.THE COMPLEXITY OF LIMIT LANGUAGES OF CELLULAR AUTOMATA: AN EXAMPLE[J].Journal of Systems Science and Complexity,2001(1). |
| |
| Authors: | XIE Huimin |
| |
| Abstract: | The limit inguages of cellular automata are defined and their complexity are discussed. New tools, which include skew evolution, skew periodic string, trace string, some algebraic calculation method, and restricted membership problem, are developed through a discussion focusing on the limit language of an elementary cellular automata of rule 94. It is proved that this language is non-regular. |
| |
| Keywords: | Cellular automata limit set limit language complexity |
| 本文献已被 CNKI 等数据库收录！ |
