CS Paper Radar

Exponential Lower Bounds for Horn Amalgamation

Jakub Rydval

cs.LO math.LO ·submitted 2026-08-12 16:01 UTC · v3
theory

Abstract

The amalgamation decision problem asks whether the finite models of a given universal first-order sentence have the amalgamation property. We prove that this problem is ExpTime-hard for universal Horn sentences of maximum relation arity three, and 2ExpTime-hard when the arity is unbounded, thereby strengthening the previous best lower bounds for universal Horn sentences. The first reduction simulates runs of nondeterministic tree automata using a single ternary relation and unary and binary auxiliary relations. The second simulates finite winning strategies in an exponential corridor game. As a secondary contribution, we prove that deciding the winner remains 2ExpTime-complete for the game normal form used in our reduction, in which each move label determines a unique legal successor from every non-winning legal row.

Comment
The upper-bound claims in v2 have been withdrawn due to an error in the proof. This version focuses on the new lower bounds

Closest papers

Nearest neighbours by meaning across the whole index.

Automata for MSO over Infinite Trees with Quantification over Borel Sets of Branches

cs.FL cs.LO ·2026-11-06 ·Mikołaj Bojańczyk, Antonio Casares, Sven Manthe, Paweł Parys
top venuetheory similarity 0.62
Abstract

Rabin's Tree Theorem says that the MSO theory of the infinite binary tree $2^*$ is decidable. Shelah showed that MSO logic becomes undecidable if this tree is extended to $2^{\le ω}$, i.e. by allowing quantification over sets of infinite branches. A longstanding open problem is whether the decidability can be recovered in $2^{\le ω}$ by restricting set quantification to Borel sets. We make some progress in this direction, by identifying a suitable automaton model, and showing that most of the automata-theoretic approach to Rabin's Theorem can be extended to the new framework. The only missing part is a conjecture about finite-memory determinacy in certain games. This paper states and explores the conjecture. We prove it in some restricted cases, and give lower bounds on the memory required in those games.

0.70

Two-Variable Logic with Arbitrarily Many Successor Relations

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

Finite Satisfiability of Two-Variable Logic with Arbitrarily Many Successors

cs.LO ·2026-10-14 ·Artur Jeż, Jakub Michaliszyn, Piotr Witkowski
theory similarity 0.56
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

Causal Resolution of Undefined Answers in Datalog with Negation

cs.DB ·2026-11-09 ·Ratan Bahadur Thapa
similarity 0.56
Abstract

Unstratified negation may leave the answer to a Boolean Datalog query undefined under the well-founded semantics. We study database causality in this setting by asking which fact insertions and deletions realize a prescribed transition and which other changes preserve the observed query answer while making a designated fact pivotal. Such a set of changes to other facts is a contingency for the designated fact and the prescribed transition. Our game representation assigns one shared move to each mutable fact and preserves query values and intervention distances. Pairing source and target certificates characterizes all minimum contingencies for the six transitions among true, false, and undefined. When inserting or deleting a move resolves a draw, a directed tree traces the newly winning and losing positions along alternating paths to the source of that move. For the fixed one-rule win--move program, deciding whether a contingency of size at most $k$ exists is $\mathrm{NP}$-complete for each transition, even on bounded-degree graphs. Computing the minimum size is $\mathrm{FP}^{\mathrm{NP}[\log]}$-complete, and counting minimum contingencies is $\#\mathrm{P}$-hard under polynomial-time Turing reductions. When only one of true and false is reachable, the prime implicants of undefinedness satisfied at the observation cover every undefined state, and their supports induce nonempty subtrees of a common tree, we compute a minimum resolving intervention in polynomial time from the game instance. From the explicit tree and these implicants, we construct an equally large family of disjoint supports, certifying optimality.

0.25

Solving Streett and Emerson-Lei Games with Universal Trees

cs.GT cs.LO ·2026-08-17 ·Daniel Hausmann, Marcin Jurdzinski, Nir Piterman
similarity 0.55
Abstract

Nearly a decade ago, Calude et al. showed that parity games can be solved in quasi-polynomial time. This result is now understood in terms of universal trees. By reduction to parity games, the quasi-polymonial result can benefit all omega-regular games. However, beyond such reductions, and with the exception of Rabin games, our understanding of the role of universal trees in direct solutions is still quite limited. In this work, we refute the common view that universal trees are relevant only for games that admit memoryless winning strategies. We contribute a full understanding of how universal trees interact with Zielonka trees for the solution of Streett and Emerson-Lei games. As a consequence, we show that winning regions and strategies in Streett games with $n$ vertices, $m$ edges, and $k$ pairs can be computed in time $O(mk\log(k)k!|U(n,k)|)$, where $U(n,k)$ is a universal tree for $n$ leaves and depth $k$. This improves upon the best previously known complexity result for Streett games, which relied on reduction to parity games and their quasi-polynomial solution. Furthermore, we show that winning regions and strategies for Emerson-Lei games with $n$ vertices, $m$ edges, and $c$ colors can be computed in time $O(mc\log(c)c!|U(n,c/2)|)$, again improving over reductions to parity games. Notably, our approach yields memory-optimal strategies, in contrast to those obtained via reductions to parity games. Finally, we show how universal trees can be used to bound the recursion tree of the Zielonka-McNaughton algorithm for Emerson-Lei games. This leads to a symbolic algorithm that replaces the factor $n^c$ in the time complexity of existing symbolic approaches with $|U(n,c)|$.

0.18

Decreasing Diagrams are Complete for Confluence

cs.LO ·2026-10-05 ·Jörg Endrullis, Ievgen Ivanov, Femke van Raamsdonk
theory similarity 0.55
Abstract

Confluence is a fundamental property of nondeterministic computations, arising from parallelism, concurrency, or freedom in the evaluation order. It guarantees that such a computation always yields the same result, regardless of the order in which steps are taken. The decreasing diagrams technique of van Oostrom is one of the most versatile methods for establishing confluence of transition systems (abstract rewriting systems). It reduces global confluence to local confluence: a system is confluent whenever its transitions admit a locally decreasing labeling. Essentially all classical confluence criteria arise as corollaries. A central question, posed by van Oostrom in 1993, asks whether the decreasing diagrams technique is complete: Does every confluent transition system admit a locally decreasing labeling? This is Problem 56 of the RTA List of Open Problems. A positive answer was known only for countable systems, and recently up to the first uncountable cardinal $\aleph_1$. The general case remained open. We settle this thirty-three-year-old problem in full. We prove that every confluent transition system admits a locally decreasing labeling using only three labels. This bound is optimal, as two labels do not suffice even at the first uncountable cardinality. It follows that this single criterion can, in principle, certify the confluence of every confluent system, and hence of every confluent program. The entire development is machine-checked in the Isabelle/HOL and Lean proof assistants and relies only on classical logic and the axiom of choice.

0.23

The Lattice of Coalition Logics between MCL and CL: Coatoms and Compact Meets

cs.LO math.LO ·2026-10-17 ·Shanxia Wang, Yuqiang Dou
similarity 0.55
Abstract · 19 pages, one table; supplementary finite-checking Python program in ancillary files

For a fixed finite set $N$ of at least two agents, we investigate the lattice $L_N$ of coalition logics between minimal coalition logic (MCL) and classical coalition logic (CL), with extensions required to be structural. This lattice is order-dual to an interval in the subvariety lattice of Boolean coalition algebras. The eight basic extensions obtained by imposing seriality, independence of agents, and determinism form a Boolean cube under inclusion, but not a sublattice of $L_N$. Our main results concern coatoms and compact meets. First, finite critical coalition algebras, realized as complex algebras of finite general concurrent games, yield three infinite families of pairwise distinct coatoms containing seriality, distinguished by failures of independence, determinism, or both. An explicit splitting characterizes the unique coatom omitting seriality. Second, the meet of two basic extensions is compact if and only if the extensions are comparable. For incomparable pairs, no axiomatization of the meet can use formulas of uniformly bounded modal depth, even with infinitely many axioms. Consequently, $L_N$ and three natural principal intervals are non-coherent algebraic lattices. These results reveal lattice-theoretic phenomena beyond the inclusion order of the eight basic extensions.

0.28

Rabin Games Revisited

cs.FL ·2026-10-11 ·Antonio Di Stasio, Moshe Y. Vardi
published similarity 0.54
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898

Rabin games have their roots in Michael Rabin's seminal work on automata over infinite trees and form a classical model for infinite-round games with ω-regular winning conditions. They play a central role in automata theory and temporal synthesis: translating an LTL specification into an equivalent deterministic Rabin automaton reduces synthesis to solving a Rabin game. In practice, however, Rabin games are typically solved indirectly, via parity games. One possible reason is that many direct algorithms have a factorial dependence on the Rabin index k, the number of Rabin pairs. In this work, we revisit Rabin's 1972 recursive algorithm. The algorithm is implicit in Rabin's proof and intertwined with finite-state determinacy. First, we "excavate" it as an explicit arena-based solver using standard reachability- and Büchi-game solving as basic building blocks, thus avoiding the exponential dependence on the alphabet in Rabin's original presentation. Second, we show that memoization removes the factorial term from the recursion-tree analysis. Finally, we introduce a variation that recurses on the Rabin index. These results provide a modern analysis of Rabin's recursive method and a basis for studying direct Rabin-game solvers for temporal synthesis.

0.37