Detail publikačního výsledku

Reducing (to) the Ranks: Efficient Rank-based Büchi Automata Complementation

HAVLENA, V.; LENGÁL, O.

Originální název

Reducing (to) the Ranks: Efficient Rank-based Büchi Automata Complementation

Anglický název

Reducing (to) the Ranks: Efficient Rank-based Büchi Automata Complementation

Druh

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

Originální abstrakt

This paper provides several optimizations of the rank-based approach for complementing Büchi automata. We start with Schewe's theoretically optimal construction and develop a set of techniques for pruning its state space that are key to obtaining small complement automata in practice. In particular, the reductions (except one) have the property that they preserve (at least some) so-called super-tight runs, which are runs whose ranking is as tight as possible. Our evaluation on a large benchmark shows that the optimizations indeed significantly help the rank-based approach and that, in a large number of cases, the obtained complement is the smallest from those produced by state-of-the-art tools for Büchi complementation.

Anglický abstrakt

This paper provides several optimizations of the rank-based approach for complementing Büchi automata. We start with Schewe's theoretically optimal construction and develop a set of techniques for pruning its state space that are key to obtaining small complement automata in practice. In particular, the reductions (except one) have the property that they preserve (at least some) so-called super-tight runs, which are runs whose ranking is as tight as possible. Our evaluation on a large benchmark shows that the optimizations indeed significantly help the rank-based approach and that, in a large number of cases, the obtained complement is the smallest from those produced by state-of-the-art tools for Büchi complementation.

Klíčová slova

Büchi automata,rank-based complementation,super-tight runs

Klíčová slova v angličtině

Büchi automata,rank-based complementation,super-tight runs

Autoři

HAVLENA, V.; LENGÁL, O.

Rok RIV

2022

Vydáno

23.08.2021

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo

Paris

Kniha

32nd International Conference on Concurrency Theory (CONCUR 2021)

ISSN

1868-8969

Periodikum

Leibniz International Proceedings in Informatics, LIPIcs

Svazek

203

Číslo

8

Stát

neuvedeno

Strany od

1

Strany do

19

Strany počet

19

URL

https://doi.org/10.4230/LIPIcs.CONCUR.2021.2

BibTex

@inproceedings{BUT175801,
  author="Vojtěch {Havlena} and Ondřej {Lengál}",
  title="Reducing (to) the Ranks: Efficient Rank-based Büchi Automata Complementation",
  booktitle="32nd International Conference on Concurrency Theory (CONCUR 2021)",
  year="2021",
  journal="Leibniz International Proceedings in Informatics, LIPIcs",
  volume="203",
  number="8",
  pages="1--19",
  publisher="Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
  address="Paris",
  doi="10.4230/LIPIcs.CONCUR.2021.2",
  issn="1868-8969",
  url="https://doi.org/10.4230/LIPIcs.CONCUR.2021.2"
}