Cellular Automata: A Parallel Model

Front Cover
M. Delorme, J. Mazoyer
Springer Science & Business Media, Dec 31, 1998 - Computers - 374 pages
Cellular automata can be viewed both as computational models and modelling systems of real processes. This volume emphasises the first aspect. In articles written by leading researchers, sophisticated massive parallel algorithms (firing squad, life, Fischer's primes recognition) are treated. Their computational power and the specific complexity classes they determine are surveyed, while some recent results in relation to chaos from a new dynamic systems point of view are also presented.
Audience: This book will be of interest to specialists of theoretical computer science and the parallelism challenge.
 

What people are saying - Write a review

User Review - Flag as inappropriate

cellular automaton unread
Arrythmiac important

Contents

An introduction to cellular automata
5
The Game of Life Universality revisited
51
Computations on cellular automata
77
Computations on grids
119
Cellular automata as languages recognizers
153
Computational complexity of cellular automata an overview
181
A counting equivalence classes method to prove negative results
199
Topological definitions of deterministic chaos
213
Dynamic properties of an automation with memory
293
Linear cellular automata and De Bruijn automata
303
Cellular autoamta finite automata and number theory
321
Decision problems on global cellular automata
331
An introduction to automata on graphs
345
Bibliography
353
List of authors
365
Index
369

Modeling diffusion of informations with probabilistic cellular automata
263
Cellular automata models and cardiac arrhythmias
279

Other editions - View all

Common terms and phrases

Popular passages

Page 356 - Vol. 8, 1979, pp. 135-159. [10] Hopcroft, J. and Ullman, J., 'Introduction to Automata Theory, Languages, and Computation', Addison-Wesley, Reading, Mass., 1979.