Computer Science – Logic in Computer Science
Scientific paper
2009-02-08
LMCS 5 (1:4) 2009
Computer Science
Logic in Computer Science
21 pages
Scientific paper
10.2168/LMCS-5(1:4)2009
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.
Grohe Martin
Schwandtner Goetz
No associations
LandOfFree
The Complexity of Datalog on Linear Orders does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Datalog on Linear Orders, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Datalog on Linear Orders will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-580760