| Title: | Constrained decision diagrams |
| Date: |
August 27, 2005 (Saturday)
|
| Time: |
10:30 a.m. - 11:30 a.m.
|
| Venue: |
Room 1027, 10/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong, Shatin, N.T. |
| Speaker: |
Prof. Roland Yap
Department of Computer Science National University of Singapore Singapore |
Constraint Satisfaction Problems (CSP) is both a useful model as well as practical approach for solving many combinatorial NP-hard problems. When modelling problems, it is common to use constraints which are built in the particular constraint system such as arithmetic constraints, disequality, etc. A more general approach is to define an arbitrary constraint over n-variables, an n-ary constraint, which is problem specific.
Typically, an n-ary constraint is represented explicitly as a set of tuples which constitute the possible values for this constraint. In general, the explicit representation may require exponential space. In this talk, we introduce a new representation for general n-ary constraints called constrained decision diagram (CDD). CDD generalizes BDDs. Its main feature is that it combines constraint reasoning/consistency techniques with a BDD-like compact data structure.
We present an application of CDD for recording all solutions of a conjunction of constraints. Instead of an explicit representation, we can implicitly encode the solutions by means of constraint propagation. Our experiments confirm the scalability and demonstrate that CDDs can drastically reduce the space needed over explicit representations.
BIOGRAPHY:
Roland Yap is an associate professor at the Department of Computer Science, National University of Singapore. He is one of the primary authors of the CLP(R) system which was the first CLP language with arithmetic constraints. His current research interests are in the area of constraints, programming languages, bioinformatics and security. He obtained his B.Sc and Ph.D from Monash University, Australia.
Enquiries: Miss Temmy So at tel 2609 8444
For more information, please refer to http://www.cse.cuhk.edu.hk/seminar