[CSUSB] >> [CompSci] >> [Dick Botting] >> [CS656/556 Course Materials] >> class/07
[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