Deciding Amalgamation Beyond Arity Two: The Semantic Horn Case
We study the amalgamation decision problem (ADP): given a universal first-order sentence $Φ$, decide whether the class $\mathrm{fm}(Φ)$ of its finite models has the amalgamation property. We call $Φ$ semantic Horn if $\mathrm{fm}(Φ)$ is closed under binary direct products. By McKinsey's theorem, this is equivalent to $Φ$ being logically equivalent to a universal Horn sentence. The distinction concerns the input representation: $Φ$ itself need not be given in Horn form, and converting it into an explicit Horn normal form can incur an exponential blow-up. We prove that the ADP is decidable…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.12206
curl -X POST /api/v1/records/arxiv/2608.12206/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.12206/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'