Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Hierarchical Adaptive State Space Caching Based on Level Sampling
verfasst von : Radu Mateescu, Anton Wijs
Erschienen in: Tools and Algorithms for the Construction and Analysis of Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the past, several attempts have been made to deal with the state space explosion problem by equipping a depth-first search (
Dfs
) algorithm with a state cache, or by avoiding collision detection, thereby keeping the state hash table at a fixed size. Most of these attempts are tailored specifically for
Dfs
, and are often not guaranteed to terminate and/or to exhaustively visit all the states. In this paper, we propose a general framework of hierarchical caches which can also be used by breadth-first searches (
Bfs
). Our method, based on an adequate sampling of
Bfs
levels during the traversal, guarantees that the
Bfs
terminates and traverses all transitions of the state space. We define several (static or adaptive) configurations of hierarchical caches and we study experimentally their effectiveness on benchmark examples of state spaces and on several communication protocols, using a generic implementation of the cache framework that we developed within the
Cadp
toolbox.