Complementation of Emerson-Lei Automata
Open Access
- 1 May 2025
- book chapter
- Published by Springer Nature
- p. 88-110
Abstract
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 $$\varphi $$ in a way that the resulting procedure handles conditions of the form $$\text {Fin}\wedge \varphi $$ . The proposed constructions give upper bounds that are exponentially better than the state of the art for some of the classes.
Keywords
This publication has 41 references indexed in Scilit:
- Modular Mix-and-Match Complementation of Büchi Automata2023
- Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition2022
- Complementing Büchi Automata with Ranker2022
- Sky Is Not the Limit2022
- Seminator 2 Can Complement Generalized Büchi Automata via Improved Semi-determinization2020
- Simulations in Rank-Based Büchi Automata Complementation2019
- Learning to Complement Büchi Automata2017
- Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique2006
- Complementation Constructions for Nondeterministic Automata on Infinite Words2005
- Automata Logics, and Infinite Games2002