Research map / Large language models / Reasoning and chain of thought
Hybrid Compositional Reasoning for Reactive Synthesis from Finite-Horizon Specifications
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Combine explicit-state minimization on smaller intermediate DFAs with symbolic-state composition after a size threshold | LTLf-to-DFA construction · 454 DFA-construction benchmarks | benchmarks solved: 338 -> 372 | Helped |
| Use hybrid rather than purely explicit-state composition | LTLf-to-DFA construction · 454 DFA-construction benchmarks | benchmarks solved: 307 -> 372 | Helped |
| Use hybrid DFA construction instead of the Mona-based conversion | LTLf synthesis · Single counter, 10 bits | total runtime (seconds): 40.4535 -> 9.31808 | Helped |
| Use hybrid DFA construction instead of the Mona-based conversion | LTLf synthesis · Double counters, 7 bits | total runtime (seconds): 1885.67 -> 80.9725 | Helped |
| Use hybrid DFA construction instead of the Mona-based conversion | LTLf synthesis · Nim, 3 heaps and 4 tokens per heap | benchmarks solved | Helped |
| Replace hybrid composition with purely explicit-state composition (ablation) | Lisa · 454 DFA-construction benchmarks | benchmarks solved: 372 -> 338 | Hurt |
| Replace hybrid composition with purely symbolic-state composition (ablation) | Lisa · Realistic benchmarks | benchmarks solved | Hurt |
| Minimize intermediate DFAs only while they are explicit | Lisa · LTLf-to-DFA conversion | state-space size | Helped |
| Use dynamic smallest-first selection when composing DFAs | Lisa · Large-minimal-DFA benchmarks | benchmarks solved | Helped |
| Switch to symbolic representation as soon as explicit composition becomes prohibitive | Lisa · Double-counter benchmarks | state-space size | Helped |
| Use dynamic rather than static variable ordering (ablation) | Syft · LTLf synthesis | runtime: up to 75% | Helped |
| Increase the number of counter bits | Winning-set computation · Single- and double-counter benchmarks | fixed-point iterations: 2^i; 2^{i+1}-2 | Hurt |
Closest papers by meaning
- Foundations of Reactive Synthesis for Declarative Process Specifications (AAAI 2024 · similarity 0.89)
- Adaptive Reactive Synthesis for LTL and LTLf Modulo Theories (AAAI 2024 · similarity 0.88)
- LTLf Synthesis Under Unreliable Input (AAAI 2025 · similarity 0.88)
- Decompositions in Compositional Translation of LTLf to DFA (Student Abstract) (AAAI 2024 · similarity 0.86)
- On the Expressiveness and Length Generalization of Selective State Space Models on Regular Languages (AAAI 2025 · similarity 0.84)
- End-to-End Learning of LTLf Formulae by Faithful LTLf Encoding (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.