\documentclass[11pt]{article}
\usepackage{amssymb,amsfonts,amsmath, psfrag, amscd, cite}
\usepackage{graphicx}
\parskip=7pt
\parskip=8pt
\newtheorem{theo}{Theorem}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{coro}[theo]{Corollary}
\newtheorem{defi}[theo]{Definition}
\newtheorem{lemm}[theo]{Lemma}
\newtheorem{rema}[theo]{Remark}
\newtheorem{exam}[theo]{Example}
\makeatletter \@addtoreset{equation}{section}
\@addtoreset{theo}{section} \makeatother
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\renewcommand{\thesection}{\arabic{section}.}
\renewcommand{\thetheo}{\arabic{section}.\arabic{theo}}
\def\qed{\hfill \rule{4pt}{7pt}}
\def\pf{\noindent {\it Proof.} }
\begin{document}
\begin{center}
{\bf\Large Discrete Dynamical Systems \\
\vspace{2mm}
on Graphs and Boolean Functions}
\end{center}
\vskip 1cm
\begin{center}
Chris L.~Barrett$^1$, William Y. C. Chen$^2$, Michelle J. Zheng$^3$\\
\vskip 0.5cm
{ $^{1}$Los Alamos National Laboratory\\
CCS-5, MS M997, Los Alamos, NM 87545, USA\\
\vskip 3mm
$^{2,3}$Center for Combinatorics, LPMC\\
Nankai University, Tianjin 300071, P. R. China}
Email: $^{1}$barrett@lanl.gov, $^{2}$chen@nankai.edu.cn,
$^{3}$jzheng@eyou.com
\end{center}
{\bf Abstract.} Discrete dynamical systems based on dependency
graphs have played an important role in the mathematical theory of
computer simulations. In this paper, we are concerned with
parallel dynamical systems (PDS) and sequential dynamical systems
(SDS) with the OR and NOR functions as local functions. It has
been recognized by Barrett, Mortveit and Reidys that SDS with the
NOR function are closely related to combinatorial properties of
the dependency graphs. We present an evaluation scheme for systems
with the OR and NOR functions which can be used to clarify some
basic properties of the dynamical systems. We show that for
forests that does not contain a single edge the number of
orientations equals the number of different OR-SDS.
{\bf Keywords:} Parallel dynamical system (PDS), sequential
dynamical system (SDS), Garden of Eden (GOE), state space, fixed
point, periodic point.
{\bf AMS Classification:} 37B99, 68Q20
{\bf Corresponding Author:} William Y.C. Chen, chen@nankai.edu.cn
\newpage
\section{Introduction}
Computer simulations are used more and more frequently in the
modern technological society. This calls for a mathematical theory
for simulations. There are two elementary elements associated with
a simulation: local rules and dependency relations. In a
simulation, there are many (maybe infinitely many) entities and
each entity has a state at a given time. The update of states is
determined by the local rules and the dependency relations.
Moreover, there are two kinds of update schemes: {\it parallel
update} and {\it sequential update}. Both update schemes have been
extensively studied in the literature.
We review the following model of discrete dynamical systems based
on a graph, which is called a dependency graph. An entity is
represented by a vertex of a graph. Two vertices are joined by an
edge if they interfere with each other in the update process. More
specifically, an update is implemented by local functions defined
for each vertex. For a vertex $v$, the local function depends on
the state of the vertex $v$ itself and the states of the neighbors
of $v$. If the states of the vertices are updated in a parallel
manner, the system is called a {\it parallel dynamical system}
(PDS). If the update is carried out in a sequential order, then
the system is called a {\it sequential dynamical system} (SDS). In
the sequential case, a permutation on the vertices is used to
specify the order of updates, see, for example, \cite{Barrett,
Reidys1999, Reidys2000, Reidys2001c, Reidys2003, Colon, Laub1,
Laub2, Reidys2001b, Reidys1998, Reidys2001}.
In this paper, we are particularly concerned with the four kinds
of dynamical systems: $OR$-PDS, $OR$-SDS, $NOR$-PDS and $NOR$-SDS.
For each of these systems, we present an evaluation theorem on the
update of the global state vectors. In fact, the state vectors are
represented by subsets of the vertex set of the dependency graph.
Such evaluation schemes turn out to be useful for the study of
properties of the dynamical systems. We demonstrate that many
properties of the dynamical systems can be characterized by the
dependency graphs. For the AND and NAND functions, we may
construct the dynamical systems based on the OR and NOR systems,
thus, we do not need to consider systems with these two Boolean
functions.
We prove that the state spaces of PDS $[OR,G]$ and SDS
$[OR,G,\pi]$ have $2^k$ components if $G$ has $k$ components; The
width of PDS $[OR,G]$ equals to the diameter of $G$, where the
width of a dynamical system on a graph is defined to be the
maximum distance from a transient state vector to the nearest
fixed state vector or periodic state vector; The width of SDS
$[OR,G,\pi]$ does not exceed the diameter of $G$ for any $\pi\in
S_n$; Any orbit (limit cycle) of PDS $[NOR,G]$ has length $2$;
There is a bijection between the periodic points of SDS
$[NOR,G,\pi]$ and the independent sets of $G$; The widths of PDS
$[NOR,G]$ and SDS $[NOR,G,\pi]$ are both equal to $1$. The maximal
in-degree in the state space of PDS $[NOR,G]$ is equal to the
number of dominant sets of $G$, which is reached by the state
vector $(0,0,\cdots,0)$. Analogously, the maximal in-degree in the
state space of SDS $[NOR,G,\pi]$ is reached by the state vector
$(0,0,\cdots,0)$.
We also show that for forests that do not contain a single edge
the number of orientations equals the number of different OR-SDS.
%********************************************************************************
\section{Definitions and Notations}
All the dynamical systems are assumed to be built on an undirected
graph $G=(V,E)$, which is called the dependency graph. The graph
$G$ is supposed to have vertex set $V=\{1,2,\cdots,n\}$. For each
vertex $1\leq i\leq n$, there is a state
$x_i\in\mathbb{F}_2=\{0,1\}$. For $1\leq i\leq n$ and a subset
$W\subseteq V$, we define \begin{eqnarray*}
N_G(i) & =& \{j\in V|(i,j)\in E\}, \\[6pt]
d_i & = & |N_G(i)|, \\[6pt]
N_G(W) & = & \bigcup_{i\in W}N_G(i), \\[6pt]
\overline{N_G(i)}& = & \{i\}\cup N_G(i).
\end{eqnarray*}
For a dynamical system on $G$, there is a local function
associated with each vertex $i$. This is a function to update the
state of the vertex $i$ based on the state of $i$ itself and the
states of the neighbors of $i$. We will be concerned with the
local functions that are symmetric on the input states. Under this
assumption, the update of the state of vertex $i$ is determined by
the states of these vertices that are related to $i$, regardless
of the order of the related vertices. In fact, the local functions
considered in this paper will be the Boolean functions OR and NOR.
As to the state vector $X=(x_1, x_2, \ldots, x_n)$ of the vertices
$V= \{ 1, 2, \ldots, n\}$, we can use a subset $W$ of $V$ to
represent the state vector $X$ by taking the elements $i$ for
which $x_i=1$ into the subset $W$.
\begin{defi}\label{pds}
Let $G$ be a graph on $V=[n]$. The following mapping
\begin{eqnarray*}
[F,G]:\mathbb{F}_2^n & \mapsto & \mathbb{F}_2^n,\\[6pt]
{[}F,G](x_1,x_2,\cdots,x_i,\cdots,x_n) & = &
(y_1,y_2,\cdots,y_i,\cdots,y_n ),
\end{eqnarray*}
is called a parallel dynamical system (PDS) over $G$, where $y_i$
is the updated state of vertex $i$ by applying the local function
of vertex $i$ with respect to the dependency graph $G$.
\end{defi}
Let $f_{i, G}$ be a local update function of the vertex $i$ with
respect to the dependency graph $G$, and let $F_{i, G}$ be the
update function on the global state vector by applying the local
function to update the state of vertex $i$, while keeping other
states unchanged. If we compose the functions $F_{i,G}(1\leq i\leq
n)$ according to a given order $\pi\in S_n$, where $S_n$ is the
set of permutations on $V$, then we can get an update function
from $\mathbb{F}_2^n$ to $\mathbb{F}_2^n$.
\begin{defi}\label{sds}
Let $G$ be a graph on $V=[n]$ and $\pi=\pi_1\pi_2\cdots\pi_n\in
S_n$. The mapping
\begin{equation*}
[F,G,\pi]= F_{{\pi_1},G} F_{\pi_2, G} \cdots F_{\pi_n, G}:
\mathbb{F}_2^n\mapsto\mathbb{F}_2^n
\end{equation*}
is called a sequential dynamical system (SDS) over $G$.
\end{defi}
We note that in the above notation of composition of functions, we
assume that the function $F_{\pi_1, G}$ is applied first,
$F_{\pi_2, G}$ is applied next, and so on, namely,
\[ F_{{\pi_1},G} F_{\pi_2, G}\cdots F_{\pi_n, G} (x_1, \ldots, x_n)
= F_{\pi_n, G}( \cdots F_{\pi_1,G}(x_1, \ldots, x_n)).\]
We will usually
use $X$ to denote a state vector $(x_1, x_2, \ldots, x_n)$, and
use $g$ to denote the global update function of a dynamical system
which acts on state vectors. The set of all state vectors is
called the state space. Given a dynamical system with global
update function $g$, we may describe the following terminology.
\begin{enumerate}
\item If $g(X)=X$, then $X$ is called a {\it fixed point}. The
notation $FIX[g]$ represents the set of all fixed points of the
dynamical system with global update function $g$.\\
\item If there exists an integer $m>1$ such that $g^m(X)=X$ and
for any integer $01$, which is contradictory to the fact that the
state vector $X$ corresponding to the subset $W$ is a periodic
point. So the claim is justified, and we get
$$\phi_{[NOR,G]}(W)=W'\mbox{ and } \phi_{[NOR,G]}(W')=W.$$
That is to say, $\phi_{[NOR,G]}^2(W)=W$. This completes the proof.
\qed
We next show that the functional digraph of PDS $[NOR, G]$ has
quite a simple structure.
\begin{theo}
The width of PDS $[NOR, G]$ is equal to $1$.
\end{theo}
\pf Let $X$ be a state vector and $W$ be the subset corresponding
to $X$. By Theorem \ref{pnor3}, it suffices to show that
$\phi^3_{[NOR,G]}(W)=\phi_{[NOR,G]}(W)$. Let
$$W_1=\phi_{[NOR,G]}(W),\quad W_2=\phi_{[NOR,G]}(W_1), \quad W_3
=\phi_{[NOR,G]}(W_2).$$ It is easy to verify that
$N_G(W_1)=N_G(W_2)$. Thus we have
\begin{eqnarray*}
W_3 &=&(V\setminus W_2)\setminus N_G(W_2)\\[6pt]
&=&(V\setminus (V\setminus W_1\setminus N_G(W_1)))\setminus
N_G(W_2)\\[6pt]
&=&W_1\cup (N_G(W_1)\setminus N_G(W_2))\\[6pt]
&=&W_1.
\end{eqnarray*}
This is to say, $\phi^3_{[NOR,G]}(W)=\phi_{[NOR,G]}(W)$. \qed
Note that the above theorem can be restated as
\begin{equation}
GOE[NOR,G]\cup PER[NOR,G]=\mathbb{F}_2^n.
\end{equation}
The following theorem shows that the maximum in-degree of the
functional digraph of the system $[NOR, G]$ is related to the
dominant sets of the dependency graph $G$.
\begin{theo}\label{maxdeg}
In the functional digraph $\Gamma[NOR,G]$, the maximum in-degree
is reached by the state vector $X=(0,0,\cdots,0)$, and it is equal
to the number of dominant sets of $G$.
\end{theo}
\pf By the evaluation theorem of PDS $[NOR, G]$, one sees that for
any subset $W'$, $\phi_{[NOR,G]}(W)=W'$ if and only if $W$ is a
dominant set of the graph $G[V\setminus W']$, the induced subgraph
of $G$ restricted to $V\setminus W'$. In particular,
$W'=\emptyset$ if and only if $W$ is a dominant set of $G$. From
Theorem \ref{pnor1}, it follows that the in-degree of
$X=(0,0,\cdots,0)$ equals to the number of dominant sets of $G$.
We continue to show that the in-degree of the state vector $X=(0,
0, \ldots, 0)$ in $\Gamma[NOR, G]$ is indeed the maximum
in-degree. For any subset $W'$, if $\phi_{[NOR,G]}(W)=W'$, then
$\phi_{[NOR,G]}(W\cup W')=\emptyset$. This implies that from a
pre-image of $W'$, we can find a pre-image of $\emptyset$.
Moreover, for any two distinct pre-images $W_1$ and $W_2$ of $W'$,
we have $W_1\cap W'=\emptyset$ and $W_2\cap W'=\emptyset$. It
follows that
\begin{equation}\label{con1}
W_1\cup W'\neq W_2\cup W'.
\end{equation}
Furthermore, $W_1\cup W'$ and $W_2\cup W'$ are both dominant sets
of $G$, namely,
\begin{equation}\label{con2}
\phi_{[NOR,G]}(W_1\cup W' )=\phi_{[NOR,G]}(W_2\cup W')=\emptyset.
\end{equation}
Therefore, for any two distinct pre-images of $W'$, there are two
distinct pre-images of $\emptyset$. So we obtain that
$$|\phi^{-1}_{[NOR,G]}(W')|\leq|\phi^{-1}_{[NOR,G]}(\emptyset)|.$$
This completes the proof. \qed
%********************************************************************************************
\section{$NOR$-SDS}
In this section, we study sequential dynamical systems with NOR
function as the local update functions, denoted by $[NOR,G,\pi]$
for a given dependency graph $G$. These systems have been studied
by Reidys \cite{Reidys2001}. We give the following evaluation
theorem which is useful to give a simpler augment for the results
obtained by Reidys.
\begin{theo}\label{snor1}
Let SDS $[NOR,G,\pi]$ be a NOR-SDS on $G$. Let $X$ be a state
vector and $W$ be the subset of $V$ corresponding to $X$. Let
$\phi_{[NOR,G,\pi]}$ be the global update function acting on
subsets of $V$ in accordance with the NOR-SDS with dependency
graph $G$. Then we have
\begin{equation}\label{snordef}
\phi_{[NOR,G,\pi]}(W)=\rho_{\pi_n}(\rho_{\pi_{n-1}}\cdots(\rho_{\pi_1}(W))),
\end{equation}
where \begin{eqnarray*}
\rho_{i}(W)&=& \left\{
\begin{array}{ll}
W\setminus\{i\},& \mbox{ if } i\in W,\\[8pt]
W\cup\{i\}, & \mbox{ if } \overline{N_G(i)}\cap W=\emptyset,\\[8pt]
W, & \mbox{ otherwise. }
\end{array}
\right.
\end{eqnarray*}
\end{theo}
An instant consequence of the above theorem is that the functional
digraph $\Gamma[NOR,G,\pi]$ has no fixed points. Furthermore, we
may use the above evaluation scheme to simplify proofs of several
results of Reidys. The set of independent sets of $G$ will be
denoted by $D_G$\cite{bela}.
\begin{lemm}\label{snor2}
For any subset $W$ of $V$, $\phi_{[NOR,G,\pi]}(W)$ forms an
independent set of $G$.
\end{lemm}
\pf Assume that there exists a subset $W$ such that
$\phi_{[NOR,G,\pi]}(W)\notin D_G$. Then there are two elements
$i,j$ in $\phi_{[NOR,G,\pi]}(W)$ such that $(i,j)$ is an edge of
$G$. Without loss of generality, we may assume that $i<_{\pi}j$
and $j=\pi_k$ for some $k$. Since $i$ is in the subset
$\rho_{\pi_{k-1}}(\rho_{\pi_{k-2}}\cdots(\rho_{\pi_1}(W)))$, after
the action of $\rho_j$ on the subset
$\rho_{\pi_{k-1}}(\rho_{\pi_{k-2}}\cdots(\rho_{\pi_1}(W)))$,
$j$ is not contained in $\rho_{\pi_{k}}(\rho_{\pi_{k-1}}\cdots(\rho_{\pi_1}(W)))$.
This leads to a contradiction. \qed
Next we show that the mapping $\phi_{[NOR,G,\pi]}$ induces a
bijection on ${D_G}$. In other words, $\phi_{[NOR, G, \pi]}$ maps
an independent set to an independent, and the mapping is
one-to-one.
\begin{lemm}\label{snor3}
For any permutation $\pi$ on $[n]$, the mapping
$\phi_{[NOR,G,\pi]}$ yields a bijection on the set of independent
sets of $G$.
\end{lemm}
\pf By the finiteness of $D_G$, we only need to prove that
$\phi_{[NOR,G,\pi]}$ over $D_G$ is an injection. Suppose that
$W_1$ and $W_2$ are two different independent set of $G$ such that
\begin{equation}\label{assu}
\phi_{[NOR,G,\pi]}(W_1)=\phi_{[NOR,G,\pi]}(W_2).
\end{equation}
Let $k_0$ be the first element in $\pi$ that appears in $W_1\cup
W_2\setminus (W_1\cap W_2)$. Without loss of generality, we assume
that $k_0\in W_1 $ and $k_0\notin W_2$. Then there exists
$k_1>_{\pi}k_0$ such that $k_1\in W_2$, $k_1\notin W_1$ and
$(k_0,k_1)\in E$. Similarly, for $k_1\in W_1\cup
W_2\setminus(W_1\cap W_2)$, there exists $k_2>_{\pi}k_1$ such that
$k_2\in W_1$, $k_2\notin W_2$ and $(k_1,k_2)\in E$. By iterating
this procedure, we will fail at certain point to find
$k_i>_{\pi}k_{i-1}$ such that $k_i\in W_1$, $k_i\notin W_2$ and
$(k_{i-1},k_i)\in E$, or to find $k_i>_{\pi}k_{i-1}$ such that
$k_i\in W_2$, $k_i\notin W_1$ and $(k_{i-1},k_i)\in E$. Hence we
get $k_{i-1}\in\phi_{[NOR,G,\pi]}(W_1)$ and
$k_{i-1}\notin\phi_{[NOR,G,\pi]}(W_2)$, or get
$k_{i-1}\in\phi_{[NOR,G,\pi]}(W_2)$ and
$k_{i-1}\notin\phi_{[NOR,G,\pi]}(W_1)$. This is contradictory to
the assumption (\ref{assu}). \qed
The above Theorem \ref{maxdeg} has the following counterpart for
SDS $[NOR, G, \pi]$. The proof is essentially the same.
\begin{lemm}
For any subset $W$ of $V$, we have
$$|\phi^{-1}_{[NOR,G,\pi]}(W)|\leq|\phi^{-1}_{[NOR,G,\pi]}(\emptyset)|.$$
\end{lemm}
From the above three lemmas, we get the following results due to
Reidys \cite{Reidys2001}.
\begin{theo}\label{snorr1}
The width of SDS $[NOR,G,\pi]$ equals to $1$.
\end{theo}
\begin{theo}\label{snorr2}
There is a bijection between the set of the periodic points of
$[NOR,G,\pi]$ and the set of the independent sets of $G$.
\end{theo}
\begin{theo}\label{snorr3}
In the functional digraph $\Gamma[NOR,G,\pi]$, the maximal
in-degree is reach by the state vector $X=(0,0,\cdots,0)$.
\end{theo}
The following example is an illustration of Theorem \ref{snorr1},
Theorem \ref{snorr2} and Theorem \ref{snorr3}.
\begin{exam}
Let $G$ be the following graph with independent sets: $\emptyset$,
$\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,4\}$, $\{2,4\}$.
\begin{center}
\setlength{\unitlength}{1mm}
\begin{picture}(70,30)
\put(4,4.5){\line(2,1){19}} \put(4,23.5){\line(2,-1){19}}
\put(4,4.5){\line(0,1){19}} \put(22.5,14){\line(1,0){25}}
\put(4,4.5){\circle*{1}} \put(4,23.5){\circle*{1}}
\put(22.5,14){\circle*{1}} \put(47.5,14){\circle*{1}}
\put(0,3.5){$2$} \put(0,22.5){$1$} \put(22.5,10){$3$}
\put(47.5,10){$4$}
\end{picture}
\end{center}
By Theorem \ref{snorr1} and Theorem \ref{snorr2}, we obtain that
for any $\pi\in S_n$,
$$PER[NOR,G,\pi]=\{0000,1000,0100,0010,0001,1001,0101\},$$ and
$$GOE[NOR,G,\pi]=\{0011,0110,0111,1010,1011,1100,1101,1110,1111\}.$$
Moreover, for the permutation $\pi=3124$, the in-degrees of the
periodic points $0000$, $1000$, $0100$, $0010$, $0001$, $1001$,
$0101$ in the functional digraph $\Gamma[NOR,G,3124]$ are
respectively $4$, $2$, $2$, $1$, $4$, $1$, $2$.
\end{exam}
%******************************************************************************************
\vspace{1cm} \noindent{\bf Acknowledgments.} We would like to
thank Arthur L. B. Yang and Chao Wang for valuable discussions. We
are also grateful to the referees for helpful suggestions. This
work was done under the auspices of the ``973'' Project on
Mathematical Mechanization and the National Science Foundation of
China.
\begin{thebibliography}{99}
\bibitem{Barrett}
C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J.
Rosenkrantz and R. E. Stearns, On some special classes of
sequential dynamical systems, Ann. Combin., {\bf 7} (2003),
381--408.
\bibitem{Reidys1999}
C. L. Barrett and C. M. Reidys, Elements of a theory of computer
simulation I: Sequential CA over random graphs, Appl. Math.
Computation, {\bf 98} (1999), 241--259.
\bibitem{Reidys2000}
C. L. Barrett, H. S. Mortveit and C. M. Reidys, Elements of a
theory of computer simulation II: sequential dynamical systems,
Appl. Math. Computation, {\bf 107} (2002), 121--136.
\bibitem{Reidys2001c}
C. L. Barrett, H. S. Mortveit and C. M. Reidys, Elements of a
theory of computer simulation III: Equivalence of SDS, Appl. Math.
Computation, {\bf 122} (2001), 325--340.
\bibitem{Reidys2003}
C. L. Barrett, H. S. Mortveit and C. M. Reidys, ETS IV: Sequential
dynamical systems: fixed points, invertibility and equivalence,
Appl. Math. Computation, {\bf 134} (2003), 153--171.
\bibitem{bela}
B. Bollob\'{a}s, Graph Theory: An Introductory Course,
Springer-Verlag, 1979.
\bibitem{Colon}
O. Col\'{o}n-reyes, R. Laubenbacher and B. Pareigis, Boolean
monomial dynamical systems, Ann. Combin., to appear.
\bibitem{Laub1}
R. Laubenbacher and B. Pareigis, Decomposition and simulation of
sequential dynamical systems, Adv. Appl. Math., {\bf 30} (2003),
655-678.
\bibitem{Laub2}
R. Laubenbacher and B. Pareigis, Finite dynamical systems,
Technical Report, Department of Mathematical Science, New Mexico
State University, Las Cruces, NM, 2000.
\bibitem{Reidys2001b}
H. S. Mortveit and C. M. Reidys, Discrete, sequential dynamical
systems, Discrete Math., {\bf 226} (2001), 281--295.
\bibitem{Reidys1998}
C. M. Reidys, Acyclic orientations of random graph, Adv. Appl.
Math., {\bf 21} (1998), 181-192.
\bibitem{Reidys2001}
C. M. Reidys, On acyclic orientations and sequential dynamical
systems, Adv. Appl. Math., {\bf 27} (2001), 790-804.
\end{thebibliography}
\end{document}