PhD Qualifying Examination


"Constraint Satisfaction Problem (CSP) and its Multi-layer
Constraint Model"


By Mr. Peter Kwok-Leung Liu


Abstract:

Constraint Satisfaction Problem (CSP) is a fundamental problem in computer
science.  In this survey, CSP and its well-studied special case called
Satisfiability problem (SAT) is introduced.  Throughout this paper, a
packing puzzle called Polyomino is used as an example to illustrate the
concepts of CSP.  The techniques for solving CSP including problem
reduction, complete search, incomplete search, distributed and hybrid
methods are introduced.  The issues on applying these algorithms for
solving CSPs will be discussed.  Finally, a multi-layer constraint model
derived from the packing puzzle is introduced.  This model may shed light
to the design of a CSP algorithm that handles hierarchical domains.


Date:     		Monday, 9 September 2002

Time:                   2:00p.m.-4:00p.m.

Venue:                  Room 3315
			Lifts 17-18

Committee Members:      	Prof. Jun Gu (Supervisor)
                        Dr. Fangzhen Lin (Chairman)
			Dr. Siu-Wing Cheng
			Dr. Shing-Chi Cheung


**** ALL are Welcome ****