Partial Order Reduction in Symbolic State Space Traversal Using ZBDDs
Minoru Tomisaka, Tomohiro Yoneda · 1999
Introduction In formal ve77O(4W7N of hardware systeON traveF7z7 state space ofthe give systeW and speFFZOF(4WZ is one ofwideO use te hnique4 Howe veF it isofte difficult tohandle practical andcomplicate systei due totheW huge state space4 Inorde to oveFWFF this probleN rebleN ting seg ofstate and/or transition reransit symbolically by using BDDs (Binary Denary( Diagrams) [1] has beO prop [2], [3], and many succec -(F rec-(F are re orteF The te hnique base on partialorde real(zW [5], [6, andotheNN is e(e(FW to be anothe promising approach tothe avoidance ofstate eateZS(4 The forme traveOSS the fullstate spaceF but se( ofstate are re7(4 te e7 tly by BDDs. The latte use the ee(FN state reteFN tation, but onlythe re(SW state space are traveFOPZ Alur,e al. first combine the two approache [14].The algorithm prop ose inthe pape nep( to construct transitionreansiti of modeFZ It re(FNFz BDD variable reable ting neg state (prime v ariableO as weO asthose forcurre tstateF and it someNFz