Research map / Architectures and efficiency / RNNs and normalization
Decompositions in Compositional Translation of LTLf to DFA (Student Abstract)
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.
Proposes restructuring the LTLf abstract syntax tree via syntactic-equivalence rules before compositional DFA construction, reducing the number of automata composition operations and improving translation to DFA (tool Swift vs Lisa and Lydia).
Problem
Compositional LTLf-to-DFA translation performs many costly DFA compositions along the syntax tree; prior work optimized only the composition phase, so the number of compositions for a formula remains high.
Approach
Rewrite the formula's AST into a semantically equivalent AST with fewer edges (e.g., factoring a common disjunct out of a conjunction of disjunctions) via bottom-up traversal with syntactic-equivalence rules, as a preprocessing step to the decomposition phase.
Key results
- Swift shows substantial runtime improvement over Lisa and Lydia on SYNTCOMP nim benchmarks.
- On counter benchmarks Swift is substantially faster than Lisa-Explicit and comparable to Lydia, and solves more benchmarks than Lydia due to lower memory usage.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce AST edges and composition operations through equivalent AST preprocessing | LTLf-to-DFA translation with Swift · SYNTCOMP 2023 Nim benchmarks | runtime | Helped |
| Reduce AST edges and composition operations through equivalent AST preprocessing | LTLf-to-DFA translation with Swift · SYNTCOMP 2023 single- and double-counter benchmarks | runtime | Helped |
| Reduce AST edges and composition operations through equivalent AST preprocessing | LTLf-to-DFA translation with Swift · SYNTCOMP 2023 single- and double-counter benchmarks | benchmarks solved | Helped |
| Reduce AST edges and composition operations through equivalent AST preprocessing | LTLf-to-DFA translation with Swift · SYNTCOMP 2023 benchmarks | memory usage | Helped |
Limitations
- Preprocessing rewriting is applied offline before decomposition and is not on-the-fly; the paper notes this as future work.
- Evaluation is limited to SYNTCOMP 2023 LTLf synthesis benchmarks on a modest system (dual-core, 4GB RAM).
- No theoretical guarantee that the resulting AST is minimal.
Experimental setup
Datasets: SYNTCOMP 2023 LTLf synthesis track benchmarks
Benchmarks: SYNTCOMP 2023 LTLf synthesis track (nim, single- and double-counter)
Metrics: runtime number of benchmarks solved memory usage
Baselines: Lisa Lisa-Explicit Lydia
Builds on: Lisa Lydia MONA
Closest papers by meaning
- How Do Language Models Compose Functions? (NeurIPS 2026 · similarity 0.81)
- Limits of Transformer Language Models on Learning to Compose Algorithms (NeurIPS 2024 · similarity 0.80)
- End-to-End Learning of LTLf Formulae by Faithful LTLf Encoding (AAAI 2024 · similarity 0.80)
- LLM Augmented LLMs: Expanding Capabilities through Composition (ICLR 2024 · similarity 0.80)
- Facilitating Multi-turn Function Calling for LLMs via Compositional Instruction Tuning (ICLR 2025 · similarity 0.79)
- LTLf Synthesis Under Unreliable Input (AAAI 2025 · similarity 0.79)
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.