Automata-2008: Theory and Applications of Cellular Automata

Front Cover
Andrew Adamatzky, R. Alonso-Sanz, A. Lawniczak
Luniver Press, 2008 - Computers - 616 pages
0 Reviews
Cellular automata are regular uniform networks of locally-connected finite-state machines. They are discrete systems with non-trivial behaviour. Cellular automata are ubiquitous: they are mathematical models of computation and computer models of natural systems. The book presents results of cutting edge research in cellular-automata framework of digital physics and modelling of spatially extended non-linear systems; massive-parallel computing, language acceptance, and computability; reversibility of computation, graph-theoretic analysis and logic; chaos and undecidability; evolution, learning and cryptography. The book is unique because it brings together unequalled expertise of inter-disciplinary studies at the edge of mathematics, computer science, engineering, physics and biology.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Solving the problem of enforced restriction to few states while evolving
228
Summary
239
Analysis of LCA
246
How far is to the next recurrent configuration? An NPcomplete
253
Conclusion
267
Results
273
the Hub and the Conservative Join
280
Conclusions and discussion
288

Automorphisms of transition graphs for a linear cellular automaton
55
Computational results
62
The discrete Baker transformation
70
Perturbations
75
Coupled automata with elementary rules
76
Number conserving rules
81
Asymmetric memory
86
Elementary rules as memory
90
Average memories
91
Conclusion
96
On undecidability of sensitivity of reversible cellular automata
100
Cellular automata
101
Undecidability results
103
A 24state universal onedimensional reversible cellular automaton
106
Preliminaries
107
A 24state universal reversible PCA P24
109
Concluding remarks
111
Construction of reversible cellular automata by amalgamations and permutations of states
114
Basic concepts
115
Permutations definiteness and amalgamations
116
Construction of reversible automata
118
Examples
120
Conclusions
123
Encryption using cellular automata chainrules
126
The Zparameter
128
Constructing chain rules at random
131
How many chainrules?
132
Generalising the methods to multivalue
133
Possible drawbacks
134
A bit of history
136
A cryptographic model based on the preimage calculus of cellular automata
139
Dynamical behavior and the Z parameter
140
The reverse algorithm
141
Toggle rules and Gutowitzs model
142
A new approach
144
Experiments
145
A proposal of a new cryptographic model with a variablelength ciphertext
150
Additional remarks
151
Conclusions
152
Acknowledgements
153
A definition of conservation degree for onedimensional cellular automata rules
156
An analytical proposal
160
Empirical conservation degree for onedimensional rules
162
Conclusion
170
A family of smallest symmetrical fourstate firing squad synchronization protocols for onedimensional ring cellular automata
174
Firing squad synchronization problem
175
A quest for fourstate symmetrical partial solutions for rings
176
Fourstate solutions
178
Conclusion
184
New approach to search for gliders in cellular automata
187
Definitions and notations
188
Search for gliders
189
Description of gliders
190
Synthesis and perspectives
192
Acknowledgements
193
Chaotic properties of elementary cellular automaton rule 168
196
Right spreading rate of rule 168
202
Realtime reversible language recognition by cellular automata
208
Reversible simulation of data structures
214
Recent results on iterative arrays with small space bounds
222
NonSymmetrical K
296
Cellular automata with dynamically reconfigurable buses
306
Asynchronous logic automata
313
Future work
320
A 1D cellular automaton that moves particles until regular spatial
323
Dynamics of the cellular automaton
329
Conclusion
336
An abstract collision system
342
Concluding remarks
354
Computing with propagating patterns
360
from histograms to spectrograms
368
Conclusion and ongoing work
377
CAmodels of phenomena which include diffusion
385
Asynchronous CAs modeling nanokinetic processes
391
Optimizing the creatures rule for alltoall communication
398
Investigations and results
405
Conclusion
409
Solving cellular automata problems with SAGEPython
417
Cellular automata with cell clustering
425
Results
434
From cellular automata to a random artificial chemistry producing
442
Analysis of the Salgorithm for S Z1 Z2 Z3
449
The mechanisms of construction
457
The realtime crossing organ
467
The Mukhopadhyay crossing organ
475
Modes of selfreplication
498
Cellular automata and nonstatic image processing for embodied robot systems on a massively parallel processor array
504
The SCAMP vision system
505
The use of SCAMP in a robotic setup
506
Embedding cellular automata into a robotic scenario
507
Experiments with moving objects
509
Conclusion
510
Evolving onedimensional radius2 cellular automata rules for the synchronization task
514
Forecast behavior parameters
515
Computational tasks
516
Evolving cellular automata rules
517
Evolutionary environment
519
Results
522
Final remarks
524
Development of CA model of highway traffic
527
The model
529
The software
534
Conclusion
539
Acknowledgements
540
Evolving robust cellular automata rules with genetic programming
542
Genetic programming
543
Evolving with genetic programming pedestrian behavior rules in evacuation dynamics
548
Conclusions
552
A simple cellular automata model for FX market forecasting
557
The Trend Machine basic assumptions
558
Work and efforts to 1999 TTM v1 x
563
Significant issues
567
Pricetime frames or increments
568
Attacks on packet switching networks short review
574
Conclusions
582
The network topology
588
Conclusions
596
The simulation
603
Abstracts of invited talks presented at AUTOMATA2008 Bristol
611
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information