Cellular Automata and Discrete Complex Systems: 22nd IFIP WG 1.5 International Workshop, AUTOMATA 2016, Zurich, Switzerland, June 15-17, 2016, Proceedings ... Notes in Computer Science Book 9664)

This volume constitutes the thoroughly refereed proceedings of the 22nd IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2016, held in Zurich, Switzerland, in June 2016. This volume contains 3 invited talks in full-paper length and 12 regular papers, which were carefully reviewed and selected from a total of 23 submissions. The papers feature research on all fundamental aspects of cellular automata and related discrete complex systems and deal with the following topics: dynamical, topological, ergodic and algebraic aspects; algorithmic and complexity issues; emergent properties; formal language processing; symbolic dynamics; models of parallelism and distributed systems; timing schemes; phenomenological descriptions; scientific modeling; and practical applications. Front Matter....Pages I-XVI Front Matter....Pages 1-1 Propagation, Diffusion and Randomization in Cellular Automata....Pages 3-9 What Automata Can Provide a Medium for Life?....Pages 10-25 A Brief Tour of Theoretical Tile Self-Assembly....Pages 26-31 Front Matter....Pages 33-33 The Corona Limit of Penrose Tilings Is a Regular Decagon....Pages 35-48 The Group of Reversible Turing Machines....Pages 49-62 Exact Discretization of 3-Speed Rational Signal Machines into Cellular Automata....Pages 63-76 An “almost dual” to Gottschalk’s Conjecture....Pages 77-89 On Finite Monoids of Cellular Automata....Pages 90-104 Sum of Exit Times in Series of Metastable States in Probabilistic Cellular Automata....Pages 105-119 Partial Reversibility of One-Dimensional Cellular Automata....Pages 120-134 Two-Dimensional Traffic Rules and the Density Classification Problem....Pages 135-148 Constant Acceleration Theorem for Extended von Neumann Neighbourhoods....Pages 149-158 Shrinking and Expanding Cellular Automata....Pages 159-169 An 8-State Simple Reversible Triangular Cellular Automaton that Exhibits Complex Behavior....Pages 170-184 Cellular Automata on Group Sets and the Uniform Curtis-Hedlund-Lyndon Theorem....Pages 185-198 Back Matter....Pages 199-199