Data structures, minimization and complexity of boolean functions
作者： C. Mccrosky , Yuke Wang
DOI:
关键词:
摘要: Boolean function manipulation is an important component of computer science. This thesis presents results related to representation and minimization. The minimization problem re-defined. A new classification theory based on permutation extension developed. More efficient algorithms can be derived the theory. also examines complexity issues graph structure OBDDs some special functions. Moreover, data structures for functions are reported in this thesis. Some found have constant while having exponential existing structures.
usask.ca参考文章(28)
Amar Mukhopadhyay, Recent developments in switching theory Academic Press. ,(1971)
E. M. Sentovich, SIS : A System for Sequential Circuit Synthesis CTIT technical reports series. ,(1992)
Ingo Wegener, The Complexity of Boolean Functions ,(1991)
Gilbert Held, Data compression: Techniques and applications : hardware and software considerations ,(1987)
John L. Hennessy, David A. Patterson, Computer Architecture: A Quantitative Approach ,(1989)
Randal E. Bryant, Yirng-An Chen, Verification of Arithmetic Functions with Binary Moment Diagrams Carnegie Mellon University. ,(1994) , 10.21236/ADA281028
S. Malik, A.R. Wang, R.K. Brayton, A. Sangiovanni-Vincentelli, Logic verification using binary decision diagrams in a logic synthesis environment international conference on computer aided design. pp. 6- 9 ,(1988) , 10.1109/ICCAD.1988.122451
D.I. Cheng, M. Marek-Sadowska, Verifying equivalence of functions with unknown input correspondence european design automation conference. pp. 81- 85 ,(1993) , 10.1109/EDAC.1993.386496
Halatsis, Gaitanis, Irredundant Normal Forms and Minimal Dependence Sets of a Boolean Function IEEE Transactions on Computers. ,vol. 27, pp. 1064- 1068 ,(1978) , 10.1109/TC.1978.1674997
Detlef Sieling, Ingo Wegener, Graph driven BDDs—a new data structure for Boolean functions Theoretical Computer Science. ,vol. 141, pp. 283- 310 ,(1995) , 10.1016/0304-3975(94)00078-W