Multiple Query Satisfiability of Constrained Horn Clauses
summary
A sound and complete equisatisfiable transformation rewrites a CHC set with multiple queries so each output query incorporates constraints from the others, letting solvers exploit interdependencies rather than modeling predicates independently. It targets ADTs (lists, trees) and requires properties expressed as catamorphisms, which guarantees termination of the transformation. Evaluation on a benchmark of 170 programs, 470 queries (sorting, permutations, BST ops) shows the pipeline plus Z3-based solving raises successful satisfiability proofs versus baseline Spacer, with moderate translation overhead.
AI-written summary · about