Characterizing the Exponential-Space Hierarchy Via Partial Fixpoints
arXiv:2511.02596 · doi:10.4204/EPTCS.435.7
Abstract
The characterization of PSPACE-queries over ordered structures as exactly those expressible in first-order logic with partial fixpoints (Vardi'82) is one of the classical results in the field of descriptive complexity. In this paper, we extend this result to characterizations of k-EXPSPACE-queries for arbitrary k, characterizing them as exactly those expressible in order-k+1-higher-order logic with partial fixpoints. For k>1, the restriction to ordered structures is no longer necessary due to the high expressive power of higher-order logic.
In Proceedings FICS 2024, arXiv:2511.00626