Discrete Baker Transformation and Cellular Automata

MaRDI QIDQ6474221zbMATH OpenFDO

Authors V. K. Bulitko

Publication date 8 July 2004

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Dynamical aspects of cellular automata (37B15) Cellular automata (computational aspects) (68Q80)

Abstract: In this paper we propose a rule-independent description of applications of cellular automata rules for one-dimensional additive cellular automata on cylinders of finite sizes. This description is shown to be a useful tool for for answering questions about automata's state transition diagrams (STD). The approach is based on two transformations: one (called {sl Baker transformation}) acts on the $n$-dimensional Boolean cube $frak{B}^n$ and the other (called {sl index-baker transformation}) acts on the cyclic group of power $n$. The single diagram of Baker transformation in $frak{B}^n$ contains an important information about all automata on the cylinder of size $n$. Some of the results yielded by this approach can be viewed as a generalization and extension of certain results by O. Martin, A. Odlyzko, S. Wolfram. Additionally, our approach leads to a convenient language for formulating properties, such as possession of cycles with certain lengths and given diagram heights, of automaton rules.

This page was built for publication: Discrete Baker Transformation and Cellular Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6474221)