Detail publikačního výsledku

Complementation of Emerson-Lei Automata

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

Originální název

Complementation of Emerson-Lei Automata

Anglický název

Complementation of Emerson-Lei Automata

Druh

Stať ve sborníku mimo WoS a Scopus

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.

Anglický 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

Klíčová slova v angličtině

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

03.05.2025

Nakladatel

Springer Verlag

Místo

Heidelberg

Kniha

Proceedings of FoSSaCS'25

ISSN

0302-9743

Periodikum

Lecture Notes in Computer Science

Svazek

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

Dokumenty

978-3-031-90897-2_5