Uma técnica para obtenção de atratores de autômatos celulares elementares

  • Eurico L. P. Ruivo UPM
  • Pedro P. B. de Oliveira UPM

Resumo


Autômatos celulares são sistemas dinâmicos totalmente discretos, apresentando uma dinâmica definida localmente. Apesar da simplicidade, tais sistemas são capazes de apresentar comportamento emergente global complexo. Uma questão fundamental no estudo dos autõmatos celulares é sobre seu comportamento global para uma evolução temporal infinita do sistema. Aqui apresentamos uma técnica para inferir atratores de autõmatos celulares elementares, tomando como base a análise das expressões regulares que descrevem as evoluções temporais finitas de um autômato celular elementar em particular.

Referências

Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15(1):1–40.

De Oliveira, P. P. B., Ruivo, E. L. P., Costa, W. L., Miki, F. T. e Trafaniuc, V. V. (2016). Advances in the study of elementary cellular automata regular language complexity. Complexity, 21(6):267–279.

Di Lena, P. e Margara, L. (2010). On the undecidability of the limit behavior of cellular automata. Theoretical Computer Science, 411(7):1075–1084.

Kari, J. (2005). Theory of cellular automata: A survey. Theoretical Computer Science, 334(1–3):3–33.

Ruivo, E. L. P. e de Oliveira, P. P. B. (2017). Inferring the limit behaviour of some elementary cellular automata. Manuscrito não publicado submetido ao International Journal of Bifurcation and Chaos.

Santé, I., García, A. M., Miranda, D. e Crecente, R. (2010). Cellular automata models for the simulation of real-world urban processes: A review and analysis. Landscape and Urban Planning, 96(2):108–122.

Wolfram, S. (1994). Cellular Automata and Complexity. Addison-Wesley Publishing Co.

Wolfram, S. (2002). A New Kind of Science. Wolfram Media.
Publicado
02/07/2017
RUIVO, Eurico L. P.; DE OLIVEIRA, Pedro P. B.. Uma técnica para obtenção de atratores de autômatos celulares elementares. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . p. 61-64. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3192.