From Time to Space: The Impact of Linearity in Higher-Order Datalog
2026-06-01 • Programming Languages
Programming LanguagesComputational ComplexityDatabasesLogic in Computer Science
AI summaryⓘ
The authors study a special type of logical programming language called Higher-Order Datalog with negation, focusing on a version that uses linear recursion. They show that this version can describe very complex problems related to how much memory (space) a computation needs, linking it to a known hierarchy in computer science called EXPSPACE. This builds on older results where simpler Datalog captured problems solvable with limited memory, but here it works without needing extra assumptions about the input data order. Their work helps understand the power and limitations of such languages, aiming to make them more practical in the future.
Higher-Order DatalogLinear Datalognegationlinear recursionEXPSPACEspace complexityStratified DatalogTuring machinesquery evaluationcomputational complexity
Authors
Angelos Charalambidis, Babis Kostopoulos, Panos Rondogiannis
Abstract
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.