The Complexity of Datalog on Linear Orders

We study the program complexity of datalog on both finite and infinite linearorders. Our main result states that on all linear orders with at least twoelements, the nonemptiness problem for datalog is EXPTIME-complete. Whilecontainment of the nonemptiness problem in EXPTIME is known for finite linearorders and actually for arbitrary finite structures, it is not obvious forinfinite linear orders. It sharply contrasts the situation on other infinitestructures; for example, the datalog nonemptiness problem on an infinitesuccessor structure is undecidable. We extend our upper bound results toinfinite linear orders with constants. As an application, we show that the datalog nonemptiness problem on Allen'sinterval algebra is EXPTIME-complete.Comment: 21 page