💻 computer science

Complementing Emerson-Lei Elevator Automata (Technical Report)

This paper introduces Emerson-Lei elevator automata as a generalization of Büchi elevator automata to richer acceptance conditions and presents a complementation algorithm with significantly improved asymptotic complexity and practical efficiency compared to existing state-of-the-art tools.

Original authors: Ondrej Alexaj, Vojtěch Havlena, Ondřej Lengál, Yong Li, Nicolas Mazzocchi

Published 2026-06-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ondrej Alexaj, Vojtěch Havlena, Ondřej Lengál, Yong Li, Nicolas Mazzocchi

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 managing a massive, infinite library where every book represents a possible future of a computer program. Some books describe "good" futures (the program works correctly), and others describe "bad" futures (the program crashes or loops forever).

In the world of computer science, we use mathematical machines called automata to sort these books. A specific type of machine, the Emerson-Lei Automaton, is like a super-flexible librarian. It can handle very complex rules for what counts as a "good" book. For example, it can say: "A book is good if it contains the word 'success' infinitely often, but the word 'error' only a few times."

However, there is a tricky problem: sometimes we need to find the complement. This means we want a machine that does the exact opposite: it sorts out all the "bad" books (the ones that don't meet the criteria). Doing this for a general, flexible librarian is incredibly hard and slow, like trying to find a single specific grain of sand in a desert by hand.

The "Elevator" Discovery

The authors of this paper noticed something interesting about the libraries we actually use in real life. Most of the time, the librarians aren't totally chaotic. They have a specific structure: they act like elevators.

Think of an elevator building:

The Lobby (Non-deterministic part): When you first enter, you might have a choice of which elevator to take. It's a bit chaotic.
The Shaft (Deterministic part): Once you are inside the elevator and the doors close, the path is fixed. You go up or down in a predictable way. You can't suddenly decide to jump to a random floor; the elevator follows a strict track.

The paper calls these "Elevator Automata." The authors found that most real-world computer verification problems actually look like these elevators. They have a chaotic start, but then they settle into a predictable, deterministic flow.

The New Solution: A Smarter Sorting Machine

The paper introduces a new, faster way to build the "complement" machine (the one that finds the bad books) specifically for these Elevator Automata.

Here is the analogy of how their new algorithm works:

The Old Way (The General Approach):
Imagine trying to sort the bad books by checking every single possible path a book could take, all at once, without knowing which path is the "elevator" path. It's like trying to herd cats while blindfolded. The number of possibilities explodes, making the process incredibly slow and memory-hungry.

The New Way (The Elevator Approach):
The authors' algorithm realizes, "Hey, once the book enters the elevator shaft, the path is fixed!" So, instead of checking every wild possibility, it splits the job:

The Lobby Phase: It keeps track of the chaotic choices at the start.
The Elevator Phase: Once a path enters the "shaft," it stops guessing. It knows the rules are fixed. It uses a clever "checkpoint" system (like a security guard at the elevator door) to see if the book violates the rules.

They use a technique called breakpoints. Imagine a group of runners (the books) entering a track. The algorithm sets up a checkpoint.

If a runner sees a "bad" sign (a specific color), they are removed from the group.
If the group of runners becomes empty, the algorithm resets the checkpoint and starts again.
If this "reset" happens infinitely often, it proves that every possible path eventually hit a "bad" sign. Therefore, the book is definitely "bad."

Why This Matters

The paper proves that by using this "Elevator" structure, the size of the machine needed to find the bad books becomes much, much smaller than the old methods.

The Result: They built a tool (called Kofola) that uses this new method.
The Comparison: They tested it against the current industry standard tool (called Spot).
The Outcome: In almost every test case, their new tool created a much smaller, more efficient machine. It's like switching from a massive, fuel-guzzling truck to a sleek, electric car to do the same job.

Summary

In short, this paper says: "We realized that most computer verification problems act like elevators (chaotic start, fixed path). We built a new, super-fast way to find the 'bad' outcomes for these specific problems by treating the fixed path part differently. This makes the math much simpler and the computer programs run much faster."

It is a technical breakthrough in making computer verification tools more efficient, specifically for the types of problems that actually show up in real-world software testing.

Technical Summary: Complementing Emerson-Lei Elevator Automata

Problem Statement

The complementation of $\omega$ -automata is a fundamental operation in formal methods, essential for tasks such as program termination analysis, model checking of temporal logics (e.g., LTL, HyperLTL), and deciding logical theories (e.g., S1S). However, complementing general $\omega$ -automata is notoriously difficult, often resulting in a state-space explosion that renders practical verification infeasible.

While structural restrictions like "elevator automata" (where every strongly connected component is either deterministic or inherently weak) have been shown to enable more efficient complementation for standard Büchi automata, these optimizations have not been fully extended to automata with richer acceptance conditions. Specifically, Emerson-Lei automata (ELAs), which support arbitrary Boolean combinations of Inf (infinitely often) and Fin (finitely often) predicates, offer greater succinctness and flexibility but currently lack efficient, structure-aware complementation algorithms. Existing algorithms for unrestricted ELAs suffer from high asymptotic complexity, and there is a gap in practical methods for complementing ELAs that exhibit the "elevator" structure frequently found in real-world applications.

Methodology

The paper introduces Emerson-Lei Elevator Automata (ELEAs), a generalization of Büchi elevator automata to the Emerson-Lei acceptance framework. The authors propose a novel complementation algorithm that leverages the structural properties of ELEAs to achieve significantly better complexity bounds than general ELA complementation.

The methodology proceeds in three main stages:

Semi-Deterministic Automata (ELSA) with Specific Conditions:
The authors first address the complementation of Emerson-Lei Semi-Deterministic Automata (ELSA), where runs eventually enter a deterministic component. They develop constructions for two specific cases:
- Generalized Rabin Pairs: The algorithm combines the Miyano-Hayashi construction (for Fin conditions) and the NCSB algorithm (for Inf conditions). It utilizes a macrostate structure $(N, R, C, S_1, \dots, S_k, B)$ to track runs in the nondeterministic part ( $N$ ) and the deterministic part. The deterministic part is split into sets tracking Fin violations ( $R$ ) and Inf violations ( $C$ and safe sets $S_i$ ). A global breakpoint set $B$ ensures that all runs are inspected infinitely often.
- Generalized Streett Pairs: As a dual to the Rabin case, this construction uses a round-robin scheduling counter ( $z$ ) to sequentially invalidate all conditions in the Streett pair. It reuses sets between an NCSB instance (for the Inf condition) and multiple Miyano-Hayashi instances (for Fin conditions).
Inductive Procedure for Arbitrary Emerson-Lei Conditions:
To handle arbitrary Boolean combinations of Inf and Fin, the authors introduce a tree-macrostate approach. The negated acceptance condition $\psi = \neg Acc$ is represented as a tree mirroring its syntactic structure.
- Sampling Mode: Runs entering the deterministic component are nondeterministically assigned to subtrees corresponding to disjuncts of $\psi$ .
- Checking Mode: The algorithm verifies that runs satisfy the assigned subformulas. For Inf conditions, it uses breakpoint sets to ensure infinite visits; for Fin conditions, it ensures runs avoid specific colors.
- Optimizations: The paper details several optimizations to reduce state-space blowup:
  - Tree-Macrostate Normalization: Merging redundant run tracking when runs merge.
  - Shared Breakpoint Optimization: Using a single shared breakpoint for multiple Inf leaves via round-robin scheduling.
  - OR-FIN Optimization: Sequentially propagating violating states through Fin leaves in disjunctions to avoid exponential branching.
Extension to Full Elevator and Unrestricted Automata:
The techniques developed for ELSAs are extended to full ELEAs. The authors note that in practice, many non-elevator automata are "almost elevator" (containing only a few non-elevator SCCs). Their conversion treats these efficiently, leveraging the fact that most SCCs in practical automata are already elevator components.

Key Contributions and Results

Definition of ELEAs: The paper formally defines Emerson-Lei Elevator Automata, generalizing the concept of elevator automata to rich acceptance conditions.
Improved Complexity Bounds: The proposed algorithm achieves significantly lower asymptotic state-space complexity for the complement of an ELEA compared to the best-known algorithms for unrestricted ELAs.
- For a generalized Rabin pair with $k$ pairs, the complement size is bounded by $(k+3)n$ (or $(5+k)n$ in the general case presented in Section 3), whereas unrestricted ELAs have bounds like $O(n^{k}(0.76n)^{n})$ .
- Table 1 in the paper provides a comprehensive comparison, showing exponential or polynomial improvements over unrestricted bounds for various conditions (Büchi, Rabin, Streett, Parity, and Emerson-Lei).
Practical Implementation and Evaluation: The algorithm is implemented in the tool Kofola. Experimental comparisons with the state-of-the-art tool Spot demonstrate that Kofola often produces complements that are much smaller in size. The benchmarks include ELAs from literature, randomly generated Generalized Rabin Automata, and ELAs derived from LTL translations.

Significance and Claims

The authors claim that this work represents the first step towards practical algorithms for complementing, determinizing, and testing universality and inclusion for Emerson-Lei automata with rich acceptance conditions.

The significance lies in bridging the gap between theoretical succinctness (provided by ELAs) and practical verification efficiency. By exploiting the structural prevalence of elevator components in real-world automata (as noted in prior work [1]), the authors provide a method that drastically reduces the state explosion problem inherent in complementation. The paper positions this as a foundational contribution, enabling more efficient verification workflows for systems modeled with sophisticated acceptance conditions, without inventing new applications beyond those already established in the field (LTL model checking, hyperproperty verification).

The work is modest in its scope, focusing strictly on the complementation problem and its immediate implications for determinization and inclusion testing, while acknowledging that further work is needed to fully realize practical algorithms for all operations on ELEAs.