💻 computer science

Positional $ω$ -regular languages

This paper provides a complete characterization of positional $\omega$ -regular languages via parity automata, establishing their polynomial-time decidability, various lifting properties, and closure under union, thereby resolving Kopczyński's conjecture for the $\omega$ -regular case.

Original authors: Antonio Casares, Pierre Ohlmann

Published 2026-03-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Antonio Casares, Pierre Ohlmann

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 playing a very long, infinite board game with a friend. The board is a map of cities (vertices) connected by roads (edges). Each road has a color painted on it. You and your friend take turns moving a token along these roads, creating an endless trail of colors.

The goal of the game is defined by a specific rule: Eve (you) wins if the infinite trail of colors you create matches a specific pattern. Adam (your opponent) wins if the trail breaks that pattern.

The big question this paper answers is: Can you always play perfectly without remembering your past moves?

The Core Concept: "Positional" Strategies

In many games, to play optimally, you might need to remember: "I went left, then right, then left again, so now I must go up." This is a history-dependent strategy.

However, a positional strategy is much simpler. It's like a GPS that only cares about where you are right now. No matter how you got to this city, the GPS says, "From here, always go North." If a game objective allows you to win using only these "current location only" rules, we call that objective positional.

Why does this matter?

Simplicity: It's easier to program a robot (or a computer controller) to follow simple "if-then" rules than complex memory-based ones.
Efficiency: Solving games with simple strategies is computationally much faster.

The Problem: The "Black Box" of Rules

For decades, computer scientists knew that some rules (like "Parity" or "Büchi" conditions) were positional, and others were not. But there was no general recipe to look at a complex rule and say, "Yes, this one is positional," or "No, you need a memory."

It was like having a box of 100 different board games, and for each one, you had to play it a million times to figure out if a simple strategy worked. We needed a way to look at the rulebook and instantly know the answer.

The Solution: The "Signature" Blueprint

The authors of this paper (Antonio Casares and Pierre Ohlmann) have discovered a structural blueprint for these rules. They found that if a rule is positional, it must look a specific way when translated into a machine (called a Parity Automaton).

Think of an Automaton as a flowchart or a decision tree that checks the colors as they appear. The authors found that for a rule to be positional, this flowchart must have a very specific, tidy architecture:

Nested Layers (The Onion): Imagine the states of the machine are organized in layers, like an onion.
Strict Hierarchy: You can't have a chaotic mess. The layers must be strictly ordered. If you are in "Layer 3," you can only move to "Layer 3" or "Layer 2," never jumping randomly to "Layer 5."
The "Signature": They call these tidy machines Signature Automata. If you can rearrange a complex rule's flowchart into this specific "Signature" shape, then you know for sure that a simple, memory-less strategy exists.

The Magic Trick: The "Neutral Letter"

One of the most surprising discoveries is about a "neutral letter" (a color that doesn't really change the outcome, like a blank space).

The Old Belief: Scientists thought that adding a neutral letter to a game might break the simplicity, making a positional game suddenly require memory.
The New Discovery: The authors proved that for the vast class of rules they studied (called $\omega$ -regular), adding a neutral letter never breaks positionality. If a rule is simple enough to be played without memory, it stays simple even if you add "do nothing" moves.

The "Universal Map" Analogy

To prove their theory, the authors used a concept called Universal Graphs.

Imagine you want to design a game board that is so complex it can simulate any other game board of a certain size.

If you can build a Universal Map that is "monotone" (meaning it has a clear, logical order, like a staircase going up) and can simulate any winning path, then the rule is positional.
The authors showed that for positional rules, you can always build this specific kind of "Universal Map." If you can't build it, the rule is too chaotic for a simple strategy.

Why This Matters in the Real World

This isn't just abstract math. It applies to Reactive Synthesis, which is the process of automatically designing controllers for systems that interact with the world.

Example: Imagine designing the software for a self-driving car. The "game" is the car vs. the unpredictable traffic. The "objective" is "never crash and always reach the destination."
The Benefit: If the safety rules are "positional," the engineers can write a controller that only looks at the current sensor data (Is there a car in front? Yes/No). They don't need to store a history of the last 100 miles. This makes the software smaller, faster, and easier to verify as safe.

Summary of Achievements

The Recipe: They gave a complete checklist (Theorem 3.1) to determine if any $\omega$ -regular rule allows for a simple strategy.
The Speed-Up: They created an algorithm that checks this recipe in polynomial time (very fast), whereas previous methods were incredibly slow.
The "Lift": They proved that if a rule works simply on small, finite maps, it works simply on infinite, complex maps too. This solves a long-standing conjecture.
The Union: They proved that if you combine two simple rules (where one is "prefix-independent," meaning it doesn't care about the start), the combined rule is still simple.

The Bottom Line

This paper provides the missing manual for understanding when complex, infinite games can be won with simple, "here-and-now" strategies. It turns a chaotic guessing game into a structured engineering problem, allowing us to build better, safer, and more efficient automated systems.

1. Problem Statement

The paper addresses the fundamental problem of strategy complexity in two-player infinite-duration games played on graphs. Specifically, it investigates positionality: the property of a winning objective $W$ (a language of infinite words) such that the protagonist (Eve) can play optimally using positional strategies. A positional strategy depends only on the current vertex of the game graph, not on the history of the play.

While the class of bipositional objectives (where both players have positional optimal strategies) is well-understood (characterized by parity objectives for prefix-independent cases), the characterization of positional objectives (where only Eve needs positional strategies) has remained an open and difficult problem. The authors focus specifically on $\omega$ -regular languages, a central class in formal verification and reactive synthesis.

The paper aims to answer:

What is the structural characterization of $\omega$ -regular languages that are positional?
Is positionality decidable for $\omega$ -regular objectives, and if so, with what complexity?
Do standard "lifts" hold (e.g., does positionality over finite games imply positionality over infinite games)?
Is the union of two positional objectives positional (Kopczyński's conjecture)?

2. Methodology

The authors employ a combination of automata theory, game theory, and graph theory. Their methodology relies on several key technical tools:

Universal Graphs: They utilize the framework of monotone universal graphs (introduced by Ohlmann) as the primary tool for proving positionality. If a language admits a well-ordered monotone universal graph for every cardinality, it is positional.
Signature Automata: The core of their contribution is the definition of a new syntactic class of deterministic parity automata called signature automata. These automata are equipped with a hierarchy of nested total preorders over their states that satisfy specific structural properties (faithful congruences, safe separation, and local monotonicity).
$\varepsilon$ -completable Automata: They introduce the concept of $\varepsilon$ -completable automata. An automaton is $\varepsilon$ -completable if one can add $\varepsilon$ -transitions (silent moves) to form a specific structure (total preorders on $\varepsilon$ -transitions) without changing the recognized language.
History-Determinism (HD): The proofs heavily rely on history-deterministic automata (automata where non-determinism can be resolved based on the prefix of the input). The authors use HD automata as an intermediate step to construct universal graphs and to bridge the gap between syntactic automata properties and semantic game properties.
Congruences and Quotients: They develop a theory of congruences for parity automata that respect priority conditions, allowing them to build quotient automata that preserve the language and the necessary structural properties.

3. Key Contributions

A. Complete Characterization of Positionality (Theorem 3.1)

The paper provides the first complete characterization of positional $\omega$ -regular languages. The following statements are equivalent for an $\omega$ -regular objective $W$ :

$W$ is positional over finite, $\varepsilon$ -free Eve-games.
$W$ is recognized by a deterministic fully progress-consistent signature automaton.
$W$ is recognized by a deterministic $\varepsilon$ -completable parity automaton.
$W$ admits a well-ordered monotone universal graph for every cardinal.
$W$ is positional over all games (potentially infinite and containing $\varepsilon$ -edges).

This characterization links the semantic property of positionality directly to the syntactic structure of the recognizing automaton.

B. Polynomial-Time Decidability (Theorem 3.2)

Based on the characterization, the authors provide two distinct polynomial-time algorithms to decide whether a given deterministic parity automaton recognizes a positional language:

Recursive Decomposition: Attempts to transform the input automaton into a signature automaton by iteratively applying safe-centralization, re-determinization, and polishing. If the process fails, the language is not positional.
$\varepsilon$ -Completion: Attempts to construct an $\varepsilon$ -completion of the automaton. If successful, the language is positional.

C. Resolution of Open Conjectures

The characterization resolves several long-standing open questions:

Finite-to-Infinite Lift: An $\omega$ -regular objective is positional over all games if and only if it is positional over finite, $\varepsilon$ -free Eve-games (Theorem 3.3). This answers a conjecture by Vandenhove.
1-to-2-Player Lift: For $\omega$ -regular objectives, if Eve can play optimally positionally in all Eve-games, she can do so in all games (Theorem 3.3).
Closure under Union (Kopczyński's Conjecture): The union of two positional $\omega$ -regular objectives is positional, provided at least one of them is prefix-independent (Theorem 3.4). This solves a stronger variant of Kopczyński's conjecture for the $\omega$ -regular case.
Neutral Letter Conjecture: Adding a neutral letter to a positional $\omega$ -regular objective preserves positionality (Theorem 3.9). This confirms Ohlmann's conjecture for $\omega$ -regular languages.

D. Generalizations beyond $\omega$ -regularity

The authors extend their results to non- $\omega$ -regular classes:

Bipositionality: They characterize all bipositional objectives (not just $\omega$ -regular ones) using total order of residuals, bi-progress consistency, and recognition by a parity automaton over the residual automaton (Theorem 7.1).
Closed and Open Objectives: They provide characterizations for positional closed and open objectives based on the well-foundedness of residuals and reset-stability (Theorems 8.4 and 8.10).

4. Key Results and Technical Details

Signature Automata Structure: A signature automaton is defined by a sequence of nested total preorders $\sqsubseteq_0, \dots, \sqsubseteq_d$ $⊑_{0}, \dots, ⊑_{d}$ .
- $\sqsubseteq_0$ refines the inclusion of residuals.
- Even layers correspond to safe components (states reachable without seeing lower priorities).
- Odd layers correspond to safe languages (inclusion of languages avoiding lower priorities).
- Full Progress Consistency: A semantic condition ensuring that if a word makes strict progress in the preorder, repeating it infinitely often yields an accepting word. This prevents "stalling" in non-winning loops.
$\varepsilon$ -Completion: The construction of an $\varepsilon$ -completion involves adding $\varepsilon$ -transitions that respect the total preorders of the signature automaton. This transforms the deterministic automaton into a history-deterministic one, which is then used to build the universal graph.
Universal Graph Construction: The paper constructs a universal graph $U_A$ from an $\varepsilon$ -complete history-deterministic automaton $A$ . The vertices of $U_A$ are pairs of (state of $A$ , tuple of ordinals), ordered lexicographically. The edges are defined to mimic the transitions of $A$ while respecting the parity condition of the universal graph for parity objectives.

5. Significance and Impact

Theoretical Breakthrough: This work provides the first complete structural characterization of positional $\omega$ -regular languages, filling a major gap in the theory of infinite games. It moves beyond specific subclasses (like Büchi or coBüchi) to the full class of $\omega$ -regular languages.
Algorithmic Efficiency: The polynomial-time decidability result is crucial for practical applications in reactive synthesis. It allows tools to automatically verify if a specification admits a simple (positional) controller, which is significantly easier to implement and verify than a history-dependent one.
Unification of Concepts: The paper unifies various concepts (universal graphs, history-determinism, congruences, and progress consistency) into a cohesive framework. It demonstrates that history-determinism is a canonical property for positional objectives.
Resolution of Conjectures: By settling Kopczyński's conjecture (under the prefix-independence condition) and the neutral letter conjecture for $\omega$ -regular languages, the paper clarifies the boundaries of positionality and provides a solid foundation for future research on memory requirements in games.
Future Directions: The authors suggest that their techniques (particularly the use of congruences and signature automata) could lead to minimization algorithms for parity automata and further characterizations for objectives requiring finite memory (e.g., in the Borel hierarchy).

In summary, this paper establishes a deep connection between the syntactic structure of parity automata and the game-theoretic property of positionality, offering both a theoretical characterization and efficient decision procedures for a central class of objectives in formal methods.