Power Spectra of Regular Languages and Cellular Automata
Wentian Li
Center for Complex Systems Research,
University of Illinois at Urbana-Champaign,
508 South Sixth Street, Champaign, IL 61820, USA
and
Physics Department, Columbia University,
New York, NY 10027, USA
Abstract
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.
