Cellular Automata: 8th International Conference on Cellular Automata for Research and Industry, ACRI 2008, Yokohama, Japan, September 23-26, 2008, Proceedings (Lecture Notes in Computer Science, 5191)

Annotation This book constitutes the refereed proceedings of the 8th International Conference on Cellular Automata for Research and Industry, ACRI 2008, held in Yokohama, Japan, in September 2008. The 43 revised full papers and 22 revised poster papers presented together with 4 invited lectures were carefully reviewed and selected from 78 submissions. The papers focus on challenging problems and new research not only in theoretical but application aspects of cellular automata, including cellular automata tools and computational sciences. The volume also contains 11 extended abstracts dealing with crowds and cellular automata, which were presented during the workshop C & CA 2008. The papers are organized in topical sections on CA theory and implementation, computational theory, physical modeling, urban, environmental and social modeling, pedestrian and traffic flow modeling, crypto and security, system biology, CA-based hardware, as well as crowds and cellular automata front-matter fulltext From CA to Gene Expression: Machines and Mechanisms Introduction Traffic of Kinesins on Microtubule Track: Change of Lane? Traffic of RNAP Motors on DNA Tracks Conclusion References fulltext_2 What’s New in Wolfram’s New Kind of Science? fulltext_3 Quantum Walks and Quantum Cellular Automata Introduction QW QCA and QW QCA and SCA References fulltext_4 Modelling of Transport and Traffic Problems Introduction Asymmetric Simple Exclusion Process (ASEP) Highway Traffic Empirical Results NaSch Model Extensions of the NaSch Model Ant Trails Pedestrian Dynamics Molecular Motors Discussion References fulltext_5 Occurrence of Gliders in an Infinite Class of Life-Like Cellular Automata Introduction An Infinite Class of Life-Like Cellular Automata Useful Configurations in the Kaleidoscope of Life Gliders in the Infinite Class of Cellular Automata Probabilistic Analysis Conclusions and Discussion References fulltext_6 Cellular Automata-Based Structures to Compute the Solutions of Linear Difference Equations Introduction Fundamentals and Basic Notation Linear Difference Equations with Binary Coefficients One-Dimensional Linear Hybrid CA Generalization to More Complex Difference Equations Realization of the Linear Difference Equation Solutions by Means of CA Illustrative Example Conclusions References fulltext_7 Computing by Swarm Networks Introduction Computational Elements Model of the Agents Building Circuits by Swarm Networks Conclusions and Discussion References fulltext_8 On a Membrane Formation in a Spatio-temporally Generalized Prisoner’s Dilemma Introduction Definitions and Notations of Generalized Prisoner's Dilemma Membrane Formation Discussions References fulltext_9 An Asynchronous Cellular Automaton Implementing 2-State 2-Input 2-Output Reversed-Twin Reversible Elements Introduction Reversible Logic Elements Construction of RE by the Reversible Elements Embedding Reversible Elements in STCA Conclusions and Discussion References fulltext_10 Game ‘Life’ with Anticipation Property Introduction ‘LifeA’ Model: A Brief Description Next State Function Anticipation Topology of the Example Simulation Results Discussion References fulltext_11 On the Representation of Gliders in Rule 54 by De Bruijn and Cycle Diagrams Preliminaries Gliders in Rule 54 De Bruijn Diagrams Calculating Gliders in Rule 54 Cycle Diagrams Calculating Gliders in Rule 54 Coding Rule 54 Conclusions References fulltext_12 A Cellular Automaton Model for Tribological Problems Introduction Friction and Wear in the Interface of Brake Systems A Cellular Automaton Model to Describe the Interface Dynamics Summary, Conclusions and Outlook References fulltext_13 Stabilizing and Destabilizing Effects of Embedding 3-Node Subgraphs on the State Space of Boolean Networks Introduction Model and Method Boolean Network Numerical Condition Path Length Complexity of State Space Entropy and Mutual Information Results Discussion Control Parameters for Boolean Networks Differences in Correlation Productivity References fulltext_14 About 4-States Solutions to the Firing Squad Synchronization Problem The Firing Squad The Rule 60 Based Solution The Rule 150 Based Solutions Strict Optimum-Time Solution Simple Folding Variants of Rule 150 Based Solution Conclusion References fulltext_15 Evaluating Cellular Automata Models by Evolutionary Multiobjective Calibration Introduction Multiobjective Optimization of Cellular Automata An Application Example Conclusions References fulltext_16 Entropy and Chaos in a Lattice Gas Cellular Automata Introduction Model Lyapunov Exponents Entropy Results and Discussion References fulltext_17 Analysis of 90/150 Two Predecessor Nongroup Cellular Automata Introduction CA Preliminaries An Algorithm for Finding 90/150 Two Predecessor CA Analysis of 90/150 Two Predecessor CA Conclusion References fulltext_18 Analysis of Linear Group $GF$(2^{p}) Cellular Automata Introduction Linear $GF$(2^{p}) CA Preliminaries Characterization of Linear Group $GF$(2^{p}) CA The Relationship between Characteristic Polynomial and Transition Rule of Linear $GF$(2^{p}) CA Conclusion References fulltext_19 On the Collision-Propagation and Gather-Update Formulations of a Cellular Automata Rule Introduction Cellular Automata on a Graph Topology Equivalence between the Gather-Update and Collision-Propagation Formulation Invertible CA Conclusions References fulltext_20 Exploring $CA$ State Space to Synthesize CellularAutomata with Specified Attractor Set Introduction Characterization of Single Cycle Attractors Identification of Attractors of a $CA$ Extraction of $PE$-Bits Synthesis of $CA$ with Single Cycle Attractors Conclusion References fulltext_21 Characterization of Non-reachable States in Irreversible $CA$ State Space Introduction Cellular Automata Basics Reachability Tree Characterization of $CA$ Targeting Non-reachable States and the Attractors Computing the Number of Non-reachable States Computing the Number of Attractors Conclusion References fulltext_22 An Efficient n $ imes$ n Boolean Mapping Using Additive Cellular Automata Introduction Reaching States Far from Initial State of CA Using Very Few Cycles Exploring Full State Space An n $ imes$ n Boolean Mapping Statistical Tests Implementation Conclusion References fulltext_23 Controlling the Dynamics of the Fuzzy Cellular Automaton Rule 90, I. Introduction Basic Definitions Cellular Automata Fuzzy Cellular Automata Control of Fuzzy Rule 90 Problem Statement The Case of an Excited Cell with a Single Initial Seed in a Background of Zeros References fulltext_24 Examples of Fast and Slow Convergence of 2D Asynchronous Cellular Systems Introduction Definitions Convergence Times A {it Coupon Collector} Automaton The {it Majority} Rule The {it Epidemic} Automaton An {it Erratic} Automaton The Parity Counter Concluding Remark References fulltext_25 Multi-scale Modeling with Cellular Automata: The Complex Automata Approach Introduction Multi-scale Cellular Automata Complex Automata Preliminary Definitions Complex Automata Formalism Coupled Evolution of a CxA Error Analysis Conclusions References fulltext_26 Reconfiguring Circuits Around Defects in Self-Timed Cellular Automata Introduction Preliminaries Self-Timed Cellular Automaton Laying Out Circuit Modules on STCA Scanning Non-defective Areas and Placing Modules Computation by the Modules Conclusion References fulltext_27 Theory of Composing Non-linear Machines with Predictable Cyclic Structures Introduction Preliminaries on Cellular Automata and Non-linearity of Boolean Functions Proposed Composition of the Non-linear Cellular Automata with Group Properties Construction of Small Non-linear Invertible CA Construction of 6 Cell Non-linear Group Cellular Automata Conclusion References fulltext_28 Combined Effect of Topology and Synchronism Perturbation on Cellular Automata: Preliminary Results Introduction Definitions and Experimental Protocol Perturbed Cellular Automata Experimental Protocol Exhaustive Study of the ECA Space Rules Insensitive to Both Perturbations Rules Sensitive Only to Synchronism Perturbation Rules Sensitive Only to Topology Perturbation Rules Sensitive to Both Perturbations Discussion and Perspectives References fulltext_29 Finite Size Stability Analysis for Stochastic Cellular Automata Introduction Model Simulation Results Conclusions and Discussions References fulltext_30 On the Addition of Recurrent Configurations of the Sandpile-Model Introduction Basics The Problem Number of Grains in Recurrent Configurations Examples Searching for Local Minima Minimizing f_{c+d} for Fixed c The Cutting Algorithm The Local Minimum Condition Outline of the Algorithm Analysis Strategies for Choosing the Toppling Sequence Conclusion References fulltext_31 A Construction Method of Moore Neighborhood Number-Conserving Cellular Automata Introduction Definitions Von Neumann Neighborhood Number-Conserving Cellular Automata A Sufficient Condition Based on Quaternary Functions A Logically Universal NCCA Conclusion References fulltext_32 Changing Neighborhoods of CA: Reduced Local Structures and Embeddings for Universality Introduction Basics Reduced Local Structures Equivalence of Local Structures Universality Revisited A Short Review of the Construction Discussion of the Embedding Summary and Outlook References fulltext_33 Error Investigations in Complex Automata Models for Reaction-Diffusion Systems Introduction Complex Automaton for a Reaction-Diffusion System Error Investigations Numerical Results References fulltext_34 Simulation of the Effect of Intermittent Flow in Polycrystals on the Basis of Cellular Automata and Relaxation Element Method Introduction The Peculiarities of the Simulation by Relaxation Element Method Results Conclusions References fulltext_35 Lattice Gas Automata Simulation of 2D Site-Percolation Diffusion: Configuration Dependence of the Theoretically Expected Crossover of Diffusion Regime Introduction Results and Discussion Conclusion References fulltext_36 Study on Acoustic Field with Fractal Boundary Using Cellular Automata Introduction The Cellular Automata Model for Wave Propagation Space Partitioning and State Definition Definition of Local Rules Generating Fractal Pattern with CA Wave Propagation in a Cavity with Fractal Boundary Frequency Response of Sound Pressure Inside Fractal Cavity Equivalent Absorption Coefficient Conclusions References fulltext_37 The Heart Pacemaker by Cellular Automata on Complex Networks Introduction The Network Topology The FRA Cellular Automaton Results Conclusions References fulltext_38 A Proposal for a Japanese Keyboard on Cellular Phones Introduction A Few Words on the Pentagrid The Proposal For the Cell Phones Conclusion References fulltext_39 Quick Energy Drop in Stochastic 2D Minority Introduction Definitions Proof Decreasing Sequences Enumeration of Acceptable Coloring References fulltext_40 The Diffusion of Perturbations in a Model of Coupled Random Boolean Networks Introduction Random Boolean Networks (RBN) Multi Random Boolean Network (MRBN) Experiments Results Conclusions References fulltext_41 Research into the Generation of Sound Effects Using a Cellular Automaton Introduction Related Study Wave Propagation CA Model Proposed Method Parameters Basic Parameters Tonal Parameters Generated Sound Examples Conclusion References fulltext_42 Modelling Combined Subaerial-Subaqueous Flow-Like Landslides by Cellular Automata Introduction A $CA$ Model for Combined Subaerial-Subaqueous Flow-Like Landslides The Model SCIDDICA-SS2 The SCIDDICA-SS2 Transition Function Simulations of the 1997 Albano Lake Debris Flow Conclusions References fulltext_43 Unstructured Cellular Automata and the Application to Model River Riparian Vegetation Dynamics Introduction Study Site Model Development Model Framework Hydrodynamic Module Vegetation Module Model Results Hydrodynamic Model Outputs Vegetation Model Outputs Discussions References fulltext_44 Improving the Behavior of Creatures by Time-Shuffling References fulltext_45 Contact Network Modeling of Flu Epidemics Introduction Methodology Generating the Contact Network Disease Spreading and Intervention Mechanisms Results and Discussion Evaluation and Future Work References fulltext_46 A Slight Delay in the Onset of Conservation May Bring about an Abrupt Increase of Extinction Risk: Perturbation Experiments in an Ecological Lattice Model Introduction Model and Method Contact Process (CP) Fluctuation Enhancement (FE) Perturbation Experiments (PE) Results Results of the Extinction Process(First PE) Results of the Recovering Process(Second PE) Discussion and Conclusion References fulltext_47 Lattice Population and Optimality of Sex Ratio: Effect of Sterile Male Introduction Model and Method Model Simulation Methods Mean-Field Theory Simulation Results Results of Global Simulation Results of Local Simulation Conclusion and Discussions References fulltext_48 Real Option Approach to Quoting Queueing System Introduction Analogy between the ASEP and Real Option Concept The ASEP and Domain Wall Dynamics Valuing a Queue Nonlinear Property Conclusion References fulltext_49 Modeling of Environmental Effects on Bridge Components: Possibilities of Cellular Programming Introduction Spatial Simulation of Chloride Penetration Based on Cellular Automaton Field of Application Diffusion Equation Cellular Automata Local Degradation Modeling and Probabilistic Simulation Case Studies An Application to an Existing Bridge Reinforcement Corrosion Conclusions References fulltext_50 A CA Model of Spontaneous Formation of Concentration Gradients Introduction The Model and Its Behaviour The Limiting Case of Two Homogeneous Compartments Conclusions References fulltext_51 Applying a Cellular Automata Method for the Study of Transport and Deposition of Volcanic Particles Introduction Tephra Transport Model Cellular Automata Tephra Transport Model Eruptions and Simulation Parameters Results and Discussion References fulltext_52 Global and Local Processes in a Model of Innovation Introduction Theory and Model A Brief Description of the Basic Model The Topology The Model Behaviour: A Preliminary Analysis Conclusions References fulltext_53 GP Generation of Pedestrian Behavioral Rules in an Evacuation Model Based on SCA Introduction SCA Approach to Pedestrian Dynamics Genetic Programming Modeling Pedestrian Behavior for Evacuation with GP Conclusions and Future Works References fulltext_54 A Three-Dimensional Pedestrian-Flow Simulation for High-Rising Buildings Introduction System Configuration Floor-Flow Model Elevator-TrafficModel Pedestrian-Motion Model for an Elevator Hall Verification Summary References fulltext_55 Compartment Lines Forming Emergent Alternative Configurations of Vehicles on Weaving Sections Introduction Compartment Lines on Weaving Sections Modeling for Simulations and the Four ClusterApproximation A CA Model of Weaving Sections along a Compartment Line MLSOV Model as the Dynamics along a Compartment Line The Four Cluster Approximation Quantifying the Degree of the Alternative Configurations in CA The Results of the Simulations and the Four ClusterApproximation Conclusive Discussions References fulltext_56 Real-Time Railway Network Simulator “KUTTY” Introduction Database Network Structure Origin-Destination Estimation Models and Homogenization System Model of Passengers Model of Trains Homogenization System Simulations and Results Conclusion References fulltext_57 Cellular Automata Simulation of Traffic Jam in Sag Section Introduction Simulation Model Object Under Consideration Local Rules Numerical Results Traffic Jam in Sag Zone Behavior of a Car Conclusions References fulltext_58 Simulation of Fire Evacuation by Real-Coded Cellular Automata (RCA) Introduction NumericalMethod RCA Model for Pedestrian Dynamics Percolation Model for Flame Spread in Fire Calculation Domain Results and Discussion Evacuee Velocity and Distance from Spreading Flame Effect of Exit Location Conclusions References fulltext_59 Walking-Distance Introduced Queueing Theory Introduction Walking-Distance Introduced Queueing Theory Walking Distances Update Rules Mean Field Analysis Comparison of a Parallel Queue and a Fork Queue Method for Decreasing Waiting Time and Stress Conclusion References fulltext_60 An Improved Double Byte Error Correcting Code Using Cellular Automata Introduction CA-Based Double Byte Error Correcting Code Cellular Automata Preliminaries Overview of the CA-Based Double Byte Error Correcting Code Weakness and Limitation of the CA-Based DoubleByte Error Correcting Code Weakness of the CA-Based Double Byte Error Correcting Code Limitation of the CA-Based Double Byte Error CorrectingCode Our Improved Scheme Conclusion References fulltext_61 Nonlinear Pseudorandom Sequences Based on 90/150 LHGCA Introduction Preliminaries Interleaved Sequences SI Sequence Based on 90/150 LHGCA Conclusion References fulltext_62 Cryptographically Strong S-Boxes Based on Cellular Automata Introduction S-Boxes in Cryptography The Most Important Cryptographic Criteria forBoolean Functions Cellular Automata Cellular Automata and Constructing S-Boxes Designing CA-Based S-Boxes and Their Analysis Searching for CA Rules and Construction of CA-Based S-Boxes Comparison of CA-Based S-Boxes with Classical S-Boxes Conclusions and Future Work References fulltext_63 Computational Hematology in Systems Biology Introduction Methods Compartmentalization of Granulopoiesis Stem Cell Division Model Development of a CA Model Description of the Local Neighbor Rules Results Homeostatic Production of Granulocyte-Lineage Cells A Model for Anticancer Drug-Induced Neutropenia Simulation Studies of G-CSF Administration for the Treatment of Neutropenia Simulation Studies for Hematopoietic Stem Cell Transplantation (HSCT) Discussion References fulltext_64 Dynamically Reorganising Vascular Networks Modelled Using Cellular Automata Approach Introduction Tumour-Induced Angiogenesis Model with Vascular Network Reorganisation Results Quantitative Verification Conclusions References fulltext_65 A Stochastic Multi-agent Model of Stem Cell Proliferation Introduction Hierarchical Stem Cell Proliferation A Multi-agent Model Based on HSP A Case Study Extending the Base Model: Agents with Chromosomes Simulating BrdU Kinetics in Murine Hematopoietic Stem Cells Results and Comparison to Existing BrdU Models Conclusion References fulltext_66 coreBIST: A Cellular Automata Based Core for Self Testing System-on-Chips Introduction State-of-the-Art of Pseudo-random BIST coreBIST - Concept and Design Pseudo-random Test Pattern Generation Output Response Analyzer Experimental Results Conclusion References fulltext_67 GPU Accelerated Computation and Visualization of Hexagonal Cellular Automata Introduction Previous Work Current Model: GPU-Accelerated 2DhbCA Performance Conclusions and Future Work References fulltext_68 Automatic Design of FPGA Processor for the Backtracking of DNA Sequences Evolution Using Cellular Automata and Genetic Algorithms Introduction Modeling DNA in Terms of Cellular Automata CAs for DNA CAD Tool Automatic FPGA Implementation Conclusions References fulltext_69 From Data and Signals Cellular Automata to Self-organizing Circuits Introduction DSCA Based Reconfigurable Circuit Circuit Characteristics Configuration Layer Application Layer Routing Layer Multi-processor Application MOVE Processor Timer Application POEtic Implementation Conclusion References fulltext_70 Integrated Simulation and Information Sharing System for Disaster Mitigation fulltext_71 Towards an Ontology for Crowds Description:A Proposal Based on Description Logic DL Language for Ontology Representation Elias Canetti's Crowd Concluding Remarks References fulltext_72 Towards a Multi-agent Model for Planning andDesign of Exposition Spaces Introduction Outline of the Model Behaviour of Agents Model Development fulltext_73 Potential Field Approach of a Cellular Automaton Evacuation Model and Its FPGA Implementation Introduction Potential Field Approach to Pedestrian Movement Architecture of the Dedicated FPGA Processor Conclusions References fulltext_74 Evolving Multi-creature Systems for All-to-All Communication References fulltext_75 Counterflow Extension for the F.A.S.T.-Model Introduction Extension of the F.A.S.T.-Model by a Comoving Dynamic Potential Simulation Results Conclusions and Outlook References fulltext_76 Conflicts and Friction in Pedestrian Dynamics Introduction The Floor Field Model Conflicts and Friction Evacuation Simulations Conclusions fulltext_77 Fundamental Diagram and Validation of CrowdModels Introduction Specifications and Measurements Influence of the Measurement Method fulltext_78 Multi-agent Frame of Social Distances Model Introduction Short Description of Social Distances Model Adaptation of Social Distances for Complex Modeling of Pedestrians Traffic Rules of Movement Familiarities in Social Distances Model Concluding Remarks fulltext_79 Evacuation Simulation in Floor Field by Real-Coded Cellular Automata Introduction Numerical Model Simulation Results Summary and Future Work References back-matter