For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Formulation of Composition for Cellular Automata on Groups
Shuichi INOKUCHI Takahiro ITO Mitsuhiko FUJIO Yoshihiro MIZOGUCHI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2014/03/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—)
Category: Cellular Automata
cellular automata, groups, models of computation, automata,
Full Text: PDF(474.6KB)>>
We introduce the notion of 'Composition', 'Union' and 'Division' of cellular automata on groups. A kind of notions of compositions was investigated by Sato  and Manzini  for linear cellular automata, we extend the notion to general cellular automata on groups and investigated their properties. We observe the all unions and compositions generated by one-dimensional 2-neighborhood cellular automata over Z2 including non-linear cellular automata. Next we prove that the composition is right-distributive over union, but is not left-distributive. Finally, we conclude by showing reformulation of our definition of cellular automata on group which admit more than three states. We also show our formulation contains the representation using formal power series for linear cellular automata in Manzini .