Cai, Yang ;
Zhang, Ting
A Tight Lower Bound for Streett Complementation
Abstract
Finite automata on infinite words (omegaautomata) proved to be a powerful weapon for modeling and reasoning infinite behaviors of reactive systems. Complementation of omegaautomata is crucial
in many of these applications. But the problem is nontrivial; even after extensive study during the past two decades, we still have an important type of omegaautomata, namely Streett automata, for which the gap between the current best lower bound 2^(Omega(n lg nk)) and upper bound 2^(O (nk lg nk)) is substantial, for the Streett index size k can be exponential in the number of states n. In a previous work we showed a construction for complementing Streett automata with the upper bound 2^(O(n lg n+nk lg k)) for k = O(n) and 2^(O(n^2 lg n)) for k = omega(n). In this paper we establish a matching lower bound 2^(Omega (n lg n+nk lg k)) for k = O(n) and 2^(Omega
(n^2 lg n)) for k = omega(n), and therefore showing that the construction is asymptotically optimal with respect to the ^(Theta(.)) notation.
BibTeX  Entry
@InProceedings{cai_et_al:LIPIcs:2011:3347,
author = {Yang Cai and Ting Zhang},
title = {{A Tight Lower Bound for Streett Complementation}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
pages = {339350},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897347},
ISSN = {18688969},
year = {2011},
volume = {13},
editor = {Supratik Chakraborty and Amit Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3347},
URN = {urn:nbn:de:0030drops33474},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2011.339},
annote = {Keywords: omegaautomata, Streett automata, complementation, lower bounds}
}
Keywords: 

omegaautomata, Streett automata, complementation, lower bounds 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Issue date: 

2011 
Date of publication: 

2011 