10.2168/LMCS-5(1:4)2009
https://lmcs.episciences.org/811
Grohe, Martin
Martin
Grohe
Schwandtner, Goetz
Goetz
Schwandtner
The Complexity of Datalog on Linear Orders
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.
Comment: 21 pages
episciences.org
Computer Science - Logic in Computer Science
Computer Science - Computational Complexity
Computer Science - Databases
F.4.1
D.3.2
H.2.3
arXiv.org - Non-exclusive license to distribute
2015-06-25
2009-02-27
2009-02-27
eng
journal article
arXiv:0902.1179
10.48550/arXiv.0902.1179
1860-5974
https://lmcs.episciences.org/811/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 5, Issue 1
Researchers
Students