首页 | 本学科首页   官方微博 | 高级检索  
     


Exact OBDD Bounds for Some Fundamental Functions
Authors:Beate Bollig  Niko Range  Ingo Wegener
Affiliation:1. LS2 Informatik, TU Dortmund, 44221, Dortmund, Germany
Abstract:Ordered binary decision diagrams (OBDDs) are nowadays one of the most common dynamic data structures or representation types for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Although many exponential lower bounds on the OBDD size of Boolean functions are known, there are only few functions where the OBDD size is asymptotically known exactly. In this paper the exact OBDD sizes of the fundamental functions multiplexer and addition of n-bit numbers are determined.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号