Publication detail

Complementing Büchi Automata with Ranker

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

Original Title

Complementing Büchi Automata with Ranker

Type

conference paper

Language

English

Original 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.

Keywords

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

Authors

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

Released

7. 8. 2022

Publisher

Springer Verlag

Location

Haifa

ISBN

978-3-031-13187-5

Book

Proceedings of the 34th International Conference on Computer Aided Verification

ISBN

0302-9743

Periodical

Lecture Notes in Computer Science

Number

13372

State

Federal Republic of Germany

Pages from

188

Pages to

201

Pages count

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