Proceedings of First Asian Symposium on Cellular Automata Technology: ASCAT 2022 (Advances in Intelligent Systems and Computing)

This book gathers selected research papers presented at the First Asian Symposium on Cellular Automata Technology (ASCAT 2022), organized online by academicians from Kolkata, India, during March 3–5, 2022. The book presents one of the most emergent areas in natural computing, cellular automaton (CA). CA is a paradigm of uniform fine-grained parallel computation which has been explored to understand complex systems by developing its model at the microscopic level. The book discusses many real-life problems in the domain of very large-scale integration (VLSI) design and test, pattern recognition and classification, cryptography, pseudo-random pattern generation, image processing, sensor networks, material science, etc., by using CA. Committees 6 Foreword 9 Preface 11 Contents 13 About the Editors 15 Invited Papers 16 Computing in a Simple Reversible and Conservative Cellular Automaton 17 1 Introduction 18 2 A New Model of Reversible and Conservative Cellular Automaton P0 19 3 Useful Patterns and Phenomena in P0 21 3.1 Useful Patterns in P0 21 3.2 Three Useful Phenomena in P0 23 4 Making Reversible Turing Machines in P0 24 4.1 Reversible Logic Element with Memory (RLEM) 24 4.2 Reversible Turing Machines Implemented in P0 28 5 Concluding Remarks 29 References 30 Algorithms for Group Cellular Automata 31 1 Introduction 31 2 Preliminaries 32 2.1 Subshifts and Cellular Automata 32 2.2 Group Shifts and Group Cellular Automata 33 3 Algorithms 34 3.1 Injectivity and Surjectivity 34 3.2 Density of Periodic Points 35 3.3 Nilpotency and Periodicity 36 3.4 Sensitivity and Equicontinuity 37 3.5 Mixing Properties 38 References 38 Revisiting Logic Obfuscation Using Cellular Automata 40 1 Introduction 41 2 Background 43 2.1 The Cellular Automata (CA) 43 2.2 A Non-group Additive CA: D1*CA 44 2.3 Properties of D1*CA 44 2.4 FSM Synthesis using D1*CA 45 3 FSM Obfuscation using Cellular Automata 46 3.1 The Obfuscation Technique 46 3.2 The ORACALL Attack Methodology 47 4 Incorporating Non-linearity to Thwart ORACALL 49 5 Experimental Results 51 6 Conclusion 53 References 53 Accepted Papers 55 Grade Estimation of Mineral Resources: An Application of Cellular Automata 56 1 Introduction 56 2 Preliminaries 58 2.1 Cellular Automata 58 2.2 Variogram Model and Krigging 59 3 Estimation of Grade Values Using Cellular Automata 60 4 Conclusion 64 References 64 Shape Generation Using Cellular Automata with Clustering 66 1 Introduction 66 2 Background 67 2.1 Cellular Automata 67 2.2 Cellular Automata with Clustering 68 2.3 Ant Sorting Using the Lumer and Faieta Model 69 2.4 Ant Sorting Using Clustered Cellular Automata 70 3 Shape Generation 70 3.1 Fitness-Based Strategies 71 3.2 FIFO Queue-Based Strategies 74 3.3 Priority Queue-Based Strategies 76 4 Conclusion 78 References 78 Evolution Patterns of Some One-Dimensional Non-uniform Cellular Automata 79 1 Introduction 79 2 Basic Concepts 80 3 Relation Between Local and Global Transition Function of a Non-uniform CA 82 4 Patterns of Evolution of a Non-uniform CA Under Some Transitions 83 5 Conclusion 86 References 87 Relationship of Two Discrete Dynamical Models: One-Dimensional Cellular Automata and Integral Value Transformations 88 1 Introduction 88 2 Mathematical Preliminaries 89 3 Wolfram Code of CA and IVT 91 3.1 Some Particular Wolfram Codes and Particular IVTs 92 4 Transition Function of a CA and IVT 93 5 Some Algebraic Results on CA and IVT 95 6 Conclusion 101 References 101 Emulating Mersenne Twister with Cellular Automata 103 1 Introduction 103 2 Background 105 2.1 Mersenne Twister 105 2.2 Cellular Automata 107 3 Phase I: Making Our Own PRNG 108 3.1 Choosing the Size of CA(150') 108 3.2 Need of Temper Function 110 3.3 Finding The Best Seed 110 3.4 Results and Comparison with MT 111 4 Phase II: Improving our PRNG by Non-linearity 113 4.1 Using Twist 114 4.2 XOR + MULTIPLY 115 5 Conclusion and Next Steps 115 References 116 Defining Reachability Tree Under Adiabatic and Reflexive Boundary Conditions 117 1 Introduction 117 2 Basics of Cellular Automata 118 2.1 Rule Min Term (RMT) 119 2.2 State Transition Diagram 120 2.3 Boundary of a Finite CA 120 3 Reachability Tree 122 3.1 Construction of Reachability tree 123 3.2 Reachability Tree for ABC 124 3.3 Reachability Tree for RBC 126 4 Conclusion 128 4.1 Future scope 129 References 129 First Degree Cellular Automata as Pseudo-Random Number Generators 130 1 Introduction 130 2 Background 131 2.1 Definitions 131 2.2 Desirable Properties of Cellular Automata 133 3 The Selection and Rejection Criteria 134 3.1 Selection Criterion: Maximum Information Flow on One Side 134 3.2 Rejection Criterion: Theoretical Filtering 135 4 Finding Rules for PRNG 136 4.1 Rule of First Degree 136 4.2 Development of PRNG 137 5 Conclusion 143 References 143 Asynchronous Cellular Automata as Randomness Enhancer 145 1 Introduction 145 2 Preliminaries 146 2.1 Cellular Automata 146 2.2 Asynchronous Cellular Automata & Reversibility 148 3 ACAs with Large Cycles 149 3.1 Recurrent ACAs 149 3.2 ACAs with Multi-length Attractor 150 4 ACAs with Large Cycles and Sense of Democracy 151 5 Empirical Verification of the Proposed ACAs-based Randomness Enhancer 152 6 Conclusion 153 References 156 Cellular-Automata Based Simulation of Dynamic Recrystallization and Statistical Analysis of Resulting Grain Growth 158 1 Introduction 158 2 Model Description 161 2.1 Static Recrystallization Model 161 2.2 Dynamic Recrystallization Model 162 2.3 Summary of Rules 164 2.4 Domain Setup 164 3 Result and Discussion 165 3.1 Realising Grain Growth in Dynamic Recrystallization 165 3.2 Examining Grain Growth Kinetics 167 4 Conclusion 169 References 170 A New Notion of Universality in Respect of Logic Gates Generation Capability of ECAs 172 1 Introduction 172 2 Elementary Cellular Automata 173 2.1 Basics 173 2.2 ECA as n-Input n-Output Block 174 3 Exploring Gate Design Capability of ECAs 176 3.1 Realization of Basic Gates 176 3.2 Comparison of Gate Design Capability of ECAs 178 4 Conclusion 178 References 194 Impact of Genetic Algorithm on Low Power QCA Logic Circuit with Regular Clocking 196 1 Introduction 196 2 Background and Related Work 197 2.1 QCA Basic 198 2.2 Regular Clocking 199 2.3 Genetic Algorithm 199 3 Proposed Method 200 3.1 Case Study 200 4 Power Analysis 202 4.1 Discussion 204 5 Conclusion 207 References 207 Cellular Automata Based Model for Finding Minimum Spanning Tree in Wireless Sensor Networks 209 1 Introduction 209 2 Preliminaries 210 2.1 Wireless Sensor Networks 210 2.2 Cellular Automata 210 2.3 Survey of Existing Work 211 2.4 Contribution of This Work 212 3 Proposed Work 212 3.1 Computation Using Cellular Automaton 212 3.2 Set of States 213 3.3 State Transition 213 3.4 Example 215 3.5 Implementation of CA Based Model in WSN 217 4 Simulation Results 221 5 Conclusion 223 References 224 A Novel Hash Function Based on Hybrid Cellular Automata and Sponge Functions 225 1 Introduction 226 2 Preliminaries 226 2.1 Basics of CA 226 2.2 Sponge Functions 227 2.3 Cryptographic Hash Functions 227 2.4 Omega-Flip Permutations 228 3 Related Work 228 3.1 Hash Functions Based on Cellular Automata 228 3.2 Hash Functions Based on Sponge Functions 229 3.3 Hash Functions Based on CA and Sponge Functions 229 4 Proposed Hash Function 230 4.1 Description of the Hash Function 230 4.2 Single Round of the Internal Function 231 5 Design Rationale 232 6 Security and Performance Analysis 233 6.1 Security Analysis 233 6.2 Performance Analysis 235 7 Conclusion and Future Work 236 References 236 Synthesis of Single Length Cycle Two Attractor CA Using NSRT Diagram 238 1 Introduction 238 2 CA Preliminaries 239 3 Next State RMT Transition Diagram 242 3.1 Identification of NSRs 243 3.2 Construction of NSRTD 244 4 Proposed Methodology 245 5 Conclusion 249 References 249 Author Index 250