Linear Cellular Automata via de Bruijn Diagrams

Harold V. McIntosh
Departamento de Aplicación de Microcomputadoras,
Instituto de Ciencias, Universidad Autónoma de Puebla,
Apartado postal 461, 72000 Puebla, Puebla, México.
E-mail:mcintosh@servidor.unam.mx

August 10, 1991

Abstract:

Graph theory plays several important roles in the theory of cellular automata, one of which consists in describing the evolution of the automaton, and another of which consists in relating local properties to global properties. Evolution is described by local rules mapping cell neighborhoods into its subsequent state; because successive neighborhoods overlap it is important to be able to take the overlap into account when relating the behavior of successive cells to one another. In illustration, the de Bruijn diagram and its subdiagrams are applied to the study of cellular automata in one dimension.

---

• Introduction
• Five representations
  • Mathematical definition
  • Simple drawing
  • Topological matrix
  • Symbolic equations
  • Regular expression
• Comparison of diagrams
  • Order relation
  • Least upper bound, or union
  • Greatest lower bound, or intersection
• Mappings and equivalences
  • Homomorphisms
  • Matrix representation
  • Regular expression
• Dual diagrams
  • The tail-head factorization
  • Duals and homomorphism
  • The head-tail factorization
  • Counting paths
  • Eigenvalues and eigenvectors
• Reverses and complements
  • Reversed graph
  • Complementary graph
• The de Bruijn diagram
  • Definition
  • Subdiagrams
  • A master diagram
• The de Bruijn matrix
  • One stage binary matrix
  • Two stage binary matrix
  • Three stage binary matrix
  • General de Bruijn matrix
  • RC and CR factorizations
  • Hamiltonian and Eulerian paths
• Subset diagrams
  • Scalar subset diagram
  • Vector subset diagram
  • Rule 126
  • Structural observations
• Use of the subset diagrams
  • Garden of Eden
  • Counting counterimages
• Pair diagram
• Probabilistic de Bruijn matrix
  • Positive matrices
  • Largest eigenvalue
  • Second eigenvalue and convergence
  • Equilibrium eigenvector
• Determinant and inverse
• Chacteristic equation
  • Merged product
  • Trace
  • second coefficient
  • principal minors
  • determinant
• Summary
• acknowledge
• References
• About this document ...

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx