Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

Mitarbeiterseminar Logik in der Informatik

Montag, 21. November 2005, 14:15 Uhr
RUD 25, Raum 4.410

Complexity of DATALOG on dense linear orders

Götz Schwandtner
Johannes Gutenberg-Universität Mainz
Humboldt-Universität zu Berlin

DATALOG is a modification of logic programming to the database context and has become a common database query language in database theory. While most research has concentrated on finite databases, we consider DATALOG on infinite structures. One motivation for this is, that DATALOG can be seen as a restriction of constraint logic programming -- which deals with infinite structures -- and it could be used to learn more about the relation between the complexity of constraint logic program evaluation and the structure of the constraints involved. This talk will deal with strict linear orders as constraints, or EDBs in the DATALOG context, and it will be shown that DATALOG on dense strict linear orders has EXPTIME-complete program complexity, and that monadic DATALOG has PTIME-complete program complexity on strict linear orders. Some of these results are transfers of the results for DATALOG on finite structures while others demonstrate techniques for evaulating DATALOG programs on infinite structures.

Zurück zur Vortragsübersicht 

Last modified: Tue Nov 15 11:37:33 CET 2005
André Hernich