Finite LTL Synthesis is EXPTIME-complete

Christian MuisearXiv 2016 · arXiv

TL;DR

This paper revisits the complexity of synthesizing reactive systems from specifications written in Linear Temporal Logic (LTL) interpreted over finite traces (LTLf). Contrary to previous claims of 2EXPTIME-completeness, the authors prove that LTLf synthesis is actually EXPTIME-complete. This result is significant because it tightens the complexity bound and aligns LTLf synthesis with the complexity of non-deterministic planning with full observability.

What Problem Does This Paper Address?

The synthesis problem, a cornerstone of computer science, aims to automatically construct a system (a "reactive module") that satisfies a given logical specification. When the specification is expressed in Linear Temporal Logic (LTL), the problem of finding such a module has been known to be computationally expensive. Specifically, for LTL interpreted over infinite traces, the synthesis problem is 2EXPTIME-complete.

This paper focuses on a variant of LTL called finite LTL (LTLf), which is interpreted over finite traces. LTLf is particularly relevant in domains like automated planning and controller synthesis where finite execution paths are common. While LTLf synthesis was also previously believed to be 2EXPTIME-complete, this paper challenges that assumption. The authors aim to provide a more precise complexity characterization for LTLf synthesis, specifically demonstrating that it is EXPTIME-complete. This refinement is important for understanding the practical tractability of synthesizing systems with finite-trace specifications.

Methods

The paper's core contribution lies in establishing the EXPTIME-completeness of LTLf synthesis. This is achieved through a two-part proof:

  1. Membership in EXPTIME (Lemma 1): The authors present an algorithm for deciding LTLf realizability (whether a specification can be satisfied). This algorithm is based on a technique for compiling LTLf formulas into alternating automata. They show that this procedure can be executed by an alternating Turing machine (ATM) with polynomial space. Since APSPACE (the class of problems solvable by ATMs in polynomial space) is known to be equal to EXPTIME, this establishes that LTLf realizability is in EXPTIME.
  2. EXPTIME-hardness (Lemma 2): To prove that LTLf synthesis is EXPTIME-hard, the authors introduce a polynomial-time transformation from a given Alternating Turing Machine (ATM) with a polynomial space bound to an LTLf synthesis specification. They demonstrate a one-to-one correspondence between accepting computation trees of the ATM and solutions to the synthesized LTLf problem. This reduction shows that any problem solvable by an ATM with a polynomial space bound can be reduced to LTLf synthesis, thus proving its EXPTIME-hardness.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Tightening Complexity: The most significant insight is the correction of the previously held belief that LTLf synthesis is 2EXPTIME-complete. The paper establishes that it is, in fact, EXPTIME-complete. This is a crucial refinement for understanding the computational landscape of temporal logic synthesis.
  • Connection to Planning: The result aligns LTLf synthesis with the complexity of non-deterministic planning with full observability (which is EXPTIME-complete). This strengthens the analogy between planning and synthesis, especially when considering different levels of observability.
  • Leveraging Alternating Automata: The proof for LTLf realizability in EXPTIME relies on a construction of alternating automata, highlighting the power of these models in analyzing temporal logic specifications.
  • ATM to LTLf Transformation: The EXPTIME-hardness proof ingeniously transforms an ATM computation into an LTLf specification. This demonstrates a powerful technique for establishing lower bounds by reducing problems from computational models to logical synthesis problems.

Key Results

  • LTLf Synthesis is EXPTIME-complete: The paper formally proves that the LTLf synthesis problem is EXPTIME-complete. This is the central result.
  • LTLf Realizability is in EXPTIME: Lemma 1 shows that deciding if an LTLf formula is realizable can be done in EXPTIME.
  • LTLf Synthesis is EXPTIME-hard: Lemma 2 establishes that LTLf synthesis is at least as hard as problems solvable by ATMs with polynomial space bounds, thus proving EXPTIME-hardness.

Limitations and Future Work

  • Focus on Full Observability: The paper's primary result concerns LTLf synthesis under the assumption of full observability, aligning it with non-deterministic planning with full observability. The authors note that LTLf synthesis with partial observability is 2EXPTIME-complete, a result recently reported elsewhere. Future work could explore the nuances and specific complexity classes for various levels of observability in LTLf synthesis.
  • Practical Algorithms: While the paper establishes theoretical complexity bounds, the development of efficient, practical algorithms for LTLf synthesis remains an area of active research. The authors mention that their work leverages recent advances in alternating automata and automated planning, suggesting that further exploration in these areas could lead to more efficient synthesis techniques.
  • Broader Applications: The paper highlights the relevance of LTLf synthesis in areas like automated planning and finite controller applications. Future work could explore specific applications and case studies where this refined complexity understanding can guide the design and implementation of synthesized systems.

Summary updated

BibTeX
@misc{muise2016finite,
  author = {Christian Muise},
  title = {{Finite LTL Synthesis is EXPTIME-complete}},
  year = {2016},
  eprint = {1609.04371},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1609.04371},
}
Figure