Characterizing the Exponential-Space Hierarchy Via Partial Fixpoints

2025/11/04 by Bruse, Florian, Kronenberger, David, Lange, Martin
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge

paper · doi:10.48550/arxiv.2511.02596

openalex publication_date 2025/11/04 · openalex created_date 2025/11/06 · openalex updated_date 2026/07/28

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.

Citations

• The polynomial-time hierarchy

Related

• EXPSPACE-Completeness of the Logics K4xS5 and S4xS5 and the Logic of Subset Spaces, Part 2: EXPSPACE-Hardness
• Traversal-invariant characterizations of logarithmic space
• Ordered fragments of first-order logic
• EXPSPACE-Completeness of the Logics K4xS5 and S4xS5 and the Logic of\n Subset Spaces, Part 1: ESPACE-Algorithms
• Complete Problems of Propositional Logic for the Exponential Hierarchy