Selected problems in the theory of classical cellular automata

								
Introduction
Chapter 1. The basic concepts of classical cellular automata
Chapter 2. Nonconstructability problem in classical cellular automata (classical CA models)
2.1. Preliminary information on the CA problems
2.2. The nonconstructability types for classical CA models
2.3. Existence criteria of the basic nonconstructability types in classical CA models
2.4. The nonconstructability problem for finite CA models and CA models on splitting
2.5. The reversibility problem of dynamics of classical CA models
2.6. Algorithmical aspects of the nonconstructability problem and some connected questions of dynamics of classical CA models
Chapter 3. Extremal constructive opportunities of classical cellular automata
3.1. Universal finite configurations in classical CA models
3.2. Self–reproduction of finite configurations in classical CA models
Chapter 4. The complexity problem of finite configurations in classical CA models
Chapter 5. Parallel formal grammars and languages determined by classical cellular automata (CA models)
5.1. The basic properties of the parallel languages, determined by classical cellular automata
5.2. Parallel grammars determined by classical CA models in comparison with formal grammars of some other classes and types
5.3. Parallel grammars defined by nondeterministic CA models
5.4. Algorithmical problems of the theory of parallel grammars, determined by classical CA models
Chapter 6. The modelling problem in classical cellular automata (CA) along with the related questions
6.1. Concepts of modelling in classical CA
6.2. Modelling of the well–known formal processing algorithms of words in finite alphabets by means of CA models
6.3. Simulating of classical CA models by means of CA models of the same class
6.4. The formal parallel algorithms determined by classical one–dimensional CA models
6.5. Special questions of simulating in classical CA models concerning their dynamics
6.6. Sketch on sofrware oriented on CA simulating
Chapter 7. The decomposition problem of global transition functions in classical CA models
7.1. Decomposition of special global transition functions in classical CA models
7.2. Some approaches to solution of the general decomposition problem of global transition functions
7.3. Questions of solvability of the decomposition problem for global transition functions of CA models
7.4. The complexity problem for global transition functions in classical CA models
Chapter 8. Certain applied aspects of the CA problematics
8.1. Solution of the Steinhaus combinatory problem
8.2. Solution of the Ulam problem from number theory
8.3. Certain applied aspects of CA models in biological sciences
Conclusion
References
About the authors
								Rate this book:
4.0 / 2 votes