Optimal CHC Solving via Termination Proofs
summary
Presents a new optimality checker that reduces CHC maximality to program termination, encodes termination-argument synthesis (angelic strategy and ranking-function generation) as constraint solving, and implements a prototype that iteratively refines solutions. Evaluated on CHCs encoding maximal-specification synthesis, the tool finds optimal solutions for a similar number of benchmarks as prior work while flagging unsoundness in that tool; authors validate 47/50 validated solutions and report two incorrect optima from the competitor.
AI-written summary · about