CS Paper Radar

The Undecidability of FO3 and the Calculus of Relations with Just One Binary Relation

Yoshiki Nakamura

cs.LO math.LO ·submitted 2026-10-26 17:13 UTC · v1
publishedtheoryhighly cited

Abstract

The validity problem for first-order logic is a well-known undecidable problem. The undecidability also holds even for $\mathsf{FO}3$ and (equational formulas of) the calculus of relations. In this paper we tighten these undecidability results to the following: (1) $\mathsf{FO}3$ with just one binary relation is undecidable even without equality; and (2) the calculus of relations with just one character and with only composition, union, and complement is undecidable. Additionally we prove that the finite validity problem is also undecidable for the above two classes.

Comment
Long version of the paper at ICLA'19, with (Ax.1) and (Ax.2) in Section 3 corrected
DOI
10.1007/978-3-662-58771-3_11

Closest papers

Nearest neighbours by meaning across the whole index.

Finite Satisfiability of Two-Variable Logic with Arbitrarily Many Successors

cs.LO ·2026-10-14 ·Artur Jeż, Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.64
Abstract

We study finite satisfiability of two-variable first-order logic over structures equipped with an arbitrary finite number of independent successor relations of linear orders. The number of successor relations is part of the input, and the vocabulary may contain further unrestricted unary and binary relations. We prove decidability in deterministic doubly exponential space together with a triply exponential bound on the size of a smallest finite model. This settles the unrestricted finite case beyond two successors.

0.05

Decidability of Elementary Modal Logics is Undecidable

cs.LO ·2026-11-08 ·Jakub Michaliszyn
theory similarity 0.64
Abstract

We study the decidability of modal satisfiability over classes of Kripke frames defined by universal first-order sentences. Although some such classes yield undecidable satisfiability problems, decidability is guaranteed for wide families of frame conditions, including universal Horn sentences and universal sentences implying transitivity. A more than decade-old open problem asks a natural question: can decidable and undecidable cases be distinguished algorithmically? We prove that this is impossible, already for equality-free universal frame conditions over a single binary relation. More precisely, there is no algorithm that, given such a condition, decides whether its associated local modal satisfiability problem is decidable. We first establish the result for conditions with equality and then eliminate equality by passing to quotients of worlds with identical incoming and outgoing edges.

0.16

Two Variables and Two-Dimensional Structures

cs.LO ·2026-10-14 ·Bartosz Jan Bednarczyk, Daumantas Kojelis, Krzysztof Szymański
theory similarity 0.62
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

Two-Variable Logic with Arbitrarily Many Successor Relations

cs.LO ·2026-10-07 ·Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.61
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.50

An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations

cs.LO cs.CC ·2026-09-22 ·Yuya Uezato, Yoshiki Nakamura
theory similarity 0.61
Abstract · v2: Simplified the construction, streamlined the exposition, and added a subexponential circuit upper bound for fixed vocabularies and expon…

Three-variable first-order logic ($\mathrm{FO}^3$) and the calculus of relations (CoR) define the same binary queries, an equivalence that goes back to Tarski's work in the 1940s. The classical translation from $\mathrm{FO}^3$ to CoR is single-exponential, but it has remained open whether this blowup is necessary. We prove that it is, even over finite structures and even for circuits that share subterms. Our proof introduces a new technique: we modify a single finite structure in exponentially many local ways, each changing the answer of a short $\mathrm{FO}^3$ formula $\varphi$. In any CoR circuit $C$ equivalent to $\varphi$, only compositions of binary relations can notice these modifications, and each composition can notice at most two; thus, $C$ requires exponentially many compositions. The same technique gives an exponential succinctness gap between $\mathrm{FO}^3$ and $\mathrm{FO}^2$, and exponential lower bounds for matrix query languages over the Boolean and tropical semirings, where the analogous question was also open.

0.22

Undecidability of Reachability for Constraint Automata

cs.FL ·2026-10-11 ·Jakub Michaliszyn
theoryhot direction similarity 0.60
Abstract

We prove that reachability for constraint automata over finite binary words is undecidable. Eight registers suffice, with conjunctive guards using only equality, proper prefix, proper suffix, and infix incomparability, without word constants or concatenation. Finite-run nonemptiness, Buechi nonemptiness, and bounded Buechi nonemptiness are undecidable as consequences. For Boolean guards over equality, prefix, suffix, and prefix and suffix incomparability, Buechi nonemptiness is PSPACE-complete with arbitrarily many registers and word constants. The upper bound also allows positive infix atoms and yields PSPACE-completeness of prefix--suffix LTL satisfiability.

0.31

On existential Büchi arithmetic in two coprime bases

cs.LO cs.FL ·2026-08-25 ·Joris Nieuwveld
similarity 0.59
Abstract

For multiplicatively independent natural numbers $α$ and $β$, Villemaire showed in 1992 that the first-order theory of Presburger arithmetic expanded with both Büchi predicates $V_α$ and $V_β$ is undecidable, as it encodes multiplication. In recent years, Hieronymi and Schulz showed that Presburger arithmetic expanded with the weaker power predicates $α^\mathbb{N} = \{α^n: n \in \mathbb{N}\}$ and $β^\mathbb{N}$ is also undecidable, while Karimov et al. showed that the existential fragment of this theory is decidable. These results left open the natural problem of determining the decidability of the existential fragment of Villemaire's original expansion. We settle this question for coprime $α$ and $β$. Specifically, we give a quantifier-elimination argument that proves the decidability of the existential fragment of $\mathsf{FO}(\mathbb{Z};<,+, V_α, V_β)$.

0.45

Unary Functions, Automorphisms, and Unlabeled First-Order Model Counting

cs.LO cs.DM ·2026-08-31 ·Ondřej Kuželka
theory similarity 0.59
Abstract · fixed typos, 61 pages

Every fixed first-order sentence $\varphi$ determines an enumerative sequence $n\mapsto \mathrm{FOMC}(\varphi,n)$, counting its models on the labeled domain $[n]$. We study the complexity of these sequences when logical specifications may use genuine unary function symbols and hence nested terms such as $x,f(x),f^2(x),\ldots$. We prove that, for every fixed sentence $\varphi\in \mathrm{C}^1_{=}[f]$ with one unary function and an arbitrary finite relational vocabulary, $\mathrm{FOMC}(\varphi,n)$ is computable in time polynomial in $n$. By contrast, either a second variable or a second unary function yields hardness: there is a fixed sentence in $\mathrm{FO}^2_{=}[f]$ whose model-counting function is $\#\mathrm{P}_1$-complete, and there is a fixed constant-free universal sentence in $\mathrm{FO}^1_{=}[f,g]$, using only unary predicates besides $f$ and $g$, with the same property. We also relate labeled and unlabeled enumeration exactly. For every relational sentence $\varphi$, we construct an extension $\varphi_{\mathrm{aut}}$ in which a unary function records an automorphism and $\mathrm{FOMC}(\varphi_{\mathrm{aut}},n)=n! \cdot \mathrm{UFOMC}(\varphi,n)$, where $\mathrm{UFOMC}(\varphi,n)$ counts the $n$-element models of $\varphi$ up to isomorphism. This gives a one-query exact reduction from unlabeled to labeled model counting at the same domain size. If $\varphi$ belongs to $\mathrm{FO}^k_{=}$, respectively $\mathrm{C}^k$, and its relational vocabulary has maximum arity $r$, eliminating the auxiliary function yields a single-query reduction to labeled model counting in $\mathrm{FO}^{\max\{k,r+1\}}_{=}$, respectively $\mathrm{C}^{\max\{k,r+1\}}$.

0.19