CS Paper Radar

A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures

Steffen van Bergerem, Martin Grohe, Charlotte Lenz, Nicole Schweikardt

cs.LO math.LO ·submitted 2026-09-29 12:09 UTC · v1
theory

Abstract

We prove a rank-preserving version of Gaifman's Theorem. Compared to earlier rank-preserving locality theorems (in particular, [Grohe, Kreutzer, Siebertz, JACM 2017]), our theorem is much simpler and yields formulas in exactly the same normal form as Gaifman's original theorem. Furthermore, it holds not only for first-order logic, but also for first-order logic with modulo-counting quantifiers and, more generally, for the first-order logic on weighted structures ngFOW+ that is introduced in this article. As an application of our theorem, we give a simplified proof of the algorithmic meta-theorem of [Grohe, Kreutzer, Siebertz, JACM 2017] stating that first-order properties of nowhere dense structures can be decided in almost-linear time. Our locality theorem for the weight logic ngFOW+ can be seen as an essential step toward such a meta-theorem for this logic.

Comment
54 pages, 1 figure. This paper supersedes the preprint arXiv:2606.11993

Closest papers

Nearest neighbours by meaning across the whole index.

Counting on Nowhere Dense Classes

cs.LO ·2026-09-16 ·Steffen van Bergerem, Nicole Schweikardt
similarity 0.63
Abstract · 22 pages

For every effectively nowhere dense class $\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\mathcal{A} \in \mathcal{C}$ and a first-order formula $φ(x_1, \dots, x_k, y_1, \dots, y_\ell)$. After the preprocessing, whenever given a tuple $\bar{v} \in A^k$, the algorithm computes the number of tuples $\bar{w} \in A^\ell$ that satisfy $\mathcal{A} \models φ(\bar{v}, \bar{w})$ in constant time. Building on this, we provide an algorithm for constant-time query answering and constant-delay enumeration after almost-linear-time preprocessing for the recently introduced logic clique-guarded first-order logic with counting (cgFOC) on effectively nowhere dense classes. This generalises the testing and enumeration results for first-order logic [Schweikardt, Segoufin, and Vigny, JACM 2022] and the evaluation result for the first-order logic with counting FOC1 [Grohe and Schweikardt, PODS 2018] on nowhere dense classes.

0.32

Two Variables and Two-Dimensional Structures

cs.LO ·2026-10-14 ·Bartosz Jan Bednarczyk, Daumantas Kojelis, Krzysztof Szymański
theory similarity 0.61
Abstract · 23 pages, 4 figures, 1 table. Under submission

We study the two-variable fragment FO^2 of first-order logic over two-dimensional structures. Formulae may employ two linear orders <=_1, <=_2, their successor relations S_1, S_2, and auxiliary predicates of any arity. Despite two decades of work, three cases of finite satisfiability in this setting were still open; we settle all three. First, finite satisfiability of FO^2 with one linear order and one successor relation, of the same or of a different order, is NExpTime-complete, even with arbitrary auxiliary predicates and constant symbols. This closes a gap left open by Manuel and Zeume (CSL 2013). As an application, a reduction based on swaps of adjacent elements shows that order-invariance and order-successor-invariance of FO^2 are coNExpTime-complete. This reproves the main result of Zeume and Harwath (LICS 2016) and settles their question on order-successor-invariance. Second, finite satisfiability of FO^2 with two linear orders is ExpSpace-hard, already without auxiliary non-unary predicates, matching the upper bound known since 2010. Our reduction combines Kieronski's encoding of alternating Turing machines with the classical fact that the pre-order and post-order traversals of a tree define its descendant relation. Third, with two linear orders and the successor of one of them, finite satisfiability is in ExpSpace even with arbitrary auxiliary predicates, improving the previous 2NExpTime bound and confirming a conjecture of Zeume and Harwath. Together with known results, our theorems show that in two dimensions, auxiliary (non-unary) predicates and constants come for free: with or without them, the complexities coincide. All our proofs are simple.

0.10

First-Order Model Checking on Monadically Dependent Graph Classes

cs.LO cs.DMcs.DSmath.CO+1 ·2026-11-05 ·Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
similarity 0.57
Abstract

Monadically dependent graph classes are those in which first-order logic cannot encode all graphs. They include all nowhere dense classes and all classes of bounded twin-width. We show that first-order model checking is fixed-parameter tractable on every monadically dependent graph class. Together with the known hardness result for hereditary classes that are not monadically dependent, this gives a complete characterization of the hereditary graph classes with fixed-parameter tractable first-order model checking. This resolves a central open problem in algorithmic model theory. Our proof combines ideas from structural graph theory (graph decompositions), finite model theory (locality of first-order logic), and model theory (counting types). In particular, we show that in monadically dependent classes, tuples of fixed length have only $|U|^{O(1)}$ types of fixed quantifier rank over any set of parameters $U$.

0.18

Weighted First-Order Model Counting over Ordered Domains

cs.LO ·2026-08-11 ·Jan Tóth, Qipeng Kuang, Kuncheng Zou, Václav Kůla, Yuyi Wang +2 more
similarity 0.57
Abstract · Submitted to JAIR

The Weighted First-Order Model Counting Problem (WFOMC) asks for the weighted sum of models of a first-order logical sentence over a domain. It is a fundamental problem in statistical relational learning, with applications extending to enumerative combinatorics and graph polynomials. Computing WFOMC for the three-variable fragment is $\mathsf{\#P}_1$-hard, whereas polynomial-time algorithms exist for the two-variable fragment and its extensions by cardinality constraints and counting quantifiers. In this work, we explore computing WFOMC in polynomial time over linearly ordered domains, enabling tractable reasoning across inference scenarios and combinatorial problems involving sequences. Because encoding a linear order in standard first-order logic requires three variables, negating our polynomial-time aspirations, we add a linear order axiom directly to the language. This forces one predicate to impose a total ordering on domain elements. We first prove that WFOMC with the linear order axiom can be solved in time polynomial in the domain size. We then extend this result to ordered domains with access to successor relations. While this holds when successors are explicitly defined via the linear order, we demonstrate an alternative implicit approach where successor relations are part of the axiom. This implicit method exhibits significantly better performance on all tested instances, sometimes providing exponential runtime improvements. Finally, we analyze scenarios with two distinct linear orders. We show that WFOMC over the two-variable fragment with two linear orders is $\mathsf{\#P}_1$-hard. However, we develop a polynomial-time algorithm for WFOMC with one linear order and a successor relation of another, pushing the intractability barrier further, yet still leaving the question of how close to a second full linear order one can get.

0.35

Order-Invariant CFO Contains Local-Order-Invariant FO

cs.LO math.LO ·2026-11-01 ·Derek R. Aoki
similarity 0.56
Abstract · 19 pages

Order-invariant cluster first-order logic (CFO) and local-order-invariant first-order logic are two fragments of order-invariant first-order logic, both motivated by the study of invariant logics on classes of bounded degree. Our main result is that order-invariant CFO contains local-order-invariant FO on arbitrary classes of finite structures, settling the conjecture of Ghasemi and Grange that order-invariant CFO contains plain FO. By combining this with a collapse result of Ghasemi and Grange, we obtain the equivalence of FO, local-order-invariant FO, and order-invariant CFO on classes of finite colored graphs of bounded degree. The proof makes use of Gaifman normal form, which allows our translation from local-order-invariant FO to order-invariant CFO to be effective. Combined with the fixed-parameter tractability of model-checking for order-invariant CFO on bounded-degree colored graph classes, this shows that model-checking for local-order-invariant FO on bounded-degree colored graph classes is fixed-parameter tractable. To generalize our collapse and model-checking results beyond colored graphs, we use a method based on first-order interpretations which also yields a collapse of order-invariant FO to FO when restricted to graph classes of bounded shrub-depth. Finally, we give an application to the database-motivated frozen-witness logic of Abiteboul, Simon, and Vianu by showing that local-order-invariant FO contains deterministic frozen-witness FO, and thus that deterministic frozen-witness FO collapses to FO on classes of finite structures of bounded degree.

0.30

A sound pure type system with ranks as sorts and Type-in-Type

cs.LO math.LO ·2026-10-18 ·Pavel Sokolov, Alexander Kuklev
code/data similarity 0.54
Abstract · 28 pages, 3 figures, supplementary material to be found at http://github.com/TurtlePU/pts-rk

We present a dependently typed pure type system that contains a circular axiom $s : s$ for a certain sort $s$ and is nonetheless strongly normalizing. Girard's paradox is avoided because our sorts are not closed under a $Π$-former: function types are placed in sorts according to their rank. Turns out that this system has a unique set of characteristics: it has similar normalization behaviour as STLC (so complexity of normalization is TOWER-complete) while at the same time allowing non-uniform representation of arbitrary elementary recursive functions; furthermore, it has a nontrivial set-theoretical model in ZF+GCH and allows to carry out nontrivial proof developments. Base normalization proof is surprisingly simple (modulo general metatheoretical properties of pure type systems) and has been fully formalized in vanilla Rocq (formerly Coq) without additional axioms.

0.30

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.53
Abstract

We study two-variable first-order logic with a finite, input-dependent number of distinguished successor relations and arbitrary additional unary and binary predicates. Each distinguished relation must be the exact immediate-successor relation of some linear order on the common domain; the orders themselves are not available in the language and may have arbitrary order types. We prove that satisfiability belongs to 2NEXPTIME, uniformly in the number of successors. The proof gives finite certificates for possibly infinite models. A closure operation separates local neighbourhood descriptions, called star types, into those of bounded multiplicity and those that can be realized infinitely often. The bounded part is represented explicitly. Outside it, integer height vectors allow overlapping successor requirements to be matched without creating cycles or unintended identifications. Ordering the resulting path components densely then recovers exact successor relations. Consistent assignments of the additional binary predicates handle witnesses involving the bounded part. The same certificates decide infinite satisfiability in 2NEXPTIME and give a doubly exponential threshold above which a finite model guarantees an infinite model. A doubly exponentially large finite core can be forced with only two successors and unary predicates. For finite models, we prove that satisfiability subject to a bound on the total number of reference adjacencies lost by the other orders is NEXPTIME-complete, even when the budget is encoded in binary and the number of successors is part of the input.

0.49

A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs

cs.DS cs.CC ·2026-10-05 ·Thomas Depian, Robert Ganian, Jakob Greilhuber, Marlene Gründel, Simon Wietheger
similarity 0.53
Abstract

A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; however, this provides neither a procedure for constructing these algorithms nor computable bounds on their parameter dependence. We turn this existential result into a uniform algorithmic metatheorem. Given a Strict NP sentence $\varphi$ and a relational structure $\mathcal{R}$, our algorithm decides whether $\mathcal{R}\models\varphi$ in time $f(|\varphi|, td(\mathcal{R})) \cdot |\mathcal{R}|$ for a computable function $f$, where the treedepth of $\mathcal{R}$ is measured on the Gaifman graph. The algorithm also constructs witness relations, with the polynomial exponent depending on their arity, and provides a unified framework for settling hereditary graph problems parameterized by treedepth. We also present several applications - among others, our result resolves open questions on the fixed-parameter tractability of computing the stack number, queue number, track number and twin-width parameterized by treedepth.

0.29