{"id":{"repo_id":"sask","oai_identifier":"oai:harvest.usask.ca:10388/etd-10202004-235642"},"canonical_url":"https://search.dev.ndltd.org/etd/sask/oai:harvest.usask.ca:10388/etd-10202004-235642","repository":{"repo_id":"sask","name":"University of Saskatchewan","base_url":"https://harvest.usask.ca/server/oai/request"},"display":{"title":"Data structures, minimization and complexity of boolean functions","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Wang, Yuke"],"institution":"University of Saskatchewan","degree_name":"Doctor of Philosophy (Ph.D.)","degree_level":"Doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":["McCrosky, Carl"],"year":1996,"date_issued":"1996-01-01","date_published":"1996-01-01","updated_at":"2026-07-24T04:27:11Z","subjects":[],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/10388/etd-10202004-235642","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.committeemember","label":"Committee Member","values":["McCrosky, Carl"]},{"key":"dc:creator","label":"Author","values":["Wang, Yuke"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2004-10-20T23:56:42Z","2013-01-04T05:01:39Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["1996-01-01T08:00:00Z","2013-01-04T05:01:39Z"]},{"key":"dc:date.issued","label":"Date","values":["1996-01-01"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (Ph.D.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Saskatchewan"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10388/etd-10202004-235642"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Data structures, minimization and complexity of boolean functions"]}]}],"canonical_facts":{"dc:contributor.committeemember":["McCrosky, Carl"],"dc:creator":["Wang, Yuke"],"dc:date.accessioned":["2004-10-20T23:56:42Z","2013-01-04T05:01:39Z"],"dc:date.available":["1996-01-01T08:00:00Z","2013-01-04T05:01:39Z"],"dc:date.issued":["1996-01-01"],"dc:description.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."],"dc:identifier.uri":["https://hdl.handle.net/10388/etd-10202004-235642"],"dc:language.iso":["en_US"],"dc:title":["Data structures, minimization and complexity of boolean functions"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy (Ph.D.)"],"thesis:institution_name":["University of Saskatchewan"]},"updated_at":"2026-07-24T04:27:11Z"}