Cellular Automata Associated with Σ-Algebras

Shuichi INOKUCHI  Hitoshi FURUSAWA  Toshikazu ISHIDA  Yasuo KAWAHARA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.3   pp.588-597
Publication Date: 2016/03/01
Publicized: 2015/12/16
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015FCP0002
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)
Category: 
Keyword: 
Cellular Automata,  Σ-algebras,  Hedlund's theorem,  

Full Text: PDF(297.4KB)>>
Buy this Article




Summary: 
In this paper we present a novel treatment of cellular automata (CA) from an algebraic point of view. CA on monoids associated with Σ-algebras are introduced. Then an extension of Hedlund's theorem which connects CA associated with Σ-algebras and continuous functions between prodiscrete topological spaces on the set of configurations are discussed.