Introduction
In formal verification, modeling infinite sequences of events—known as $\omega$-words—is essential for program synthesis and bug detection. While Angluin’s $L^*$ algorithm is the gold standard for learning finite-word languages (DFAs), extending it to infinite words has historically been computationally expensive. Existing methods often target Nondeterministic Büchi Automata (NBAs), where the critical "equivalence query" (checking if a guessed model is correct) is PSPACE-complete. This paper introduces a novel Angluin-style active learning algorithm for Deterministic Büchi Automata (DBAs) and Deterministic co-Büchi Automata (DCAs), reducing the complexity of equivalence queries to NL-complete and making $\omega$-regular language learning significantly more practical.
The DBA Learning Framework
The proposed framework shifts the focus to deterministic models to leverage more efficient verification procedures. The architecture consists of three primary components interacting with a DBA oracle:
- Limit FDFA Learner: Uses membership and equivalence queries to build a "limit FDFA," a canonical representation for $\omega$-regular languages.
- DBA Construction: A transformation process that converts the intermediate FDFA into a language-equivalent DBA conjecture.
- Counterexample (CEX) Analysis: A specialized logic to handle mismatches between the FDFA and the resulting DBA.
Solving the Representation Mismatch
A key challenge in this approach is that the standard learning cycle is disrupted by the transformation from FDFA to DBA. A counterexample provided by the oracle might be in the target language and the underlying FDFA, but not in the conjecture DBA.
The authors categorize these discrepancies into three cases. "Case 3" represents a scenario where a counterexample is valid for the DBA conjecture but does not directly contradict the current state of the FDFA. The core technical contribution of this work is a specialized CEX analysis (Algorithm 2) that extracts refinement information from these complex cases to ensure the learner continues to progress toward the correct model.
Key Results and Complexity
By targeting deterministic automata, the algorithm achieves a massive reduction in the computational cost of the oracle's task, moving from PSPACE to NL (Nondeterministic Logarithmic space).
- Termination: The authors provide formal proofs that the algorithm is guaranteed to terminate with a correct DBA.
- Polynomial Time: The learner runs in polynomial time relative to the size of the periodic FDFA. While the theoretical worst-case upper bound is high ($O(n^{32} \cdot m \cdot |\Sigma|)$), empirical observations within the ROLL (Regular Omega-Language Learning) library suggest that the algorithm often converges much faster in practice, frequently before the FDFA reaches its full canonical form.
Limitations and Future Outlook
The primary limitation is expressiveness; the algorithm is restricted to languages that are DBA-recognizable. While many verification properties fit this criteria, some $\omega$-regular languages require more complex structures like parity automata. Future research aims to optimize the CEX analysis to lower the theoretical complexity exponent and integrate this learner into real-world automated verification and synthesis pipelines to measure practical speedups.
Summary updated