Publication details

Simple Complementation of Generalized Büchi Automata

Investor logo
Authors

DOKOUPIL David STREJČEK Jan

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

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.

More info