Constrained Horn clauses

Constrained Horn clauses (CHCs) are a fragment of first-order logic with applications to program verification and synthesis. Constrained Horn clauses can be seen as a form of constraint logic programming.

A constrained Horn clause is a formula of the form

${\displaystyle \phi \land P_{1}(\mathbf {x} _{1})\land \ldots \land P_{n}(\mathbf {x_{n}} )\to P(\mathbf {x} )}$

where ${\displaystyle \phi }$is a constraint in some first-order theory, ${\displaystyle P_{i}}$are predicates, and ${\displaystyle \mathbf {x} _{i}}$are universally-quantified variables. The addition of constraint makes it a generalization of the plain Horn clause.

The satisfiability of constrained Horn clauses with constraints from linear integer arithmetic is undecidable.

There are several automated solvers for CHCs, including the SPACER engine of Z3.

CHC-COMP is an annual competition of CHC solvers. CHC-COMP has run every year since 2018.

Constrained Horn clauses are a convenient language in which to specify problems in program verification. The SeaHorn verifier for LLVM represents verification conditions as constrained Horn clauses, as does the JayHorn verifier for Java.