Search


Volume

Author

Year

  • < Previous
  • 1
  • Next >
1 result

The Complexity of Datalog on Linear Orders

Martin Grohe ; 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&nbsp;[&hellip;]
Published on February 27, 2009
Volume 5, Issue 1
  • < Previous
  • 1
  • Next >