Computing with cellular automata and their temporal or spatial compositions

• Grant number: 05/04696-3
• Support Opportunities: Regular Research Grants
• Start date: May 01, 2006
• End date: April 30, 2009
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computing Methodologies and Techniques
• Principal Investigator: Pedro Paulo Balbi de Oliveira
• Grantee: Pedro Paulo Balbi de Oliveira
• Host Institution: Faculdade de Computação e Informática (FCI). Universidade Presbiteriana Mackenzie (UPM). Instituto Presbiteriano Mackenzie. São Paulo , SP, Brazil

Abstract

Cellular automata are fully discrete complex systems, with both a dynamic and a computational nature, consisting of a grid-like regular lattice of cells, and a state transition rule that governs how the state change of every cell in the lattice has to occur, as a function of the states of the neighbouring cells.A strong motivation for studying cellular automata is their ability to perform computations, a motivation that is in the core of this project. The ability to grasp how cellular automata compute and how they should be designed so as to perform a given computational task could yield a very deep impact on information technology and computing theory, in that they would provide a completely new model of computation, totally parallel, decentralised and local.However, the understanding of how these computations are carried out is still extremely vague; in fact, regardless of more than four decades of cellular automata research, their use for computing functions at large are still at an embryonic stage. And the main reason for this failure is the lack of a robust method for designing cellular automata of a predefined behaviour.Interesting cellular automata currently known, have typically been found through stepwise and thought-out engineering, exhaustive searches in very restricted domains, formal methods in extremely particular problems, and specialised search methods, mostly evolutionary, in constrained spaces.Although each of these individual approaches have been successful in their own way, their dissociation has precluded real advancements in fulfilling the need for some more general and flexible design method, that might be useful across different problems and disciplines. Pursuing this target is the aim of this project, and the way to go about it is by combining what has been known from the approaches above.Given the proven ability of evolutionary algorithms in the design of complex systems, across many diverse domains, this family of algorithms is the one to primarily guide our efforts. Evolutionary algorithms are search methods gleaned from biological evolution, that are particularly well suited for problems where the search space is very large, or when no alternative direct methods are available, as usually happens in the design of complex systems in general, and cellular automata in particular. The pathway to be followed combines evolutionary computation techniques, with enumerative searches in small regions of the search space, both processes guided by static information drawn from the state transition table of the cellular automata involved. In tune of the latter, three related issues will also be investigated related to the so-called elementary cellular automata, namely, the limit behaviour of elementary rules, the outcome of combining their temporal evolutions, and the spatial combination of different rules in the same lattice.All in all, the combined objective of this project is to make advances on the understanding and exploration of the computational ability of cellular automata (either through individual rules, or by their temporal or spatial combinations), as well as the development of effective ways to their design by means of enumerative and evolutionary computation techniques. The project will revolve primarily around a selection of three problems, the density classification task, the recognition of hand-written decimal digits, and the parity problem, although others may also be considered, as the investigations progress and the research group associated with it develops. (AU)

Scientific publications

(5)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

ZIMBRES, RUBENS A.; DE OLIVEIRA, PEDRO P. B.. Dynamics of Quality Perception in a Social Network: A Cellular Automaton Based Model in Aesthetics Services. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 252, p. 24-pg., 2009-10-01. (05/04696-3)

DE OLIVEIRA‚ P.P.B.; BORTOT‚ J.C.; OLIVEIRA‚ G.. The best currently known class of dynamically equivalent cellular automata rules for density classification. Neurocomputing, v. 70, n. 1, p. 35-43, 2006. (05/04696-3)

OLIVEIRA, C. C., JR.; DE OLIVEIRA, P. P. B.; GELBUKH, A; MORALES, EF. An Approach to Searching for Two-Dimensional Cellular Automata for Recognition of Handwritten Digits. Lecture Notes in Computer Science, v. 5317, p. 3-pg., 2008-01-01. (05/04696-3)

ZIMBRES, RUBENS A.; BRITO, ELIANE P. Z.; DE OLIVEIRA, PEDRO P. B.; CORDEIRO, J; FILIPE, J. CELLULAR AUTOMATA BASED MODELING OF THE FORMATION AND EVOLUTION OF SOCIAL NETWORKS A Case in Dentistry. ICEIS 2008: PROCEEDINGS OF THE TENTH INTERNATIONAL CONFERENCE ON ENTERPRISE INFORMATION SYSTEMS, VOL AIDSS, v. N/A, p. 2-pg., 2008-01-01. (05/04696-3)

MARTINS, CLAUDIO L. M.; DE OLIVEIRA, PEDRO P. B.. Improvement of a Result on Sequencing Elementary Cellular Automata Rules for Solving the Parity Problem. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 252, p. 17-pg., 2009-10-01. (05/04696-3)