Introduction: Bridging the Readability Gap
In reactive synthesis, the goal is to automatically build a system, such as a hardware controller, that is guaranteed to satisfy a mathematical specification—typically written in Linear-time Temporal Logic (LTL). While traditional tools are effective, they usually output Finite State Machines (FSMs). These FSMs represent logic as massive, flat graphs of states, making them nearly unreadable to human developers who rely on high-level structures like while loops and if-then-else blocks.
This research introduces the first "bounded synthesis" approach for generating actual imperative programs. By forcing the synthesis tool to use a specific programming grammar, the resulting output naturally inherits a human-readable structure while remaining mathematically correct.
Methodology: Automata vs. Direct Encoding
The authors propose two distinct methods to search for the smallest possible program that satisfies a given LTL specification:
- The Automata-Theoretic Approach: This method translates the LTL specification into a Two-Way Universal Co-Büchi Tree Automaton. This automaton "walks" up and down the syntax tree of a candidate program to verify its behavior. While mathematically elegant, this approach requires generalizing bounded synthesis theory to handle "two-way" transitions.
- The Direct (Two-Wayless) Encoding: Instead of complex intermediate automata, this method encodes the program's syntax and execution logic directly into Boolean constraints for a SAT solver. It uses an "inductive chain" to create shortcuts between input and output statements, effectively simulating program execution as logical jumps.
Key Insights and Results
The experiments showed a clear winner in terms of computational efficiency. The direct "Two-Wayless" encoding significantly outperformed the automata-based approach. For example, on a standard latch benchmark, the direct encoding finished in just 8 minutes and 7 seconds, while the automata approach took over 120 minutes.
Despite the performance difference, both methods successfully synthesized concise, structured code for benchmarks like the 2-bit arbiter. The "Two-Wayless" approach succeeds because it focuses on "InOut" behavior, calculating the effect of internal program steps (assignments, loops) as single logical jumps, which modern solvers can process much faster than the overhead-heavy two-way automata.
Limitations and Future Work
The current approach is limited to a simple imperative language using only Boolean variables. It does not yet support complex data types (integers, arrays) or recursive functions. Since synthesis is an EXPTIME-complete task, scaling to multi-thousand-line programs remains a challenge. Future work will explore expanding the supported syntax and using "syntax-guided" constraints to help solvers navigate even larger search spaces.
Summary updated