Computing cellular automata spectra under fixed boundary conditions via limit graphs

Eurico L. P. Ruivo and Pedro P. B. De Oliveira ()
Additional contact information
Eurico L. P. Ruivo: Faculdade de Computação e Informática, Pós-Graduação em Engenharia Elétrica e Computação, Universidade Presbiteriana Mackenzie, Rua da Consolação 896, Consolação, 01302-907 São Paulo, SP, Brazil
Pedro P. B. De Oliveira: Faculdade de Computação e Informática, Pós-Graduação em Engenharia Elétrica e Computação, Universidade Presbiteriana Mackenzie, Rua da Consolação 896, Consolação, 01302-907 São Paulo, SP, Brazil

International Journal of Modern Physics C (IJMPC), 2016, vol. 27, issue 07, 1-19

Abstract: Cellular automata are fully discrete complex systems with parallel and homogeneous behavior studied both from the theoretical and modeling viewpoints. The limit behaviors of such systems are of particular interest, as they give insight into their emerging properties. One possible approach to investigate such limit behaviors is the analysis of the growth of graphs describing the finite time behavior of a rule in order to infer its limit behavior. Another possibility is to study the Fourier spectrum describing the average limit configurations obtained by a rule. While the former approach gives the characterization of the limit configurations of a rule, the latter yields a qualitative and quantitative characterisation of how often particular blocks of states are present in these limit configurations. Since both approaches are closely related, it is tempting to use one to obtain information about the other. Here, limit graphs are automatically adjusted by configurations directly generated by their respective rules, and use the graphs to compute the spectra of their rules. We rely on a set of elementary cellular automata rules, on lattices with fixed boundary condition, and show that our approach is a more reliable alternative to a previously described method from the literature.

Keywords: Elementary cellular automata; Fourier spectrum; limit language; process graph; finite automata; complexity (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S012918311650073X
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:27:y:2016:i:07:n:s012918311650073x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S012918311650073X

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().