Computational Analysis of One-Dimensional Cellular Automata By Burton H. VoorheesRecently 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.
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 6Chapter 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 RulesAppendix 2: Canonical Forms and Decompositions of 3-Site Rules
Appendix 3: Strongly Legal 3-Site Non-Generative Rules Appendix 4: The Mod(2) Pascal TriangleAppendix 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 thefollowing 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 firstname.lastname@example.org 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