Martin Grohe ; Goetz Schwandtner - The Complexity of Datalog on Linear Orders

lmcs:811 - Logical Methods in Computer Science, February 27, 2009, Volume 5, Issue 1 -
The Complexity of Datalog on Linear OrdersArticle

Authors: Martin Grohe ORCID; Goetz Schwandtner

    We study the program complexity of datalog on both finite and infinite linear orders. Our main result states that on all linear orders with at least two elements, the nonemptiness problem for datalog is EXPTIME-complete. While containment of the nonemptiness problem in EXPTIME is known for finite linear orders and actually for arbitrary finite structures, it is not obvious for infinite linear orders. It sharply contrasts the situation on other infinite structures; for example, the datalog nonemptiness problem on an infinite successor structure is undecidable. We extend our upper bound results to infinite linear orders with constants. As an application, we show that the datalog nonemptiness problem on Allen's interval algebra is EXPTIME-complete.

    Volume: Volume 5, Issue 1
    Published on: February 27, 2009
    Imported on: December 20, 2006
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Computer Science - Databases,F.4.1,D.3.2,H.2.3

    1 Document citing this article

    Consultation statistics

    This page has been seen 1031 times.
    This article's PDF has been downloaded 327 times.