Publication Details
Complementation of Emerson-Lei Automata
Havlena Vojtěch, Ing., Ph.D. (DITS)
Lengál Ondřej, Ing., Ph.D. (DITS)
Emerson-Lei automata, TELA, complementation, Büchi automata, rank-based
complementation, Rabin automata, parity automata
We give new constructions for complementing subclasses of Emerson-Lei automata
using modifications of rank-based Büchi automata complementation. In particular,
we propose a specialized rank-based construction for a Boolean combination of Inf
acceptance conditions, which heavily relies on a novel way of a run DAG labelling
enhancing the ranking functions with models of the acceptance condition.
Moreover, we propose a technique for complementing generalized Rabin automata,
which are structurally as concise as general Emerson-Lei automata (but can have
a larger acceptance condition). The construction is modular in the sense that it
extends a given complementation algorithm for a condition in a way that the
resulting procedure handles conditions of the form Fin & phi. The
proposed constructions give upper bounds that are exponentially better than the
state of the art for some of the classes.
@inproceedings{BUT196842,
author="Barbora {Šmahlíková} and Vojtěch {Havlena} and Ondřej {Lengál}",
title="Complementation of Emerson-Lei Automata",
booktitle="Proceedings of FoSSaCS'25",
year="2025",
journal="Lecture Notes in Computer Science",
pages="19",
publisher="Springer Verlag",
issn="0302-9743"
}