Recursion Synthesis with Unrealizability Witnesses
summary
Procedure synthesizes recursive functions by combining syntax-guided synthesis with a new functional unrealizability checker that emits counterexample witnesses and drives predicate learning; predicates are synthesized by a SyGuS-style grammar over linear integer arithmetic. Implementation in the tool "induced" evaluates 140 benchmarks: a baseline symbolic CEGIS solves 70, adding the unrealizability checker proves 25 more unanalyzable cases, and the combined dual-loop algorithm solves 137 of 140 benchmarks, demonstrating practical scalability.
AI-written summary · about