Computational Analysis of One-Dimensional Cellular Automata

By

Burton H. Voorhees

Recently published by World Scientific. From one of their flyers:

The aim of this book is to give an introduction to the analysis of cellular automata in terms of an approach in which CA rules are viewed as elements of a non-linear operator algebra, which can be expressed in component form much as ordinary vectors are in vector algebra. Although a variety of different topics are covered, this viewpoint provides the underlying theme. The actual mathematics used is not hard, and the material should be accessible to anyone with a junior level university background, and a certain degree of mathematical maturity.

Contents:

Chapter 1: The Operator Algebra of Cellular Automata
     Basic definitions and notation
     Boolean forms of CA rules
     The canonical basis operators
     Symmetry transformations on CA rules
     CA rules as maps of the interval
     Exercises for chapter 1
Chapter 2:  Cellular Automata Arithmetic
     Products of CA rules
     The division algorithm
     Residue arithmetic of cellular automata
     Exercises for chapter 2
Chapter 3:  Fixed Points and Cycles
     Fixed points and shift cycles via rule decomposition
     Jen's invariance matrix method
     Exercises for chapter 3
Chapter 4:  Commutation of CA Rules
     Computation of commutator sets
     Idempotence
     Ito relations
     Some interesting sub-groups
     Exercises for chapter 4
Chapter 5:  Additive Rules: I. Basic Analysis
     Conditions for additivity
     Cyclotomic analysis
     Injectivity
     Another view of injectivity
     Exercises for chapter 5
Chapter 6:  Additive Rules: II. Cycle Structure and Entropy
     State transition diagrams
     Cycle periods
     Reachability
     Conditions for states on cycles
     Entropy reduction
     Exercises for chapter 6

Chapter 7: Additive Rules: III. Computation of Predecessors

     Predecessors of 3-site rules
     k-site rules
     Examples
     The operator B
     Exercises for chapter 7
Chapter 8:  The Binary Difference Rule
     Basic properties of D
     The Graph of D:[0,1]->[0,1]
     Some numerical relations
     A density result
     Exercises for chapter 8
Chapter 9:  Computation of Pre-Images
     Pre-images and predecessors
     The rule graph and basic matrix
     Computation of pre-images from the basic matrix
     Pre-images and the Jen recurrence relations
     Exercises for chapter 9
Chapter 10:  The Garden of Eden
     GE(X) and GE*(X)
     Computation of GE*(X)
     GE*(X) for 3-site rules
     Classification with GE*
     Exercises for chapter 10
Chapter 11:  Time Series Simulation
     Cellular automata generating time series
     Statistics of time series
     Exercises for chapter 11
Chapter 12:  Surjectivity of Cellular Automata Rules
     A kitchen sink theorem
     The de Bruijn diagram
     The subset diagram
     The semi-group G(X)
     The subset matrix and some replacement diagrams
     Exercises for chapter 12
Appendix 1:  Boolean Expressions for 2 and 3-Site Rules

Appendix 2: Canonical Forms and Decompositions of 3-Site Rules

Appendix 3:  Strongly Legal 3-Site Non-Generative Rules
Appendix 4:  The Mod(2) Pascal Triangle

Appendix 5: GE*(X) for 3-Site T-Equivalance Class Exemplars

Appendix 6:  G(X) for Selected Rules

The book can be ordered from World Scientific at one of the

following addresses:

USA  1060 Main Street, River Edge, NJ 07661
     1-800-227-7562

UK   57 Shelton Street, Covent Garden, London WC2H 9HE
     44-171-836-0888    wspc@wspc.demon.co.uk

Singapore
     Farrer Road, P.O. Box 128, Singapore 9128

Hong Kong
     P.O. Box 72482, Kowloon Central Post Office, Hong Kong

India
     4911, 9th Floor, High Point IV, 45 Palace Road, Bangalore 560 001

Taiwan
     5F-6, No. 88, Sec 3, Hsin-Sheng S Road, Taipei, Taiwan, ROC