Problème d'accessibilité

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.

Le problème d'accessibilité consiste à atteindre une situation finale depuis une situation initiale.

Graphe fini explicite

Le problème d'accessibilité dans un graphe orienté décrit explicitement est NL-complet. Reingold, dans un article de 2008, a démontré que le problème d'accessibilité pour un graphe non-orienté est dans LOGSPACE^[2].

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

Graphe fini implicite

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

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 la façon d'implémenter ce problème en pratique^[5]. En 2018, le problème a été démontré comme non-élémentaire^[6].