Abstract
We present a novel algorithm for generating state spaces of asynchronous systems using Multi-valued Decision Diagrams. In contrast to related work, we encode the next-state function of a system not as a single Boolean function, but as cross-products of integer functions. This permits the application of various iteration strategies to build a system’s state space. In particular, we introduce a new elegant strategy, called saturation, and implement it in the tool SMART. On top of usually performing several orders of magnitude faster than existing BDD-based state-space generators, our algorithm’s required peak memory is often close to the final memory needed for storing the overall state space.
This work was partially supported by the National Aeronautics and Space Administration under NASA Contract No. NAS1-97046 while the authors were in residence at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, VA 23681, USA. G. Ciardo and R. Siminiceanu were also partially supported by NASA grant No. NAG-1-2168.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
P. Aziz Abdulla, P. Bjesse, and N. Eén. Symbolic reachability analysis based on SAT-solvers. In TACAS 2000, vol. 1785 of LNCS, pp. 411–425. Springer-Verlag, 2000.
R. Alur, R.K. Brayton, T.A. Henzinger, S. Qadeer, and S.K. Rajamani. Partialorder reduction in symbolic state-space exploration. In CAV’ 97, vol. 1254 of LNCS, pp. 340–351. Springer-Verlag, 1997.
H.R. Andersen, J. Staunstrup, and N. Maretti. Partial model checking with ROBDDs. In TACAS’ 97, vol. 1217 of LNCS, pp. 35–49. Springer-Verlag, 1997.
P. Ashar and M. Cheong. Efficient breadth-first manipulation of binary decision diagrams. In ICCAD’ 94, pp. 622–627. Computer Society Press, 1994.
J.A. Bergstra, A. Ponse, and S.A. Smolka. Handbook of Process Algebra. Elsevier Science, 2000.
A. Biere, A. Cimatti, E.M. Clarke, and Y. Zhu. Symbolic model checking without BDDs. In TACAS’ 99, vol. 1579 of LNCS, pp. 193–207. Springer-Verlag, 1999.
R.E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Trans. on Comp., 35(8):677–691, 1986.
R.E. Bryant. Symbolic Boolean manipulation with ordered binary-decision diagrams. ACM Comp. Surveys, 24(3):393–418, 1992.
J.R. Burch, E.M. Clarke, K.L. McMillan, D.L. Dill, and L.J. Hwang. Symbolic model checking: 1020 states and beyond. Inform. & Comp., 98(2):142–170, 1992.
G. Ciardo, G. Lìttgen, and R. Siminiceanu. Efficient symbolic state-space construction for asynchronous systems. In ICATPN 2000, vol. 1639 of LNCS, pp. 103–122. Springer-Verlag, 2000.
G. Ciardo and A.S. Miner. SMART: Simulation and Markovian Analyzer for Reliability and Timing. In IPDS’ 96, p. 60. IEEE Computer Society Press, 1996.
A. Cimatti, E. Clarke, F. Giunchiglia, and M. Roveri. NuSMV: A new symbolic model veriér. In CAV’ 99, vol. 1633 of LNCS, pp. 495–499. Springer-Verlag, 1999.
E.M. Clarke, O. Grumberg, and D. Peled. Model Checking. MIT Press, 1999.
R. Cleaveland, J. Parrow, and B. Steén. The Concurrency Workbench: A semantics-based tool for the verification of finite-state systems. TOPLAS, 15(1):36–72, 1993.
M. Fujita, H. Fujisawa, and Y. Matsunaga. Variable ordering algorithms for ordered binary decision diagrams and their evaluation. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 12(1):6–12, 1993.
A. Geser, J. Knoop, G. Lìttgen, B. Steén, and O. Rìthing. Chaotic fixed point iterations. Techn. Rep. MIP-9403, Univ. of Passau, 1994.
S. Graf, B. Steén, and G. Lìttgen. Compositional minimisation of finite state systems using interface specifications. Formal Asp. of Comp., 8(5):607–616, 1996.
T. Kam, T. Villa, R.K. Brayton, and A. Sangiovanni-Vincentelli. Multi-valued decision diagrams: Theory and applications. Multiple-Valued Logic, 4(1–2):9–62, 1998.
K. Larsen, P. Pettersson, and W. Yi. Compositional and symbolic model-checking of real-time systems. In RTSS’ 95, pp. 76–89. Computer Society Press, 1995.
K.L. McMillan. Symbolic Model Checking: An Approach to the State-explosion Problem. PhD thesis, Carnegie-Mellon Univ., 1992.
K.L. McMillan. A conjunctively decomposed Boolean representation for symbolic model checking. In CAV’ 96, LNCS, pp. 13–24. Springer-Verlag, 1996.
A.S. Miner and G. Ciardo. Efficient reachability set generation and storage using decision diagrams. In ICATPN’ 99, vol. 1639 of LNCS, pp. 6–25. Springer-Verlag, 1999.
T. Murata. Petri nets: Properties, analysis and applications. Proc. of the IEEE, 77(4):541–579, 1989.
E. Pastor and J. Cortadella. Efficient encoding schemes for symbolic analysis of Petri nets. In DATE’ 98, pp. 790–795. IEEE Computer Society Press, 1998.
E. Pastor, O. Roig, J. Cortadella, and R.M. Badia. Petri net analysis using Boolean manipulation. In ICATPN’ 94, vol. 815 of LNCS, pp. 416–435. Springer-Verlag, 1994.
M. Sheeran and G. Stålmarck. A tutorial on Stålmarck’s proof procedure for propositional logic. Formal Methods in System Design, 16(1):23–58, 2000.
B. Yang, R.E. Bryant, D.R. O’Hallaron, A. Biere, O. Coudert, G. Janssen, R.K. Ranjan, and F. Somenzi. A performance study of BDD-based model checking. In FMCAD’ 98, vol. 1522 of LNCS, pp. 255–289. Springer-Verlag, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ciardo, G., Lüttgen, G., Siminiceanu, R. (2001). Saturation: An Efficient Iteration Strategy for Symbolic State—Space Generation. In: Margaria, T., Yi, W. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2001. Lecture Notes in Computer Science, vol 2031. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45319-9_23
Download citation
DOI: https://doi.org/10.1007/3-540-45319-9_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41865-8
Online ISBN: 978-3-540-45319-2
eBook Packages: Springer Book Archive