Research map / Learning theory and algorithms / Combinatorial and search optimization
LTLf Synthesis Under Unreliable Input
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies LTLf reactive synthesis where a backup spec must hold under unreliable input variables, giving three techniques (direct automata, belief states, QLTLf/MSO) with complexity bounds and an empirical comparison.
Problem
Reactive synthesis for an LTLf main goal that must also guarantee an LTLf backup goal when certain environment input variables are unreliable, without relying on probabilities.
Approach
Formalizes LTLf synthesis under unreliable input as a brave main goal plus a cautious backup goal over all expansions of unreliable inputs, and solves it via synchronous product of a main automaton with a projected/belief automaton, or by encoding as QLTLf (forall over unreliable inputs) and translating to MSO via MONA.
Key results
- MSO-based technique performs best in solved instances and runtime, followed by belief-state construction and then direct automata manipulation.
- Direct automata approach solves only very small instances; hiker examples up to trail length 50 solved by MSO and belief-state approaches.
- Synthesis under unreliable input is shown 2EXPTIME-complete; belief-state technique is 3EXPTIME and QLTLf/MSO technique has non-elementary worst case via MONA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the MSO approach instead of direct automata manipulation | LTLf synthesis under unreliable input · benchmark suite | number of test cases solved within the time limit | Helped |
| use the belief-state approach instead of direct automata manipulation | LTLf synthesis under unreliable input · benchmark suite | number of test cases solved within the time limit | Helped |
| use the MSO approach instead of direct automata manipulation | LTLf synthesis under unreliable input · benchmark suite | runtime | Helped |
| use the MSO approach instead of belief-state construction | LTLf synthesis under unreliable input · benchmark suite | runtime | Helped |
| use projection instead of the MSO or belief-state approach | LTLf synthesis under unreliable input · Hiker | maximum trail length solved | Hurt |
| use the MSO approach instead of the full/partial-observability formula synthesis comparison | MSO synthesis technique · benchmark suite | runtime overhead: maximum 2.5x overhead | Hurt |
Surprising findings
- Theoretical worst-case bounds do not translate into observed performance: the MSO technique, with non-elementary worst case, performs best.
- Direct approach, despite optimal 2EXPTIME bound, solves the fewest instances, attributed to slow DFA construction for reversed languages.
Limitations
- Empirical evaluation limited to three synthetic example families (hiker, sheep, trap) with sizes limited by MONA timeouts (sheep n>10 timed out).
- Relies on MONA, which is non-elementary in worst case, so scalability is limited.
- Unreliability is modeled only on environment inputs in a non-probabilistic, worst-case way, so may be overly conservative.
Experimental setup
Benchmarks: hiker sheep trap
Metrics: runtime (seconds) number of instances solved within timeout
Baselines: direct automata construction belief-state construction
Builds on: LTLf synthesis via DFA games LTLf synthesis under partial observability QLTL Syft
Closest papers by meaning
- Adaptive Reactive Synthesis for LTL and LTLf Modulo Theories (AAAI 2024 · similarity 0.88)
- Foundations of Reactive Synthesis for Declarative Process Specifications (AAAI 2024 · similarity 0.85)
- LTLf Synthesis on First-Order Agent Programs in Nondeterministic Environments (AAAI 2025 · similarity 0.85)
- End-to-End Learning of LTLf Formulae by Faithful LTLf Encoding (AAAI 2024 · similarity 0.84)
- On the Expressive Power and Limitations of Multi-Layer SSMs (NeurIPS 2026 · similarity 0.84)
- Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks (NeurIPS 2025 · 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.