Hierarchical Adaptive State Space Caching based on Level Sampling

Radu Mateescu 1 Anton Wijs 1
1 VASY - System validation - Research and applications
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : 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.
Type de document :
Communication dans un congrès
Stefan Kowalewski and Anna Philippou. The 15th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Mar 2009, York, United Kingdom. Springer Verlag, 5505, pp.215-229, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-00768-2_21〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00381682
Contributeur : Radu Mateescu <>
Soumis le : mercredi 6 mai 2009 - 12:06:23
Dernière modification le : jeudi 11 janvier 2018 - 06:22:03
Document(s) archivé(s) le : lundi 15 octobre 2012 - 10:00:42

Fichier

Mateescu-Wijs-09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Radu Mateescu, Anton Wijs. Hierarchical Adaptive State Space Caching based on Level Sampling. Stefan Kowalewski and Anna Philippou. The 15th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Mar 2009, York, United Kingdom. Springer Verlag, 5505, pp.215-229, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-00768-2_21〉. 〈inria-00381682〉

Partager

Métriques

Consultations de la notice

186

Téléchargements de fichiers

78