Power Spectra of Regular Languages and Cellular Automata
Wentian Li · 1987
Abstract. The spatial structure of attractors produced by many oned imensional cellular automata can be described by regu lar languages. This paper gives simulations and analytical resu lts for the power spectra of such att ractors. The power spectra are Fourier t ransforms of autocorrelation functions which ar e 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. 1. Intro duction Spectra or Fourier transforms are some of the most frequently used tools in physics to reveal regularity in seemingly irregular behaviour. Recent examples in experimental physics include such events as the discovery of the so-called quasicryst aIs in MnAla by electron diffraction [11 which in effect is a spat ial Four ier transform, and t he observation of the pe riod-doubling rout e to chaos in Rayleigh-Bernard cells found by looking at the t emporal