First-Order Quantified Separator in Alloy Analyzer

Abstract

First-Order Logic (FOL) is a powerful language for specifying system invariants and properties, yet its formal complexity often hinders its adoption. To address this, we present Folloy, a tool that synthesizes FOL specifications from examples. Our core contribution translates specification learning into a constraint satisfaction problem by declaratively modeling FOL syntax and semantics in the Alloy Analyzer. This method is expressive, allowing synthesis of non-prenex formulas and user-defined syntactic constraints. By leveraging a Max-SAT solver, Folloy also guarantees that the learned formula is minimal in size. We evaluate our tool on benchmark problems and show that while this general approach is slower than a specialized algorithm, it solves a broader class of problems, establishing a trade-off between performance and expressive power.