Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
HAVLENA, V. LENGÁL, O. ŠMAHLÍKOVÁ, B.
Originální název
Complementing Büchi Automata with Ranker
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
angličtina
Originální abstrakt
We present the tool Ranker for complementing Büchi automata (BAs). Ranker builds on our previous optimizations of rank-based BA complementation and pushes them even further using numerous heuristics to produce even smaller automata. Moreover, it contains novel optimizations of specialized constructions for complementing (i) inherently weak automata and (ii) semi-deterministic automata, all delivered in a robust tool. The optimizations significantly improve the usability of Ranker, as shown in an extensive experimental evaluation with real-world benchmarks, where Ranker produced in the majority of cases a strictly smaller complement than other state-of-the-art tools.
Klíčová slova
Büchi automata, complementation, rank-based complementation, omega-regular languages
Autoři
HAVLENA, V.; LENGÁL, O.; ŠMAHLÍKOVÁ, B.
Vydáno
7. 8. 2022
Nakladatel
Springer Verlag
Místo
Haifa
ISBN
978-3-031-13187-5
Kniha
Proceedings of the 34th International Conference on Computer Aided Verification
ISSN
0302-9743
Periodikum
Lecture Notes in Computer Science
Číslo
13372
Stát
Spolková republika Německo
Strany od
188
Strany do
201
Strany počet
14
BibTex
@inproceedings{BUT178204, author="Vojtěch {Havlena} and Ondřej {Lengál} and Barbora {Šmahlíková}", title="Complementing Büchi Automata with Ranker", booktitle="Proceedings of the 34th International Conference on Computer Aided Verification", year="2022", journal="Lecture Notes in Computer Science", number="13372", pages="188--201", publisher="Springer Verlag", address="Haifa", doi="10.1007/978-3-031-13188-2\{_}10", isbn="978-3-031-13187-5", issn="0302-9743" }