Cellular Automata and Discrete Complex Systems : 23rd IFIP WG 1.5 International Workshop, AUTOMATA 2017, Milan, Italy, June 7-9, 2017, Proceedings

This volume constitutes the thoroughly refereed proceedings of the 23rd IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2017, held in Milan, Italy, in June 2017. The 14 full papers presented together with one full-length invited paper and 2 invited talk abstracts were carefully reviewed and selected from a total of 28 submissions. The papers feature research on correlated models of automata. The topics include aspects and features of such models: dynamics; topological, ergodic, and algebraic aspects; algorithmic and complexity issues; emergent properties; formal languages; symbolic dynamics; tilings; models of parallelism and distributed systems; timing schemes; synchronous versus asynchronous models; phenomenological descriptions; scientific modelling; practical applications. Preface 6 Organization 7 Abstracts of Invited Talks 9 Two Dimensional Cellular Automata and Computational Complexity 10 Fixed Points in Boolean Networks 12 Contents 13 Invited Papers 15 Strict Asymptotic Nilpotency in Cellular Automata 16 1 Introduction 16 2 Nilpotency on Multidimensional Full Shifts 16 3 Nilpotency from a Subset of Configurations 17 4 Nilpotency on Multidimensional Subshifts 18 4.1 SFTs 19 4.2 Sofics (and Beyond) 20 5 Nilpotency as Uniform Convergence to a Point 21 6 Cellular Automata on Graphs and Groups 23 6.1 What Works on General Groups? 24 7 CA with Very Sparse Spacetime Diagrams 25 References 27 Regular Papers 29 Infinite Two-Dimensional Strong Prefix Codes: Characterization and Properties 30 1 Introduction 30 2 Preliminaries 32 3 Two-Dimensional Codes 33 4 Infinite Strong Prefix Codes 35 5 Measure of Two-Dimensional Languages and Codes 38 References 41 Restricted Binary Strings and Generalized Fibonacci Numbers 43 1 Introduction 43 2 A Simple Bijection and Some Applications 44 3 Number of 1's in the Strings of Fn(k) 47 4 Conclusion 53 References 53 Von Neumann Regular Cellular Automata 55 1 Introduction 55 2 Regular Cellular Automata 57 3 Regular Finite Cellular Automata 60 4 Regular Linear Cellular Automata 63 References 66 Enumerative Results on the Schröder Pattern Poset 67 1 Introduction 67 2 The Covering Relation in the Schröder Pattern Poset 69 3 Enumerative Results on Pattern Avoiding Schröder Paths 72 3.1 The Pattern (UD)k 73 3.2 The Pattern Uk Dk 74 3.3 The Pattern H2 k 74 3.4 The Pattern UH2 k-1D 75 3.5 The Pattern H2 k-1UD 76 4 Suggestions for Further Work 78 References 78 Canonical Form of Gray Codes in N-cubes 79 1 Introduction 79 2 Canonical Form of Gray Codes 80 2.1 Isomorphic Cycles 80 2.2 Preliminary Tools 81 2.3 Canonical Form 83 2.4 Examples of Application of C 84 2.5 Discussion over the Interest of the Canonical Form 86 3 Balanced Gray Codes Generation Algorithm 86 4 Application 88 4.1 Validation of the Canonical Form and the Generation Algorithm 88 4.2 Application of the Balanced Gray Code Generation Algorithm 88 5 Conclusion 90 References 90 Equicontinuity and Sensitivity of Nondeterministic Cellular Automata 92 1 Introduction 92 2 Preliminaries 93 2.1 Cellular Automata 93 2.2 Nondeterministic Cellular Automata 94 3 Equicontinuity 96 4 Sensitivity 100 5 Transitivity 104 6 Conclusions 105 References 106 Diploid Cellular Automata: First Experiments on the Random Mixtures of Two Elementary Rules 108 1 Introduction 108 2 Definitions 109 3 First Steps in the Space of Diploids 113 3.1 Experimental Protocol 113 3.2 Mixtures with the Null Rule (ECA 0) 114 3.3 Mixtures with the Identity Rule: -asynchronous ECA 116 3.4 Mixtures with the Inversion Rule (ECA 51) 117 4 Discussion 118 References 119 On the Computational Complexity of the Freezing Non-strict Majority Automata 120 1 Introduction 120 2 Preliminaries 121 3 A Characterization of Stable Sets 123 4 The Algorithm 127 5 Conclusion 128 References 129 Distortion in One-Head Machines and Cellular Automata 131 1 Introduction 131 2 Definitions 132 2.1 Subshifts and Cellular Automata 132 2.2 Neighborhoods and Radii 132 2.3 Distortion 133 3 Distorted One-Head Machines 134 3.1 One-Head Machines 134 3.2 Speed Trichotomy 135 3.3 Aperiodic Machines 139 3.4 Distortion on Sofic Shifts 139 3.5 Undecidability of Distortion 141 4 Unbalanced Distortion in General Subshifts 142 5 Future Work 148 References 148 Fast One-Way Cellular Automata with Reversible Mealy Cells 150 1 Introduction 150 2 Preliminaries and Definitions 152 3 The Computational Capacity of One-Way Mealy Cellular Automata with Weakly Reversible Cells 156 4 Reversible One-Way Partitioned Cellular Automata 157 5 Conclusions 160 References 161 Enumerating Orthogonal Latin Squares Generated by Bipermutive Cellular Automata 162 1 Introduction 162 2 Preliminaries 163 2.1 Basic Definitions 163 2.2 Latin Squares Generated by Cellular Automata 165 3 Main Results 167 4 Enumeration of Pairwise Balanced Bipermutive Rules 170 5 Conclusions 173 References 174 Filling Curves Constructed in Cellular Automata with Aperiodic Tiling 176 1 Introduction 176 2 Constructions and Fillings 177 2.1 Cellular Automata 177 2.2 Tile Set 178 3 Aperiodic Tile Set 179 3.1 From Tile Set Determinism to Cellular Automaton 179 3.2 A NW-Deterministic Aperiodic Tile Set 180 4 Aperiodic Filling 181 4.1 Linear Functions 182 4.2 Over-Logarithmic Growth Functions 183 5 Conclusions and Perspectives 185 References 186 Some Computational Limits of Trellis Automata 187 1 Introduction 187 2 Trellis Automaton 188 3 Factors Diagram for a Language 190 4 Trellis Automaton Patterns and Language Patterns 191 5 Counting Argument 193 6 Some Non Trellis Language 195 7 Conclusion 197 References 197 Turing-Completeness of Asynchronous Non-camouflage Cellular Automata 198 1 Introduction 198 2 Preliminaries 199 2.1 Asynchronous CA 199 2.2 Requirements 201 2.3 Priese System 202 3 Proposing Asynchronous Non-camouflage CA 204 3.1 Proposed CA M 204 3.2 Simulation of s-automaton 204 4 Discussion 209 References 210 Author Index 211 Front Matter....Pages I-XVI Front Matter....Pages 1-1 Strict Asymptotic Nilpotency in Cellular Automata....Pages 3-15 Front Matter....Pages 17-17 Infinite Two-Dimensional Strong Prefix Codes: Characterization and Properties....Pages 19-31 Restricted Binary Strings and Generalized Fibonacci Numbers....Pages 32-43 Von Neumann Regular Cellular Automata....Pages 44-55 Enumerative Results on the Schröder Pattern Poset....Pages 56-67 Canonical Form of Gray Codes in N-cubes....Pages 68-80 Equicontinuity and Sensitivity of Nondeterministic Cellular Automata....Pages 81-96 Diploid Cellular Automata: First Experiments on the Random Mixtures of Two Elementary Rules....Pages 97-108 On the Computational Complexity of the Freezing Non-strict Majority Automata....Pages 109-119 Distortion in One-Head Machines and Cellular Automata....Pages 120-138 Fast One-Way Cellular Automata with Reversible Mealy Cells....Pages 139-150 Enumerating Orthogonal Latin Squares Generated by Bipermutive Cellular Automata....Pages 151-164 Filling Curves Constructed in Cellular Automata with Aperiodic Tiling....Pages 165-175 Some Computational Limits of Trellis Automata....Pages 176-186 Turing-Completeness of Asynchronous Non-camouflage Cellular Automata....Pages 187-199 Back Matter....Pages 201-201