In order to make model checking applicable to realistic problems, simplification techniques are essential. Models may be simplified eliminating the variables that do not appear in the cone-of-influence (COI) of the properties under verification. Efficient COI computation is thus required. Algorithms based on depth-first visits may become cumbersome when they must be applied several times; for instance, when multiple properties must be verified on the same model. An alternative is to resort to graph-labeling methods, trading-off time for memory. Modeling the problem in terms of graphs, this paper develops a technique based on bitmaps that keeps the amount of memory needed within acceptable limits. The paper also describes a portfolio of optimizations of the original algorithm that allow even more reductions in memory usage. Experimental results show that the basic algorithm and its optimized versions perform very well on standard benchmark circuits used in the model-checking community.
A graph-labeling approach for efficient cone-of-influence computation in model-checking problems with multiple properties / Cabodi, Gianpiero; Camurati, Paolo Enrico; Quer, Stefano. - In: SOFTWARE-PRACTICE & EXPERIENCE. - ISSN 0038-0644. - ELETTRONICO. - 46:4(2016), pp. 493-511. [10.1002/spe.2321]
A graph-labeling approach for efficient cone-of-influence computation in model-checking problems with multiple properties
CABODI, Gianpiero;CAMURATI, Paolo Enrico;QUER, Stefano
2016
Abstract
In order to make model checking applicable to realistic problems, simplification techniques are essential. Models may be simplified eliminating the variables that do not appear in the cone-of-influence (COI) of the properties under verification. Efficient COI computation is thus required. Algorithms based on depth-first visits may become cumbersome when they must be applied several times; for instance, when multiple properties must be verified on the same model. An alternative is to resort to graph-labeling methods, trading-off time for memory. Modeling the problem in terms of graphs, this paper develops a technique based on bitmaps that keeps the amount of memory needed within acceptable limits. The paper also describes a portfolio of optimizations of the original algorithm that allow even more reductions in memory usage. Experimental results show that the basic algorithm and its optimized versions perform very well on standard benchmark circuits used in the model-checking community.File | Dimensione | Formato | |
---|---|---|---|
spe.2321.pdf
non disponibili
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
1.67 MB
Formato
Adobe PDF
|
1.67 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2629364
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo