Highlights Conference 2025 Conference Abstract
Efficient Learning of Weak Deterministic Büchi Automata
- Mona Alluwaym
Author name cluster
Mona Alluwaym
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
2 author rows
Possible papers
2ECAI Conference 2025 Conference Paper
Efficient Learning of Weak Deterministic Büchi Automata
- Mona Alluwaym
- Yong Li 0031
- Sven Schewe
- Qiyi Tang 0001
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.