Efficient Learning of Weak Deterministic Büchi Automata

2025/08/19 by Alluwayma, Mona, Li, Yong, Schewe, Sven +1
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2508.14274

Abstract

We present an efficient Angluin-style learning algorithm for weak deterministic Büchi automata (wDBAs). Different to ordinary deterministic Büchi and co-Büchi automata, wDBAs have a minimal normal form, and we show that we can learn this minimal normal form efficiently. We provide an improved result on the number of queries required and show on benchmarks that this theoretical advantage translates into significantly fewer queries: while previous approaches require a quintic number of queries, we only require quadratically many queries in the size of the canonic wDBA that recognises the target language.

Citations

• A novel family of finite automata for recognizing and learning ω-regular languages
• Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples
• Learning to Prove Safety over Parameterised Concurrent Systems (Full Version)
• A Novel Learning Algorithm for Büchi Automata based on Family of DFAs and Classification Trees

Related

• A Novel Learning Algorithm for Büchi Automata based on Family of DFAs and Classification Trees
• LTL to Büchi Automata Translation: Fast and More Deterministic
• Minimal History-Deterministic Co-Büchi Automata: Congruences and Passive Learning
• From LTL to Unambiguous Büchi Automata via Disambiguation of Alternating Automata
• A Quasi-Linear Time Algorithm Deciding Whether Weak Büchi Automata Reading Vectors of Reals Recognize Saturated Languages