Cellular Automata and Discrete Complex Systems

1. Front Matter

   Pages I-X

   PDF

2. Cellular Automaton Models for Collective Cell Behaviour

   • Andreas Deutsch

   Pages 1-10

3. Tag Systems and the Complexity of Simple Programs

   • Turlough Neary, Damien Woods

   Pages 11-16

4. Groups and Monoids of Cellular Automata

   • Ville Salo

   Pages 17-45

5. A Physically Universal Quantum Cellular Automaton

   • Luke Schaeffer

   Pages 46-58

6. Effect of Graph Structure on the Limit Sets of Threshold Dynamical Systems

   • Abhijin Adiga, Chris J. Kuhlman, Henning S. Mortveit, Sichao Wu

   Pages 59-70

7. A Cellular Automaton for Blocking Queen Games

   • Matthew Cook, Urban Larsson, Turlough Neary

   Pages 71-84

8. Hard Core via PCA: Entropy Bounds

   • Kari Eloranta

   Pages 85-98

9. Classification of Elementary Cellular Automata Up to Topological Conjugacy

   • Jeremias Epperlein

   Pages 99-112

10. Remarks on the Cellular Automaton Global Synchronisation Problem

    • Nazim Fatès

    Pages 113-126

11. L-Convex Polyominoes Are Recognizable in Real Time by 2D Cellular Automata

    • Anaël Grandjean, Victor Poupet

    Pages 127-140

12. Shrinking One-Way Cellular Automata

    • Martin Kutrib, Andreas Malcher, Matthias Wendlandt

    Pages 141-154

13. Universal Time-Symmetric Number-Conserving Cellular Automaton

    • Diego Maldonado, Andrés Moreira, Anahí Gajardo

    Pages 155-168

14. The Ideal Energy of Classical Lattice Dynamics

    • Norman Margolus

    Pages 169-180

15. On the Periods of Spatially Periodic Preimages in Linear Bipermutive Cellular Automata

    • Luca Mariot, Alberto Leporati

    Pages 181-195

16. Merging Cellular Automata Rules to Optimise a Solution to the Modulo-n Problem

    • Claudio L. M. Martins, Pedro P. B. de Oliveira

    Pages 196-209

17. Network Structure and Activity in Boolean Networks

    • Abhijin Adiga, Hilton Galyean, Chris J. Kuhlman, Michael Levet, Henning S. Mortveit, Sichao Wu

    Pages 210-223

18. Group-Walking Automata

    • Ville Salo, Ilkka Törmä

    Pages 224-237

19. Restricted Density Classification in One Dimension

    • Siamak Taati

    Pages 238-250

20. Recognition of Linear-Slender Context-Free Languages by Real Time One-Way Cellular Automata

    • Véronique Terrier

    Pages 251-262

This volume constitutes the thoroughly refereed proceedings of the 21st International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2015, held in Turku, Finland, in June 2015. This volume contains 4 invited talks in full-paper length and 15 regular papers, which were carefully reviewed and selected from a total of 33 submissions. Topics of interest include, the following aspects and features of such systems: dynamical, topological, ergodic and algebraic aspects; algorithmic and complexity issues; emergent properties; formal language processing aspects; symbolic dynamics; models of parallelism and distributed systems; timing schemes; phenomenological descriptions; scientific modeling; and practical applications.

• Automata networks
• Automata theory
• Cellular automata
• Combinatorics on grids
• Computability
• Conservation laws
• Density classification
• Discrete complex system
• Dynamical system
• Emergent computation
• Formal languages
• Graph dynamical systems
• Intrinsic universality
• Percolation
• Phase transition
• Probabilistic cellular automata
• Reversible computation
• SAT solving
• Symbolic dynamics
• Synchronization

• University of Turku, Turku, Finland

  Jarkko Kari

Policies and ethics