License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.112
URN: urn:nbn:de:0030-drops-32269
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3226/
Go to the corresponding LIPIcs Volume Portal

Cai, Yang ; Zhang, Ting

Tight Upper Bounds for Streett and Parity Complementation

pdf-format:
13.pdf (0.6 MB)

Abstract

Complementation of finite automata on infinite words is not only a fundamental problem in automata theory, but also serves as a cornerstone for solving numerous decision problems in mathematical logic, model-checking, program analysis and verification. For Streett complementation, a significant gap exists between the current lower bound 2^{Omega(n*log(n*k))} and upper bound 2^{O(n*k*log(n*k))}, where n is the state size, k is the number of Streett pairs, and k can be as large as 2^{n}. Determining the complexity of Streett complementation has been an open question since the late 80's. In this paper we show a complementation construction with upper bound 2^{O(n*log(n)+n*k*log(k))} for k=O(n) and 2^{O(n^{2}*log(n))} for k=Omega(n), which matches well the lower bound obtained in the paper arXiv:1102.2963. We also obtain a tight upper bound 2^{O(n*log(n))} for parity complementation.

BibTeX - Entry

@InProceedings{cai_et_al:LIPIcs:2011:3226,
  author =	{Yang Cai and Ting Zhang},
  title =	{{Tight Upper Bounds for Streett and Parity Complementation}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{112--128},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Marc Bezem},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3226},
  URN =		{urn:nbn:de:0030-drops-32269},
  doi =		{10.4230/LIPIcs.CSL.2011.112},
  annote =	{Keywords: Streett automata, omega-automata, parity automata, complementation, upper bounds}
}

Keywords: Streett automata, omega-automata, parity automata, complementation, upper bounds
Collection: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue Date: 2011
Date of publication: 31.08.2011

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