Detail publikace

Complementing Büchi Automata with Ranker (Technical Report)

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

Originální název

Complementing Büchi Automata with Ranker (Technical Report)

Typ

zpráva odborná

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

6. 6. 2022

Nakladatel

Cornell University Library

Místo

Ithaca

Strany počet

16

URL

https://arxiv.org/abs/2206.01946

BibTex

@techreport{BUT178225,
  author="Vojtěch {Havlena} and Ondřej {Lengál} and Barbora {Šmahlíková}",
  title="Complementing Büchi Automata with Ranker (Technical Report)",
  year="2022",
  publisher="Cornell University Library",
  address="Ithaca",
  pages="16",
  doi="10.48550/arXiv.2206.01946",
  url="https://arxiv.org/abs/2206.01946"
}