Campus Event Calendar
Event Entry
What and Who
Understanding tractable decompositions for constraint satisfaction
Zoltan Miklos
Oxford University
Talk
AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 16 November 2007
10:00
60 Minutes
E1 4
433
Saarbrücken
Abstract
Many important problems in computer science and in artificial
intelligence can be modeled as constraint satisfaction problems
(CSPs). Essentially the same problem is the Boolean conjunctive query
evaluation over a relational database, which is a one of the central
questions studied in database theory. As solving a CSP (and evaluating
a Boolean conjunctive query) is NP-complete in general, it is
important to identify tractable subclasses. A possible way to find
such subclasses is to associate a graph or a hypergraph to the problem
and impose restrictions on its structure. This is what I will discuss
in this talk. I review the most important decomposition methods
arising in this way, in particular the generalizations of the concept
of hypergraph acyclicity. I will also report on some computational
experiments and further applications of the decomposition techniques.
The talk is based on papers by G. Gottlob, N. Leone, F. Scarcello, T.
Schwentick, and others and also outlines the main results of my PhD
thesis
intelligence can be modeled as constraint satisfaction problems
(CSPs). Essentially the same problem is the Boolean conjunctive query
evaluation over a relational database, which is a one of the central
questions studied in database theory. As solving a CSP (and evaluating
a Boolean conjunctive query) is NP-complete in general, it is
important to identify tractable subclasses. A possible way to find
such subclasses is to associate a graph or a hypergraph to the problem
and impose restrictions on its structure. This is what I will discuss
in this talk. I review the most important decomposition methods
arising in this way, in particular the generalizations of the concept
of hypergraph acyclicity. I will also report on some computational
experiments and further applications of the decomposition techniques.
The talk is based on papers by G. Gottlob, N. Leone, F. Scarcello, T.
Schwentick, and others and also outlines the main results of my PhD
thesis
Contact
Gerhard Weikum
500
--email hidden
passcode not visible
logged in users only
Petra Schaaf, 11/12/2007 11:23 -- Created document.