Detail publikačního výsledku

Complementing Büchi Automata with Ranker

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

Originální název

Complementing Büchi Automata with Ranker

Anglický název

Complementing Büchi Automata with Ranker

Druh

Stať ve sborníku v databázi WoS či Scopus

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.

Anglický 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

Klíčová slova v angličtině

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

Autoři

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

Rok RIV

2023

Vydáno

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