Subshift attractors of cellular automata

被引:17
作者
Formenti, Enrico
Kurka, Petr
机构
[1] Univ Nice Sophia Antipolis, Dept Informat, F-06108 Nice 2, France
[2] Charles Univ Prague, Ctr Theoret Study, CZ-11000 Prague, Czech Republic
关键词
D O I
10.1088/0951-7715/20/1/007
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A subshift attractor is a two-sided subshift which is an attractor of a cellular automaton. We prove that each subshift attractor is chain-mixing, contains a configuration which is both F-periodic and sigma-periodic and the complement of its language is recursively enumerable. We prove that a subshift of finite type is an attractor of a cellular automaton iff it is mixing. We identify a class of chain-mixing sofic subshifts which are not subshift attractors. We construct a cellular automaton whose maximal attractor is a non-sofic mixing subshift, answering a question raised in Maass (1995 Ergod. Theory Dyn. Syst. 15 663-84). We show that a cellular automaton is surjective on its small quasi-attractor which is the non-empty intersection of all subshift attractors of all F-q sigma(p), where q > 0 and p is an element of Z.
引用
收藏
页码:105 / 117
页数:13
相关论文
共 8 条
[1]  
[Anonymous], INTRO SYMBOLIC DYNAM
[2]   COMPUTATION THEORETIC ASPECTS OF CELLULAR AUTOMATA [J].
CULIK, K ;
HURD, LP ;
YU, S .
PHYSICA D-NONLINEAR PHENOMENA, 1990, 45 (1-3) :357-378
[3]  
Hurd L. P., 1990, Complex Systems, V4, P119
[4]   ATTRACTORS IN CELLULAR AUTOMATA [J].
HURLEY, M .
ERGODIC THEORY AND DYNAMICAL SYSTEMS, 1990, 10 :131-140
[5]   Languages, equicontinuity and attractors in cellular automata [J].
Kurka, P .
ERGODIC THEORY AND DYNAMICAL SYSTEMS, 1997, 17 :417-433
[6]  
Kurka P., 2005, DISCRETE CONTINUOUS, P524
[7]  
Kurka P., 2003, Specialized Courses, V11
[8]   ON THE SOFIC LIMIT-SETS OF CELLULAR-AUTOMATA [J].
MAASS, A .
ERGODIC THEORY AND DYNAMICAL SYSTEMS, 1995, 15 :663-684