2024/10/15 by Havlena, Vojtěch, Lengál, Ondřej, Šmahlíková, Barbora
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2410.11644
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 combines a given complementation algorithm for a condition φ in a way that the resulting procedure handles conditions of the form Fin ∧ φ. The proposed constructions give upper bounds that are exponentially better than the state of the art for some of the classes.