| 22号初等元胞自动机的极限语言复杂性 |
| |
| 引用本文： | Jiang Zhisong Wang Yi. 22号初等元胞自动机的极限语言复杂性[J]. 高校应用数学学报(英文版), 2005, 20(3): 268-276. DOI: 10.1007/s11766-005-0002-z |
| |
| 作者姓名： | Jiang Zhisong Wang Yi |
| |
| 作者单位： | [1]Dept. of Math. , East China Univ. , of Science and Technology,Shanghai 200237,China. [2]Dept. of Math. , Suzhou Univ. , Suzhou 215006, China; Faculty of Engineering, Hiroshima Univ.,Higashi Hiroshima 739-8527,Japan. |
| |
| 基金项目： | Supported partly by the National Natural Science Foundation of China （10101016）and Tian YuanFoundation of China（10126020）. |
| |
| 摘 要： | §1Introduction Thetaskofthispaperistosolvetheproblemproposedin[1],i.e.,toexplorethe complexityoflimitset,orequivalently,limitlanguageoftheelementarycellularautomaton ofrule22bythetoolsofformallanguagetheory.Cellularautomata(abbreviatedasCA),asmathematicalmodelsforcomplexnatural systemscontaininglargenumbersofsimpleidenticalcomponentswithlocalinteractions,havebeenwidelyusedinphysical,biological,chemicalandcomputationalsystems[2].Despitetheirsimpleconstruction,someCAcandisplayveryrichandcompl…
|
| 关 键 词： | 原始细胞 语言限制 自动控制 复杂性 动态特性 |
| 收稿时间： | 2003-02-25 |
| 修稿时间： | 2004-11-07 |
Complexity of limit language of the elementary cellular automaton of rule 22 |
| |
| Jiang Zhisong,Wang Yi. Complexity of limit language of the elementary cellular automaton of rule 22[J]. Applied Mathematics A Journal of Chinese Universities, 2005, 20(3): 268-276. DOI: 10.1007/s11766-005-0002-z |
| |
| Authors: | Jiang Zhisong Wang Yi |
| |
| Affiliation: | Dept.of Math., East China Univ., of Science and Technology,Shanghai 200237,China;Dept.of Math., Suzhou Univ.,Suzhou 215006,China;Faculty of Engineering,Hiroshima Univ., Higashi Hiroshima 739-8527,Japan |
| |
| Abstract: | In this paper, the limit set of the elementary cellular automaton of rule 22 is considered. The limit language is defined from limit set and its complexity is studied by using formal language theory. It is proved that this language is not a regular language. This result shows that the dynamics of this cellular automaton is actually complicated. |
| |
| Keywords: | complexity cellular automaton limit set limit language. |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
|
