Paper Info
Title
Almost periodic configurations on linear cellular automata
Abstract
We study computational properties of linear cellular automata on configurations that differ from spatially periodic ones in only finitely many places. It is shown that the degree structure of the orbits of cellular automata is the same on these configurations as on the space of finite configurations. We also show that it is undecidable whether the cellular automaton exhibits complicated behavior on configurations of sufficiently long spatial periods and exhibit cellular automata with undecidable orbits whose orbits on backgrounds of all fixed sizes are decidable.
Year
Venue
Keywords
2003
Fundam. Inform.
periodic configuration,linear cellular automaton,cellular automaton,long spatial period,almost periodic configurations,undecidable orbit,finite configuration,complicated behavior,linear cellular automata,fixed size,degree structure,computational property,cellular automata
Field
DocType
Volume
Discrete mathematics,Quantum finite automata,Cellular automaton,Continuous automaton,Combinatorics,Continuous spatial automaton,Mobile automaton,Pure mathematics,Reversible cellular automaton,Block cellular automaton,Stochastic cellular automaton,Mathematics
Journal
58
Issue
ISSN
Citations 
3-4
0169-2968
6
PageRank 
References 
Authors
0.58
5
1
Name
Order
Citations
PageRank
Klaus Sutner111919.42