×

zbMATH — the first resource for mathematics

Application of multiroot decision diagrams for integer functions. (English. Russian original) Zbl 1251.68082
Vestn. St. Petersbg. Univ., Math. 43, No. 2, 92-97 (2010); translation from Vestn. St-Peterbg. Univ., Ser. I, Mat. Mekh. Astron. 2010, No. 2, 91-98 (2010).
Summary: New data structures for representation of integer functions and matrices are proposed, namely, multiroot binary decision diagrams (MRBDD). Algorithms for performing standard operations on functions and matrices represented by MRBDDs are presented. Thanks to the more efficient reuse of structural elements, representation by multiroot binary decision diagrams is more efficient than the widely used multiterminal binary decision diagrams (MTBDD). Experimental results are given, which show that multiroot binary decision diagrams are a promising alternative to multiterminal binary decision diagrams, in particular, in probabilistic verification, manipulation of probability distributions, analysis of Petri nets, and other computational models.

MSC:
68P05 Data structures
Software:
CUDD
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Cimatti, E. M. Clarke, F. Giunchiglia, and M. Roveri, in Proceedings of the 11th International Conference on Computer Aided Verification (Springer, Berlin, 1999).
[2] R. M. Jensen, Ph.D. Thesis (Carnegie Mellon Univ., Pittsburgh, 2003).
[3] R. E. Bryant, ACM Computing Surveys, 24(3), 293–318 (1992). · doi:10.1145/136035.136043
[4] M. Fujita, P. C. McGeer, and J. C.-Y. Yang, Form. Methods Syst. Des. 10(2–3), 149–169 (1997). · doi:10.1023/A:1008647823331
[5] D. Parker, Ph.D. Thesis (Univ. of Birmingham, Birmingham, 2002).
[6] R. Bahar, E. Frohm, C. Gaona, et al., in Proceedings of IEEE/ACM International Conference on CAD (IEEE, Santa Clara, 1993), pp. 188–191.
[7] F. Somenzi, CUDD: Colorado University Decision Diagram Package, http://vlsi.colorado.edu/fabio/CUDD .
[8] A. Afshin, in ICCADT07: Proceedings of the 2007 IEEE/ACM International Conference on Computer-Aided Design (IEEE, Piscataway, NJ, 2007).
[9] C. Y. A. C. Jinqing and L. G. Gianfranco, Intern. J. Software Tools Technol. Transf. 11(2), 117–131 (2009). · Zbl 05781728 · doi:10.1007/s10009-009-0099-0
[10] J. G. Kanupriya and K. S. P. Nikhil, in ISLPEDT05: Proceedings of the 2005 International Symposium on Low Power Electronics and Design (ACM, New York, 2005), pp. 111–114.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.