Data structures, minimization and complexity of boolean functions

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.

Name thesis:degree_name

Doctor of Philosophy (Ph.D.)

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Saskatchewan

Year dc:date.issued

1996

Author dc:creator

• Wang, Yuke

Committee member dc:contributor.committeemember

• McCrosky, Carl

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/10388/etd-10202004-235642

OAI identifier oai:identifier

oai:harvest.usask.ca:10388/etd-10202004-235642