Problème d'accessibilité

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Le problème d'accessibilité consiste à atteindre une situation finale depuis une situation initiale.

Le problème d'accessibilité (aussi appelé le problème d'atteignabilité)[1] est, en informatique, le problème algorithmique qui consiste à déterminer si, dans un système, une situation finale est accessible/atteignable depuis une situation initiale. Le problème d'accessibilité a été étudié dans les automates finis, les automates cellulaires, les automates temporisés, les systèmes infinis, etc.

Graphe fini explicite[modifier | modifier le code]

Le problème d'accessibilité dans un graphe orienté décrit explicitement est NL-complet. Sur la classes des graphes non orienté, Reingold a démontré que le problème d'accessibilité est dans LOGSPACE[2].

En vérification de modèles, l'accessibilité correspond à un propriété de vivacité.

Graphe fini implicite[modifier | modifier le code]

En planification, plus précisément en planification classique, on s'intéresse à savoir si on peut atteindre un état depuis un état initial à partir d'une description des actions. La description des actions définissent un graphe des états implicites, qui est de taille exponentielle en la taille de la description.

En vérification de modèles symbolique, le modèle (le graphe sous-jacent) est décrit à l'aide d'une représentation symbolique comme des diagrammes de décision binaire.

Réseaux de Petri[modifier | modifier le code]

Le problème d'accessibilité dans un réseau de Petri est décidable[3]. Dès 1976, on savait que ce problème était EXPSPACE-dur[4]. Il y a des résultats sur combien implémenter ce problème en pratique[5]. En 2018, le problème a été démontré comme non-élémentaire[6].

Notes et références[modifier | modifier le code]

  1. (en) RP Organization Committee, « (RP'17) 11th International Workshop on Reachability Problems 2017 », sur rp17.cs.rhul.ac.uk (consulté le 18 janvier 2018)
  2. Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, no 4,‎ , p. 1–24 (lire en ligne)
  3. Ernst W. Mayr, « An algorithm for the general Petri net reachability problem », {{Article}} : paramètre « périodique » manquant, ACM,‎ , p. 238–246 (DOI 10.1145/800076.802477, lire en ligne)
  4. R. Lipton, « The Reachability Problem Requires Exponential Space », Technical Report 62,‎ (lire en ligne)
  5. P. Küngas (July 26–29, 2005). « Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies » dans Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation—SARA 2005 . 
  6. (en) Auteur inconnu « The Reachability Problem for Petri Nets is Not Elementary (Extended Abstract) », .