|
TITLE: Searching While Keeping a Trace: The Evolution from Satisfiability to Knowledge Compilation
PRESENTER: Adban Darwiche, http://www.cs.ucla.edu/~darwiche/, darwiche@cs.ucla.edu
AFFILIATION:Computer Science Department, University of California, http://www.cs.ucla.edu/
DATE: Thursday 14th December 2006
TIME: 13:00:00
PLACE: CSE Seminar Room, Level 1, K17
ABSTRACT:
I will discuss in this talk two influential areas of automated
reasoning, satisfiability and knowledge compilation. Historically,
these two areas have been developing independently, but have come
to an intersection point recently that is interesting both
theoretically and practically. In particular, I will show that
the intersection point rests on recent extensions of satisfiability
solvers to perform exhaustive searches for the purpose of model
counting and enumeration, aided by sophisticated techniques
such as component analysis and formula caching. More precisely,
I will show that the traces of these exhaustive search algorithms
can be interpreted as sentences and that each search algorithm
corresponds to a (tractable) language generated by all its possible
executions. I will provide multiple matches between key search
algorithms and well known tractable languages and discuss two
implications of this matching: (1) harnessing advances in
satisfiability to compile knowledge bases, leading to some new
algorithms for knowledge compilation, and (2) invoking known
results on tractable languages to identify previously unknown
powers and limitations of search algorithms. The talk will provide
empirical results and applications from various areas, including
planning, diagnosis and probabilistic reasoning.
BIOGRAPHY OF SPEAKER:
Dr. Darwiche is a professor of computer science at UCLA and directs
the Automated Reasoning Group at UCLA. He obtained his M.S. and Ph.D.
degrees in computer science from Stanford University in 1989 and 1993,
respectively. Prior to joining UCLA, he established and managed the
department of Diagnostics and Modeling at Rockwell Science Center
(see DTOOL/CNETS diagnostic system). Dr. Darwiche's research interests
include probabilistic and symbolic reasoning, with their application to
diagnosis, planning, and cognition, in addition to system design and
analysis. His teaching interests include graduate and undergraduate
courses in Artificial Intelligence, Probabilistic Reasoning, and
Symbolic Reasoning.
Seminar information is also available at
http://www.cse.unsw.edu.au/db/ai/seminars/list/index.html
Host:
Toby Walsh
Seminar Convenor:
Van Hai Ho
|
