...

diff --git a/main.tex b/main.tex
index 545524feed5c07a727395d780b39820755607c45..b72eb6d8ba43fb5945c7d9fd561aeddae914b5af 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -107,6 +107,9 @@ is far more difficult than non chaotic behaviors.
 \section{Introduction}
 \label{S1}
 
 \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
 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


@@ -146,7 +149,7 @@ using  a theoretical  framework  based on  the  Devaney's  definition of  chaos
 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
 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
 iterations and  a class of globally  recurrent MLP.
 The investigation the  converse problem is the second contribution: 
 we indeed study the  ability for


@@ -193,7 +196,10 @@ iterations and Devaney's chaos is  finally presented at the end of this
 section.
 
 In what follows and for  any function $f$, $f^n$ means the composition
 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}
 
 
 \subsection{Devaney's chaotic dynamical systems}
 


@@ -229,11 +235,11 @@ point dependence on initial conditions.
 
 Topological  transitivity   is  checked  when,  for   any  point,  any
 neighborhood of its future evolution eventually overlap with any other
 
 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)$
 
 \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}$
 open  sets $U$,  $V  \in  \mathcal{X}$ there  exists  
 $k \in
 \mathds{N}^{\ast}$


@@ -248,12 +254,12 @@ On  the contrary,  a dense set  of periodic points  is an
 element of regularity that a chaotic dynamical system has to exhibit.
 
 \begin{definition} \label{def3}
 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}
 \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).
   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).


@@ -265,23 +271,27 @@ in a completely different  manner, leading to unpredictability for the
 whole system. Then,
 
 \begin{definition} \label{sensitivity}
 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
   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}
 \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}
 
 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}
 
 
 \subsection{Asynchronous Iterations}
 


@@ -326,7 +336,17 @@ In the  sequel, the  {\it strategy} $S=(S^{t})^{t  \in \Nats}$  is the
 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 
 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.
 
 Next section shows the link between asynchronous iterations and 
 Devaney's Chaos.
 


@@ -352,7 +372,8 @@ $F_{f}:   \llbracket1;n\rrbracket\times   \mathds{B}^{n}   \rightarrow
     \right. 
 \end{equation}
 
     \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}   
 $t=0,1,2,\ldots$ by:
 \begin{equation}\label{eq:sync}   
 \left\{\begin{array}{l}   


@@ -376,16 +397,20 @@ X^{k+1}& = & G_{f}(X^{k})\\
 \label{eq:Gf}
 \end{equation}
 where  $\sigma$ is the  function that  removes the  first term  of the
 \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 ,
 \begin{equation}
 d((S,x);(\check{S},\check{x}))=d_{e}(x,\check{x})+d_{s}(S,\check{S})
 \enspace ,


@@ -401,8 +426,7 @@ d_{s}(S,\check{S})=\frac{9}{2n}\sum_{t=0}^{\infty
 }\frac{|S^{t}-\check{S}^{t}|}{10^{t+1}} \in [0 ; 1] \enspace .
 \end{equation}
 
 }\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
 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


@@ -421,10 +445,23 @@ Let $f:\Bool^n\to\Bool^n$. Iterations of $G_f$ are chaotic  according
 to  Devaney if and only if  $\Gamma(f)$ is strongly connected.
 \end{theorem}
 
 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.
 
 With this  material, we are now  able to build a  first chaotic neural
 network, as defined in the Devaney's formulation.


@@ -432,14 +469,13 @@ network, as defined in the Devaney's formulation.
 \section{A chaotic neural network in the sense of Devaney}
 \label{S2}
 
 \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
 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


@@ -479,7 +515,7 @@ Eq.~(\ref{eq:CIs}).  It  means that  mathematically if we  use similar
 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
 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.
 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.


@@ -567,13 +603,13 @@ Let us first recall  two fundamental definitions from the mathematical
 theory of chaos.
 
 \begin{definition} \label{def8}
 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}
 \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$.
 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$.


@@ -592,8 +628,8 @@ according  to  Devaney's definition.  First  of  all, the  topological
 transitivity property implies indecomposability.
 
 \begin{definition} \label{def10}
 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}
 
 \subset \mathcal{X}$ such that $f(A) \subset A, f(B) \subset B$.
 \end{definition}
 


@@ -603,8 +639,8 @@ strongly connected.  Moreover, under this  hypothesis CI-MLPs($f$) are
 strongly transitive:
 
 \begin{definition} \label{def11}
 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}
 z  \in  \mathcal{X}$,  $d(z,x)~\leq~r  \Rightarrow  \exists  n  \in
 \mathds{N}^{\ast}$, $f^n(z)=y$.
 \end{definition}