• DocumentCode
    874830
  • Title

    On the OBDD-representation of general Boolean functions

  • Author

    Liaw, Heh-Tyan ; Lin, Chen-Shang

  • Author_Institution
    Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei, Taiwan
  • Volume
    41
  • Issue
    6
  • fYear
    1992
  • fDate
    6/1/1992 12:00:00 AM
  • Firstpage
    661
  • Lastpage
    664
  • Abstract
    The behavior of ordered binary decision diagrams (OBDD) for general Boolean functions is studied. A tight upper bound of (2n /n)(2+ε) for the worst case OBDD size is derived. Although the size of an OBDD is dependent on the ordering of decision variables, it is shown that almost all functions are not sensitive to variable ordering
  • Keywords
    Boolean functions; computational complexity; general Boolean functions; ordered binary decision diagrams; tight upper bound; Artificial intelligence; Boolean functions; Councils; Data structures; Logic design; Logic testing; Merging; Upper bound;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/12.144618
  • Filename
    144618
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=874830