github.com/ctlab/fbSAT ↗
Tool for automatic inference of minimal finite-state models of function blocks from execution scenarios and temporal properties
Open this visualization on its own page →
Contributors
1
Lines of Code
845
From
2019-01-18
To
2020-02-02
About ctlab/fbSAT
fbSAT is a research tool for automatically inferring minimal finite-state automaton models of function blocks from execution scenarios and temporal logic properties. The tool takes as input a set of execution traces and formal specifications, then synthesizes the smallest possible state machine that conforms to both the observed behavior and the specified properties. This is particularly useful in formal methods and hardware design where understanding or verifying system behavior requires deriving precise state machine models.
The tool provides multiple inference algorithms with varying computational strategies, including basic, extended, and modular approaches, as well as counterexample-guided synthesis (CEGIS) for iterative refinement. All algorithms are built on SAT solver technology, with flexible backend support for multiple solvers including MiniSat, Glucose, CryptoMiniSat, and CaDiCaL, either through native JNI bindings or external processes. The project includes special support for incremental SAT solving, which is crucial for the minimization and CEGIS algorithms that progressively tighten constraints.
Written in Kotlin, fbSAT is a JetBrains Research project that targets researchers and practitioners in formal verification, automated synthesis, and reactive systems. The tool exposes its functionality through a comprehensive command-line interface with numerous tuning options for automaton properties, guard formulas, and solver backends, making it suitable for both quick prototyping and detailed experimental evaluation of different synthesis strategies.