Cellular Automata and Discrete Complex Systems: 29th IFIP WG 1.5 International Workshop, AUTOMATA 2023, Trieste, Italy, August 30 – September 1, 2023, Proceedings (Lecture Notes in Computer Science)

This book constitutes the proceedings of the 29th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2023, which took place in Trieste, Italy, in August/September 2023. For AUTOMATA 2023, 7 full papers have been carefully reviewed and selected from 11 submissions. The book also contains 3 full papers from AUTOMATA 2022, which have been selected from a total of 18 submissions. In addition, the proceedings contain one invited talk in full paper length from AUTOMATA 2023. Preface Organization – AUTOMATA 2023 Organization – AUTOMATA 2022 Sandpile Models and P-completeness (Abstracts of Invited Talk) Contents Invited Paper Isometric Words and Edit Distance: Main Notions and New Variations 1 Introduction 2 Basic Notation on Words 3 Hamming Distance and Isometric Words 4 Variations on Isometric Words 4.1 Lee-Isometric Words 4.2 Tilde-Isometric Words 4.3 Isometric Two-Dimensional Words 5 Isometric Sets of Words References Regular Papers – AUTOMATA 2023 On the Surjunctivity and the Garden of Eden Theorem for Non-uniform Cellular Automata 1 Introduction 2 Definitions 3 Non-uniform Cellular Automata 4 Garden of Eden Theorem 5 Surjunctivity 6 Conclusions References Diddy: A Python Toolbox for Infinite Discrete Dynamical Systems 1 Introduction 2 Definitions 3 Representations 4 Defining Topologies, SFTs and Block Maps 5 Comparing SFTs 6 Computing and Comparing Block Maps 7 Minimum Density 7.1 Upper Bounds by Periodic Configurations 7.2 Lower Bounds by Discharging 8 Future Directions References Convergence of Vector-Valued Fuzzy Cellular Automata with Weighted-Averaging Rules 1 Introduction 1.1 Our Contributions 1.2 Related Works 2 Weighted-Averaging Rules in VFCA 3 Convergence of VFCA with Weighted-Averaging Rules 3.1 Commutative Case of the Weighted-Averaging Rules of Type 1 3.2 Non-commutative Case of the Weighted-Averaging Rules of Type 1 3.3 Weighted-Averaging Rules of Type 2 4 Conclusion References A Decentralised Diagnosis Method with Probabilistic Cellular Automata 1 Introduction 2 The Isotropic Model 2.1 Numerical Experiments 3 A Directional Model: The Biased-Quiescent Rule 3.1 Definition of the Rule 3.2 Change of Representation and Partial Order on Configurations 3.3 Initial Configuration with only One Alert and No Defect 3.4 Initial Configuration with only One Defect 3.5 Initial Configuration with a Positive Density of Defects References Optimized Reversible Cellular Automata Based Clustering 1 Introduction 2 Related Works and Our Contribution 3 Methodology 3.1 Selection of Proper Rules 3.2 A New Encoding Technique: BiNCE Encoding 4 Implementation and Results 4.1 Packaging as a Python Module 4.2 Evaluation Metrics 4.3 Datasets 4.4 Results 5 Conclusion References Multiple-Stream Parallel Pseudo-Random Number Generation with Cellular Automata 1 Introduction 2 Background 2.1 Cellular Automata 2.2 The Temper Function in Mersenne Twister 2.3 Testing 3 CA as Multiple Stream Parallel Generator 4 CA(150') Based Parallel PRNG 4.1 Bitwise Implementation 4.2 PRNG with Jumping Ahead 4.3 Finding the Best Seed 4.4 The Carry Bits 4.5 GPU Implementation of the PRNG and Speed Test 5 Conclusion and Future Work References On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata 1 Introduction 2 Basic Definitions 2.1 Cellular Automata 2.2 Subspace Codes 3 Subspaces Codes from Families of Linear CA 3.1 Computing Preimage of Linear CA with Linear Feedback Shift Register 4 Relation Between Minimum Distance and GCD 5 Equidistant Constant Dimension Codes from Linear CA 5.1 Example 6 Conclusions and Future Works References Regular Papers – AUTOMATA 2022 Triangle Solitaire 1 Introduction 2 Definitions 3 Characterisation of the Orbits 3.1 Notations and First Result 3.2 The Filling Process 3.3 Characterisation of the Orbit Through the Filling 3.4 Excess Sets 4 Algorithmic Aspects 4.1 Complexity of the Identification of the Orbit of a Pattern 4.2 Number of Steps Needed to Put a Pattern in Normal Form 5 Size of the Line Orbit 6 Bases 7 Prospects for Future Work References Pattern Classification with Temporally Stochastic Cellular Automata 1 Introduction 2 Temporally Stochastic Cellular Automata 2.1 Dynamical Behaviour 2.2 Convergence 3 Multiple Attractor TSCA as Pattern Classifier 3.1 Training Phase 3.2 Testing Phase 3.3 Margin of Error 3.4 Comparison 4 Conclusion References Building Correlation Immune Functions from Sets of Mutually Orthogonal Cellular Automata 1 Introduction 2 Preliminary Definitions 2.1 Boolean Functions and Orthogonal Arrays 2.2 Cellular Automata and Latin Squares 3 Construction of Correlation Immune Functions 4 Computational Search Results 5 Conclusions References Author Index