Detail publikace

Complementation of Emerson-Lei Automata

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

Originální název

Complementation of Emerson-Lei Automata

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

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

Vydáno

3. 5. 2025

Nakladatel

Springer Verlag

Místo

Heidelberg

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Ročník

15691

Číslo

1

Stát

Spolková republika Německo

Strany od

88

Strany do

110

Strany počet

19

URL

https://link.springer.com/chapter/10.1007/978-3-031-90897-2_5

Plný text v Digitální knihovně

http://hdl.handle.net/11012/255204

BibTex

@inproceedings{BUT196842,
  author="Vojtěch {Havlena} and Ondřej {Lengál} and Barbora {Šmahlíková}",
  title="Complementation of Emerson-Lei Automata",
  booktitle="Proceedings of FoSSaCS'25",
  year="2025",
  journal="Lecture Notes in Computer Science",
  volume="15691",
  number="1",
  pages="88--110",
  publisher="Springer Verlag",
  address="Heidelberg",
  doi="10.1007/978-3-031-90897-2\{_}5",
  issn="0302-9743",
  url="https://link.springer.com/chapter/10.1007/978-3-031-90897-2_5"
}