| 146号初等元胞自动机的演化语言的复杂性 |
| |
| 引用本文： | 王益.146号初等元胞自动机的演化语言的复杂性[J].高校应用数学学报(英文版),2006,21(4):418-428. |
| |
| 作者姓名： | 王益 |
| |
| 作者单位： | [1]School of Mathematical Sciences, Suzhou University, Suzhou 215006, China. [2]Faculty of Engineering, Hiroshima University, Higashi Hiroshima 739-8527, Japan. |
| |
| 摘 要： | Symbolic dynamics of cellular automata is introduced by coarse-graining the temporal evolution orbits. Evolution languages are defined. By using the theory of formal languages and automata, the complexity of evolution languages of the elementary cellular automaton of rule 146 is studied and it is proved that its width 1-evolution language is regular, but for every n ≥ 2 its width n-evolution language is not context-free but context-sensitive. Also, the same results hold for the equivalent （under conjugation） elementary cellular automaton of rule 182.
|
| 关 键 词： | 复杂性 细胞机器人 进化语言 象征动力学 |
| 收稿时间： | 2006-02-21 |
Complexity of evolution languages of the elementary cellular automaton of rule 146 |
| |
| Yi Wang,Kenichi Morita.Complexity of evolution languages of the elementary cellular automaton of rule 146[J].Applied Mathematics A Journal of Chinese Universities,2006,21(4):418-428. |
| |
| Authors: | Yi Wang Kenichi Morita |
| |
| Institution: | (1) School of Mathematical Sciences, Suzhou University, Suzhou, 215006, China;(2) Faculty of Engineering, Hiroshima University, Higashi Hiroshima 739-8527, Japan |
| |
| Abstract: | Symbolic dynamics of cellular automata is introduced by coarse-graining the temporal evolution orbits. Evolution languages are defined. By using the theory of formal languages and automata, the complexity of evolution languages of the elementary cellular automaton of rule 146 is studied and it is proved that its width 1-evolution language is regular, but for every n ≥ 2 its width n-evolution language is not context-free but context-sensitive. Also, the same results hold for the equivalent (under conjugation) elementary cellular automaton of rule 182. |
| |
| Keywords: | complexity cellular automaton evolution language formal language |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
|
