ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 34/4 - 2015  - pp.463-484  - doi:10.3166/TSI.34.463-484
TITRE
Analyses statiques de la dynamique des réseaux d’automates indéterministes

TITLE
Static analyses of the dynamics of non-deterministic automata networks

RÉSUMÉ

Cet article présente une synthèse de résultats récents permettant l’analyse à grande échelle de la dynamique des réseaux d’automates. Nous nous focalisons sur deux types de propriétés : l’accessibilité – étant donné un état global du réseau, existe-t-il une suite de transitions permettant d’atteindre un état local donné pour un automate donné ? ; et la caractérisation des points fixes à partir de la topologie du réseau d’automates et de ses transitions locales. Pour l’accessibilité, nous donnons des conditions nécessaires applicables à tout réseau d’automates et des conditions suffisantes pour les réseaux d’automates asynchrones. Nous abordons également le calcul d’ensembles de coupes pour l’accessibilité, qui sont des ensembles d’états locaux d’automates qui, s’ils sont désactivés, rendent impossible l’accessibilité étudiée. Ces analyses de la dynamique exploitent la concurrence au sein des réseaux d’automates non déterministes et reposent sur des abstractions donnant une représentation compacte, non redondante, mais approchée, de l’ensemble des comportements possibles. Ces méthodes ont rendu possible l’analyse de la dynamique de réseaux biologiques avec des milliers de composants.



ABSTRACT

This paper gives an overview of recent results on scalable analysis of automata networks dynamics. We focus on two properties: reachability – given a global state of the network, does there exist a sequence of transitions that reach a given local state of a given automaton?; and fixed point characterization. Concerning reachability, we give necessary conditions in the general scope of automata networks; and sufficient conditions in the scope of asynchronous automata networks.We address the computation of cut sets for reachability, that is, the sets of local states such that, if disabled, will make the concerned reachability impossible. Those analyses exploit the concurrency in nondeterministic automata networks and rely on abstractions giving compact, non-redundant, but approximate representations of the network dynamics. Such methods have made tractable the analysis of dynamics of biological networks gathering thousands of components.



AUTEUR(S)
Loïc PAULEVÉ, Maxime FOLSCHETTE, Morgan MAGNIN, Olivier ROUX

Reçu le 24 mars 2014.    Accepté le 15 juillet 2015.

MOTS-CLÉS
Réseaux discrets, concurrence, interprétation abstraite, accessibilité, points fixes.

KEYWORDS
Discrete networks, concurrency, abstract interpretation, reachability, fixed points.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (299 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier