Publication detail

Complementation of Emerson-Lei Automata

ŠMAHLÍKOVÁ, B. HAVLENA, V. LENGÁL, O.

Original Title

Type

article in a collection out of WoS and Scopus

Language

English

Original 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 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.

Keywords

Emerson-Lei automata, TELA, complementation, Büchi automata, rank-based complementation, Rabin automata, parity automata

Authors

ŠMAHLÍKOVÁ, B.; HAVLENA, V.; LENGÁL, O.

Released

3. 5. 2025

Publisher

Springer Verlag

Location

Heidelberg

ISBN

0302-9743

Periodical

Lecture Notes in Computer Science

Number

15691

State

Federal Republic of Germany

Pages from

Pages to

110

Pages count

BibTex

@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",
  number="15691",
  pages="88--110",
  publisher="Springer Verlag",
  address="Heidelberg",
  doi="10.1007/978-3-031-90897-2\{_}5",
  issn="0302-9743"
}

Responsibility: Ing. Marek Strakoš