Angluin-Style Learning of Deterministic Büchi and Co-Büchi Automata

Yong Li, Sven Schewe, Qiyi TangIJCAI 2024

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:

  1. Limit FDFA Learner: Uses membership and equivalence queries to build a "limit FDFA," a canonical representation for $\omega$-regular languages.
  2. DBA Construction: A transformation process that converts the intermediate FDFA into a language-equivalent DBA conjecture.
  3. Counterexample (CEX) Analysis: A specialized logic to handle mismatches between the FDFA and the resulting DBA.
Architecture of the DBA learner framework showing the interaction between the Limit FDFA learner, the DBA oracle, and the CEX analysis component.

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.

Venn diagram illustrating the relationship between the target language L, the intermediate FDFA F, and the conjecture DBA. Case (3) highlights counterexamples that exist within the FDFA but outside the DBA conjecture.

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

BibTeX
@inproceedings{li2024angluin,
  author = {Yong Li and Sven Schewe and Qiyi Tang},
  title = {{Angluin-Style Learning of Deterministic Büchi and Co-Büchi Automata}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure