CS Paper Radar

Capturing Bisimulation-Invariant Exponential-Space Complexity Classes

Florian Bruse, David Kronenberger, Martin Lange

cs.LO cs.CC ·submitted 2026-10-11 09:27 UTC · v1
publishedtheory

Abstract

Otto's Theorem characterises the bisimulation-invariant PTIME queries over graphs as exactly those that can be formulated in the polyadic mu-calculus. This extends to a characterisation of the full bisimulation-invariant exponential-time hierarchy, using a higher-order extension of the polyadic mu-calculus, called PHFL, which is naturally stratified by type order. The bisimulation-invariant fragment of k-EXPTIME is captured by the fragment of PHFL whose formulas have type order at most k. This is obtained using a generalisation of the Immerman-Vardi Theorem by Freire and Martins. Here we provide such a characterisation of the exponential-space hierarchy. We show that the bisimulation-invariant fragment of k-EXPSPACE is captured by the fragment of PHFL of type order k+1 whose formulas are tail-recursive. Tail recursion limits the interplay between fixpoints and higher-order functions so that model checking based on fixpoint iteration can be made more space efficient in a way comparable to tail recursion in programming languages. The capturing result makes use of a generalisation of Vardi's characterisation of PSPACE as first-order logic with partial fixpoints, namely that k-EXPSPACE is captured by higher-order logic of order k+1 with partial fixpoints.

Comment
In Proceedings GandALF 2026, arXiv:2610.08898
Journal ref
EPTCS 454, 2026, pp. 49-66
DOI
10.4204/EPTCS.454.5

Closest papers

Nearest neighbours by meaning across the whole index.

Weak Bisimulation Finiteness of Pushdown Systems With Deterministic $\varepsilon$-Transitions Is 2-ExpTime-Complete

cs.FL ·2026-08-11 ·Stefan Göller, Paweł Parys
top venuetheory similarity 0.61
Abstract

We consider the problem of deciding whether a given pushdown system all of whose $\varepsilon$-transitions are deterministic is weakly bisimulation finite, that is, whether it is weakly bisimulation equivalent to a finite system. We prove that this problem is 2-ExpTime-complete. This consists of three elements: First, we prove that the smallest finite system that is weakly bisimulation equivalent to a fixed pushdown system, if exists, has size at most doubly exponential in the description size of the pushdown system. Second, we propose a fast algorithm deciding whether a given pushdown system is weakly bisimulation equivalent to a finite system of a given size. Third, we prove 2-ExpTime-hardness of the problem. The problem was known to be decidable, but the previous algorithm had Ackermannian complexity (6-ExpSpace in the easier case of pushdown systems without $\varepsilon$-transitions); concerning lower bounds, only ExpTime-hardness was known.

0.40

Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable

cs.FL cs.LO ·2026-10-29 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.61
Abstract · 31 pages, 3 figures. Rocq artifact: https://doi.org/10.5281/zenodo.23734555

Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, $Π^0_1$-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet $Σ_2=\{e:0,d:2\}$, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over $Σ_2$. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled $\bot$.

0.32

Maltsev Constraint Satisfaction Problems and Deterministic Logspace With Counting

cs.CC ·2026-09-25 ·Dejan Delic, Ali Syed
theoryhot direction similarity 0.60
Abstract

In this article, we prove that the problem of solving $\operatorname{CSP}(\mathbf{A})$, where $\mathbf{A}$ is a finite relational template which admits a Maltsev polymorphism is in a specific complexity class DET, which is related to the complexity of computing the determinant of a matrix with integer entries. Such a class is intimately related to well-studied MOD-logspace classes in the theory of computational complexity. To prove this fact, we develop a new algorithm for solving syntactically simple binary instances of Maltsev constraint satisfaction problems, rather different from the well-known Bulatov-Dalmau algorithm, which does not require the explicit use or knowledge of a Maltsev polymorphism of the template but, rather, utilizes a graph whose vertices are 2-generated subuniverses of $\mathbb{A}$, where $\mathbb{A}$ is the Maltsev algebra parametrizing $\operatorname{CSP}(\mathbf{A})$. The theoretical importance of this algorithm is reflected in two facts: (1) it places the problem $ \operatorname{CSP}(\mathbf{A})$ in a complexity class related to the deterministic logspace with counting, which, in itself, has a strong connection to a variety of standard algorithmic problems in linear algebra, and (2) it only makes use of the relational structure of the template without the need for the explicit use of a compatible Maltsev polymorphism, depending entirely on the strong ``symmetry" of constraints compatible with such polymorphisms and the knowledge of 2-generated subuniverses of $\mathbb{A}$.

0.49

Descriptive Complexity in Lean: Completeness by First-Order Reductions

cs.LO cs.CC ·2026-09-16 ·Pierre Senellart, Anton Gnatenko
theorycode/data similarity 0.60
Abstract · 25 pages. Library available at https://github.com/PierreSenellart/descriptive-complexity

We show that descriptive complexity can serve as a foundation for formalizing computational complexity results in a proof assistant, by constructing a Lean library centered around the following concepts: decision problems are isomorphism-invariant predicates on finite structures; complexity classes are defined by their logical characterization; membership is shown by definability witnesses; hardness is shown by first-order reductions from a known hard problem. We also establish bridges to traditional machine models such as (non)deterministic Turing machines. The library proves 73 completeness results, on 68 problems or problem families, over 14 different classes; relations between the classes established inside the logic and not by machine simulation, among them NL = coNL and the Abiteboul-Vianu theorem; and unconditional lower bounds, among them $\mathrm{FO}(\leq) \subsetneq \mathrm{FO}(\leq, \mathrm{TC})$ and the failure of order-free FO(IFP) to capture PTIME.

0.47

From Block Orthogonality to Decidability in Complex-Weighted Counting CSP

cs.CC ·2026-08-14 ·Chenghua Liu, Boning Meng
theory similarity 0.60
Abstract · 68 pages; revised proof and exposition, including a correction; Lean repository linked

In a landmark JACM paper recognized with the 2021 Gödel Prize, Cai and Chen established a complexity dichotomy for counting CSPs over arbitrary finite domains with algebraic complex weights. Their tractability criterion consists of three conditions on the infinite family of functions obtained from CSP instances by summing out some variables: the Block Orthogonality and Type Partition conditions, and a Mal'tsev polymorphism condition on support and row-equivalence relations. They left open whether this criterion is decidable from the finite set of constraint functions. We resolve this question by giving a total exact algorithm for every $q$-element domain ($q\ge 1$), with algebraic weights encoded exactly. We also prove that the Block Orthogonality condition implies the other two conditions, reducing the tractability criterion to a single structural property. We obtain similar decidability and structural results for Lin's tractability criterion for $\#\mathrm{CSP}^{d}$, where each variable occurs a multiple of $d$ times. Our method first shows that every failure of Block Orthogonality can be witnessed by a generated function of arity at most $q^2+1$. At each such arity, we reduce checking infinitely many generated functions to finitely many exact algebraic tests, using tensor products and a pinned extension of Young's all-instance isomorphism theorem. For the structural implication, we use powers of generated functions to control complex cancellation and construct functions whose supports encode row equivalence. These constructions yield the Type Partition and Mal'tsev polymorphism conditions.

0.10

Step Recursion: Resource Profiles and Descent Quotients

cs.CC cs.LO ·2026-08-23 ·Kirill Osipov
similarity 0.59
Abstract · Companion to arXiv:2608.04871

We develop a resource representation for step recursion in which mutable-state width and recursion descent are explicit and independent parameters. A width bound $u$ controls the size of the encoded machine state, while an effective descent $ρ$ determines the available recursion depth $δ_ρ(u)$. For generalized-inverse descents, we derive the depth directly from generator growth and characterize the increasing sequences that can occur as generator orbits. We then connect this depth--width geometry to standard finite-branching computation. Every deterministic bounded-state dynamics is realizable by a single ordinary bounded step recursion over a fixed finite numerical basis. Using deterministic, existential, universal, or alternating aggregation on the same local dynamics yields the corresponding machine semantics. After closure under the width reparameterizations needed to absorb fixed local cost, the resulting language classes are exactly the machine time--space classes on profiles $(δ_ρ(u),u)$. Finally, profile domination quotients effective descents by admissible width reparameterization. Some depth curves collapse, yet polynomial widths support an explicit infinite strict hierarchy between the canonical polynomial- and exponential-depth profiles. Thus descent remains a nonredundant resource coordinate after polynomial width reparameterization; standard complexity classes are calibration points.

0.33

Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse

cs.LO math.LO ·2026-10-29 ·Kirill Osipov
theory similarity 0.58
Abstract

For a strictly increasing $G:\mathbb{N}\to\mathbb{N}$ with $G(0)\geq 1$, we study minimal-basis function algebras generated by recursion along generalized inverses of its iterates. Bounded recursion requires an earlier pointwise majorant; unbounded recursion has no such requirement. If the orbit $G^{[t]}(0)$ has no polynomial upper bound, we obtain exact fixed-function membership spectra, reverse-divisibility inclusion, and indexed intersections that need not be single-stride algebras. Every finite divisibility-downset is realized in both regimes, and mixed strides admit fixed functions expressing any finite monotone Boolean condition on their additive stride monoid. For every generator, the realized bounded spectra form a bounded meet-semilattice: a construction sharing a bounding input coordinate realizes finite intersections without an unrestricted selector. Polynomial orbit growth is equivalent to definability of each of ordinary predecessor, unary doubling, and addition in any fixed unbounded stride algebra. In this case the algebra is ordinary primitive recursion relative to its inverse map, giving full collapse for primitive-recursive $G$. Ordinary predecessor belongs to a bounded stride algebra exactly when the orbit is polynomially bounded and $G$ has bounded successive differences; equivalently, ordinary bounded recursion embeds. A locality obstruction explains the additional bounded requirement, and two primitive-recursive generators with quadratic orbits have opposite bounded collapse behavior.

0.23

Machine-Checked Computational Group Theory in Lean 4: Operational Schreier-Sims Stabilizer Chains, BSGS Sifting, and Backtrack Ordered Partitions

cs.LO cs.SC ·2026-09-29 ·Volkan Dağlı, Zerrin Dağlı, Dağhan Dağlı
publishedtheorycode/data similarity 0.58
Abstract · 3 pages, 1 table, Release v0.2.0, 35 machine-checked theorems with 0 sorry in Lean 4 / Mathlib4. Repository: https://github.com/pCwOrM/gap-l…

We present gap-lean4-port (Release v0.2.0), a machine-checked formalization of foundational algorithms in computational discrete algebra and permutation group theory within the Lean 4 interactive theorem prover and Mathlib4. While modern proof assistants feature extensive abstract algebraic hierarchies, constructive and operational permutation group algorithms, such as Charles Sims' 1970 Schreier-Sims algorithm, transversal tree lookups, and backtrack ordered partition refinement, have remained largely unformalized in dependent type theory. Here, we formalize the operational algorithmic core of the Groups, Algorithms, Programming (GAP) system library across four foundational modules, proving 35 machine-checked theorems with zero unproven conjectures (sorry) and zero custom axioms under standard Lean 4 foundations (propext, Classical.choice, Quot.sound). We machine-check: (1) Schreier-Sims stabilizer chain hierarchies (StabLevel, StabChain) and the invariance of incremental transversal tree extensions (extendSchreierPoint_invariant); (2) single-level and multi-level Schreier sifting reductions (siftOneLevel, siftFull), proving that full sifting strictly fixes all base points (siftFull_fixes_all_basePoints); (3) constructive soundness and completeness of Base and Strong Generating Set (BSGS) membership testing (membershipTestKnownBase_iff_mem); (4) backtrack ordered partition cell refinement (splitCellByPred), proving mutual cell disjointness, union conservation, and exact cardinality preservation; (5) cyclotomic extension rings Z/nZ(eps_m) and machine-check GAP's exact size theorem |Z/nZ(eps_m)| = n^m; and (6) executable Bezout inverses via Extended Euclidean GCD (Nat.gcdA) over residue rings Z/nZ. The entire codebase compiles deterministically under 'lake build RequestProject' and is openly available at https://github.com/pCwOrM/gap-lean4-port.

0.37