Cai, Yang ;
Zhang, Ting
Tight Upper Bounds for Streett and Parity Complementation
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, modelchecking, 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 = {112128},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897323},
ISSN = {18688969},
year = {2011},
volume = {12},
editor = {Marc Bezem},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3226},
URN = {urn:nbn:de:0030drops32269},
doi = {http://dx.doi.org/10.4230/LIPIcs.CSL.2011.112},
annote = {Keywords: Streett automata, omegaautomata, parity automata, complementation, upper bounds}
}
2011
Keywords: 

Streett automata, omegaautomata, parity automata, complementation, upper bounds 
Seminar: 

Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL

Related Scholarly Article: 


Issue date: 

2011 
Date of publication: 

2011 