Assume-Guarantee Synthesis for Prompt Linear Temporal Logic

Nathanaël Fijalkow, Bastien Maubert, Aniello Murano, Moshe Y. VardiIJCAI 2020 · DOI

TL;DR

This paper tackles the long-standing challenge of synthesizing reactive systems that satisfy temporal properties with bounded waiting times. They introduce a novel algorithm for "assume-guarantee synthesis" for Prompt Linear Temporal Logic (Prompt-LTL), proving it's 2-EXPTIME-complete and providing a constructive method for generating such systems. This work bridges a decade-old gap in formal methods for real-time systems.

What Problem Does This Paper Address?

Formal verification and synthesis of reactive systems often rely on Linear Temporal Logic (LTL). However, standard LTL struggles to express requirements like "a request must be granted within a certain time frame." Prompt-LTL addresses this by introducing a "bounded eventually" operator (F≤B), allowing specifications like "eventually granted within B steps."

The problem arises when we want to synthesize a system (S) that satisfies a guarantee (ψ) given that its environment satisfies an assumption (φ). This is "assume-guarantee synthesis." For standard LTL, this is straightforward: if φ and ψ are LTL formulas, the problem is equivalent to synthesizing a system for the implication φ ⇒ ψ.

However, for Prompt-LTL, this equivalence breaks down. The issue is the implicit quantification over bounds. An assumption φ might hold for some bound b, and a guarantee ψ might need to hold for some bound b'. The standard LTL approach doesn't capture this crucial alternation of bounds. This has been an open problem for a decade. The authors refine this by considering "uniform" (system independent of bounds) and "non-uniform" (system can depend on bounds) variants, focusing on the latter as it's more tractable.

Methods

The authors propose an automata-theoretic approach, extending classical LTL synthesis techniques. The core steps are:

  1. Prompt Automata: They introduce "prompt automata," a type of cost automaton designed to capture Prompt-LTL formulas. These automata are essentially Büchi automata augmented with counters that can be incremented or reset, reflecting the bounded eventually operator. A key insight is that while prompt automata are powerful, they are not determinizable in the classical sense.
  2. History-Determinisation: To overcome the non-determinism issue, they develop a "history-determinisation" procedure. This technique transforms a non-deterministic prompt automaton into an equivalent "history-deterministic" one. Informally, a history-deterministic automaton's non-determinism can be resolved "on the fly" based on the input history, making it suitable for game-theoretic constructions. This is a significant technical contribution, extending previous work on finite words to infinite words for this specific class of automata.
  3. Domination Games: The synthesis problem is then translated into solving a "domination game." In this game, Adam (representing the environment) chooses inputs and transitions in the assumption automaton, while Eve (representing the system) chooses outputs and transitions in the guarantee automaton. The game is set up such that Eve wins if and only if she can ensure that whenever the assumption holds (with some bound), the guarantee also holds (with some potentially different bound). This game structure elegantly captures the assume-guarantee requirement with alternating bounds.

The overall complexity is shown to be 2-EXPTIME-complete, matching the complexity of classical LTL synthesis.

Datasets

Not discussed in the paper. The paper focuses on theoretical synthesis and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "Boundedness" Gap: The fundamental insight is that the simple implication (φ ⇒ ψ) doesn't work for Prompt-LTL assume-guarantee synthesis because it fails to capture the crucial alternation of existential quantifiers over bounds in the assumption and guarantee.
  • History-Determinisation as a Bridge: The development of history-determinisation for prompt automata is key. It allows them to leverage existing game-theoretic synthesis techniques, which typically require deterministic automata, by providing a functionally equivalent but more structured form.
  • Domination Games for Alternating Bounds: The formulation of the problem as a domination game is elegant. It provides a direct mechanism to model the interaction between an environment (Adam) and a system (Eve) where the success criteria involve bounded temporal properties and the bounds themselves can differ between the assumption and the guarantee.
  • 2-EXPTIME-Completeness: The result that the problem is 2-EXPTIME-complete is significant. It shows that adding bounded eventualities and assume-guarantee reasoning doesn't inherently increase the complexity beyond classical LTL synthesis, suggesting that these richer specifications are computationally feasible.

Key Results

  • Algorithm for Prompt-LTL Assume-Guarantee Synthesis: The paper presents a constructive algorithm for solving the assume-guarantee synthesis problem for Prompt-LTL.
  • 2-EXPTIME-Completeness: The authors prove that the assume-guarantee synthesis problem for Prompt-LTL is 2-EXPTIME-complete.
  • History-Deterministic Prompt Automata: They provide a method to construct history-deterministic prompt automata from non-deterministic ones, which is crucial for the subsequent game-theoretic steps.
  • Domination Game Equivalence: They establish an equivalence between the synthesis problem and the solvability of a constructed domination game.

Limitations and Future Work

  • Uniform vs. Non-Uniform Synthesis: The paper focuses on the "non-uniform" variant where the synthesized system can depend on the bound of the assumption. The authors leave the decidability of the "uniform" variant (where the system must work for all bounds without depending on them) as an open question. This is related to whether prompt automata can be made history-deterministic in a uniform way.
  • Complexity: While the 2-EXPTIME complexity is established, it's still high. Future work might explore optimizations or subclasses of Prompt-LTL that admit lower complexity.
  • Practical Implementation: The paper provides a theoretical framework. Translating this into practical synthesis tools would be a valuable next step.
  • Generalization of History-Determinisation: The history-determinisation procedure is presented for prompt automata, a subclass of cost automata. Extending this to more general cost automata remains an open problem.

Summary updated

BibTeX
@inproceedings{fijalkow2020assume,
  author = {Nathanaël Fijalkow and Bastien Maubert and Aniello Murano and Moshe Y. Vardi},
  title = {{Assume-Guarantee Synthesis for Prompt Linear Temporal Logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/17},
}

Loading related content...

Figure