text:
\chapter{Cellular Automata}

\section{Introduction}\label{cellularAutomataIntroduction}
Nowadays most of the basic natural phenomena are well described and known,
thanks to the effort of lots of scientist that studied the basic physic's laws for
centuries; for example, the freezing of water or the conduction that are well
know and qualitative analyzed. Natural system are usually composed by
many parts that interact in a complex net of causes/consequences that is at
least very difficult but most of the times impossible to track and so to
describe. Even if the single component are each very simple,
extremely complex behavior emerge naturally due to the cooperative effect of
many components. Much has been discovered about the nature of the components in
natural systems, but little is known about the interactions that these
components have in order to give the overall complexity observed.
Classical theoretical investigations of physical system have been based on
mathematical models, like differential equations, that use calculus as tool
to solve them, which are able to describe and allow to understand the
phenomena, in particular for those that can be described by which are linear
differential equation\footnote{Some electro-magnetism phenomena, for instance,
can be described by linear differential equations.} that are easy solvable with calculus.
Problems arise when non-linear differential equations come out from the
modellation of the phenomena, like fluid turbulence\footnote{Conventionally
described by Navier-Strokes differential equation.}.
Classical approach usually fails to handle these kind of equations due to the
too high number of components, that make the problem intractable even for a computer based numerical approach.
Another approach to describe such systems is to distill only the fundamental and
essential mathematical mechanism that yield to the complex behavior and at  the
same time capture the essence of each component process. Cellular automata are a
\begin{wrapfigure}{r}{0.40\textwidth}
\includegraphics[scale=0.9]{./images/torus-2}
\caption{3D cellular automata with toroidal cellular space.}\label{torus}
\end{wrapfigure}
candidate class of such systems and are well suitable for the modellation and
simulation of a wide class of systems, in particular those ones constructed from
\textbf{many identical} components, each (ideally) simple, but together capable
of complex behaviour\cite{Toffoli1984}\cite{toffoli1987}. In literature there
are lots applications of cellular automata in a wide rage of class problems from
gas\cite{Frisch1986} and fluid turbulence\cite{Succi1991} simulation to
macroscopic phenomena\cite{Gregorio1999} like epidemic
spread\cite{Sirakoulis2000}, snowflakes and lava
flow\cite{Crisci2004}\cite{Spataro2010}.
CA were first investigated by S. Ulam working on growth of crystals using
lattice network and at the same time by Von Neumann in order to study
self-reproduction\cite{Neumann1966}; it was not very popular until the 1970 and
the famous Conway's game of life\cite{Conway1970}, then was widely studied on
the theoretical viewpoint, computational universality were
proved\footnote{CA is capable of simulating a Turing machine, so, in theory is
capable of computing every computable problems(Church-Turing
thesis). Game of life, for example was proved to be capable
of simulating logical gates (with special patterns as
\textit{gliders} and \textit{guns})}\cite{Thatcher1970} and then mainly
utilised, after 1980's, as parallel model due to its intrinsically parallel nature implemented on parallel computers\cite{Margolus1986}.

\section{Informal Definition}

Informally a \emph{cellular automata} (CA) is a mathematical model that
consists of a discrete lattice of sites  and a value, the state, that is
updated in a sequence of discrete timestamps (steps) according to some logical rules that
depend on a neighbor  sites of the cell. Hence CA describe systems whose the
overall behavior and evolution of the system may be exclusively described on the basis of local
interactions\cite{wolfram1984}, property also called centrism.
The most stringent and typical characteristic of the CA-model is the restriction
that the local function does not depend on the time t or the place i: a cellular automaton has homogeneous
space/time behavior. It is for this reason that ca are sometimes referred to as
\textit{shift-dynamical} or \textit{translation invariant} systems. From another
point of view we can say that in each lattice site resides a finite state
automaton\footnote{A simple and well know computational model. It has inputs,
outputs and a finite number of states (hence a finite amount of memory);
An automata changes state at regular time-steps.}  that take as
input only the states of the cells in its neighborhood (see figure \ref{amod3Automata}).

\subsection{Cellular space dimension and geometry}
The cellular space is a \emph{discrete} d-dimensional lattice of sites (see
figure \ref{spazioCellulare}).
For 1-D automaton the only way to discretize the space is in a one-dimensional
grid. For automaton with dimensionality higher than 1 the shape of each cell can
be different than squared. In 2D tessellation for example each cell can be
hexagonal or triangular instead of squared. Each tessellation present advantages
and disadvantages. For instance the squared one does not give any graphical
representation problem\footnote{Each cell could be easily mapped onto a
pixel.}, but present problems of anisotropy for some kind of
simulations\footnote{The HPP model for fluid simulation was highly anisotropyc due to the squared tessellation.}\cite{Frisch1986}.
An Hexagonal tessellation can solve the anisotropy problem\cite{wolfram1986} but
presents obvious graphical issues. Often, to avoid complications
due to a boundary, periodic boundary conditions are used, so that a two-dimensional grid
is the surface of a torus (see picture \ref{torus}).

\subsection{Neighborhood}
\begin{figure}
\centering
\caption{Examples of cellular spaces. (a) 1-D, (b) 2-D squared cells,
(c) 2-D hexagonal cells, (d) 3-D cubic cells.}\label{spazioCellulare}
\includegraphics[scale=0.3]{./images/spazioCellulare}
\end{figure}
The evolution of a cell's state is function of the states of the neighborhood's
cells. The geometry and the number of cells that are part of the neighborhood
depends on the tessellation type, but it has to have three fundamental
properties:
\begin{enumerate}
  \item \textbf{Locality}. It should involve only a 'limited' number of cells.
  \item \textbf{Invariance}. It should not be changed during the evolution.
  \item \textbf{Homogeneity}. It has to be the same for each cell of the
  automaton.
\end{enumerate}
Typically neighborhood ``surrounds'' the central cell. For 1-D cellular automata
its borders are identified with a number $r $ called
\textit{radius}\cite{wolfram1983}. A $r=2$ identify
$n=2r+1$ cells in a 1D lattice: the central cell plus the
right and left cells. Typical 2D cellular space neighborhood are the those of
Moore and von Neumann neighborhood. The number of cells in the Moore
neighborhood of range r is the odd squares $(2r+1)^2,$ the
first few of which are 1, 9, 25, 49, 81, and so on as r is increased.
Von Neumann's one consist of the central cell plus the cell at north, south,
east, and west of the central cell itself. Moore's ($r=1$)
one add  the farther cells at north-east, south-east, south-west and north-west
(see figure \ref{mooreNeigh}).

\begin{figure}
\centering
\caption{Examples of different kind of neighborhood with
different radius values.}\label{mooreNeigh}
\includegraphics[scale=0.9]{./images/mooreNeigh}
\end{figure}

\subsection{Transition Function}
The evolution of the cell's state is decided by the transition function that
is applied at the same time and on each cell. Usually that transition function
is deterministic and defined by a \textit{look-up} table only when the total
number of state for each cell is small\footnote{Otherwise the dimension of that table would be enormous because the number of entries is exponential in the number of
states.} otherwise is defined by an algorithmic procedure.
It may be probabilistic, in the case of stochastic cellular automata.

\section{Formal Definition}
Cellular automata are dynamic models that are
discrete in time, space and state. A simple cellular
automaton A is defined by a lattice of cells each containing a finite state
automaton so we briefly give its definition.

\subsection{Finite State Automaton}\label{DFA}
Also known as deterministic finite automata (DFAs) or as deterministic finite
state machines, are ones of the most studied and simple computational model
known.
 It is a theoretical model of computation\footnote{Language recognition
problem solvers.} that can be in a finite number of states, only one at a time,
the current state. Its state can change in response of inputs taken by a
transition function that describe the state change given the current state and
\begin{wraptable}{r}{6.0cm}
\scalebox{1.2}{
\begin{tabular}{|c|ccccc|}\hline
\delta & \(a\) & \(b\) & \(c\) & \(d\) & \(e\) \\ \hline
\(q_0\) &\(q_0\) &\(q_0\) &\(q_2\) &\(q_1\) &\(q_1\)\\
\(q_1\) &\(q_1\) &\(q_3\) &\(q_1\) &\(q_1\) &\(q_1\)\\
\(q_2\) &\(q_3\) &\(q_2\) &\(q_2\) &\(q_0\) &\(q_1\)\\
\(q_3\) &\(q_0\) &\(q_1\) &\(q_1\) &\(q_0\) &\(q_1\) \\ \hline
 \end{tabular}
 }
 \caption{Tabular representation of a DFM's next-state function}
 \label{tab:tabularTransitionFunction}
\end{wraptable}
the received input of the automata.
Its a much more restrictive in its capabilities than a Turing
machines,\footnote{For example we can show that is not possible for an
automaton to determine whether the input consist of a prime number of symbols.}
but they are still capable to solve simpler problems, and hence to recognize
simpler languages, like well parenthesized string; More in general they are capable
to recognize the so called \emph{Regular languages}\footnote{Languages
defined by regular expressions and generated by regular grammar, Class 3 in
Chomsky classification. We can prove that for each language L accepted by a DFA
exists a grammar $L_G $ s.t. $ L=L_G$},
but they fail for example in parsing \emph{context-free} languages.
More formally a DFA is a 5-tuple:
\[M = <Q,\Sigma,\delta,q_0,F>\]

\begin{itemize}
  \item \textit{Q} is a finite, nonempty, set of states.
\item $\Sigma$ is the alphabet
\item $ \delta : Q \times \Sigma \longmapsto Q  $ is the
transition function (also called next-state function, may be represented in
tabular form  (see table
\ref{tab:tabularTransitionFunction})
\item $q_0 $ is the initial (or starting) state :
$ q_0 \in  Q $
\item  $F $ is the set, possibly empty, of final states :
$ F \subseteq Q $

\end{itemize}

A run of DFA on a input string $u = a_0,a_1,\ldots,a_n$ is a
sequence of states \\ $ q_0,q_1,\ldots,q_n$ s.t.
$q_i  \overset{a_i}{\longmapsto} q_{i+1} $,
$ 0 \leq i \le n$. It means that for each couple of state
and input the transition function deterministically return the next DFA's
state \\ $q_i=\delta(q_{i-1},a_{i}) $.
For a given word $\textit{w}\in \Sigma^* $ the DFA has a
unique run (it is deterministic), and we say that it \textbf{accepts} w if the
last state $q_n \in F $. A DFA recognizes the
language L(M) consisting of all accepted strings.

Figure \ref{amod3Automata} is an example of DFA\footnote{Graph representation
is the most common way to define and design DFA. Nodes are the states, and
the labelled edges are the possible states transition from a state \textit{u}
to a state \textit{w} given a certain input.
Note that, because the automaton is deterministic is not possible for two
edges to point to two different nodes if same labelled.}.
It accepts the language made up of strings with a number N s.t $N
\;mod\; 3 = 0 $
\begin{itemize}
  \item$ \Sigma = \{a,b\}$
  \item $ Q = \{t_0,t_1,t_2\}$
  \item $ q_0 = t_0$
  \item $ F = \{t_0\} $
\end{itemize}

If we execute the DFA on an input string S=\{aaabba\} we can see that at time
t=0 the DFA is in the initial state $t_0$ and the first
symbol of S is read.
The transition function is applied once per each symbol is S
(i.e. $\left\vert{S}\right\vert$). The only rule that match
the current state and input is $\delta=(t_0,a)=t_1 $ hence the
new state is $t_1$. The DFA accept the string only if  there
is not any input left and the current state is the final state
$q_f$\footnote{Previously we stated that F was a set but
we can assume that there is only one final state
($\left\vert{F}\right\vert=1$), because it is easy prove
that exist a DFA with only one final state given a generic DFA
($\left\vert{F}\right\vert \geq 1$). We add one more state
$q_f$ and for each final state $q_i \in
F$ we define new rules of the type $\delta(q_i,*)=q_f, * \in I $.}.
S is not accepted by the DFA defined in the example \ref{amod3Automata} because
at the end of the computation the reached state is $t_1$
that is not a final state.
 \[
 t_0\overset{\delta(t_0,a)}
 {\longmapsto}t_{1}\overset{\delta(t_1,a)}
 {\longmapsto}t_{2}\overset{\delta(t_2,a)}
 {\longmapsto} t_{0}\overset{\delta(t_0,b)}
 {\longmapsto}t_{0}\overset{\delta(t_0,b)}
 {\longmapsto}t_{0}\overset{\delta(t_0,a)}
 {\longmapsto} t_{1}
\]
On the input $S^1=\{abababb\}$ the DFA accept:
 \[
 t_0\overset{\delta(t_0,a)}
 {\longmapsto}t_{1}\overset{\delta(t_1,b)}
 {\longmapsto}t_{1}\overset{\delta(t_1,a)}
 {\longmapsto} t_{2}\overset{\delta(t_2,b)}
 {\longmapsto}t_{2}\overset{\delta(t_2,a)}
 {\longmapsto}t_{0}\overset{\delta(t_0,b)}
 {\longmapsto}t_{0}\overset{\delta(t_0,b)}
 {\longmapsto}\mathbf{t_{0}}
\]
\begin{figure}
\begin{center}
  \includegraphics[scale=0.17]{./images/amod3Automata}
  \caption{Graph representation of a DFA}
  \label{amod3Automata}
\end{center}
\end{figure}
\FloatBarrier

\section{Homogeneous Cellular Automata}\label{homogeneousCellularAutomata}
Formally a CA \emph{A} is a quadruple $ A=<Z^d,X,Q,\sigma>$
where:
\begin{itemize}
  \item $\mathbb{Z}^d=\{i=(i_1,i_1,\ldots,i_d)\mid i_k \in
  \mathbb{Z}, \forall k=1,2,\ldots,d \}$ is the set of cells of the d-dimensional
   Euclidean space.
  \item $X$ is the neighborhood, or neighborhood template; a
  set of m d-dimensional vectors (one for each neighbor)
  \[\xi_j=\{\xi_{j1},\xi_{j2},\ldots,\xi_{jd}\} \;,\: 1\leq j \leq m\] that
  defines the set of the neighbors cells of a generic cell
  $i=(i_1,i_1,\ldots,i_d)$
  \[
  N(X,i)=\{i+\xi_0,i+\xi_2,\ldots,i+\xi_d\}
  \] where $\xi_0$ is the null vector. It means that the
  cell $i$ is always in its neighborhood and we refer to it
  cell as \emph{central cell}  (see example below).
\item Q is the finite set of states of the elementary automaton EA.

  \item $\sigma=Q^m \rightarrow Q $ is the transition
  function of the EA. $\sigma$ must specify
  $q_k \in Q $ as successor  state of the central cell.
  If there are $m$ cells in the neighborhood of the central
  cell including itself, then there are
  ${\left\vert{Q}\right\vert}^m$ possible neighborhood's
  state configuration. It  means that there are
  ${\left\vert{Q}\right\vert}^{{\left\vert{Q}\right\vert}^m}$
  possible transition functions. Plus we can see that the tabular definition of
  the next-state function is unsuitable for practical purpose. It should have
  $\left\vert{\sigma}\right\vert={\left\vert{Q}\right\vert}^m$
  entries, an exceedingly large number.
  \item $\tau=C \longrightarrow C \longmapsto
  \sigma(c(N(X,i)))$ where $C=\Set*{c}{c \colon Z^d
  \rightarrow Q}$ is called the set of the possible configuration and
  $
  C(N(X,i)))$ is the set of states of the neighborhood of \textit{i}.
\end{itemize}

For example consider a 2D cellular automata with Moore neighborhood and a
generic cell c=(10,10) and ${\left\vert{Q}\right\vert}=5$
possible state for each cell .
\[X=\{\xi_{0},\xi_{1},\xi_{2},\xi_{3},\xi_{4},\xi_{5},\xi_{6},\xi_{7},\xi_{8}\}
=\]\[=\{(0,0),(-1,0),(0,-1),(1,0),(0,1),(-1,-1),(1,-1),(1,1),(-1,1)\}
\]
Hence the set of the cells belonging to the neighborhood(defined by X) of
c=(10,10) is:
$V(X,c)=\{(0,0)+c,(-1,0)+c,(0,-1)+c,(1,0)+c,(0,1)+c,(-1,-1)+c,(1,-1)+c,(1,1)+c,(-1,1)+c\}
$
\[=\{(10,10),(9,10),(10,9),(11,10),(10,11),(9,9),(11,9),(11,11),(9,11)\}
\]
and the total number of entries for the tabular definition of the
transition-function is  ${\left\vert{Q}\right\vert}^{\left\vert{X}\right\vert}=
5^9=1953125$ and the total number of possible transition functions
is
${\left\vert{Q}\right\vert}^{{\left\vert{Q}\right\vert}^{\left\vert{X}\right\vert}}=
5^{5^9}=5^{1953125}$.

\section{Theories and studies}

\subsection{Elementary cellular automata}
The most simple AC we can imagine are the elementary cellular
automata\cite{wolfram1983}. They are one-dimensional periodic N cells array
$\{C_i \mid 1\leq i \leq N, C_i \in \{0,1\} \}$ each
with 2 possible state (0,1), and rules that depend only on nearest neighbor
value hence a radius r=1 neighborhood with a total number of involved cell
$2r+1=2\times1+1=3$ (central, right and left cells).
Since there are only $2\times2\times2\times=2^{2r+1}=2^3=8$ possible states for
the neighborhood of a given cell there are a total of
$2^{2^3}=2^8=256$ possible elementary automata (each of
which may be identified with a 8-bit binary number\cite{wolfram2002}).

\subsubsection{Wolfram's code}
The transition function  is $F(C_{i-1},C_i,C_{i+1})$ is
defined by a look-up table of the form stated in table
\ref{wolframcodeGeneral}, and an example of an instance of a function is given
(rule 110, an important rule on which \cite{cook2004} proved universal
computational power, as Wolfram had conjectured in 1985, and is arguably the
simplest Turing complete system\cite{wolfram2002}) in table
\ref{wolframcodeGeneral}.

\begin{table}
\caption{Encoding of a transition function for a generic elementary CA. On the
right the instance 110.}
\centering
\begin{tabular}{l}
\label{wolframcodeGeneral}

\hfill \\
\hline
  $F(1,1,1)=\{0,1\}$  \\
  $F(1,1,0)=\{0,1\}$  \\
  $F(1,0,1)=\{0,1\}$  \\
  $F(1,0,0)=\{0,1\}$  \\
  $F(0,1,1)=\{0,1\}$  \\
  $F(0,1,0)=\{0,1\}$  \\
  $F(0,0,1)=\{0,1\}$  \\
  $F(0,0,0)=\{0,1\}$  \\
\hline
\end{tabular}
\quad
$\overset{instance}{\longrightarrow}$
\begin{tabular}{l}

\label{wolframcoderule}
\hfill \\
\hline
  $F(1,1,1)=0$  \\
  $F(1,1,0)=1$  \\
  $F(1,0,1)=1$  \\
  $F(1,0,0)=0$  \\
  $F(0,1,1)=1$  \\
  $F(0,1,0)=1$  \\
  $F(0,0,1)=1$  \\
  $F(0,0,0)=0$  \\
\hline
\end{tabular}
\end{table}

More generally Wolfram's code\cite{wolfram1983,wolfram2002} can be calculated
Conventionally neighborhoods are sorted in non-decreasing order
,(111=7),(110=6),(101=5) etc., and the may be interpreted as a 8-digit number
\[01101110=2^0\times0+2^1\times1+2^2\times1+2^\times1+2^4\times0+2^5\times1+2^6\times1+2^7\times0=110\]

\begin{enumerate}
  \item List and sort in decreasing numerical (if interpreted as number) order
  all the possible configuration of the neighborhood of a given cell.
  \item For each configuration, list the state which the given cell will have,
  according to this rule, on the next iteration.
  \item Interprets the resulting list as binary number and convert it to
  decimal. That  is the Wolfram's code.
\end{enumerate}

Note that is not possible to understand from that code which is the size or the
shape of the neighborhood. Is tacit to suppose that those information are
already known.

\subsection{Wolfram's classification}
Mathematical analysis of CA may be not so straightforward despite their simple
definition. A first attempt to classify CA was attempted by
Wolfram\cite{wolfram2002}. He proposed a set of four classes for CA
classification that are the most popular method of CA classification, but they
suffer from a degree of subjectivity. Classification is based only on visual
valuations, that are obviously subjective. A more rigorous definition of these
classes is given in \footnote{They prove that decide the class(from the
wolfram's four one) of membership of a generic CA is an undecidable problem. Is
not possible to design an algorithm that solve this problem.}\cite{culik1998}.
Here the four Wolfram's classes.
\begin{enumerate}

  \item these CA have the simplest behavior; almost all initial conditions
  result in the same uniform initial state (homogeneous state).
  \item different initial conditions yield different final patterns, but
  these different patterns consist of an arrangement of a certain set of
  structures, which stays the same forever or repeats itself within a few
  steps(periodic structures).
  \item behavior is more complicated and appears random, but some repeated
  patterns are usually present (often in the form of triangles)(chaotic pattern).
  \item in some respects these are the most complicated class; these behave
  in a manner somewhere in between Class II and III, exhibiting sections
  both of predictable patterns and of randomness in their pattern
  formation(complex structures).
\end{enumerate}
He observed that the behavior of a meaningful class of Cellular Automata
by performing computer simulations of the evolution of the automata starting
from random configurations. Wolfram suggested that the different behavior of
automata in his classes seems to be related to the presence of different types
of attractors.

In figures \ref{class12} and \ref{class34} some elementary automata divided
in their classes.\footnote{Images courtesy of
\url{http://plato.stanford.edu/entries/cellular-automata/}}

 \begin{figure}
 \caption{Class 1 (a,b) and 2 (c,d) elementary cellular automata}
 \label{class12}
\centering
        \subfigure[Rule 250]{%
            \label{fig:first}
            \setlength{\fboxrule}{1pt}%
             \fbox{\includegraphics[scale=0.32]{./images/rule250}}
        }%
        \subfigure[Rule 254]{%
           \label{fig:second}
           \setlength{\fboxrule}{1pt}
           \fbox{\includegraphics[scale=0.32]{./images/rule254}}
        } %  ------- End of the first row ----------------------%
         \subfigure[Rule 4]{%
            \label{fig:first}
            \setlength{\fboxrule}{1pt}
             \fbox{\includegraphics[scale=0.32]{./images/rule4}}
        }%
        \subfigure[Rule 108]{%
           \label{fig:second}
           \setlength{\fboxrule}{1pt}
           \fbox{ \includegraphics[scale=0.32]{./images/rule108}}
        }\\ %  ------- End of the first row ----------------------%

\end{figure}

We can well see from these examples that automata from class 1 have all cells
ending up very quickly with the same value, in a homogeneous state and automata
from class 2 with a simple final periodic patterns.
Class 3 appear to be chaotic and non-periodic and automata from class 4 have
a mixed behaviour, complex-chaotic structures are locally propagated.
\subsection{At the edge of Chaos}
Class 4 automata are at \emph{the edge of chaos} and give a good metaphor for
the idea that the \textit{interesting} complexity (like the one exhibit by
biological entities and their interactions or analogous to the phase transition
between solid and fluid state of the matter, is in equilibrium between
stability and chaos\cite{Langton1990}.

\begin{quotation}
\em Perhaps the most exciting implication (of CA representation of biological
phenomena) is the possibility that life had its origin in the vicinity of a
phase transition and that evolution reflects the process by which life has
gained local control over a successively greater number of environmental
parameters affecting its ability to maintain itself at a critical balance point
between order and chaos.\\
(\textit{\textbf{Chris Langton} - Computation at the edge of chaos.
Phase transition and emergent computation - pag.13}).
\end{quotation}

 \begin{figure}
\centering
 \caption{Class 3 (a,b) and 4 (c,d) elementary cellular automata}
\label{class34}
        \subfigure[Rule 30]{%
            \label{fig:first}
            \setlength{\fboxrule}{1pt}%
             \fbox{\includegraphics[scale=0.32]{./images/rule30}}
        }%
        \subfigure[Rule 90]{%
           \label{fig:second}
           \setlength{\fboxrule}{1pt}
           \fbox{\includegraphics[scale=0.32]{./images/rule90}}
        } %  ------- End of the first row ----------------------%
         \subfigure[Rule 54]{%
            \label{fig:first}
            \setlength{\fboxrule}{1pt}
             \fbox{\includegraphics[scale=0.32]{./images/rule54}}
        }%
        \subfigure[Rule 110]{%
           \label{fig:second}
           \setlength{\fboxrule}{1pt}
           \fbox{ \includegraphics[scale=0.32]{./images/rule110}}
        }\\ %  ------- End of the first row ----------------------%

\end{figure}
%%
% -------------- End of figure environment ----------------------%

Langton in his famous paper, \textit{Computation at the edge of chaos: phase
transition and emergent computation}\cite{Langton1990},was able to
identify, simply parametrizing the rule space, the various AC classes, the
relation between them and to ``couple'' them with the classical complexity classes.
He introduced the parameter $\lambda$\cite{LangtonThesis1990}that, informally, is simply
the fraction of the entries in the transition rule table that are mapped  the
not-quiescent state.
\[\lambda=\frac{K^N-n_q}{K^N}\]
where:
\begin{itemize}
  \item K is the number of the cell states
  \item N the arity of the neighborhood
  \item $n_q$ the number of rules mapped to the quiescent
  state $q_q$
\end{itemize}

\begin{figure}
\centering
\caption{Relation between lambda parameter and the CA
behaviors-Wolfram's classes.}\label{lambdaWolframClass}
\includegraphics[scale=0.4]{./images/edgeofchaos}
\end{figure}
Langton's major finding was that a simple measure such as it correlates with the
system behavior: as it goes from 0 to $ 1-\frac{1}{K}$(respectively the most
homogeneous and the most heterogeneous rules table scenario), the average
behavior of the system goes from freezing to periodic patterns to chaos and functions with an average
value of $\lambda$ (see \cite{Langton1990} for a
more general discussion) are being on \emph{on the edge}(see figure \ref{lambdaWolframClass}).

He studied a entire family of totalistic CA with $k=4
$ and $N=5$ with $\lambda$
varying in $[0,0.75]$. He was able to determine that values
of $\lambda\approx0.45$ raise up to class 4 cellular
automata.
Computational system must to provide fundamental properties if it is
to support computation. Only CA  \emph{on the edge} show these properties on
manipulating and store information data.
Here the properties that a computational system as to provide:
\begin{description}
  \item[Storage] \hfill \\
  Storage is the ability of the system of preserving information for
arbitrarily long times
  \item[Transmission] \hfill \\
  Transmission is the propagation of the information in the
form of signals over arbitrarily long distance
  \item[Modification] \hfill \\
Stored and transmitted
information is the mutual possible modification of two signals.

\end{description}

Storage is coupled with less entropy of the system, but transmission and
modification are not. Few entropy is associated with CA of Class 1 and 2 and
high entropy with class 3. Class 4 is something in between, the cells cooperate
and are correlate each other, but not too much otherwise they would be overly
dependent with one mimicking the other supporting computation in all its aspects
and requirements. Moreover class 4 CA are very dependent from the initial
configuration opening to the possibility to encode programs in it.

\subsection{Game of life}\label{sect:GOL}
CA are suitable for representing many physical, biological, social and other
human phenomena. But they are a good tool to study under which condition a
physical system supports the basic operation constituting the capacity to
support computation. Game of life is a famous 2D
cellular automaton of '70s early studied (and perhaps proved) for its universal
computation capacity.

\subsubsection{Game of life - brief definition}
Game of Life (see figure \ref{gameoflife}) (GOL)\cite{Conway1970} is a
totalistic CA\footnote{A totalistic cellular automaton is a cellular automata in which the rules depend only on the
total (or equivalently, the average) of the values of the cells in a neighborhood.} defined by :
\begin{itemize}
  \item a 2-D lattice of square cells in an orthogonal grid, ideally infinite
  \item $Q=\{0,1\} $ 2 states, and we can picture 1 as
  meaning alive and 0 dead (those interpretation come from the
behaviour of the next-state function).
\item $X$ is the Moore neighborhood template.
\item $\sigma$ is the transition function and can be
summarized :
	\begin{itemize}
	  \item \emph{Birth}: If the cell is in the state \textbf{\textit{dead}} and
	  the number of alive neighbors is \textbf{\textit{3}}, then the cell state
	  becomes alive (1).
	  \item \emph{Survival}: If the cell is in the state \textbf{\textit{alive}}
	  and the number of alive neighbors is \textbf{\textit{2 or 3}}, then the cell
	  state is still alive (1).
	  \item \emph{Dead}: If the cell is in the state \textbf{\textit{alive}} and
	  the number of alive neighbors is \textbf{\textit{less than 2 or higher
	  than 3}}, then the cell state becomes dead (0).
	  \end{itemize}
\end{itemize}

GOL is a class 4 Wolfram's taxonomy, rich complex structures, stable blocks and
moving patterns come into existence even starting from a completely random
configuration.
\begin{figure}
\centering
\caption{GOL execution example.}
\label{gameoflife}
\includegraphics[scale=0.9]{./images/game-of-life}
\end{figure}
\FloatBarrier

A famous block for example is the \emph{glider} ( see picture \ref{fig:glider}) that
is a 5-step-period pattern that is capable of moving into the cellular space.

\subsubsection{Game of life as Turing machine}
Every CA con be considered a device capable of supporting computation and the
initial configuration can encode an input string (a program for example). At
some point the current configuration can be interpreted as the result of the
computation and decoded in a output string. But as we stated before in section
\ref{DFA} not all the computational device have the same computational power. So
which is the one of the game of life? Life was proved can compute everything a
universal Turing machine can, and under Turing-Church's thesis, everything can
be computed by a computer\cite{berlekamp1982}.
\begin{figure}
\centering
\caption{Glider in Conway's game of life.}
\label{fig:glider}
\setlength{\fboxrule}{1pt}%
\fbox{\includegraphics[scale=0.9]{./images/glider}}
\end{figure}

This raises a computational issue; given the \emph{Halting
Theorem}\footnote{There can not be any algorithm to decide whether, given an
input, a Turing machine will accept or not.} the evolution of \emph{Life} is
unpredictable (as all the universal computational systems) so it means that is
not possible to use any algorithmically shortcuts to anticipate the resulting
configuration given an initial input. The most efficient way is to let the
system run.

\begin{quotation}
\em Life, like all computationally universal systems, defines the most efficient
simulation of its own behavior\cite{Ilachinski2001}
\end{quotation}

\section{Extension of the Cellular automata model}
It is possible to relax some of the assumptions in the general characterization
of CA provided in the ordinary CA definitions and get interesting results.
Asynchronous updating of the cell, non homogenous lattice with different
neighborhood or transition functions.

\subsection{Probabilistic CA}
Probabilist CA is are an extension of the common CA paradigm. They share all
the basic concept of an ordinary homogeneous
CA with an important difference in the transition function.
$\sigma$ is a stochastic-function that choose the next-state
according to some probability distributions. They are used in a wide class of
problems like in modelling ferromagnetism, statistical mechanics
\cite{Vichniac1984} or the cellular Potts model\footnote{Is a computational
lattice-based model to simulate the collective behavior of cellular structures.}

\subsubsection{Cellular automata as Markov process}
Another approach in studying CA, even if it is probably not a practical
way to study the CA is to see CA as a Markov process\footnote{Name for the
Russian mathematician Andrey Markov best known for his work on stochastic
processes.}. A Markov process, is a stochastic process that exhibits
memorylessness \footnote{Also called Markov property.} and it means that the
future state is conditionally independent\footnote{Two event
$A$ and $B$ are independent if
$P(A B)=P(A)P(B)$ or in other words that the conditional
probability $P(A|B)=P(A)$.} of the past.
This property of the process means that future probabilities of an event may be
determined from the probabilities of events at the current time.
More formally if a process has this property following  equation holds:
\begin{align*}
P(X(t_n)&= x \,| X\,(t_1) = x_1,X(t_2) = x_2, \ldots,X(t_{n-1})=x_{n-1}) \\
&= P(X(t_n)=x | X(t_{n-1}=x_{n-1})
\end{align*}

In PCA analysis we are more interested in Markov chain because each cell has a
discrete set of possible value for the status variable.
In terms of chain a CA is a process that starts in one of these states and moves
successively from one state to another. If the chain is currently in state
$s_i$, than it evolve to state $s_j$ at
the next step with probability $p_{ij}$.The changes of state
of the system are called transitions, and the probabilities associated with
various state changes are called transition probabilities usually represented
in the Markov chain transition matrix :
\[
M =
\left( {\begin{array}{cccc}
p_{11} & p_{12} & p_{13} &\cdots \\
p_{21} & p_{12} & p_{23} &\cdots \\
p_{31} & p_{32} & p_{33} &\cdots \\
\vdots & \vdots  &\vdots& \ddots\\
\end{array} } \right)
\]

This could seems to be a good way to analyze the probabilistic CA but, a
small grid  $10\times10$ (common models model use grid
$100\times100$ or larger) identify
$2^{10\times10}$possible states and the resulting matrix
dimension of $2^{10\times10}\times2^{10\times10}$ that is a
very large number!


text:
\documentclass[10pt]{article}
\usepackage{import}
\import{utils/}{utils.TeX}
% if table is used uncomment this below
\captionsetup[table]{position=bottom}

% \darkmode
\newcommand{\lrtitle}{Stirling Engine Lab}
\date{March 15, 2021}

\begin{document}
\createtitlepage
% \TOC % uncomment for Table of contents page

\section{Overview}

In this lab report we attempt to explore the performance of a real Stirling compared to the idealized Stirling engine and Carnot engine. To do this we considered
\bul{
\item Mechanical Work output of the engine
\item Efficiencies of the engines
\item Important assumptions made in calculations
}
to make judgements on how the engine performs with different power inputs.\\It was found that by increasing the power input, the power output increases (which is expected) but also the efficiency of the engine decreases. Hence I concluded that two heaters was the best choice when trying to optimize power output and efficency.

\section{Introduction}
\twoimg{imgs/fig1.PNG}{1}{Stages of the Stirling engine cycle}{fig1}{imgs/fig2.PNG}{.565}{$p-V$ diagram of Stirling engine cycle}{fig2}

\noindent
The role of the string energy is to convert heat to mechanical work, it achieves this by going through 4 stages in the cycle. The 4 stages are shown in \autoref{fig:fig1} and \autoref{fig:fig2}, the transition between stages can be used to explain how this engine works:

\bul{
\item Stage 1 to 2: The gas is hot therefore the pressure is high. The high pressure gas ``pushes" the work piston upwards, driving the flywheel. This represents an isothermal expansion, as the pressure decreases and the volume increases, as shown in the path from 1 to 2 in \autoref{fig:fig2}.
\item Stage 2 to 3: As displacement piston moves back down (due to the flywheels motion), the gas is exposed to the cool end of the engine hence it cools down at a constant volume (isochoric cooling). This is represented by going from Stage 2 to 3 on \autoref{fig:fig2}.
\item Stage 3 to 4: The both pistons now move down which causes the gas to be compressed (isothermally), hence its pressure increases.
\item Stage 4 to 1: The displacer piston now moves upwards exposing the air to the hot part of the cylinder. The air heats up at a constant volume (isochoric heating).
}

\noindent
Through repetition of this cycle we can see that the heat was used to drive the flywheel and successfully output mechanical work.\\[1em]
The area closed in the $p-V$ cycle (\autoref{fig:fig2}) represents the \textbf{Mechanical Work Output} of the engine. The power of the engine could then be calculated by dividing this work by the time taken for one cycle. The efficiency $\eta$ is

\eq{
    \eta = \frac{\text{Mechanical Work output}}{\text{Energy input used to heat up the engine}}
}

\section{Methodology}
\subsection{Small angle approximations}
Small angle approximations can be useful in simplifying equations. The two main small angle approximations that we could use for $\cos\theta$ are
\eq{
(1) \cos\theta = 1\hspace{5em}  (2) \cos\theta = 1-\frac{\theta ^2}{2}
}
The errors due to the approximations are shown in the table below

\begin{table}[h]
\centering
\begin{tabular}{@{}cc@{}}
\toprule
Approximation & \% Difference from true value of $[x/L_2]_{\theta = \theta _{max}}$ \\ \midrule
(1)           & +9.38                                                               \\
(2)           & +0.0305                                                             \\ \bottomrule
\end{tabular}
\caption{Errors due to approximations}
\label{table:approx}
\end{table}
\FloatBarrier
\noindent
\autoref{table:approx} shows that using approximation (2) seems to be the better option in terms of accuracy. But option (1) was chosen in the end as it vastly simplifies the equation for $x$, and the error due to this approximation is not too large.
\subsection{Energy calculation}
This section covers the approaches that can be used to calculate the work output, which is the area enclosed in a cycle in the $p-V$ graph.
\eq{
W=\hspace{-.5em}\oint\displaylimits_{\text{\hspace{.3em}cycle}}\hspace{-.5em}{pdV}
}
\subsubsection{Method 1 - Counting squares}
We calculate the area of one square, $A_{one}$ in the graph by multiplying the pressure and volume intervals between minor grid lines.\\
The the number of squares $N$ in cycle can be counted manually. Then the total work is just $NA_{one}$\\[1em]
\underline{Pros}
\bul{
\item Quick and to calculate
\item Gives a reasonably accurate answer (see \autoref{table:poeff})
}
\underline{Cons}
\bul{
\item High susceptible to human error
\item Not as accurate as numerical methods
}

\subsubsection{Method 2 - Cross product of vectors}
\label{Method 2}
We firstly defined a arbitrary vector in the form of $\bf{q}=\begin{pmatrix}p\\V\end{pmatrix}$ which for example is at the center of the $p-V$ cycle. Let us call this vector $\bf{q_{center}}$ where
\eq{
\bf{q_{center}}= \begin{pmatrix}p_{center}\\V_{center}\end{pmatrix}
}
The we consider the vector of two points 1 and 2 on the cycle which are close to each other $\bf{q_1},\bf{q_2}$. The area $\delta A$ of a triangle with vertices at point 1 and 2 and the center can be defined as
\eq{
\delta A = \frac{1}{2}\left|(\bf{q_1}-\bf{q_{center}})\times(\bf{q_2}-\bf{q_{center}})\right|
}
Then it is trivial that that total area under the graph which is the work, $W$ is
\eq{
W=\hspace{-.7em}\sum_{\text{All edges}}{\hspace{-.7em}\delta A}
}
\underline{Pros}
\bul{
\item Making the distance between edges very small will give us very accurate value of the area
\item No human error
}
\underline{Cons}
\bul{
\item Difficult to implement
}

\begin{table}[h]
\centering
\begin{tabular}{@{}ccccc@{}}
\toprule
&\multicolumn{2}{c}{\bfseries Method 1}
&\multicolumn{2}{c}{\bfseries Method 2}
\\
\cmidrule(lr){2-3} \cmidrule(l){4-5}
\bfseries Number of heaters
& Power/W & Efficiency/\%
& Power/W & Efficiency/\%
\\
\midrule
1 & 0.123 & 0.37 & 0.12 & 0.36 \\
2 & 0.250 & 0.39 & 0.21 & 0.36\\
3 & 0.345 & 0.36 & 0.35 & 0.34\\
\bottomrule
\end{tabular}

\captionof{table}{Power and efficiency calculations}
\label{table:poeff}
\end{table}
\FloatBarrier
\noindent
% \\[1em]
In the end the  \hyperref[Method 2]{cross product method} was chosen due to its far superior accuracy.

\section{Results}

\img{imgs/C1.pdf}{.8}{Processes on the Stirling and Carnot cycle}{process}
\noindent
\autoref{fig:process} shows the Carnot, Ideal Stirling, Real Stirling cycles. We can see that the area of the Carnot cycle is greater than the others implying that the Carnot cycle converts more heat to work, and hence is more efficient than the other cycles. Unsurprisingly the area under the ideal Stirling is greater than the real cycle due to all the energy losses, thus the ideal Stirling efficiency is greater than the real efficiency.
\pagebreak

\subsection{Difference between real and ideal cycles}
\twoimg{imgs/1heat.pdf}{1}{1 Heater}{1heat}{imgs/2heat.pdf}{1}{2 Heaters}{2heat}
\FloatBarrier
\img{imgs/3heat.pdf}{.6}{3 Heaters}{3heat}
\FloatBarrier
\noindent
From the figures above you can see that the real cycle deviates from the ideal cycle for all of the scenarios. \\The \emph{quasi-elliptical} shape of the real cycle is different because the volume varies near-sinusoidally with respect to time. The near-sinusoidal behaviour means at certain times the gas is being compressed very quickly resulting in a sudden increase in pressure (which is expected) but it also causes an sudden increase in temperature, this behaviour is evident when you look at the \emph{pseudo-isothermal compression} in \autoref{fig:3heat}, as the curve is above the real cycle, the temperature must have increased slightly (effectively moving up to another isotherm).\\ Consequently, from \autoref{fig:process}, we noted that the expansion is the slowest part of the cycle, meaning the variation in volume will not cause significant changes in the temperature (quasi-equilibrium), hence the curve of \emph{pseudo-isothermal expansion} should be reasonably close to the ideal cycle, which is exactly what the figures above show.
\\[1em]
As the number of heaters increase, the size of the closed cycle for all the processes increase, meaning the energy output increases. It is quite notable
when comparing \autoref{fig:1heat} to \autoref{fig:3heat} that the ratio of the area between the non-ideal Stirling cycle and the Carnot cycle ($\frac{A_{non-ideal}}{A_{carnot}}$) decreases. This means the Stirling engine has increasing energy loss hence it has a lower efficiency compared to the perfect Carnot cycle. This ratio is proportional to the \emph{exergy efficiency}, which is covered in the next section.
\pagebreak
\subsection{Variation of power and efficiencies}
\begin{table}[h]
\centering\begin{tabular}{@{}ccccc@{}}
\toprule
&\multicolumn{2}{c}{\bfseries Ideal Stirling}
&\multicolumn{1}{c}{\bfseries Carnot}
\\
\cmidrule(lr){2-3} \cmidrule(l){4-4}
\bfseries Number of heaters
& Energy output/J & Efficiency/\%
& Efficiency/\% & Exergy Efficiency/$\times 10^{-3}$
\\
\midrule
1 & 0.392 & 7.13 & 33 & 11.2 \\
2 & 0.532 & 6.05 & 43 & 9.09\\
3 & 0.671 & 6.67 & 51 & 7.05\\
\bottomrule
\end{tabular}
\caption{Carnot and Ideal Stirling efficiencies}
\label{table:c4}
\end{table}
\FloatBarrier
\noindent
It is import to realize that the calculations of efficiencies in \autoref{table:c4} assumes the temperature of the gas at the hot and cold side of the engine is equal to the temperature as each side of the engine.\\[1em]
\noindent
From both \autoref{table:poeff} and \autoref{table:c4} we can see that for the Stirling engine as the power input increases, the energy output increases. However for the non-ideal engine past 2 heaters we see that the efficiency starts decreases. This is because with 3 heaters the temperature difference between the hot end of the engine and the atmosphere is very large, thus there is a significant heat transfer between the the hot end and atmosphere which results in a substantial energy loss. It is then obvious that the \emph{actual temperature} of the air (when at the hot end) will be less than the temperature of the hot end of the engine. This very fact explains why there is such a large difference between the ideal Stirling efficiency and the real Stirling efficiency.\\
The Carnot efficiency represents the maximum possible efficiency that an engine could have. The equation for Carnot efficiency is
\eq{
\eta _{carnot} = 1-\frac{T_{cold}}{T_{hot}}
}
As it is just a function of temperature, increasing the power input should increases the efficiency, due to a higher values of $T_{hot}$.
\\
We can define a new term called, exergy efficiency which is
\eq{
\text{Exergy efficiency} = \frac{\text{Non-ideal Stirling efficiency}}{\text{Carnot efficiency}} = \frac{\text{Energy out}}{\text{Maximum possible energy out}}
}
This term quantitatively expresses how well a engine does compared to the Carnot engine (which is a theoretical ``perfect" engine). From \autoref{table:c4} you can see that increasing the energy input resulted in a decreases in exergy efficiency meaning the Stirling engine has an increasing power loss. \\So when you are implementing a Stirling engine you must make a comprise that for engines with higher output powers you are going to get a lower efficiency. In our scenario, 2 heaters had a relatively high power output and a better exergy efficient compared to the 3 heaters, so it would be the best one in terms of keeping the power and efficiency high.

\section{Conclusion}

In conclusion we have explored the methods that can be used to calculate the work done by a Stirling engine, and how a the real Stirling engine differs from the idealized engine that we are normally taught. Furthermore we compared our results to the theoretical best engine called the Carnot engine. This report demonstrated that for a real Stirling engine it is very import that we chose balance between power output and efficiency.

\end{document}

ext: tex

max_stars_repo_name: LakeeSiv/LaTeXTemplate

max_issues_repo_name: LakeeSiv/LaTeXTemplate

max_forks_repo_name: LakeeSiv/LaTeXTemplate


text:
%!TEX root = TTK4150-Summary.tex
\section{Lyapunov stability}

\paragraph{Lyapunov function (LF)}
$V(x)$ is an LF iff
\begin{itemize}
	\item $V \in C^1$
	\item $V(0) = 0$ \\
	      $V(x) > 0 \quad \forall \quad x \in \mathbb{D} \backslash \{0\}$
	\item $\dot{V}(0) = 0$ \\
	      $\dot{V}(x) \leq 0 \quad \forall \quad x \in \mathbb{D} \backslash \{0\}$
\end{itemize}

\paragraph{Strict Lyapunov function (SLF)}
$V(x)$ is an SLF iff it is an LF and
\begin{itemize}
	\item $\dot{V}(x) < 0 \quad \forall \quad x \in \mathbb{D} \backslash \{0\}$
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Autonomous systems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Theorem 4.1 (Direct Lyapunov method)}
\begin{itemize}
	\item If $\exists$ an LF for the origin, then the origin is stable.
	\item If $\exists$ an SLF for the origin, then the origin is asymptotically stable.
\end{itemize}

\paragraph{Theorem 4.2 (GAS)}
If $\exists$ an SLF $V$ for the origin and $V$ is radially unbounded, then the origin is globally asymptotically stable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Invariance principle}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Invariant set} A set $M$ is an \emph{invariant set} w.r.t. $\dot{x} = f(x)$ if
\begin{equation}
	x(0) \in M \implies x(t) \in M \quad \forall t \in \mathbb{R}.
\end{equation}
(Any solution in $M$ stays in $M$ for all future and past.)

\paragraph{Theorem 4.4 (LaSalle's theorem)}
If $\exists \: V : \mathbb{D} \to \mathbb{R}$ such that
\begin{itemize}
	\item $V \in C^1$,
	\item $\exists \: c > 0$ such that $\Omega_c = \{x \in \mathbb{R}^n | V(x) \leq c \} \subseteq \mathbb{D}$ is bounded,
	\item $\dot{V}(x) \leq 0 \quad \forall \quad x \in \Omega_c$.
\end{itemize}
Let $E = \{ x \in \Omega_c | \dot{V}(x) = 0 \}$. Let $M$ be the largest invariant set in $E$. Then
\begin{equation}
	x(0) \in \Omega_c \implies x(t) \xrightarrow{t \to \infty} M.
\end{equation}

\paragraph{Corollary 4.1} Let $x^* = 0$ for $\dot{x} = f(x)$. If for an LF $V(x)$ we have $\dot{V}(x) \leq 0$ on $D$: Let $S = \{ x \in D | \dot{V}(x) = 0 \}$ and only $x(t) \equiv 0$ can stay in $S$, then $x = 0$ AS.

\paragraph{Corollary 4.2} If corollary 4.1 holds with $D = \mathbb{R}^n$, then $x = 0$ GAS.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Linear systems and linearisation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Theorem 4.7 (Lyapunov's indirect method)}
Let $x^* = 0$ for $\dot{x} = f(x)$ where $f : \mathbb{D} \rightarrow \mathbb{R}^n$ satisfies $f \in \mathbb{C}^1$ and $\mathbb{D}$ is a neighborhood of the origin. Let
\begin{equation}
	% A = \pd{f}{x} (x) \evalat{x = 0}
	A = \pd{f}{x} (x) \big\rvert_{x = 0}
\end{equation}
and $\lambda_i$ be the eigenvalues of $A$. Then
\begin{enumerate}
	\item $\Re \lambda_i < 0 \mbox{ for all } \lambda_i \implies x = 0$ AS.
	\item $\Re \lambda_i > 0 \mbox{ for any } \lambda_i \implies x = 0$ unstable.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Comparison functions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Class $\mathcal{K}$ function}
A continuous function $\alpha : [0,a) \to [0, \infty)$ belongs to class $\mathcal{K}$ iff
\begin{itemize}
	\item it is stricly increasing,
	\item $\alpha(0) = 0$.
\end{itemize}

\paragraph{Class $\mathcal{K}_\infty$ function}
A continuous function $\alpha : [0,a) \to [0, \infty)$ belongs to class $\mathcal{K}_\infty$ iff
\begin{itemize}
	\item it is of class $\mathcal{K}$,
	\item $a = \infty$,
	\item $\alpha(r) \xrightarrow{r \to \infty} \infty$.
\end{itemize}

\paragraph{Class $\mathcal{KL}$ function}
A continunous function $\beta : [0,a) \times [0,\infty) \to [0,\infty)$ belongs to class $\mathcal{KL}$ if for each fixed $s$
\begin{itemize}
	\item $\beta(r,s)$ is a class $\mathcal{K}$ function w.r.t. $r$,
\end{itemize}
and for each fixed $r$
\begin{itemize}
	\item $\beta(r,s)$ is decreasing w.r.t. $s$,
	\item $\beta(r,s) \xrightarrow{s \to \infty} 0$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Nonautonomous systems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation}\label{eq:nonautonomous}
	\dot{x} = f(t,x), \quad f : [0,\infty) \times \mathbb{D} \to \mathbb{R}^n
\end{equation}

\paragraph{Decrescentness}
$V(t,x)$ is \emph{decrescent} iff
\begin{equation}
	\begin{rcases}
		V(t,0) =    0      \\
		V(t,x) \leq W_2(x)
	\end{rcases}
	\forall \: t \geq 0
	\mbox{, for some pos. def. }
	W_2(x).
\end{equation}

\paragraph{Theorem 4.8--4.9}
Let $V : [0,\infty) \times \mathbb{D} \to \mathbb{R}$ and $V \in C^1$ for \eqref{eq:nonautonomous}. Then $x^* = 0$ is
\begin{center}
	\begin{tabular}{lllll}
		& S & US & UAS & GUAS \\
		\hline
		$V$ & PD & PD, decr. & PD, decr. & PD, decr., RU \\
		$\dot{V}$ & NSD & NSD & ND & ND \\
		$\forall x \in$ & $\mathbb{D}$ & $\mathbb{D}$ & $\mathbb{D}$ & $\mathbb{R}^n$
	\end{tabular}
\end{center}
(PD = positive definite, decr. = decrescent, RU = radially unbounded, NSD = negative semidefinite, ND = negative definite.)

\paragraph{Theorem 4.10 (exponential stability)}
If $\exists \: a, k_1, k_2, k_3 > 0$ such that
\begin{itemize}
	\item $V \in C^1$
	\item $k_1 \norm{x}^a \leq V(x) \leq k_2 \norm{x}^a \quad \forall \: x \in \mathbb{D}$
	\item $\dot{V}(x) \leq - k_3 \norm{x}^a \quad \forall \: x \in \mathbb{D}$
\end{itemize}
then $x = 0$ ES. If $\mathbb{D} = \mathbb{R}^n$, $x = 0$ is GES.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Converse theorems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{Corollary 4.3}
The origin of $\dot{x} = f(x)$ is ES iff $A$ is Hurwitz, where
\begin{equation}
	A =
	\begin{bmatrix}
		\pd{f}{x}
	\end{bmatrix}
	% \evalat{x=0}
	\bigg\rvert_{x=0}
	.
\end{equation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Input-to-state stability}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation}\label{eq:iss-system}
	\Sigma: \quad \dot{x} = f(t,x,u)
\end{equation}

\paragraph{Theorem 4.19}
Let $V : [0,\infty) \times \mathbb{R}^n \to \mathbb{R}$ be cont. diff.able such that
\begin{equation}
	\alpha_1 \left( ||x|| \right) \leq V(t,x) \leq \alpha_2 \left( ||x|| \right)
\end{equation}
\begin{equation}
	\dot{V} \leq -W_3(x) \quad \forall \quad ||x|| \geq \rho \left( ||u|| \right) > 0
\end{equation}
$\forall (t,x,u) \in [0,\infty) \times R^n \times R^m$, where
\begin{itemize}
	\item $\alpha_1, \alpha_2 \in \mathcal{K}_\infty$,
	\item $\rho \in \mathcal{K}$, and
	\item $W_3(x)$ is a cont. pos. def. function on $\mathbb{R}^n$.
\end{itemize}
Then, the system is ISS with $\gamma=\alpha_1^{-1} \circ \alpha_2 \circ \rho$.

\paragraph{ISS vs. 0-GUAS}
\begin{gather}
	\Sigma \mbox{ ISS} \implies \Sigma \mbox{ 0-GUAS} \\
	\neg (\Sigma \mbox{ 0-GUAS}) \implies \neg (\Sigma \mbox{ ISS})
\end{gather}

\paragraph{Lemma 4.6 (ISS vs. 0-GES)}
For \eqref{eq:iss-system} with $f \in C^1$ and $f$ globally Lipschitz in $(x,u)$, then
\begin{equation}
	\Sigma \mbox{ 0-GES} \implies \Sigma \mbox{ ISS}
	.
\end{equation}

\paragraph{Lemma 4.7}
The cascade of a GUAS and an ISS system is ISS. (Output of GUAS is the input of ISS.)

max_stars_repo_path: TTK4150 Nonlinear control systems/sec-lyapunov-stability.tex

max_stars_repo_name: jakoblover/ntnu-course-summaries

max_issues_repo_name: jakoblover/ntnu-course-summaries

max_forks_repo_name: jakoblover/ntnu-course-summaries


text:
% This template is a modified version of one
% downloaded from a free templates website.
% Original documentation perserved below:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Medium Length Graduate Curriculum Vitae
% LaTeX Template
% Version 1.1 (9/12/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Rensselaer Polytechnic Institute (http://www.rpi.edu/dept/arc/training/latex/resumes/)
%
% Important note:
% This template requires the res.cls file to be in the same directory as the
% .tex file. The res.cls file provides the resume style used for structuring the
% document.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[margin, 10pt]{res} % Use the res.cls style, the font size can be changed to 11pt or 12pt here

\usepackage{helvet} % Default font is the helvetica postscript font
%\usepackage{newcent} % To change the default font to the new century schoolbook postscript font uncomment this line and comment the one above

\setlength{\textwidth}{5.1in} % Text width of the document

\begin{document}

%----------------------------------------------------------------------------------------
%	NAME AND ADDRESS SECTION
%----------------------------------------------------------------------------------------

\moveleft.5\hoffset\centerline{\large\bf Kelly Sovacool} % Your name at the top

\moveleft\hoffset\vbox{\hrule width\resumewidth height 1pt}\smallskip % Horizontal line after name; adjust line thickness by changing the '1pt'

%\moveleft.5\hoffset\centerline{123 Broadway} % professional / academic address
%\moveleft.5\hoffset\centerline{City, State 12345}
%\moveleft.5\hoffset\centerline{(000) 111-1111 or (111) 111-1112}

%----------------------------------------------------------------------------------------

\begin{resume}

%----------------------------------------------------------------------------------------
%	OBJECTIVE SECTION
%----------------------------------------------------------------------------------------

%\section{OBJECTIVE}

% text goes here

%----------------------------------------------------------------------------------------
%	EDUCATION SECTION
%----------------------------------------------------------------------------------------

\section{EDUCATION}

{\sl Bachelor of Science,} Biology \hfill 2014-2018 \\
University of Kentucky, Lexington, KY \\
Minor: Computer Science
\begin{itemize} \itemsep -2pt % Reduce space between items
\item 4-year Full Tuition Presidential Scholarship
\item Lewis Honors College
\item Honors Biology Scholar
\end{itemize}

%----------------------------------------------------------------------------------------
%	RESEARCH EXPERIENCE SECTION
%----------------------------------------------------------------------------------------

\section{RESEARCH}

{\sl Undergraduate Lab Assistant} \hfill 2015-present \\
Moseley Bioinformatics Lab, Dept. of Molec. \& Cell. Biochemistry, University of Kentucky
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Developing a computational tool for identifying sets of orthologous and paralogous gene products across any set of whole genomes to facilitate collinearity analysis and detection of gene duplication events.
\end{itemize}

{\sl BIO395 Independent Research Student} \hfill 2016-present \\
Weisrock Lab, Dept. of Biology, University of Kentucky
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Population structure analysis of the {\sl Ambystoma} tiger salamander complex.
\item Bayesian species delimitation of the {\sl Desmognathus} dusky salamander complex.
\item Writing Bash and Python scripts for managing sequence data.
\item Developing a SNP calling pipeline for amplicon sequence data
\end{itemize}

{\sl Undergraduate Lab Assistant} \hfill 2015-2016 \\
Jaromczyk Lab, Dept. of Computer Science, University of Kentucky
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Maintained the E. festucae genome project database.
\item Applied methods of processing RNA-seq data to {\sl C. quinoa} and the Coffee ringspot virus.
\end{itemize}

%----------------------------------------------------------------------------------------
%	AWARDS SECTION
%----------------------------------------------------------------------------------------

\section{AWARDS}

{\sl Oswald Research \& Creativity Award,} University of Kentucky \hfill 2017
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Awarded a \$200 prize for second place in the Biological Sciences category.
\item Manuscript title: Developing a Global Homology and Collinearity Analysis Framework for Identifying Gene Duplication Events. Supervised by Prof. Hunter NB Moseley.
\end{itemize}

{\sl Summer Research Grant,}  University of Kentucky \hfill 2017
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Awarded a \$2,000 grant by the UK Office of Undergraduate Research to work full time on a research project during the summer.
\item Project title: Developing a Global Homology and Collinearity Analysis Framework for Identifying Gene Duplication Events. Supervised by Prof. Hunter NB Moseley.
\end{itemize}

%----------------------------------------------------------------------------------------
%   PRESENTATIONS SECTION
%----------------------------------------------------------------------------------------

\section{POSTERS \& ORALS} % the word "PUBLICATIONS" was too long and ran into the title of the first one :(

{\sl Developing a Global Homology Analysis Framework for Comparative Genomics} \\
Supervised by Prof. Hunter NB Moseley.
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Poster presented at the Showcase of Undergraduate Scholars, University of Kentucky. April 25, 2018.
\item Oral presentation given at the Systems Biology \& Omics Integration Seminar Series, University of Kentucky. April 16, 2018.
\item Poster presented at the National Conference on Undergraduate Research, University of Central Oklahoma. April 4-7, 2018.
\end{itemize}

{\sl Processing RNA-seq Reads of Plants Infected with the Coffee Ringspot Virus} \\
Supervised by Profs. Jerzy W Jaromczyk and Michael M Goodin.
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Poster presented at the Showcase of Undergraduate Scholars, University of Kentucky. April 27, 2016.
\item Poster presented at the UT-KBRIN Bioinformatics Summit, Cadiz, KY. April 8-10, 2016.
\end{itemize}

{\sl The Effect of Meditation on Performance} \\
Supervised by Prof. Bruce O’Hara.
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Poster presented at the Showcase of Undergraduate Scholars, University of Kentucky. April 29, 2015
\end{itemize}

%----------------------------------------------------------------------------------------
%   OTHER WORK SECTION
%----------------------------------------------------------------------------------------

\section{OTHER WORK}

{\sl Tutor} \hfill 2012-2017
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Tutored high school and college students in Biology, Calculus, Chemistry, Computer Science, and Bioinformatics.
\end{itemize}

{\sl Sound Technician} \hfill 2009-present
\begin{itemize} \itemsep -2pt % Reduce space between items
\item Setting up, maintaining, repairing, and operating audio equipment for bands, churches, and other non-profit organizations.
\item Operating the front of house, monitor, and recording systems during sound checks, rehearsals, services, and concerts.
\item Training new sound techs in the art and science of live sound.
\end{itemize}

%----------------------------------------------------------------------------------------
\end{resume}
\end{document}

max_stars_repo_name: kelly-sovacool/latex-cv

max_issues_repo_name: kelly-sovacool/latex-cv

max_forks_repo_name: kelly-sovacool/latex-cv