Detail publikace

Complementation of Emerson-Lei Automata

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

Originální název

Typ

článek ve sborníku mimo WoS a Scopus

Jazyk

angličtina

Originální abstrakt

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.

Klíčová slova

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

Autoři

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

Vydáno

3. 5. 2025

Nakladatel

Springer Verlag

Místo

Heidelberg

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Číslo

15691

Stát

Spolková republika Německo

Strany od

Strany do

110

Strany počet

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"
}

Odpovědnost: Ing. Marek Strakoš