Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper explores a fragment of Higher-Order Datalog with negation, establishing its expressive power in relation to space complexity classes. The authors show that the $(k+1)$-order fragment of Stratified Linear Higher-Order Datalog$^\neg$ captures $(k-1)$-EXPSPACE for all $k \ge 1$, indicating a shift in expressive power from time to space when linear recursion is applied. This finding generalizes the classical result of Linear Datalog capturing NL without requiring an ordering assumption on the input database, thus enhancing the potential for practical applications in Higher-Order Datalog systems.
Linear recursion in Higher-Order Datalog can elevate expressive power from time to space, capturing complex space classes without ordering assumptions.
We consider a fragment of Higher-Order Datalog with negation and argue that it generalizes the familiar and important fragment of Linear Datalog. We investigate the expressive power of this fragment, establishing a tight connection with the hierarchy of space complexity classes. In particular, we demonstrate that for all $k \ge 1$, the $(k+1)$-order fragment of Stratified Linear Higher-Order Datalog$^\neg$ captures $(k-1)$-EXPSPACE. This result suggests that restricting programs to linear recursion shifts the expressive power of the corresponding fragments from time to space, generalizing the classical result that (Stratified) Linear Datalog captures NL. Unlike the first-order setting where an ordering assumption is required to capture NL, our results hold without any such assumption on the input database. The proof relies on simulating space-bounded Turing machines using Stratified Linear Higher-Order Datalog$^\neg$ programs and providing a space-efficient evaluation of the query program. We argue that identifying such computationally well-behaved fragments is a crucial step towards paving the way for practical implementations of Higher-Order Datalog.