💻 computer science

A Theory of Hanoi Omega-Automata and Games

This paper provides the first systematic investigation into the theoretical complexity of Hanoi Omega-Automata (HOA) and the newly formalized Hanoi Omega-Games (HOG), establishing that their symbolic encoding via Boolean transition guards elevates standard decision problems like non-emptiness and language inclusion to NP-complete and PSPACE/EXPSPACE-complete levels, respectively, while deriving tight complexity bounds for solving games under various acceptance conditions.

Original authors: Emmanuel Filiot, Allen Joseph, Guillermo A. Pérez, Saina Sunny

Published 2026-04-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Emmanuel Filiot, Allen Joseph, Guillermo A. Pérez, Saina Sunny

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a very sophisticated robot that needs to follow a set of rules forever. To tell the robot what to do, you don't write out a giant list of every single possible situation it might face (which would be impossible because there are infinite situations). Instead, you write a smart, compact rulebook using logic puzzles (Boolean formulas).

This paper is about analyzing the "Hanoi Omega-Automata" (HOA) format, which is the industry standard for writing these compact rulebooks. The authors asked a simple question: "How hard is it for a computer to check if these rulebooks actually work?"

Here is the breakdown of their findings using everyday analogies:

1. The "Magic Door" Problem (Non-Emptiness)

The Scenario: Imagine a maze with millions of doors. Each door has a sign with a logic puzzle on it (e.g., "Open if it is raining AND you have an umbrella"). You want to know: Is there at least one path through this maze that never gets stuck?

The Old Way: In traditional formats, the maze was drawn out with every single door listed. Checking if a path exists was relatively straightforward.

The HOA Way: In HOA, the doors are grouped by their logic puzzles. One sign might cover thousands of doors at once.
The Finding: The authors discovered that because these logic puzzles are so powerful, checking if a path exists is actually quite hard. It falls into a category called NP-complete.

Analogy: It's like being given a massive lock with a complex combination. You can't just look at it and see if it opens; you have to try different combinations. If you guess the right one, you can prove it works quickly, but finding that right combination in the first place is a tough job.

2. The "Copycat" Problem (Language Inclusion)

The Scenario: You have two robots. Robot A follows Rulebook A, and Robot B follows Rulebook B. You want to know: Does Robot B do everything Robot A does, and maybe more? (i.e., Is Robot A's behavior completely contained within Robot B's?)

The Finding:

For most rulebooks, this is PSPACE-complete.
- Analogy: This is like trying to memorize a library of books to see if one book is a subset of another. You don't need a super-computer, but you need a lot of scratch paper (memory) to keep track of the comparisons.
The Twist: For the most complex type of rulebook (Emerson-Lei), the problem jumps to EXPSPACE-complete.
- Analogy: This is like trying to compare two libraries where the books are written in a language that requires you to write a new book for every single letter in the alphabet just to understand the first sentence. The amount of memory needed explodes so fast that even the biggest supercomputers would run out of space.

3. The "Game of Strategy" (Hanoi Omega-Games)

The Scenario: Now, imagine the maze is a game between two players: The Controller (who wants the robot to succeed) and The Environment (who wants to trick the robot). They take turns making choices. The Controller wins if they can force the robot to follow the rules no matter what tricks the Environment plays.

The Finding:

For standard rules (like "visit this room infinitely often"), the game is $\Pi_2$ -complete.
- Analogy: This is a "For all, there exists" game. The Controller must say, "For every move the Environment makes, there exists a counter-move I can make to win." It's a two-layered thinking process that is harder than a simple game of chess but not quite as impossible as the hardest math problems.
For the most complex rules (Emerson-Lei), the difficulty drops back to PSPACE-complete.
- Analogy: Surprisingly, the most complex rules actually make the game easier to solve in terms of memory than the "middle-tier" complex rules. It's like how a very strict, rigid set of rules in a board game can sometimes make the strategy simpler because there are fewer loopholes to exploit.

4. The "Universal Translator" (Symbolic Games)

The Scenario: The authors realized their methods for solving these logic-maze games could be generalized. Instead of just Boolean logic (True/False), you could use rules about numbers, time, or other data types.

The Finding: They showed that as long as you can solve the underlying logic puzzles (the "satisfiability" problem), you can solve the game.

Analogy: They built a universal translator. If you can teach a computer to solve the basic logic puzzles (like "Is 5 greater than 3?"), then that same computer can figure out the winning strategy for the robot game, even if the rules involve complex math.

Summary

The paper reveals that while the HOA format is great for saving space (it's a very efficient way to write rules), this efficiency comes with a hidden cost: it makes the math behind checking those rules significantly harder.

Checking if a path exists: Hard (NP).
Comparing two rulebooks: Very Hard (PSPACE) to Extremely Hard (EXPSPACE).
Playing the strategy game: Hard (P2) to Very Hard (PSPACE), depending on the rules.

The authors didn't just find these difficulties; they provided the exact "complexity map" (the mathematical boundaries) for how hard these problems are, which helps tool builders know what to expect when they try to automate these systems.

1. Problem Statement

The paper addresses a significant gap in the theoretical understanding of Hanoi Omega-Automata (HOA) and Hanoi Omega-Games (HOG).

Context: HOA has become the de facto standard format for encoding $\omega$ -regular automata in modern synthesis tools (e.g., Spot, Owl, LTL3TELA) and competitions (SYNTCOMP). It uses symbolic transitions (Boolean formulas over atomic propositions) and transition-based acceptance (colors on transitions rather than states).
The Gap: While widely used, the exact computational complexity of decision problems (emptiness, language inclusion) and game-solving for HOA-encoded structures was unknown. Standard complexity results for classical automata (where transitions are labeled by single symbols) do not directly apply due to the succinctness of the Boolean encoding.
Core Question: How do the structural features of HOA (symbolic alphabets, transition-based coloring) affect the complexity of classical automata-theoretic problems and reactive synthesis games?

2. Methodology

The authors employ a combination of automata theory, game theory, and complexity analysis:

Reduction to State-Based Models: They first establish that any HOA can be converted into an equivalent state-based HOA (where colors depend only on the source state) with only a quadratic blow-up in size. This allows them to leverage properties of state-based systems.
Small Lasso Property: They prove that for HOA, if an accepting run exists, there exists a "lasso-shaped" run (a finite prefix followed by a finite cycle) of polynomially bounded size that preserves the set of colors occurring finitely and infinitely often. This is crucial for establishing upper bounds in non-deterministic complexity classes.
Symbolic Game Reduction: For games, they define a reduction from a symbolic HOG to a classical turn-based game ( $P_G$ $P_{G}$ ). In this reduction:
- Player In's moves correspond to choosing a valuation for input propositions.
- Player Out's moves correspond to choosing a subset of states (the "q-good" sets) that Player In can force the system into.
- This reduction transforms the symbolic game into a classical game with an exponentially larger arena, allowing the application of classical determinacy and complexity results.
Oracle-Based Analysis: For generalized symbolic games (over first-order theories), they analyze complexity relative to the satisfiability of specific quantified formulas ( $\exists^*\forall^*$ ) within the underlying theory.

3. Key Contributions and Results

A. Decision Problems for HOA (Automata)

The paper establishes tight complexity bounds for standard decision problems on HOA:

Acceptance Condition	Non-Emptiness	Language Inclusion
Reachability / Safety / Büchi / co-Büchi / Parity / Streett	NP-complete	PSPACE-complete
Rabin	NP-complete	PSPACE-complete
Muller	NP-complete	PSPACE-complete
Emerson-Lei (EL)	NP-complete	EXPSPACE-complete

Non-Emptiness: Proven NP-complete for all conditions. The hardness arises directly from the Boolean transition guards (reduction from SAT). The upper bound is achieved by guessing a polynomial-sized lasso run and verifying the Boolean constraints.
Language Inclusion:
- For most conditions (Streett, Parity, etc.), it is PSPACE-complete. The proof involves simulating the intersection of the automata on-the-fly using Safra's determinization (for Streett) without explicitly constructing the exponential state space.
- For Emerson-Lei, the problem jumps to EXPSPACE-complete. This is because converting an EL automaton to a Büchi automaton (a necessary step for standard inclusion algorithms) incurs an exponential blow-up in size.

B. Hanoi Omega-Games (HOG)

The paper formalizes HOGs, where the underlying arena is a deterministic HOA with inputs ( $P_{in}$ ) and outputs ( $P_{out}$ ).

Winning Condition	Complexity Class
Reachability / Safety / Büchi / co-Büchi / Parity / Streett	$\Pi_2$ -complete
Rabin	$\Sigma_3$ -complete (Upper bound) / $\Pi_2$ -hard
Muller / Emerson-Lei	PSPACE-complete

$\Pi_2$ -Completeness: For Streett and related conditions, the problem is shown to be $\Pi_2$ -complete (equivalent to $\forall \exists$ quantified Boolean formulas). The proof involves reducing to a classical game where Player In has memoryless winning strategies, but verifying the "q-good" property requires checking a $\Pi_1$ formula (universal quantification over outputs).
Rabin Complexity: Unlike classical games where Rabin objectives are $\Pi_2$ -complete, HOGs with Rabin conditions are harder. The authors prove an upper bound of $\Sigma_3$ by introducing "super-memoryless" strategies. These strategies rely on a fixed linear order over states to break ties, allowing the strategy to be represented in polynomial space despite the exponential arena size.
Muller/EL Complexity: Surprisingly, these revert to PSPACE-complete. The authors adapt McNaughton's algorithm for Muller games, utilizing the fact that the underlying sub-problems (safety and reachability games) are solvable in PSPACE.

C. Generalization to Symbolic Games

The authors generalize their techniques to Symbolic Games played over arbitrary decidable first-order theories (e.g., Presburger arithmetic).

Decidability: If the satisfiability of $\exists^*\forall^*$ formulas in the theory is decidable, then the game is decidable.
Complexity:
- For Streett/Parity conditions: coNP $^C$ (where $C$ is the complexity of the satisfiability problem for $\exists^*\forall^*$ formulas).
- For Rabin conditions: NP $^C$ .
Example: For Presburger arithmetic with a fixed number of variables, solving Streett games is coNP-hard and in $\Pi_2$ .

4. Significance

Theoretical Foundation: This work provides the first rigorous complexity analysis of the HOA format, which is the backbone of modern synthesis tools. It clarifies that while HOA is succinct, it does not inherently make problems harder than classical automata for emptiness (still NP), but it significantly impacts inclusion (PSPACE/EXPSPACE) and game solving (moving from P to $\Pi_2$ /PSPACE).
Tool Optimization: The results guide tool developers (e.g., in SYNTCOMP) on where to focus optimization efforts. For instance, knowing that Rabin HOGs are $\Sigma_3$ -hard suggests that solvers must handle complex quantifier alternations, whereas Muller HOGs might be more tractable via PSPACE algorithms.
Bridging Symbolic and Classical: The paper successfully bridges the gap between symbolic automata (using Boolean formulas) and classical game theory, providing a framework to analyze games over infinite data domains (like Presburger arithmetic) by reducing them to classical games with oracle calls.
New Strategy Concepts: The introduction of "super-memoryless" strategies for Rabin games in the symbolic setting offers a novel technique for compressing exponential strategy spaces into polynomial representations, which may have applications beyond HOA.

In summary, the paper confirms that the succinctness of HOA makes language inclusion and game solving more complex than in traditional formats, establishing precise complexity bounds that are essential for the theoretical understanding and practical optimization of reactive synthesis.