Paperlane

no. 12 · Tuesday 10 November 2026

Exponential Lower Bounds for Horn Amalgamation

Jakub Rydval

math.LO · v3

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.

comments
The upper-bound claims in v2 have been withdrawn due to an error in the proof. This version focuses on the new lower bounds
fields
Logic
pdf ↗ page arXiv:2608.12206 ↗