TY - JOUR

T1 - Application of multiroot decision diagrams for integer functions

AU - Bugaychenko, D. Yu.

AU - Soloviev, I. P.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - binary decision diagrams - multi-terminal binary decision diagrams - function and matrices representation

U2 - 10.3103/S1063454110020056

DO - 10.3103/S1063454110020056

M3 - Article

VL - 43

SP - 92

EP - 97

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 2

ER -