## Automata-2008: Theory and Applications of Cellular AutomataCellular 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 conﬁguration? 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 deﬁniteness 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 deﬁnition 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 ﬁring 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 |

Deﬁnitions 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 reconﬁgurable 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 diﬀusion | 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 artiﬁcial 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 traﬃc | 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 eﬀorts to 1999 TTM v1 x | 563 |

Signiﬁcant 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 |

### Other editions - View all

Automata-2008: Theory and Applications of Cellular Automata Andrew Adamatzky,R. Alonso-Sanz,A. Lawniczak No preview available - 2008 |

### Common terms and phrases

Ammann bars Artiﬁcial automaton beam search behavior bits cell cellicules cellular automata chain rule cluster complex construction arm corresponding coupled CTAG cycle cyclic tag system dart tiling DDoS attacks deﬁned deﬁnition diﬀerent dynamical system edge eﬀect encryption entropy equicontinuity evolution example Fibonacci tree ﬁgure ﬁnal ﬁnd ﬁnite ﬁre ﬁring ﬁrst ﬁve ﬁxed Genetic Algorithms gliders global grains of sand grid implementation inﬁnite initial conﬁguration input iterative kite and dart Kite Rhomb lattice layer Lemma linear locomotive machine memory method neighbourhood neighbours Neumann nodes operation output packet traﬃc parameters patterns Penrose tiling pentagrid permutation possible pre-image problem properties Q Q Q random reverse algorithm rhomb rhomb tiling rtco self-replicator shown in Fig shows signal crossing signiﬁcantly simulation solution space speciﬁc step structure suﬃcient switch synchronization tape Theorem track transition graph transition rules Turing machine University update vertex block vNCA