The Extended HOA Format for Synthesis

Guillermo A. PérezarXiv 2019 · OpenReview

Abstract

Reactive synthesis provides a framework for automatically generating correct-by-construction systems from formal specifications. While the Hanoi Omega-Automata (HOA) format has standardized the representation of infinite-word automata, it previously lacked the necessary metadata to describe the games essential for synthesis. This paper proposes a minimal extension to the HOA format—the controllable-AP header—to bridge the gap between automata translation and game-solving tools. We define the semantics of games played on these extended automata and discuss the integration of this format into the Reactive Synthesis Competition (SYNTCOMP).

1. Introduction

In formal methods, reactive synthesis represents a shift from verification to construction. Instead of manually developing a system and verifying it against a Linear Temporal Logic (LTL) specification, synthesis tools automatically derive a strategy that is guaranteed to satisfy the specification. This process typically involves two distinct phases: translating the LTL specification into an omega-automaton and solving a game played on that automaton.

The Hanoi Omega-Automata (HOA) format has been widely adopted as a standard for the output of the first phase. However, its original specification did not account for the game-theoretic requirements of the second phase. Specifically, it lacked a mechanism to distinguish between atomic propositions (APs) controlled by the system and those controlled by the environment.

The standard synthesis pipeline requires a clear demarcation of agency. In a game-theoretic context, the environment and the controller take turns or make simultaneous moves that determine the progression of the automaton. Without knowing which APs belong to which player, a game solver cannot determine if a winning strategy exists for the controller.

Historically, this lack of standardization forced researchers to develop monolithic tools or custom, ad-hoc formats to pass data between the translation and solving stages. This fragmentation hindered the comparison of different game-solving algorithms and slowed the development of modular synthesis engines.

3. The Proposed Extension: controllable-AP

To resolve this, we propose a minimal but impactful extension to the HOA format. The extension introduces a single new header item:

controllable-AP: INT*

This header is followed by a space-separated list of integer indices. These indices correspond to the atomic propositions defined in the AP: header that are under the control of the system (the "controller"). Any atomic proposition not explicitly listed in the controllable-AP header is implicitly assigned to the environment.

3.1 Game Semantics

By identifying controllable APs, a deterministic automaton is transformed into a formal game. The semantics are defined as follows:

  1. In each round, the environment chooses values for its variables.
  2. The controller, observing the environment's choice, chooses values for its variables.
  3. The automaton transitions to a new state based on the combined assignment of all APs.

The controller wins the game if the resulting infinite run satisfies the automaton's acceptance condition (e.g., Parity, Büchi, or Muller conditions).

4. Decoupling and Interoperability

One of the primary advantages of this extension is the decoupling of the synthesis pipeline. By standardizing the intermediate format, the community can optimize "LTL-to-automata" tools independently from "game-solving" tools. This allows for a "best-of-breed" approach where the most efficient translator can be paired with the most efficient solver.

For the output of the synthesis process—the strategy itself—the paper recommends the AIGER format. AIGER represents the strategy as a sequential circuit, ensuring that the synthesized results are compatible with existing hardware synthesis benchmarks and verification tools.

5. Tooling and Competition Integration

The utility of the extended HOA format was demonstrated through its integration into the 2020 Reactive Synthesis Competition (SYNTCOMP). For the "Synthesis from Automata" track, the competition focused on deterministic and complete parity automata.

To support this transition, the tool hoa2pg was developed. This utility transforms extended HOA files into the PGSolver format, enabling the use of a vast library of existing parity-game solvers. This bridge allows researchers to immediately apply state-of-the-art game-solving techniques to synthesis problems defined in HOA.

6. Limitations and Future Directions

While the extension is powerful, certain challenges remain:

  • Non-determinism: If the input automaton is non-deterministic, the resulting game is a Gale-and-Stewart game. Solving these requires either prior determinization or specialized algorithms that can handle non-determinism directly.
  • Strategy Extraction: While checking for realizability (the existence of a winning strategy) is straightforward via tools like hoa2pg, extracting a concrete, usable strategy in AIGER format from a parity game solver remains a complex task that requires further tool development.
  • Acceptance Conditions: The initial SYNTCOMP implementation focused on specific parity conditions. Future work will involve expanding tool support to handle the full expressive range of HOA's acceptance conditions.

7. Conclusion

The addition of the controllable-AP header to the HOA format provides the "missing link" for reactive synthesis. By enabling the description of games within a standardized automata format, this extension fosters interoperability, simplifies tool development, and provides a clear path forward for the synthesis community.

Summary updated

Abstract

We propose a small extension to the Hanoi Omega-Automata format to define reactive-synthesis problems. Namely, we add a "controllable-AP" header item specifying the subset of atomic propositions which is controllable. We describe the semantics of the new format and propose an output format for synthesized strategies. Finally, we also comment on tool support meant to encourage fast adoption of the extended Hanoi Omega-Automata format for synthesis.
BibTeX
@misc{perez2019extended,
  author = {Guillermo A. Pérez},
  title = {{The Extended HOA Format for Synthesis}},
  year = {2019},
  eprint = {1912.05793},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.05793},
}
Figure