The paper tackles a fundamental question in mathematical logic: given a set of rules (a "universal first-order sentence") describing which finite structures are allowed, can you always "glue" two overlapping allowed structures together into a larger allowed structure that still satisfies the rules? This gluing property is called amalgamation, and deciding whether a given set of rules has it is generally very hard or even impossible. The authors focus on a special but important class of rule sets, called "semantic Horn," where any two allowed structures can be combined by taking their direct product and still get an allowed structure. This condition is a natural closure property that many practical logical theories satisfy.
The main result is that for this semantic Horn class, the amalgamation decision problem is actually solvable by an algorithm, and they pin down how computationally expensive that algorithm needs to be. The complexity is at most doubly exponential in general, and drops to singly exponential if the relations in the rules involve only a bounded number of arguments at a time. The key technical strategy is to reduce the amalgamation question to a "finite completion problem," asking whether partial structures can always be extended consistently. They then reformulate this as finding a graph homomorphism into a specially constructed template, and show that the semantic Horn assumption forces this template to have a useful algebraic property called a semilattice polymorphism, which guarantees that a local consistency check is sufficient to determine global solvability.
What makes this result notable is that amalgamation decidability was previously only well understood for binary relations, and extending it to relations of arbitrary arity has been a longstanding challenge. The semantic Horn assumption provides just enough algebraic structure to make the problem tractable without restricting the arity of the relations involved. The authors also point out that their approach generalizes beyond the Horn case: whenever the associated completion template happens to have "bounded width" in a technical sense, the same algorithm works. This suggests a broader program for identifying larger classes of logical theories where amalgamation can be decided algorithmically.