Efficient Learning of Weak Deterministic Büchi Automata
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916909398622208 |
|---|---|
| author | Alluwayma, Mona Li, Yong Schewe, Sven Tang, Qiyi |
| author_facet | Alluwayma, Mona Li, Yong Schewe, Sven Tang, Qiyi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14274 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Learning of Weak Deterministic Büchi Automata Alluwayma, Mona Li, Yong Schewe, Sven Tang, Qiyi Formal Languages and Automata Theory 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. |
| title | Efficient Learning of Weak Deterministic Büchi Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2508.14274 |