Páginas:
176
Edición:
1
Fecha de publicación:
28/06/2020
ISBN:
9788426729972
Formato:
17x24 cms

Message Passing Cellular Automata

24,80 23,57
24,80 23,57
Añadir a cesta
Recíbelo en 24/48h
debido a la situación actual, el pedido puede sufrir demoras

Cellular automata have been used in computer science since the 1940s. A cellular automaton consists of many identical
simple processing units that interact with each other in a local way and in discrete time. Cellular automata have been applied to a wide variety of tasks and, due to the growing interest of the scientific community, a good number of relevant journals and conferences are dedicated to their study and development. One of the main characteristics of cellular automata is their simplicity, which makes them relatively easy to program. Nonetheless, despite their simplicity, cellular automata are able to generate complex results in many domains, even in the context of artificial life. Another remarkable characteristic of cellular automata is that they are suitable for parallel implementation.
The present book deals with the fundamentals of cellular automata. Additionally, a new approach to extending cellular
automata with the use of message passing is introduced. Each of the seven chapters of this book includes a number of
figures, bibliographic references, and exercises of interest to the reader. The book offers students, practitioners and
researchers a concise but broad coverage of the main aspects of cellular automata.
The author of the book is an associate professor in the Department of Artificial Intelligence at UNED (Spanish Open
University). Since the middle 1990s, he has performed teaching and research activities within the field of artificial
intelligence, mainly in the areas of Bayesian networks and evolutionary computation. This book is the result of a long journey that started when the author became interested in NetLogo. NetLogo is an agent]based programming environment well suited for modeling and inspecting complex systems developing over time.

Preface ix
1 Introduction to Cellular Automata 1
1.1 History of Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Components of a Cellular Automaton . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Lattice of Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 States of Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Transition Function . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Updating Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Second-Order Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . 7
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 One-Dimensional Classical Cellular Automata 9
2.1 Elementary Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Ternary One-Dimensional Cellular Automata . . . . . . . . . . . . . . . . 14
2.3 Continuous One-Dimensional Cellular Automata . . . . . . . . . . . . . . 18
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 One-Dimensional Message Passing Cellular Automata 23
3.1 General Denition of Message Passing Cellular Automaton . . . . . . . . 23
3.2 Message Passing in One Dimension . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Elementary Message Passing Cellular Automata . . . . . . . . . . . . . . . 26
3.4 Ternary One-Dimensional Message Passing Cellular Automata . . . . . . 35
3.5 Continuous One-Dimensional Message Passing Cellular Automata . . . . . 39
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 Two-Dimensional Classical Cellular Automata 45
4.1 Basic Two-Dimensional Cellular Automata . . . . . . . . . . . . . . . . . . 45
4.2 Majority Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Parity Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4 Game of Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5 Two-Dimensional Message Passing Cellular Automata 59
5.1 Message Passing in Two Dimensions . . . . . . . . . . . . . . . . . . . . . 59
5.2 Message Passing Cellular Automata with Fixed Messages . . . . . . . . . 62
5.3 Message Passing Cellular Automata with Sender-Dependent Messages . . 64
5.4 Message Passing Cellular Automata with Receiver-Dependent Messages . 64
5.5 Message Passing Cellular Automata with Link-Dependent Messages . . . 69
5.6 Message Passing Cellular Automata with Neighborhood-Dependent Messages 69
5.6.1 Rotation Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.6.2 Reection Messages . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.6.3 Majority Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6.4 Parity Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6.5 Extensions of the Game of Life . . . . . . . . . . . . . . . . . . . . 77
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6 Applications of Classical Cellular Automata 83
6.1 Applications in Physics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.1.1 Partial Dierential Equations . . . . . . . . . . . . . . . . . . . . . 83
6.1.1.1 Diusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.1.1.2 Reaction-Diusion . . . . . . . . . . . . . . . . . . . . . . 87
6.1.1.3 Waves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.1.1.4 Wavefronts . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.1.2 Fluids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.1.2.1 Lattice Gas Model . . . . . . . . . . . . . . . . . . . . . . 92
6.1.2.2 Lattice Boltzmann Model . . . . . . . . . . . . . . . . . . 95
6.1.3 Ising Spin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.1.4 Sandpile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.1.5 Diusion-Limited Aggregation . . . . . . . . . . . . . . . . . . . . 103
6.2 Applications in Excitable Media . . . . . . . . . . . . . . . . . . . . . . . 103
6.2.1 Brian’s Brain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.2 Greenberg-Hastings Model . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.3 Threshold Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.4 Cyclic Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . 108
6.2.5 Hodgepodge Machine . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.3 Applications in Biology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.1 Seashell Pigmentation Patterns . . . . . . . . . . . . . . . . . . . . 110
6.3.2 Bacterial Growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3.3 Predator-Prey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.4 Applications in Social Science . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.1 Schelling Segregation Model . . . . . . . . . . . . . . . . . . . . . . 115
6.4.2 Evacuation Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.2.1 Floor Fields Based on Shortest Paths . . . . . . . . . . . 117
6.4.2.2 Floor Fields Based on Quickest Paths . . . . . . . . . . . 120
6.4.2.3 Fast Evacuation Method . . . . . . . . . . . . . . . . . . 121
6.4.3 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.4.4 Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . 124
6.5 Applications in Mathematics . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.5.1 Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7 Applications of Message Passing Cellular Automata 135
7.1 Message Passing Versions of Classical Cellular Automata Applications . . 135
7.2 Message Passing Diusion of Innovations . . . . . . . . . . . . . . . . . . . 136
7.3 Message Passing Schelling Segregation Model . . . . . . . . . . . . . . . . 139
7.4 Message Passing Cellular Evolutionary Algorithms . . . . . . . . . . . . . 140
7.5 Message Passing Graph Layout . . . . . . . . . . . . . . . . . . . . . . . . 143
7.6 Message Passing Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Bibliography 153
Index 161

A color
Páginas:
176
Edición:
1
Año Publicación:
28/06/2020
ISBN:
9788426729972
Formato:
17x24 cms
Colección

Relacionados

¿Quiéres conocer las últimas novedades?

Inscribiéndote recibirás unos regalos exclusivos para ti