💻 computer science

Kofola 1.0: A Modular Approach to {\omega}-Regular Complementation and Inclusion Checking (Technical Report)

This paper introduces Kofola, an efficient and robust tool that employs a modular framework to decompose Büchi automata into strongly connected components for tailored complementation and inclusion checking, demonstrating superior performance over state-of-the-art tools through on-the-fly emptiness checking and new heuristics.

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

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ondrej Alexaj, Vojtěch Havlena, Lukáš Holík, 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 a quality control inspector for a massive, infinite factory. This factory produces endless streams of products (called "words" in computer science). You have two machines: Machine A and Machine B.

Your job is to answer a very difficult question: "Does every single product that Machine A makes, also get made by Machine B?"

If the answer is "Yes," then Machine A is safe to use. If there is even one product Machine A makes that Machine B never makes, then Machine A is unsafe.

This is the core problem of Language Inclusion Checking. It's a fundamental task for verifying that computer software and hardware behave correctly. However, because the streams of products are infinite, checking this manually is impossible. You need a super-smart robot to do it.

Enter Kofola, a new, highly efficient robot designed to solve this problem. Here is how it works, broken down into simple concepts:

1. The Old Way vs. The Kofola Way

Previously, robots trying to solve this had to look at the entire factory floor at once. They would try to build a giant map of every possible path Machine A could take and compare it to Machine B. This map was so huge it often caused the robot's brain to explode (a problem called "state-space explosion").

Kofola's Secret Sauce: The Modular Approach
Instead of looking at the whole factory at once, Kofola is a master organizer. It looks at Machine B and says, "This factory isn't one big mess; it's actually made of distinct neighborhoods."

Kofola breaks Machine B down into Strongly Connected Components (SCCs). Think of these as different rooms or zones in the factory:

The Dead Ends: Rooms where the machine stops making products.
The Simple Loops: Rooms where the machine spins in a circle doing the same thing over and over.
The Deterministic Zones: Rooms where the machine has only one choice at every step (like a train on a single track).
The Chaotic Zones: Rooms where the machine has many choices and can go in different directions (like a maze).

Kofola treats each "neighborhood" differently. It uses a specialized, simple tool for the simple loops and a heavy-duty tool for the chaotic zones. It doesn't waste energy trying to solve the easy parts with a sledgehammer.

2. The New "IADAC" Discovery

The paper introduces a new type of neighborhood called an IADAC (Initial Almost Deterministic Accepting Component).

The Analogy: Imagine a hallway that leads into a room. The hallway is a straight, single-lane track (deterministic). Once you enter the room, you might have choices. But here's the trick: once you leave that room, you can never come back to the hallway.
Why it matters: Because the hallway is so predictable, Kofola can use a very fast, lightweight method to check it, rather than the heavy, slow method needed for the chaotic parts. This is a new type of zone the authors identified and optimized for.

3. The "Lazy" Inspector (On-the-Fly Checking)

Usually, to check if the factory is safe, you have to build the entire map of the factory before you can say "Safe" or "Unsafe."

Kofola is maximally lazy (in a good way). It starts building the map, but as soon as it finds enough evidence to decide the answer, it stops.

If it finds a "bad product" early on, it immediately shouts, "Unsafe!" and stops working.
It doesn't waste time mapping out the rest of the factory if the answer is already clear.

This is done using a new "emptiness-checking" algorithm. Imagine you are looking for a specific type of bug in a dark room. Instead of turning on the lights for the whole room, you only shine your flashlight on the path you are walking. If you find the bug, you stop. If you walk the whole path and don't find it, you know the room is clear. Kofola does this instantly while it's building the map.

4. The Results: Kofola Wins the Race

The authors tested Kofola against the best existing robots (tools like Spot, Rabit, and Bait) using thousands of real-world factory blueprints.

Robustness: Kofola was the only tool that successfully solved every single test case without crashing or running out of memory. The others failed on many difficult ones.
Speed: On many practical problems, Kofola was not just faster; it was orders of magnitude faster. In some cases, while other tools were still trying to build the map after 2 minutes, Kofola had already finished in a fraction of a second.
Size: The maps Kofola built were often much smaller and more compact than those built by competitors.

Summary

Kofola is a new, super-efficient tool for checking if one computer system is "contained" within another. It works by:

Breaking the problem down into smaller, manageable neighborhoods.
Using the right tool for each specific neighborhood type (including a new type it discovered).
Being lazy, stopping the work the moment it has enough information to give an answer.

The result is a tool that is faster, more reliable, and handles much larger and more complex problems than anything else currently available. It is a significant upgrade for the "quality control" of computer systems.

Technical Summary: Kofola 1.0 – A Modular Approach to ω-Regular Complementation and Inclusion Checking

Problem Statement

Language inclusion checking for Büchi automata (BAs) is a fundamental problem in automata-theoretic verification, with critical applications in model checking, monitoring, and theorem proving. The problem is PSpace-complete and remains computationally demanding as system specifications grow in size and complexity. Deciding whether $L_1 \subseteq L_2$ reduces to checking the emptiness of $L_1 \cap \overline{L_2}$ , where $\overline{L_2}$ is the complement of $L_2$ . This reduction presents two primary challenges:

Compact Complementation: Constructing the complement automaton $\overline{L_2}$ efficiently without causing a state-space explosion.
Efficient Exploration: Exploring the product automaton of $L_1 \cap \overline{L_2}$ , which is often enormous.

Existing tools largely rely on classical Ramsey-based or determinization-based complementation constructions dating back over three decades. While recent advances in complementation exist, they have not been fully integrated into practical inclusion checkers.

Methodology

The paper presents Kofola, an efficient tool implemented in C++ that implements a state-of-the-art modular complementation framework. The methodology is built on decomposing the input automaton into strongly connected components (SCCs) and applying tailored complementation algorithms to each component based on its structural properties.

1. Structural Decomposition and Component Classification

Kofola performs a fine-grained structural analysis of the automaton to be complemented ( $A_2$ ). It classifies its maximal SCCs into four distinct categories:

Non-accepting components: Handled via traditional subset construction.
Inherently Weak Accepting Components (IWACs): Components where all cycles accept.
Deterministic Accepting Components (DACs): Components with only deterministic transitions.
Initial Almost Deterministic Accepting Components (IADACs): A newly identified component type introduced in this paper. These are deterministic SCCs reachable from initial states via deterministic SCCs, allowing nondeterminism only on cycle-free paths between SCCs.
Nondeterministic Accepting Components (NACs): The remaining accepting SCCs.

2. Modular Complementation Framework

For each component type, Kofola applies a dedicated partial complementation algorithm:

IWACs: Uses the classical Miyano-Hayashi construction, generating an $Inf(1)$ acceptance condition.
DACs: Uses a modification of the NCSB algorithm, generating an $Inf(2)$ acceptance condition.
NACs: Supports two approaches depending on the task:
- Complementation: Uses a determinization-based approach (Safra-Piterman variant) to produce smaller automata.
- Inclusion Checking: Uses a slice-based approach, which is better suited for on-the-fly product emptiness testing.
IADACs: The paper introduces a new partial algorithm for these components. It determinizes the IADACs using a subset construction and emits a rejecting mark ($Fin(0)$) whenever a tracked run sees an accepting transition. The correctness relies on the fact that runs in IADACs are bounded due to their restricted nondeterminism.

The top-level algorithm synchronizes these partial constructions. The resulting complement automaton is a Simple Generalized Rabin Automaton (SGRA) with a single acceptance condition of the form $Fin(0) \land Inf(1) \land \dots \land Inf(k-1)$ .

3. On-the-Fly Emptiness Checking

To address the state-space explosion in inclusion checking, Kofola employs a novel on-the-fly emptiness-checking algorithm for the resulting SGRA.

Lazy Construction: Unlike tools that require the explicit construction of the full product automaton, Kofola explores the state space lazily.
Algorithm: The algorithm is a variant of Couvreur's algorithm extended with a $Fin$ predicate. It performs a depth-first search, managing a stack of transition sets to detect SCCs.
Termination: The search terminates as soon as the explored state space is sufficient to decide the result (either finding an accepting cycle or proving emptiness). This minimizes the generated part of the complement, which is crucial as complementation is the primary source of blow-up.

Key Contributions

Kofola Tool: An efficient, modular tool for BA complementation and language inclusion checking.
IADAC Identification: The introduction and formalization of Initial Almost Deterministic Accepting Components (IADACs) as a distinct structural class.
New Complementation Algorithm: A dedicated partial algorithm for IADACs that generates the $Fin(0)$ condition, enabling the construction of a single generalized Rabin pair.
Lazy Emptiness Checking: A new on-the-fly algorithm for SGRAs that avoids explicit full automaton construction, allowing for early termination.
Modular Framework: A flexible architecture that allows different partial algorithms to be combined synchronously based on structural analysis.

Experimental Results

The authors evaluated Kofola against state-of-the-art tools: Spot, Ranker, Owl, Bait, Forklift, and Rabit.

Complementation Benchmarks

Dataset: 31,273 automata from diverse sources (program termination, logic of Sturmian words, hyperproperties, S1S, LTL translation, and random generation).
Robustness: Kofola was the only tool to successfully complement all 31,273 input automata. The next most robust tool, Spot, failed on 2 instances due to memory limits.
Size: Kofola produced significantly smaller complement automata on average (79.24 states) compared to Spot (115.38 states) and Ranker (45.80 states, though Ranker failed on 443 instances).
Performance: Kofola solved the most instances and often outperformed competitors by several orders of magnitude in runtime.

Inclusion Checking Benchmarks

Dataset: 1,014 inclusion problems from program termination, concurrent system verification, hyperproperty model checking, and theorem proving.
Performance: Kofola solved the most instances (only 2 unsolved) and had the lowest total runtime (141 seconds for solved problems).
Comparison: Kofola strictly won against Spot(Det) on 263 instances and lost on only 0. It significantly outperformed Ramsey-based tools (Bait, Forklift, Rabit), which often required an order of magnitude more time.
Observation: 98% of the automata on the right-hand side of the inclusion queries (those being complemented) were elevator automata (containing no NACs), highlighting the practical relevance of exploiting structural properties.

Significance and Claims

The paper claims that Kofola establishes a new standard for efficiency and robustness in BA complementation and inclusion checking. Its significance lies in:

Practicality: It brings modern, decomposition-based complementation techniques to practical inclusion checking, moving beyond classical constructions.
Scalability: By combining structural decomposition with lazy on-the-fly emptiness checking, it effectively mitigates state-space explosion, solving instances that are intractable for existing tools.
Extensibility: The modular architecture allows for the integration of new partial complementation algorithms for specific component types.

The authors position Kofola not merely as an incremental improvement but as a highly competitive tool that often outperforms state-of-the-art solutions by several orders of magnitude on benchmarks derived from practical applications.