Data structures, minimization and complexity of boolean functions
Date
1996-01-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ORCID
Type
Degree Level
Doctoral
Abstract
Boolean function manipulation is an important component of computer science. This thesis presents results related to Boolean function representation and minimization. The Boolean function minimization problem is re-defined. A new Boolean function classification theory based on permutation and extension is developed. More efficient Boolean function minimization algorithms can be derived based on the classification theory. The thesis also examines the complexity issues and graph structure of OBDDs of some special Boolean functions. Moreover, some new data structures for Boolean functions are reported in this thesis. Some functions are found to have constant complexity in the new data structure while having exponential complexity in existing data structures.
Description
Keywords
Citation
Degree
Doctor of Philosophy (Ph.D.)
Department
Computer Science
Program
Computer Science