两类布尔函数的OBDD阶
The OBDD Orders of Two Types of Boolean Functions
DOI: 10.12677/SEA.2018.76032, PDF,  被引量   
作者: 张媛, 江建国, 胡晓璐：辽宁师范大学数学学院，辽宁 大连
关键词: OBDD；变量序；DNF；CNF；布尔函数；OBDD； Variable Order； DNF； CNF； Boolean Function
摘要: OBDD是布尔函数的一种有效的图形化表示形式。布尔函数的OBDD的阶数对布尔变量的序敏感。本文研究了DNF型和CNF型两种类型布尔函数，给出了这两类函数在一种特定变量序下的OBDD阶的准确值，并证明了这个结论。
Abstract: OBDD is an effective graphical representation of Boolean functions. The OBDD orders of a Boolean function are sensitive to the order of Boolean variables. In this paper, the Boolean functions of DNF type and CNF type are studied. The exact OBDD order values of these two types of functions in a particular variables order are given and the conclusion is proved.
文章引用：张媛, 江建国, 胡晓璐. 两类布尔函数的OBDD阶[J]. 软件工程与应用, 2018, 7(6): 283-288. https://doi.org/10.12677/SEA.2018.76032

参考文献

[1] Huth, M. and Ryan, M. (2004) Logic in Computer Science: Modelling and Reasoning about Systems. 2nd Edi-tion.
[2] Bryant, R.E. (1986) Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, 35, 677-691. [Google Scholar] [CrossRef] 
[3] Burch, J.R., Clarke, J.M., McMillan, K.L., Dill, D.L. and Hwang, J. (1992) System Model Checking: 1020 States and Beyond. Information and Computation, 98, 142-170. [Google Scholar] [CrossRef] 
[4] Bryant, R.E. (1985) Symbolic Manipulation of Boolean Functions Using a Graphical Representation. Conference on Design Automation, IEEE, 688-694.
[5] Lee, C.Y. (2013) Representation of Switching Circuits by Binary-Decision Programs. Bell System Technical Journal, 38, 985-999. [Google Scholar] [CrossRef] 
[6] Bryant, R.E. and Chen, Y.A. (2001) Verification of Arithmetic Circuits Using Binary Moment Diagrams. International Journal on Software Tools for Technology Transfer, 3, 137-155.
[7] Kebschull, U. and Rosenstiel, W. (1993) Efficient Graph-Based Computation and Manipulation of Functional Decision Diagrams. Proceedings of Europe Conference on Decision Automation, 278-282. [Google Scholar] [CrossRef] 
[8] Slobodová, A. (1998) On the Composition Problem for OBDDs with Multiple Variable Orders. International Symposium on Mathematical Foundations of Computer Science, Springer Berlin Heidelberg, 645-655. [Google Scholar] [CrossRef] 
[9] Ishiura, N., Sawada, H. and Yajima, S. (1991) Minimization of Binary Decision Diagrams Based on Exchange of Variables. IEEE International Conference on Computer-Aided Design, 472-475. [Google Scholar] [CrossRef] 
[10] Bollig, B. and Wegener, I. (1996) Improving the Variable Ordering of OBDDs is NP-Complete. IEEE Transactions on Computers, 45, 993-1002. [Google Scholar] [CrossRef] 
[11] Siminiceanu, R.I. and Ciardo, G. (2006) New Metrics for Static Variable Ordering in Decision Diagrams. Tools and Algorithms for the Construction and Analysis of Systems, Springer Berlin Heidelberg, 90-104. [Google Scholar] [CrossRef] 
[12] Rudell, R. (1993) Dynamic Variable Ordering for Ordered Binary Decision Diagrams. IEEE/ACM International Conference on Computer-Aided Design. Iccad-93. Digest of Technical Papers, IEEE, 42-47.
[13] Furdu, I. and Brudaru, O. (2009) New Hybrid Genetic Algorithm with Adaptive Operators and Variability Target for Optimizing Variable Order in OBDD. Scientific Studies and Research Series Mathematics and Informatics, 19, 241-256.

为你推荐