Algebraic Theory of Bounded One-dimensional Cellular Automata
N. Pitsianis
G. L. Bleris
Solid State Section, Physics Department, University of Thessaloniki,
Ph. Tsalides
A. Thanailakis
Laboratory of Electrotechnical and Electronic Materials Technology,
Department of Electrical Engineering, School of Engineering,
Democritus University of Thrace, 67100 Xanthi, Greece
H. C. Card
VLSI Research Laboratory, Department of Electrical Engineering,
University of Manitoba, Winnipeg, Manitoba, Canada, R3T 2N2
Abstract
A formal mathematical presentation of various algebraic properties of rule 90 elementary one-dimensional cellular automata (CA) with null boundary conditions is given. The CA global rule transition matrix is given and its characteristic polynomial is formally obtained. Mathematical relationships between the CA register lengths and the orders of the corresponding group or semigroup algebraic structures are derived.
