From owner-cellular-automata@Think.COM Wed Jul 19 20:29 MET 1995 Received: from Hugo.espci.fr by hp750 with SMTP (1.38.193.4/16.2) id AA03958; Wed, 19 Jul 1995 20:27:33 +0200 Return-Path: Received: by Hugo.espci.fr (5.65/DEC-Ultrix/4.3) id AA14497; Wed, 19 Jul 1995 20:34:13 +0200 Received: from oeillet.saclay.cea.fr by trefle.saclay.cea.fr (8.6.10/ CEANET-ROUTER-3.0) with ESMTP id UAA05267 for ; Wed, 19 Jul 1995 20:29:41 +0200 Received: from amoco.saclay.cea.fr by oeillet.saclay.cea.fr (8.6.10/ CEANET-ROUTER-3.0) with SMTP id UAA17865 for ; Wed, 19 Jul 1995 20:32:33 +0200 Received: from oeillet.saclay.cea.fr by amoco.saclay.cea.fr (5.x/CEANET.2.0.1) id AA03086; Wed, 19 Jul 1995 20:29:31 +0200 Received: from trefle.saclay.cea.fr by oeillet.saclay.cea.fr (8.6.10/ CEANET-ROUTER-3.0) with ESMTP id UAA17861 for ; Wed, 19 Jul 1995 20:32:24 +0200 Received: from mail.think.com by trefle.saclay.cea.fr (8.6.10/ CEANET-ROUTER-3.0) with SMTP id UAA05259 for ; Wed, 19 Jul 1995 20:29:18 +0200 Received: by mail.think.com; Wed, 19 Jul 95 11:58:39 -0400 Received: from Think.COM by mail.think.com; Wed, 19 Jul 95 11:58:34 -0400 Received: from bloom-beacon.MIT.EDU by Early-Bird.Think.COM; Wed, 19 Jul 95 11:57:13 EDT Received: (from news@localhost) by bloom-beacon.MIT.EDU (8.6.12/25-eef) id LAA23376 for ca@think.com; Wed, 19 Jul 1995 11:57:08 -0400 Received: from USENET by bloom-beacon with netnews for ca@think.com (ca@think.com); contact usenet@bloom-beacon if you have questions. To: ca@Think.COM Date: Wed, 19 Jul 95 18:50:10 +0400 From: Andrew Adamatzky Message-Id: Organization: St.Petersburg State University, Biophysics Department Subject: cellular automata Sender: owner-cellular-automata@Think.COM Precedence: bulk Status: RO Dear colleagues, would you be so kind to examine the brief review and contents of my monograph concerning cellular automata, molecular computers and massively parallel algorithms. Please, inform me your opinion, comments and remarks. I am ready to share my further ideas with you as well as cooperate on any your project on cellular automata. Yours, Andrew +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ IDENTIFICATION OF CELLULAR AUTOMATA Andrew Adamatzky Taylor & Francis, London, Bristol, 1994, 337 pp + X. ISBN 0-7484-0172-5 Let A= be a cellular automaton consisted of multi- dimensional array L of cells, every cell of L takes states from finite non-empty set Q and changes its state in discrete time depending on the states of its neighbourhood (defined by neighbourhood template u) and in accordance with local transition function f. "Given a set of configurations of some unknown cellular automaton A, we wish to extract the neighbourhood template u and rules for local transitions, i.e. approximate function f". This is a pivot problem of the book. The intention of this monograph is to tie together various threads of the problem in order to give a comprehensive picture of the current state of the subject. The book has four chapters and four appendices. Chapter 1 introduces the reader to the concept of cellular automata, gives an overview on the cellular-automata technique for simulation of natural phenomena and the complete classification of cellular automata on the determinicity/indeterminicity, synchroneity/asynchroneity, structure of cell state set and cell neighbourhood, kind of cell state transition function. There were comparatively analyzed and illustrated with detailed examples canonical, totalistic, over sets, with memory, fuzzy, probabilistic, hierarchical, over words and structurally dynamic cellular automata. Hierarchies of complexity and simulation among classes were constructed. Chapter 2 deals with algorithms for identification. The algorithms for identification of cellular automata from all the defined classes were designed, their correctness and complexity of serial and parallel implementations were proved. The inverse problems of cellular automata theory is the topic of Chapter 3. In the chapter the properties of the complete configurations (complete configuration contains all possible states of neighbourhood) of one-dimensional deterministic synchronous cellular automata are discussed. There were proved some theorems on the size of complete configurations, elaborated factorization of complete configurations onto the neighbourhood states, computed sets of the complete configurations, discussed decidability of complete identification from an arbitrary pair of configurations and heredity of the complete configurations. The efficacious technique for detecting nonconstructibility (Garden- of-Eden property) of an arbitrary configuration was offered. It was shown how to compute all the possible minimal nonconstructible configurations for given cellular automaton. The unique algebraic and associated matrix systems over cellular automata were constructed and their properties were analyzed. They were used in the computation of minimal path for cellular-automata transformations of one configuration into another one. Chapter 4 considers the applications of identification and related problems. Theory of cellular automata identification were applied on system of moving objects, neural networks, morphogenetic structures, reaction-diffusion media and interacting populations of livings. Identification of distributed intelligence systems was elaborated in details. It was shown how to design massively parallel molecular computers from the structure of problem; algorithms were tested on the problems of discrete computational geometry: Voronoi diagram, convex hull, labyrinth on lattice, image processing. The Appendices 1, 2 and 3 contain catalogue of the global transitions graphs of one-dimensional cellular automata of different classes, catalogue of the matrices produced over cellular automata. Appendix 4 illustrates the properties of the so-called algebra of interacting cellular automata. There are four domains which the reader should be focused on: fuzzy cellular automata, neural nets identification, algorithms in excitable and reaction-diffusion media and identification of the groups of intelligent agents. All they can be applied directly on the practice of neurocomputing. Thus, the homogeneous locally interconnected (when, say, number of the synaptic terminals ending on single neuron is much more less then the size of net) neural networks form a definite subclass of cellular automata. The identification technique gives us an opportunity to reconstruct as neural architectonics as local structure of neural connections from the given activity patterns. This with the results on implantation of cellular automata and automatic design of massively parallel algorithms in excitable media gives a chance to produce new methods for designing neurocomputers. Via extraction of rules for local interactions of the agents from global snapshots of distributed regular epistemic doxastic actional systems one can try to map directly a structure of interpersonal communications onto the architecture of artificial intelligence systems. Unfortunately, the results on fuzzy cellular automata have been reduced to only class and wide spectrum of these automata (as defined in [Adamatzky A. Hierarchy of fuzzy cellular automata. J. Fuzzy Sets and Systems 3 (1994) 74-79]) is not presented in the book. The author tried to balance the contents of the work to be useful for both professionals with extended cellular automata experience and readers without such background who only wish to comprehend the concept of the cellular automata identification to be able to use it. In conclusion it can be said that the reader is given an interdisciplinary book which may not answer his questions concerning the particular problems he is interested in, but it familiar with some methods that can be used in these cases and expands his horizons of knowledge. ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ IDENTIFICATION OF CELLULAR AUTOMATA by Andrew Adamatzky published by Taylor & Francis, London, Bristol, 1994, 337 pp + X. ISBN 0-7484-0172-5 CONTENTS Preface vii CHAPTER 1. INITIATION 1 1.1. What Are Cellular Automata 1 1.2. Classification of Cellular Automata 4 1.2.1. Deterministic Cellular Automata 4 1.2.2. Probabilistic Cellular Automata 25 1.2.3. Fuzzy Cellular Automata 29 1.2.4. Hierarchical Cellular Automata 31 1.2.5. Exotic Cellular Automata 38 1.3. Cellular Automata Simulating Nature 45 1.4. What Is Identification ? 54 CHAPTER 2. ALGORITHMS FOR IDENTIFICATION 2.1. Deterministic Cellular Automata 57 2.1.1. Synchronous Cellular Automata of class CLAS 57 2.1.2. Cellular Automata of NSET, TOTA, INTER and ATOT 66 2.1.3. Asynchronous Cellular Automata 70 2.1.4. Cellular Automata With Memory 77 2.2. Probabilistic Cellular Automata 81 2.2.1. D-Identification 82 2.2.2. GP- and PG-identification 87 2.2.3. Example 88 2.2.4. Parallel Scheme For Identification 88 2.3. Fuzzy Cellular Automata 90 2.4. Hierarchical Cellular Automata 94 2.5. Exotic Cellular Automata 97 CHAPTER 3. INVERSE PROBLEMS OF CELLULAR AUTOMATA THEORY 105 CHAPTER 4. APPLICATIONS OF IDENTIFICATION AND RELATED PROBLEMS 4.1. Introduction 129 4.2. Discrete Motion 130 4.3. Implantation of Cellular Automata 146 4.4. Distributed Intelligence 173 4.5. Cryptography 180 4.6. Three Examples of Natural Systems 185 4.6.1. Neural Networks 186 4.6.2. Reaction-Diffusion Media 200 4.6.3. Interacting Populations 208 4.7. Design of Molecular Computers 238 4.7.1. Discrete Voronoi Diagram 246 4.7.2. Discrete Convex Hull 255 4.7.3. Planar Lattice Maze 260 4.7.4. Image Processing 264 CONCLUSION 277 APPENDIX 1. Catalogue of Global Transitions Graphs 279 APPENDIX 2. Catalogue of The Reduced I-Matrices of 1D Cellular Automata of Classes CLAS and NSET 307 APPENDIX 3. Catalogue of D- and P-Matrices of 1D Cellular Automata of Class CLAS 311 APPENDIX 4. Algebra of Interacting Cellular Automata 321 BIBLIOGRAPHY 329 INDEX 335 ---------------------------------------------------------------------------- The Publishers: Taylor & Francis Inc., 1900 Frost Road, Suite 101, Bristol PA 19007, USA Fax 215-785-5515 Taylor & Francis Ltd, 4 John St., London WC1N 2ET, UK Fax +44 (0) 71 831 2035 Tel +44 (0) 71 405 2237 Marketing Department, Taylor & Francis, Rankine Road, Basingtoke, Hants, RG24 0PR, UK Fax +44 (0) 256 479 438 Tel +44 (0) 256 840 366 Telex 0256 840366 ---------------------------------------------------------------------------- The Author: Andrew I. Adamatzky Biophysics Department St.Petersburg State University Universitetskaya nab. 7/9 St. Petersburg 199034 RUSSIA +++++++++++++++++++++++++++++++++++++++++ + Address for Correspondence: + + + + Andrew Adamatzky + + Kubinskaya street 56-64 + + St.Petersburg 196247 RUSSIA + +++++++++++++++++++++++++++++++++++++++++ + E-mail: ada@ada.usr.pu.ru + + Fax: (812) 164-5285 + + Tel: (812) 295-7279 or 164-5240 + +++++++++++++++++++++++++++++++++++++++++ -----------------------------------------------------------------