
1 Overview: PCA Models and Issues 3
sition probabilities is, however, local, and this makes PCA appealing as algorithms
for high-performance computing, distributed computing, and simulations. Indeed,
this locality makes the design of parallel implementations relatively straightforward,
both on distributed architectures (e.g., computing clusters) and on massively parallel
architectures (e.g., GPUs).
It is difficult to establish priorities and summarize the history of PCA develop-
ments. Their study was initiated by soviet mathematicians interested in artificial intel-
ligence and cybernetics. Initially, PCA were studied to determine the robustness of
CA dynamics subject to noise perturbation [92, 203]. In this setting, (non-)reliability
is related to (non-)ergodicity [66]. The well-known North-East-Center PCA rule (see
Sect.1.3.1 below) was introduced in 1978 by Toom [ 204 , for English translation] to
provide a first PCA with a non-trivial instance of rigorously proven lack of ergodic-
ity. Early applications also included models of neuronal networks [197], biological
systems [206], and large systems of interacting automata [209]. In a somewhat inde-
pendent way, PCA were studied in the 70’s and 80’s by probabilists [53, 54, 89, 123,
140, 141]—interested in their properties as stochastic processes—and by statisti-
cal physicists [102, 104, 112, 146, 214] interested in the study of equilibrium and
non-equilibrium statistical mechanical distributions on lattices. The interdisciplinary
nature of PCA studies has led to a convoluted history of independent rediscoveries
and alternative terminology. Initially, the automata were termed locally interacting
Markov chains; other names include stochastic CA or random CA. Some references
on applications are presented in Sect. 1.3.3. We refer to [185] and Part 1.4 in [159]
for surveys on historical aspects.
This introductory chapter presents some general types of phenomena that have
been represented through PCA, emphasizing open issues and challenges that will
be discussed in the remainder of this book. Our goal here is to exhibit the main
common ideas —that often traverse scientific boundaries—, leaving specific analyses
for relevant chapters. In doing so we have preferred to follow our personal, hence
subjective, viewpoints, avoiding exhaustiveness. We therefore apologize to the many
important actors of the field whose work we have failed to cite.
The rest of this chapter is organized in four sections. They deal, respectively, with
the following aspects: (1) paradigmatic examples of PCA and their mathematical
issues, (2) the three facesof the current interest in PCA: mathematical, computational,
and scientific modeling, (3) useful links and future directions of research, and (4)
summary of the structure of this book.
1.2 Phenomena Addressed by PCA Modeling
PCA dynamics belong to the category of non-equilibrium lattice models. In mod-
eling circles, a lattice is a graph defined by a countable set of vertices (called sites
or nodes) and a set of links. The latter are pairs of vertices usually visualized as a
segment joining them. A popular lattice is, for instance, Z
d
. The cells or elemen-
tary components of the automata sit in the vertices, and the links are interpreted as