Cellular automata make up a class of completely discrete dynamical systems, which have became a core subject in the sciences of complexity due to their conceptual simplicity, easiness of implementation for computer simulation, and their ability to exhibit a wide variety of amazingly complex behavior. The feature of simplicity behind complexity of cellular automata has attracted the researchers' attention from a wide range of divergent fields of study of science, which extend from the exact disciplines of mathematical physics up to the social ones, and beyond. Numerous complex systems containing many discrete elements with local interactions have been and are being conveniently modelled as cellular automata. In this book, the versatility of cellular automata as models for a wide diversity of complex systems is underlined through the study of a number of outstanding problems using these innovative techniques for modelling and simulation.
Lattice-gas cellular automata (LGCA) and lattice Boltzmann models (LBM) are relatively new and promising methods for the numerical solution of nonlinear partial differential equations. The book provides an introduction for graduate students and researchers. Working knowledge of calculus is required and experience in PDEs and fluid dynamics is recommended. Some peculiarities of cellular automata are outlined in Chapter 2. The properties of various LGCA and special coding techniques are discussed in Chapter 3. Concepts from statistical mechanics (Chapter 4) provide the necessary theoretical background for LGCA and LBM. The properties of lattice Boltzmann models and a method for their construction are presented in Chapter 5.
An accessible and multidisciplinaryintroduction to cellularautomata As the applicability of cellular automata broadens andtechnology advances, there is a need for a concise, yet thorough,resource that lays the foundation of key cellularautomata rules andapplications. In recent years, Stephen Wolfram's A New Kind ofScience has brought the modeling power that lies in cellularautomata to the attentionof the scientific world, and now, CellularAutomata: A Discrete View of the World presents all the depth,analysis, and applicability of the classic Wolfram text in astraightforward, introductory manner. This book offers anintroduction to cellular automata as a constructive method formodeling complex systems where patterns of self-organizationarising from simple rules are revealed in phenomena that existacross a wide array of subject areas, including mathematics,physics, economics, and the social sciences. The book begins with a preliminary introduction to cellularautomata, including a brief history of the topic along withcoverage of sub-topics such as randomness, dimension, information,entropy, and fractals. The author then provides a completediscussion of dynamical systems and chaos due to their closeconnection with cellular automata and includes chapters that focusexclusively on one- and two-dimensional cellular automata. The nextand most fascinating area of discussion is the application of thesetypes of cellular automata in order to understand the complexbehavior that occurs in natural phenomena. Finally, the continuallyevolving topic of complexity is discussed with a focus on how toproperly define, identify, and marvel at its manifestations invarious environments. The author's focus on the most important principles of cellularautomata, combined with his ability to present complex material inan easy-to-follow style, makes this book a very approachable andinclusive source for understanding the concepts and applications ofcellular automata. The highly visual nature of the subject isaccented with over 200 illustrations, including an eight-page colorinsert, which provide vivid representations of the cellularautomata under discussion. Readers also have the opportunity tofollow and understand the models depicted throughout the text andcreate their own cellular automata using Java applets and simplecomputer code, which are available via the book's FTP site. Thisbook serves as a valuable resource for undergraduate and graduatestudents in the physical, biological, and social sciences and mayalso be of interest to any reader with a scientific or basicmathematical background.
The thirty four contributions in this book cover many aspects of contemporary studies on cellular automata and include reviews, research reports, and guides to recent literature and available software.
International Conference on Cellular Automata for Research and Industry
8th International Conference on Cellular Automata for Research and Industry, ACRI 2008, Yokohama, Japan, September 23-26, 2008, Proceedings
Author: International Conference on Cellular Automata for Research and Industry
Publisher: Springer Science & Business Media
This volume constitutes the proceedings of the 8th International Conference on Cellular Automata for Research and Industry, ACRI 2008, which took place in Yokohama, Japan, September 23-26,2008. The conference, which was organized by YokohamaNational University, was the eighth in a series of conferences in- guratedin1994inRende, Italy, andfollowedbyACRI1996inMilan, Italy, ACRI 1998in Trieste, Italy, ACRI 2000in Karlsruhe, Germany, ACRI 2002in Geneva, Switzerland, ACRI2004inAmsterdam, TheNetherlandsandACRI2006inP- pignan, France. The ACRI conference has been traditionally focused on challenging problems and new research not only in theoretical but application aspects of cellular - tomata, including cellular automata tools and computational sciences. It is also concerned with applications and solutions of problems from the ?elds of physics, engineering, environmentscience, socialscienceandlifesciences.Itsprimarygoal istodiscussproblemsfromavarietyofscienti?c?elds, toidentify newissuesand to enlarge the research ?elds of cellular automata. Since its inception, the ACRI conference has attracted an ever-growing community and has raised knowledge andinterestinthe studyofcellularautomataforbothnewentrantsintothe ?eld aswellasresearchersalreadyworkingonparticularaspectsofcellularautomata. First invented by von Neumann, cellular automata models have been po- larizedandinvestigatedinmanyareasduring thelastfew decades.They provide a mathematically rigorous framework for a class of discrete dynamical systems that allow complex, unpredictable behavior to emerge from the deterministic - calinteractionsofmanysimple components operatinginparallelanddistributed manner.
The book introduces a hot topic of mathematics and computer science at the edge of hyperbolic geometry and cellular automata. A hyperbolic space is a geometric model where through a given point, there arc two distinct parallels to a given lino. A cellular automaton is a set of cells which are uniformly distributed in a space, connected locally and update their states by the same rule. The volume advances the novel results presented in volume 1 on a location of tiles in many tilings of the hyperbolic plane. These results arc appplied in further studios of cellular automata in non-traditional spaces. We discuss a wide range of applications from cell phones to the theoretical problems of tilings. Hyperbolic geometry is an essential part of theoretical astrophysics and cosmology, therefore ideas discussed in the book will play an important rote in the theory of relativity. Besides specialists of these traditional fields of application, many specialists of new domains start to show a growing interest both, to hyperbolic geometry and to cellular automata. This is especially the case in biology and in computer science. The book is unque because it skilfulliy hybridizes two different domains of geometry and computation in a way beneficial for mathematics, computer science and engineering. The book is an outstanding treatise of concepts and implementations which will last for decades.
The book presents findings, views and ideas on what exact problems of image processing, pattern recognition and generation can be efficiently solved by cellular automata architectures. This volume provides a convenient collection in this area, in which publications are otherwise widely scattered throughout the literature. The topics covered include image compression and resizing; skeletonization, erosion and dilation; convex hull computation, edge detection and segmentation; forgery detection and content based retrieval; and pattern generation. The book advances the theory of image processing, pattern recognition and generation as well as the design of efficient algorithms and hardware for parallel image processing and analysis. It is aimed at computer scientists, software programmers, electronic engineers, mathematicians and physicists, and at everyone who studies or develops cellular automaton algorithms and tools for image processing and analysis, or develops novel architectures and implementations of massive parallel computing devices. The book will provide attractive reading for a general audience because it has do-it-yourself appeal: all the computer experiments presented within it can be implemented with minimal knowledge of programming. The simplicity yet substantial functionality of the cellular automaton approach, and the transparency of the algorithms proposed, makes the text ideal supplementary reading for courses on image processing, parallel computing, automata theory and applications.
Memory is a universal of organized matter. What is the mathematics of memory? How does the memory affect space-time behaviour of spatially extended systems? Does the memory increase complexity? Cellular automaton models give us the answers. A cellular automaton is an array of locally connected finite state machines, or cells. The cells update their states simultaneously, in discrete time, by the same cellstate transition rule. Classical cellular automata are memoryless : a cell updates its state depending on current states of its neighbours. The book revolutionizes the conventional view on cellular automaton evolution by allowing cells to update their states looking at past states of their neighbours and analyses the effect of memory on a wide range of spatialized discrete dynamical systems scenarios. The book demonstrates that cellular automata with memory are not only priceless tools for modelling of natural phenomena but unique mathematical and aesthetic objects...
Proceedings of the Fourth International Conference on Cellular Automata for Research and Industry, Karlsruhe,4-6 October 2000
Author: S. Bandini
Publisher: Springer Science & Business Media
This book contains all full papers presented at ACRI 2000, the Fourth International Conference on Cellular Automata for Research and Industry, held at the University of Karlsruhe (Germany), 4 - 6 October, 2000. The continuation of and growing interest in research on Cellular Automata models for real world phenomena indicates the feasibility of this approach. A quick glance at the table contents of this book shows that results came from such different areas as biology, economics, physics, traffic flow and urban development. This work is complemented by contributions on the implementation and evaluation of software for Cellular Automata simulation, which is a necessary (but of course in no way sufficient) ingredient for the successful application of Cellular Automata. Applying Cellular Automata without trying to understand their behavior, in depth would be an unfortunate development. But as properties and power in earlier years it was again one of the strong points of ACRI to bring together researchers not only from different application areas but also from theory. Of course, this is reflected by the list of accepted contributions which also comprise theoretical papers and even papers which certainly belong to the intersection of several fields. Examples are the generation and recognition of geometrical patters and the influence of possible failures on the power of CA which obviously are of relevance also to applications.
It is with great pleasure that I present this fourth vol ume in the series "Advanced Applications in Pattern Recognition." It would be difficult to find two authors better versed in the design and application of parallel image processing systems, due to both their own many years of pioneering in the field and their encyclopedic knowledge of what is going on in uni versity and industrial laboratories around the world. The monograph is unique in its parallel presentation of orthogonal and hexagonal dissections, and the wealth of graphic illustration of algorithmic procedures for processing and analyz ing images in the various known implementations of parallel im age-processing architectures. This volume should find a place on the bookshelf of every practitioner of pattern recognition, image processing, and compu ter graphics. Morton Nadler General Editor vii PREFACE This book endeavors to introduce the reader to the subject of cellular logic and cellular automata and is devoted particu larly to those parts dealing with the manipulation of pictorial data. The study of cellular automata owes much to the pioneer ing work of John von Neumann during the 1950s. Von Neumann was interested in general problems in the behavior of computing structures and was immensely impressed by the complexity and performance of the human brain, which he felt must point to wards successful designs for automatic computing machines.
In the late 1960s British mathematician John Conway invented a virtual mathematical machine that operates on a two-dimensional array of square cell. Each cell takes two states, live and dead. The cells’ states are updated simultaneously and in discrete time. A dead cell comes to life if it has exactly three live neighbours. A live cell remains alive if two or three of its neighbours are alive, otherwise the cell dies. Conway’s Game of Life became the most programmed solitary game and the most known cellular automaton. The book brings together results of forty years of study into computational, mathematical, physical and engineering aspects of The Game of Life cellular automata. Selected topics include phenomenology and statistical behaviour; space-time dynamics on Penrose tilling and hyperbolic spaces; generation of music; algebraic properties; modelling of financial markets; semi-quantum extensions; predicting emergence; dual-graph based analysis; fuzzy, limit behaviour and threshold scaling; evolving cell-state transition rules; localization dynamics in quasi-chemical analogues of GoL; self-organisation towards criticality; asynochrous implementations. The volume is unique because it gives a comprehensive presentation of the theoretical and experimental foundations, cutting-edge computation techniques and mathematical analysis of the fabulously complex, self-organized and emergent phenomena defined by incredibly simple rules.
11th International Conference on Cellular Automata for Research and Industry, ACRI 2014, Krakow, Poland, September 22-25, 2014, Proceedings
Author: Jaroslaw Was
This book constitutes the proceedings of the 11th International Conference on Cellular Automata for Research and Industry, ACRI 2014, held in Krakow, Poland, in September 2014. The 67 full papers and 7 short papers presented in this volume were carefully reviewed and selected from 125 submissions. They are organized in topical sections named: theoretical results on cellular automata; cellular automata dynamics and synchronization; modeling and simulation with cellular automata; cellular automata-based hardware and computing; cryptography, networks and pattern recognition with cellular automata. The volume also contains contributions from ACRI 2014 workshops on crowds and cellular automata; asynchronous cellular automata; traffic and cellular automata; and agent-based simulation and cellular automata.
Theory and Applications in Multimedia Compression, Encryption, and Modeling
Author: Olurinde Lafe
Publisher: Springer Science & Business Media
Cellular Automata Transforms describes a new approach to using the dynamical system, popularly known as cellular automata (CA), as a tool for conducting transforms on data. Cellular automata have generated a great deal of interest since the early 1960s when John Conway created the `Game of Life'. This book takes a more serious look at CA by describing methods by which information building blocks, called basis functions (or bases), can be generated from the evolving states. These information blocks can then be used to construct any data. A typical dynamical system such as CA tend to involve an infinite possibilities of rules that define the inherent elements, neighborhood size, shape, number of states, and modes of association, etc. To be able to build these building blocks an elegant method had to be developed to address a large subset of these rules. A new formula, which allows for the definition a large subset of possible rules, is described in the book. The robustness of this formula allows searching of the CA rule space in order to develop applications for multimedia compression, data encryption and process modeling. Cellular Automata Transforms is divided into two parts. In Part I the fundamentals of cellular automata, including the history and traditional applications are outlined. The challenges faced in using CA to solve practical problems are described. The basic theory behind Cellular Automata Transforms (CAT) is developed in this part of the book. Techniques by which the evolving states of a cellular automaton can be converted into information building blocks are taught. The methods (including fast convolutions) by which forward and inverse transforms of any data can be achieved are also presented. Part II contains a description of applications of CAT. Chapter 4 describes digital image compression, audio compression and synthetic audio generation, three approaches for compressing video data. Chapter 5 contains both symmetric and public-key implementation of CAT encryption. Possible methods of attack are also outlined. Chapter 6 looks at process modeling by solving differential and integral equations. Examples are drawn from physics and fluid dynamics.
Cellular Automata presents the fundamental principles of homogeneous cellular systems. This book discusses the possibility of biochemical computers with self-reproducing capability. Organized into eight chapters, this book begins with an overview of some theorems dealing with conditions under which universal computation and construction can be exhibited in cellular spaces. This text then presents a design for a machine embedded in a cellular space or a machine that can compute all computable functions and construct a replica of itself in any accessible and sufficiently large region of the space. Other chapters consider simulation of one cellular space by another. This book discusses as well the goal of exhibiting universal computer-constructor. The final chapter deals with the use of a digital computer for research in cellular automata. This book is a valuable resource for computer designers and programmers who want a better understanding of the principles of homogeneous cellular systems. Automata theoreticians and biochemists will also find this book useful.
This paper explores the usefulness of cellular automata (CA) to traffic flow modeling. The authors extend some of the existing CA models to capture characteristics of traffic flow that have not been possible to model using either conventional analytical models or existing simulation techniques. In particular, they examine higher moments of traffic flow and evaluate their effect on overall traffic performance. The behavior of these higher moments is found to be surprising, somewhat counter-intuitive, and to have important implications for design and control of traffic systems. For example, the authors show that the density of maximum throughput is near the density of maximum speed variance. Contrary to current practice, traffic should, therefore, be steered away from this density region. For deterministic systems they found traffic flow to possess a finite period which is highly sensitive to density in a non-monotonic fashion. They show that knowledge of this periodic behavior is very useful in designing and controlling automated systems. These results are obtained for both single and two lane systems. For two lane systems, they also examine the relationship between lane changing behavior and flow performance. They show that the density of maximum lane changing frequency occurs past the density of maximum throughput. Therefore, traffic should also be steered away from this density region.
Proceedings of the Fourth International Conference on Cellular Automata for Research and Industry, Karlsruhe,4-6 October 2000
Author: T. Worsch
This volume contains the papers presented at ACRI 2000, the 4th International Conference on Cellular Automata for Research and Industry, held at the University of Karlsruhe (Germany), 4-6 October 2000. The continuation of and growing interest in research on Cellular Automata models for real world phenomena indicates the feasibility of this approach. Theoretical and Practical Issues on Cellular Automata brings together researchers not only from different application areas but also from theory. This is reflected by the list of contributions, which include theoretical papers and even papers which certainly belong to the intersection of several fields. A quick glance at the table of contents of this book shows that results come from such different areas as biology, economics, physics, traffic flow and urban development.