• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Su, Kai-Le (Su, Kai-Le.) | Lv, Guan-Feng (Lv, Guan-Feng.) | Song, Jiong (Song, Jiong.)

Indexed by:

EI Scopus PKU CSCD

Abstract:

As a data structure used for representing and manipulating Boolean functions, BDDs (Binary Decision Diagrams) are commonly used in many fields such as model checking, system verification and so on. At the worst case, the space usage can reach exponential level; so many researchers have made a great deal of technical work on designing and implementing efficient BDD packages. Up to today, many efficient BDD packages have been implemented. For saving space and improving manipulating speed, all these packages limit the number of variables to 216. However, such a limitation also limits its applicability. In this paper, an efficient BDD package is proposed to break the limit of 216. This package not only adopts the technologies used in classical BDD package implementation but also introduce some new techniques, such as sub-allocation of memory and lightweight garbage collection. Because of such effective scheme, the number of variables which BDD package can deal with reaches 232. Compared with other BDD packages with variable number 216, this BDD package can be more extensively used. Experiments show that its performance is nearly as the same as that of the best publicly available BDD package CUDD.

Keyword:

Model checking Storage allocation (computer) Decision theory Boolean functions Binary decision diagrams

Author Community:

  • [ 1 ] [Su, Kai-Le]College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua; Zhejiang ; 312004, China
  • [ 2 ] [Su, Kai-Le]Tsinghua UvA Joint Research Center for Logic, Tsinghua University, Beijing ; 100084, China
  • [ 3 ] [Lv, Guan-Feng]College of Computer Science, Beijing University of Technology, Beijing ; 100022, China
  • [ 4 ] [Song, Jiong]College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua; Zhejiang ; 312004, China

Reprint Author's Address:

  • [su, kai-le]college of mathematics, physics and information engineering, zhejiang normal university, jinhua; zhejiang ; 312004, china;;[su, kai-le]tsinghua uva joint research center for logic, tsinghua university, beijing ; 100084, china

Email:

Show more details

Related Keywords:

Related Article:

Source :

Chinese Journal of Computers

ISSN: 0254-4164

Year: 2014

Issue: 9

Volume: 37

Page: 2021-2026

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 9

Online/Total:575/10595632
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.