Cependant, même pour des réseaux discrets à peu d'éléments,
le nombre de configurations induites explose rapidement.
Les \emph{Model-Checkers}~\cite{Hol03,nusmv02,Blast07,MCErlang07,Bogor03}
-sont des classes d'outils qui addressent le problème de vérifier automatiquement
+sont des classes d'outils qui adressent le problème de vérifier automatiquement
qu'un modèle vérifie une propriété donnée. Pour traiter le problème d'explosion
combinatoire, ces outils appliquent des méthodes d'ordre partiel, d'abstraction,
de quotientage selon une relation d'équivalence.
\hfill
\subfigure[Graphe d'intéraction]{
\includegraphics[width=4cm]{images/xplCnxMc.eps}
- \label{fig:xplgraph}
+ \label{fig:xplgraph:inter:mc}
}
\end{center}
\caption{Exemple pour SDD $\approx$ SPIN.}
\begin{xpl}
On considère un exemple à trois éléments dans $\Bool$.
- Chaque configuration est ainsi un élement de $\Bool^3$, \textit{i.e.},
+ Chaque configuration est ainsi un élément de $\Bool^3$, \textit{i.e.},
un nombre entre 0 et 7.
La \Fig{fig:map} précise la fonction $f$ considérée et
- la \Fig{fig:xplgraph} donne son graphe d'intéraction.
+ la \Fig{fig:xplgraph:inter:mc} donne son graphe d'intéraction.
}
\end{lstlisting}
\end{tiny}
-\caption{Process scheduler pour la stratégie pseudo pérodique.
+\caption{Process scheduler pour la stratégie pseudo périodique.
\label{fig:scheduler}}
\end{minipage}
\begin{minipage}[h]{.30\linewidth}
\subsection{La stratégie}\label{sub:spin:strat}
Regardons comment une stratégie pseudo périodique peut être représentée en PROMELA.
Intuitivement, un process \verb+scheduler+ (comme représenté à la {\sc Figure}~\ref{fig:scheduler})
-est iterrativement appelé pour construire chaque $s^t$ représentant
+est itérativement appelé pour construire chaque $s^t$ représentant
les éléments possiblement mis à jour à l'itération $t$.
Basiquement, le process est une boucle qui est débloquée lorsque la valeur du sémaphore
\item elle mémorise dans \texttt{Xd} la valeurs disponible pour chaque élément grâce à la fonction \texttt{fetch\_values}; cette fonction est détaillée
dans la section suivante;
\item une boucle %sur les \texttt{ar\_len} éléments qui peuvent être modifiés
- met à jour iterrativement la valeur de $j$ (grâce à l'appel de fonction \texttt{f(j)})
+ met à jour itérativement la valeur de $j$ (grâce à l'appel de fonction \texttt{f(j)})
pour peu que celui-ci doive être modifié, \textit{i.e.}, pour peu qu'il soit renseigné dans
\texttt{mods[count]}; le code source de \texttt{F} est donné en {\sc Figure}~\ref{fig:p} et est une
traduction directe de l'application $f$;
Les valeurs des éléments sont ajoutées dans ce canal au travers de la fonction \verb+diffuse_values+. L'objectif de cette fonction
est de stocker les valeurs de $x$ (représenté
dans le modèle par \verb+Xp+) dans le canal \verb+channels+.
-Il permet au modèle-checker SPIN d'exécuter
+Il permet au model-checker SPIN d'exécuter
le modèle PROMELA comme s'il pouvait y avoir des délais entre processus
Il y a deux cas différents pour la valeur de $X_{j}$:
\begin{itemize}
de l'exécution en SPIN de $\psi$ est bornée par $2^{m(\delta_0+1)+n(n+2)}$.
\end{theorem}
\begin{Proof}
- Une configuration est une valuation des variables globales.
+ Une configuration est une évaluation des variables globales.
Leur nombre ne dépend que de celles qui ne sont pas constantes.
Les variables \verb+Xp+ et \verb+X+ engendrent $2^{2n}$ états.