[Index] || [Contents] || [Grades] Mon Mar 3 14:43:01 PST 2003

656/556 2003 1w 07 OBBDs 1 Assigned work due: Page 84, Exercises 1.14. #1(c). Compact data structures to encode Boolean expressions Chapter 6 OBDD. Section 6.1 Boolean functions Syntax of boolean expressions Relation to PC: wffs, Truth Tables, DNF, CNF, ... BDDs: tree ->(reduction)-> DAG Data Structure? OBDDs Order the variables -- canonical! less redundant, tests for equiv, validity, implication, satisfiability Assigned Work: Exercise 1c of exercises 6.5 page333, Hand in Tree and OBDD lab: The tutorial on ch6 http://www.cis.ksu.edu/~huth/lics/tutor/chap6/questions.html A generator of ordered Decision Diagrams http://www.rs.e-technik.th-darmstadt.de/~sth/demo.html Notation is based on LISP: wff::= atom | "(" operator #wff ")". operator::="or" | "and" | "not" |... Next: Section 6.2. Algorithms for handling OBDDs http://www.csci.csusb.edu/dick/cs656/class/08.html