\section{Introduction}
\label{S1}
+REVOIR TOUT L'INTRO et l'ABSTRACT en fonction d'asynchrone, chaotic
+
+
Several research works have proposed or run chaotic neural networks
these last years. The complex dynamics of such a networks leads to
various potential application areas: associative
qualitative and quantitative tools to evaluate the complex behavior of
a dynamical system: ergodicity, expansivity, and so on. More
precisely, in this paper, which is an extension of a previous work
-\cite{bgs11:ip}, we establish the equivalence between chaotic
+\cite{bgs11:ip}, we establish the equivalence between asynchronous
iterations and a class of globally recurrent MLP.
The investigation the converse problem is the second contribution:
we indeed study the ability for
section.
In what follows and for any function $f$, $f^n$ means the composition
-$f \circ f \circ \hdots \circ f$ ($n$ times).
+$f \circ f \circ \hdots \circ f$ ($n$ times) and an \emph{iteration}
+of a \emph{dynamical system} the step that consists in
+updating the global state $x$ with respect to a function $f$ s.t.
+$x^{t+1} = f(x^t)$.
\subsection{Devaney's chaotic dynamical systems}
Topological transitivity is checked when, for any point, any
neighborhood of its future evolution eventually overlap with any other
-given region. More precisely,
+given region. More precisely,
\begin{definition} \label{def2}
A continuous function $f$ on a topological space $(\mathcal{X},\tau)$
-is defined to be {\bf topologically transitive} if for any pair of
+is defined to be {\emph{topologically transitive}} if for any pair of
open sets $U$, $V \in \mathcal{X}$ there exists
$k \in
\mathds{N}^{\ast}$
element of regularity that a chaotic dynamical system has to exhibit.
\begin{definition} \label{def3}
-A point $x$ is called a {\bf periodic point} for $f$ of period~$n \in
+A point $x$ is called a {\emph{periodic point}} for $f$ of period~$n \in
\mathds{N}^{\ast}$ if $f^{n}(x)=x$.
\end{definition}
\begin{definition} \label{def4}
-$f$ is said to be {\bf regular} on $(\mathcal{X},\tau)$ if the set of
+$f$ is said to be {\emph{ regular}} on $(\mathcal{X},\tau)$ if the set of
periodic points for $f$ is dense in $\mathcal{X}$ ( for any $x \in
\mathcal{X}$, we can find at least one periodic point in any of its
neighborhood).
whole system. Then,
\begin{definition} \label{sensitivity}
-$f$ has {\bf sensitive dependence on initial conditions} if there
+$f$ has {\emph{ sensitive dependence on initial conditions}} if there
exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
$d\left(f^{n}(x), f^{n}(y)\right) >\delta $. The value $\delta$ is called the
- {\bf constant of sensitivity} of $f$.
+ {\emph{constant of sensitivity}} of $f$.
\end{definition}
Finally,
\begin{definition} \label{def5}
-The dynamical system that iterates $f$ is {\bf chaotic according to Devaney}
+The dynamical system that iterates $f$ is {\emph{ chaotic according to Devaney}}
on $(\mathcal{X},\tau)$ if $f$ is regular, topologically transitive,
and has sensitive dependence to its initial conditions.
\end{definition}
-Let us notice that for a metric space the last condition follows from
-the two first ones~\cite{Banks92}.
+In what follows, iterations are said to be \emph{chaotic according Devaney}
+when corresponding dynamical system is chaotic according Devaney.
+
+
+%Let us notice that for a metric space the last condition follows from
+%the two first ones~\cite{Banks92}.
\subsection{Asynchronous Iterations}
sequence defining which component to update at time $t$ and $S^{t}$
denotes its $t-$th term.
This iteration scheme that only modifies one element at each iteration
-is clasically refered as \emph{asynchronous iterations}.
+is clasically refered as \emph{asynchronous iterations}.
+More préciselly, we have here
+$$
+x^{t+1}_i = \left\{
+\begin{array}{l}
+ f_i(x^t) \textrm{ if $S^t = i$} \\
+ x_i^t \textrm{ otherwise}
+ \end{array}
+\right.
+$$
+
Next section shows the link between asynchronous iterations and
Devaney's Chaos.
\right.
\end{equation}
-\noindent With such a notation, configurations are defined for times
+\noindent With such a notation, configurations
+asynchronously obtained are defined for times
$t=0,1,2,\ldots$ by:
\begin{equation}\label{eq:sync}
\left\{\begin{array}{l}
\label{eq:Gf}
\end{equation}
where $\sigma$ is the function that removes the first term of the
-strategy ({\it i.e.},~$S^0$). This definition means that only one
-component of the system is updated at an iteration: the $S^t$-th
-element. But it can be extended by considering subsets for $S^t$.
+strategy ({\it i.e.},~$S^0$).
+This definition allows to links asynchronous iterations with
+classical iterations of a dynamical system.
+%means that only one
+%component of the system is updated at an iteration: the $S^t$-th
+%element. But it can be extended by considering subsets for $S^t$.
-The {\bf distance} $d$ between two points $(S,x)$ and
-$(\check{S},\check{x})\in \mathcal{X} = \llbracket1;n\rrbracket^\Nats
-\times \Bool^{n}$ is defined by
+To study topological properties of these iteations, we are then left to
+introduce a {\emph{ distance}} $d$ between two points $(S,x)$ and
+$(\check{S},\check{x})\in \mathcal{X} = \llbracket1;n\rrbracket^\Nats.
+\times \Bool^{n}$. It is defined by
\begin{equation}
d((S,x);(\check{S},\check{x}))=d_{e}(x,\check{x})+d_{s}(S,\check{S})
\enspace ,
}\frac{|S^{t}-\check{S}^{t}|}{10^{t+1}} \in [0 ; 1] \enspace .
\end{equation}
-This distance is defined to reflect the following
-information. Firstly, the more two systems have different components,
+Notice that the more two systems have different components,
the larger the distance between them is. Secondly, two systems with
similar components and strategies, which have the same starting terms,
must induce only a small distance. The proposed distance fulfill
to Devaney if and only if $\Gamma(f)$ is strongly connected.
\end{theorem}
-Checking if a graph is strongly connected is not difficult. For
-example, consider the function $f_1\left(x_1,\dots,x_n\right)=\left(
-\overline{x_1},x_1,x_2,\dots,x_{n-1}\right)$. As $\Gamma(f_1)$ is
-obviously strongly connected, then $G_{f_1}$ is a chaotic map.
+Checking if a graph is strongly connected is not difficult
+(by the Tarjan's algorithm for instance).
+Let be given a strategy $S$ and a function $f$ such that
+$\Gamma(f)$ is strongly connected.
+In that case, iterations of the function $G_f$ as defined in
+Eq.~(\ref{eq:Gf}) are chaotic according to Devaney.
+
+
+Let us then consider two function $f_0$ and $f_1$ both in
+$\Bool^n\to\Bool^n$ defined as follows that are used all along this article.
+The former is the vectorial negation, \textit{i.e.},
+$f_{0}(x_{1},\dots,x_{n}) =(\overline{x_{1}},\dots,\overline{x_{n}})$.
+The latter is $f_1\left(x_1,\dots,x_n\right)=\left(
+\overline{x_1},x_1,x_2,\dots,x_{n-1}\right)$.
+It is not hard to see that $\Gamma(f_0)$ and $\Gamma(f_1)$ are
+both strongly connected, then iterations of $G_{f_0}$ and of
+$G_{f_1}$ are chaotic according to Devaney.
With this material, we are now able to build a first chaotic neural
network, as defined in the Devaney's formulation.
\section{A chaotic neural network in the sense of Devaney}
\label{S2}
-Let us firstly introduce the vectorial negation
-$f_{0}(x_{1},\dots,x_{n}) =(\overline{x_{1}},\dots,\overline{x_{n}})$,
-which is such that $\Gamma(f_0)$ is strongly connected. Considering
-the map $F_{f_0}:\llbracket 1; n \rrbracket \times \mathds{B}^n \to
-\mathds{B}^n$ associated to the vectorial negation, we can build a
-multilayer perceptron neural network modeling $F_{f_0}$. Hence, for
-all inputs $(s,x) \in \llbracket 1;n\rrbracket \times \mathds{B}^n$,
-the output layer will produce $F_{f_0}(s,x)$. It is then possible to
+Firstly, let us build a
+multilayer perceptron neural network modeling
+$F_{f_0}:\llbracket 1; n \rrbracket \times \mathds{B}^n \to
+\mathds{B}^n$ associated to the vectorial negation.
+More precisely, for all inputs
+$(s,x) \in \llbracket 1;n\rrbracket \times \mathds{B}^n$,
+the output layer produces $F_{f_0}(s,x)$. It is then possible to
link the output layer and the input one, in order to model the
dependence between two successive iterations. As a result we obtain a
global recurrent neural network that behaves as follows (see
input vectors they both generate the same successive outputs
$\left(x^t\right)^{t \in \mathds{N}^{\ast}}$, and therefore that they
are equivalent reformulations of the iterations of $G_{f_0}$ in
-$\mathcal{X}$. Finally, since the proposed neural network is build to
+$\mathcal{X}$. Finally, since the proposed neural network is built to
model the behavior of $G_{f_0}$, which is chaotic according to
Devaney's definition of chaos, we can conclude that the network is
also chaotic in this sense.
theory of chaos.
\begin{definition} \label{def8}
-A function $f$ is said to be {\bf expansive} if $\exists
+A function $f$ is said to be {\emph{ expansive}} if $\exists
\varepsilon>0$, $\forall x \neq y$, $\exists n \in \mathds{N}$ such
that $d\left(f^n(x),f^n(y)\right) \geq \varepsilon$.
\end{definition}
\begin{definition} \label{def9}
-A discrete dynamical system is said to be {\bf topologically mixing}
+A discrete dynamical system is said to be {\emph{ topologically mixing}}
if and only if, for any pair of disjoint open sets $U$,$V \neq
\emptyset$, we can find some $n_0 \in \mathds{N}$ such that for any $n$,
$n\geq n_0$, we have $f^n(U) \cap V \neq \emptyset$.
transitivity property implies indecomposability.
\begin{definition} \label{def10}
-A dynamical system $\left( \mathcal{X}, f\right)$ is {\bf
-not decomposable} if it is not the union of two closed sets $A, B
+A dynamical system $\left( \mathcal{X}, f\right)$ is
+{\emph{not decomposable}} if it is not the union of two closed sets $A, B
\subset \mathcal{X}$ such that $f(A) \subset A, f(B) \subset B$.
\end{definition}
strongly transitive:
\begin{definition} \label{def11}
-A dynamical system $\left( \mathcal{X}, f\right)$ is {\bf strongly
-transitive} if $\forall x,y \in \mathcal{X}$, $\forall r>0$, $\exists
+A dynamical system $\left( \mathcal{X}, f\right)$ is {\emph{ strongly
+transitive}} if $\forall x,y \in \mathcal{X}$, $\forall r>0$, $\exists
z \in \mathcal{X}$, $d(z,x)~\leq~r \Rightarrow \exists n \in
\mathds{N}^{\ast}$, $f^n(z)=y$.
\end{definition}
