You are here:
Publication details
Simple Complementation of Generalized Büchi Automata
| Authors | |
|---|---|
| Year of publication | 2026 |
| Type | Paper in proceedings |
| Conference | LPAR-26: Proceedings of the 26th Conference on Logic for Programming, Artificial Intelligence, and Reasoning |
| MU Faculty or unit | |
| Citation | |
| web | https://easychair.org/publications/paper/zjrt |
| Doi | https://doi.org/10.29007/hngx |
| Keywords | complementation; generalized Büchi automata; greedy runs |
| Description | Transition-based generalized Büchi automata (TGBAs) can be substantially more compact than equivalent Büchi automata and they are produced or processed by most state-of-the-art ?-automata tools. Research on complementation algorithms for ?-automata focuses mainly on standard Büchi automata, with a few recent exceptions. We present a complementation construction applicable directly to TGBAs based on the idea of “simple and optimal” Büchi automata complementation by Allred and Ultes-Nitsche. We also provide an upper bound on the size of the complement. The bound is asymptotically better than the upper bounds of other complementation approaches applicable to TGBA. Experimental evaluation shows that on complex TGBAs, our complementation clearly outperforms the complementation processes available in modern tools including Spot and Kofola. |
| Related projects: |