二元决策图
布尔函数
布尔数据类型
变量(数学)
代表(政治)
数据结构
数学
时间复杂性
和逆变器图
离散数学
算法
理论计算机科学
计算机科学
多项式的
布尔电路
程序设计语言
数学分析
政治
政治学
法学
作者
Anna Bernasconi,Valentina Ciriani,Marco Longhi
标识
DOI:10.23919/date54114.2022.9774551
摘要
A Reduced Ordered Binary Decision Diagram (ROBDD) is a data structure widely used in an increasing number of fields of Computer Science. In general, ROBDD representations of Boolean functions have a tractable size, polynomial in the number of input variables, for many practical applications. However, the size of a ROBDD, and consequently the complexity of its manipulation, strongly depends on the variable ordering: depending on the initial ordering of the input variables, the size of a ROBDD representation can grow from linear to exponential. In this paper, we study the ROBDD representation of Boolean functions that describe a special class of Boolean affine spaces, which play an important role in some logic synthesis applications. We first discuss how the ROBDD representations of these functions are very sensitive to variable ordering, and then provide an efficient linear time algorithm for computing an optimal variable ordering that always guarantees a ROBDD of size linear in the number of input variables.
科研通智能强力驱动
Strongly Powered by AbleSci AI