License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1854
URN: urn:nbn:de:0030-drops-18543
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1854/
Go to the corresponding LIPIcs Volume Portal

Schewe, Sven

Büchi Complementation Made Tight

pdf-format:
09001.ScheweSven.1854.pdf (0.2 MB)

Abstract

The precise complexity of complementing B\"uchi\ automata is an intriguing and long standing problem. While optimal complementation techniques for finite automata are simple -- it suffices to determinize them using a simple subset construction and to dualize the acceptance condition of the resulting automaton -- B\"uchi\ complementation is more involved. Indeed, the construction of an EXPTIME complementation procedure took a quarter of a century from the introduction of B\"uchi\ automata in the early $60$s, and stepwise narrowing the gap between the upper and lower bound to a simple exponent (of $(6e)^n$ for B\"uchi\ automata with $n$ states) took four decades. While the distance between the known upper ($O\big((0.96\,n)^n\big)$) and lower ($\Omega\big((0.76\,n)^n\big)$) bound on the required number of states has meanwhile been significantly reduced, an exponential factor remains between them. Also, the upper bound on the size of the complement automaton is not linear in the bound of its state space. These gaps are unsatisfactory from a theoretical point of view, but also because B\"uchi\ complementation is a useful tool in formal verification, in particular for the language containment problem. This paper proposes a B\"uchi\ complementation algorithm whose complexity meets, modulo a quadratic ($O(n^2)$) factor, the known lower bound for B\"uchi\ complementation. It thus improves over previous constructions by an exponential factor and concludes the quest for optimal B\"uchi\ complementation algorithms.

BibTeX - Entry

@InProceedings{schewe:LIPIcs:2009:1854,
  author =	{Sven Schewe},
  title =	{{B{\"u}chi Complementation Made Tight}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{661--672},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1854},
  URN =		{urn:nbn:de:0030-drops-18543},
  doi =		{10.4230/LIPIcs.STACS.2009.1854},
  annote =	{Keywords: Automata and formal languages, Buchi complementation, Automata theory, Nondeterministic Buchi automata}
}

Keywords: Automata and formal languages, Buchi complementation, Automata theory, Nondeterministic Buchi automata
Collection: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI