# Hybrid Compositional Reasoning for Reactive Synthesis from Finite-Horizon Specifications

arXiv: https://arxiv.org/abs/1911.08145 · HTML: https://mlsanity.com/paper/1911.08145/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2019.

## Built on by (most cited first, 16 of 16)

- [Neuro-Symbolic Predictive Process Monitoring](https://mlsanity.com/paper/2509.00834/) (2025)
- [Forward LTLf Synthesis: DPLL At Work](https://mlsanity.com/paper/2302.13825/) (2023)
- [LTLf+ and PPLTL+: Extending LTLf and PPLTL to Infinite Traces](https://mlsanity.com/paper/2411.09366/) (2024)
- [Model Checking Strategies from Synthesis Over Finite Traces](https://mlsanity.com/paper/2305.08319/) (2023)
- [Act for Your Duties but Maintain Your Rights](https://mlsanity.com/paper/2302.03384/) (2023)
- [LTLf Best-Effort Synthesis in Nondeterministic Planning Domains](https://mlsanity.com/paper/2308.15188/) (2023)
- [Emerson-Lei and Manna-Pnueli Games for LTLf+ and PPLTL+ Synthesis](https://mlsanity.com/paper/2508.14725/) (2025)
- [On Satisficing in Quantitative Games](https://mlsanity.com/paper/2101.02594/) (2021)
- [Symbolic Synthesis for LTLf+ Obligations](https://mlsanity.com/paper/2604.18532/) (2026)
- [Mimicking Behaviors in Separated Domains](https://mlsanity.com/paper/2205.09201/) (2022)
- [Symbolic LTLf Best-Effort Synthesis](https://mlsanity.com/paper/2308.15178/) (2023)
- [On-the-fly Synthesis for LTL over Finite Traces: An Efficient Approach that Counts](https://mlsanity.com/paper/2408.07324/) (2024)
- [A Compositional Framework for On-the-Fly LTLf Synthesis](https://mlsanity.com/paper/2508.04116/) (2025)
- [DeepDFA: Injecting Temporal Logic in Deep Learning for Sequential Subsymbolic Applications](https://mlsanity.com/paper/2602.03486/) (2026)
- [Incremental LTLf Synthesis](https://mlsanity.com/paper/2603.01201/) (2026)
- [Infinite Trace Objectives with Finite Trace Techniques: Translating LTL to LTLf+](https://mlsanity.com/paper/2608.02454/) (2026)

## Abstract (arXiv)

LTLf synthesis is the automated construction of a reactive system from a high-level description, expressed in LTLf, of its finite-horizon behavior. So far, the conversion of LTLf formulas to deterministic finite-state automata (DFAs) has been identified as the primary bottleneck to the scalabity of synthesis. Recent investigations have also shown that the size of the DFA state space plays a critical role in synthesis as well. Therefore, effective resolution of the bottleneck for synthesis requires the conversion to be time and memory performant, and prevent state-space explosion. Current conversion approaches, however, which are based either on explicit-state representation or symbolic-state representation, fail to address these necessities adequately at scale: Explicit-state approaches generate minimal DFA but are slow due to expensive DFA minimization. Symbolic-state representations can be succinct, but due to the lack of DFA minimization they generate such large state spaces that even their symbolic representations cannot compensate for the blow-up. This work proposes a hybrid representation approach for the conversion. Our approach utilizes both explicit and symbolic representations of the state-space, and effectively leverages their complementary strengths. In doing so, we offer an LTLf to DFA conversion technique that addresses all three necessities, hence resolving the bottleneck. A comprehensive empirical evaluation on conversion and synthesis benchmarks supports the merits of our hybrid approach.