Publication Details

Complementing Büchi Automata with Ranker (Technical Report)

HAVLENA Vojtěch, LENGÁL Ondřej and ŠMAHLÍKOVÁ Barbora. Complementing Büchi Automata with Ranker (Technical Report). Ithaca: Cornell University Library, 2022. Available from: https://arxiv.org/abs/2206.01946
Czech title
Komplementace Büchiho automatů pomocí Rankeru (technická zpráva)
Type
technical report
Language
english
Authors
Havlena Vojtěch, Ing., Ph.D. (DITS FIT BUT)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Šmahlíková Barbora, Ing. (FIT BUT)
URL
Keywords

Büchi automata, complementation, rank-based complementation, omega-regular languages

Abstract

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.

Published
2022
Pages
16
Publisher
Cornell University Library
Place
Ithaca, US
DOI
10.48550/arXiv.2206.01946
BibTeX 
@TECHREPORT{FITPUB12768,
   author = "Vojt\v{e}ch Havlena and Ond\v{r}ej Leng\'{a}l and Barbora \v{S}mahl\'{i}kov\'{a}",
   title = "Complementing B{\"{u}}chi Automata with Ranker (Technical Report)",
   pages = 16,
   year = 2022,
   location = "Ithaca, US",
   publisher = "Cornell University Library",
   doi = "10.48550/arXiv.2206.01946",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12768"
}
Back to top