Loading AI tools
De Wikipédia, l'encyclopédie libre
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é 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é.
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.
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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.