Complex Systems

Power Spectra of Regular Languages and Cellular Automata Download PDF

Wentian Li
Center for Complex Systems Research,
University of Illinois at Urbana-Champaign,
508 South Sixth Street, Champaign, IL 61820, USA
Physics Department, Columbia University,
New York, NY 10027, USA


The spatial structure of attractors produced by many one-dimensional cellular automata can be described by regular languages. This paper gives simulations and analytical results for the power spectra of such attractors. The power spectra are Fourier transforms of autocorrelation functions which are exponentially damped (sometimes with oscillations). The characteristic length scale is related to nontrivial eigenvalues of the arc-to-arc transition matrix in the regular language graph.