1 Search Results for "Havlena, Vojtěch"

Reducing (To) the Ranks: Efficient Rank-Based Büchi Automata Complementation

Authors: Vojtěch Havlena and Ondřej Lengál

Published in: LIPIcs, Volume 203, 32nd International Conference on Concurrency Theory (CONCUR 2021)

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.

Cite as

Vojtěch Havlena and Ondřej Lengál. Reducing (To) the Ranks: Efficient Rank-Based Büchi Automata Complementation. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 203, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

  author =	{Havlena, Vojt\v{e}ch and Leng\'{a}l, Ond\v{r}ej},
  title =	{{Reducing (To) the Ranks: Efficient Rank-Based B\"{u}chi Automata Complementation}},
  booktitle =	{32nd International Conference on Concurrency Theory (CONCUR 2021)},
  pages =	{2:1--2:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-203-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{203},
  editor =	{Haddad, Serge and Varacca, Daniele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2021.2},
  URN =		{urn:nbn:de:0030-drops-143799},
  doi =		{10.4230/LIPIcs.CONCUR.2021.2},
  annote =	{Keywords: B\"{u}chi automata, rank-based complementation, super-tight runs}
  • Refine by Author
  • 1 Havlena, Vojtěch
  • 1 Lengál, Ondřej

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects

  • Refine by Keyword
  • 1 Büchi automata
  • 1 rank-based complementation
  • 1 super-tight runs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail