Lyapunov Exponents and Synchronization of Cellular AutomataComplex Systems

In these notes we discuss the concept of Lyapunov exponents of cellular automata (CA). We also present a synchronization mechanism for CA. We begin with an introduction to CA, introduce the concept of Boolean derivative and show that any CA has a finite expansion in terms of the Boolean derivatives. The Lyapunov exponents are defined as the rate of exponential growth of the linear part of this expansion using a suitable norm. We then present a simple mechanism for the synchronization of CA and apply it to totalistic one-dimensional CA. The CA with a nonzero synchronization threshold exhibit complex nonperiodic space time patterns and vice versa. This synchronization transition is related to directed percolation. The synchronization threshold is strongly correlated to the maximum Lyapunov exponent and we propose approximate relations between these quantities.