A Formulation of Composition for Cellular Automata on Groups
Summary :
We introduce the notion of 'Composition', 'Union' and 'Division' of cellular automata on groups. A kind of notions of compositions was investigated by Sato [10] and Manzini [6] 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 [6].
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.3 pp.448-454
- Publication Date
- 2014/03/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E97.D.448
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science —New Trends in Theory of Computation and Algorithm—)
- Category
- Cellular Automata
Authors
Shuichi INOKUCHI
Kyushu University
Takahiro ITO
TOME R&D Inc.
Mitsuhiko FUJIO
Kinki University
Yoshihiro MIZOGUCHI
Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shuichi INOKUCHI, Takahiro ITO, Mitsuhiko FUJIO, Yoshihiro MIZOGUCHI, "A Formulation of Composition for Cellular Automata on Groups" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 3, pp. 448-454, March 2014, doi: 10.1587/transinf.E97.D.448.
Abstract: We introduce the notion of 'Composition', 'Union' and 'Division' of cellular automata on groups. A kind of notions of compositions was investigated by Sato [10] and Manzini [6] 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 [6].
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E97.D.448/_p
Copy
@ARTICLE{e97-d_3_448,
author={Shuichi INOKUCHI, Takahiro ITO, Mitsuhiko FUJIO, Yoshihiro MIZOGUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={A Formulation of Composition for Cellular Automata on Groups},
year={2014},
volume={E97-D},
number={3},
pages={448-454},
abstract={We introduce the notion of 'Composition', 'Union' and 'Division' of cellular automata on groups. A kind of notions of compositions was investigated by Sato [10] and Manzini [6] 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 [6].},
keywords={},
doi={10.1587/transinf.E97.D.448},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - A Formulation of Composition for Cellular Automata on Groups
T2 - IEICE TRANSACTIONS on Information
SP - 448
EP - 454
AU - Shuichi INOKUCHI
AU - Takahiro ITO
AU - Mitsuhiko FUJIO
AU - Yoshihiro MIZOGUCHI
PY - 2014
DO - 10.1587/transinf.E97.D.448
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2014
AB - We introduce the notion of 'Composition', 'Union' and 'Division' of cellular automata on groups. A kind of notions of compositions was investigated by Sato [10] and Manzini [6] 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 [6].
ER -
English
