Complementing Büchi Automata with Ranker
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F22%3APU144772" target="_blank" >RIV/00216305:26230/22:PU144772 - isvavai.cz</a>
Result on the web
<a href="https://www.fit.vut.cz/research/publication/12767/" target="_blank" >https://www.fit.vut.cz/research/publication/12767/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-13188-2_10" target="_blank" >10.1007/978-3-031-13188-2_10</a>
Alternative languages
Result language
angličtina
Original language name
Complementing Büchi Automata with Ranker
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 34th International Conference on Computer Aided Verification
ISBN
978-3-031-13187-5
ISSN
0302-9743
e-ISSN
—
Number of pages
14
Pages from-to
188-201
Publisher name
Springer Verlag
Place of publication
Haifa
Event location
Haifa
Event date
Aug 7, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000870310500010