华东师范大学学报(自然科学版) ›› 2008, Vol. 2008 ›› Issue (3): 75-82.

• 计算机科学 • 上一篇    下一篇

7号初等元胞自动机生成的时间序列的复杂性分析

秦大康1, 江志松2   

  1. 1. 南通大学理学院 , 江苏 226007; 2. 华东理工大学 数学系, 上海 200237
  • 收稿日期:2007-09-20 修回日期:2008-01-02 出版日期:2008-05-25 发布日期:2008-05-25
  • 通讯作者: 秦大康

Complexity analysis of time series generated by elementary cellular automaton of Rule 7(Chinese)

QIN Da-kang1, JIANG Zhi-song2   

  1. 1. School of Science, Nantong University, Jiangsu 226007, China; 2. Department ofMathematics, East China University of Science and Technology, Shanghai 200237, China
  • Received:2007-09-20 Revised:2008-01-02 Online:2008-05-25 Published:2008-05-25
  • Contact: QIN Da-kang

摘要:

使用禁止字理论、计算机搜索和符号动力学的方法对7号初等元胞自动机生成的时间序列从形式语言的角度进行复杂性分析,确定了禁止字集及其Chomsky层次,确定了演化语言的一个精简的Chomsky层次,并由此得到了时间序列的完整描述.

关键词: 初等元胞自动机, 时间序列, 禁止字, 形式语言, Chomsky层次, 初等元胞自动机, 时间序列, 禁止字, 形式语言, Chomsky层次

Abstract:

Using the tools of distinct excluded blocks, computational search and symbolic dynamics, the complexity of the times series generated by elementary cellular automaton of Rule 7 was analyzed, the set of distinct excluded blocks and its Chomsky hierarchy and the Chomsky hierarchy of a reduction of the evolution language were determined.Finally,the mathematical structure underlying the time series was obtained.

Key words: time series, distinct excluded block, formal language, Chomsky hierarchy, elementary cellular automaton, time series, distinct excluded block, formal language, Chomsky hierarchy

中图分类号: