Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Logik-Sem., 09.10.06, M. Bodirsky

0 views
Skip to first unread message

Uwe Waldmann

unread,
Sep 29, 2006, 8:27:02 AM9/29/06
to
Logikseminar
Einladung zum Vortrag

Zeit: Montag, 09.10.06, 14.15 Uhr
Ort: Hörsaal 024, MPI Saarbrücken (Geb. E1.4)

Manuel Bodirsky (HU Berlin):
Complexity of Temporal Constraint Satisfaction
(joint work with Jan Kara)

Zusammenfassung:

We introduce two new tractable temporal constraint languages, which
both strictly contain the Ord-Horn language introduced by Bürkert
and Nebel. We also prove that our languages are maximally tractable,
i.e., if we add a new temporal relation to our constraint languages,
the corresponding constraint satisfaction problem becomes NP-complete.

For that we apply the so-called product Ramsey theorem, which we
believe will be useful in similar contexts of constraint satisfaction
complexity classification. Finally, we prove that the two languages
cannot be solved by Datalog, or, equivalently, by local consistency
techniques.

______________________________________________________________________
Das Logikseminar ist eine gemeinsame Veranstaltung des DFKI, des MPI
und der Fachrichtungen Informatik, Philosophie und Rechtswissenschaft.
Vortragswünsche bitte an Uwe Waldmann, MPI, Tel.: (0681) 9325-205,
uni-intern: 92205, E-Mail: u...@mpi-sb.mpg.de

0 new messages