A Tight Lower Bound for Streett Complementation

Abstract

Finite automata on infinite words ($ω$-automata) proved to be a powerful weapon for modeling and reasoning infinite behaviors of reactive systems. Complementation of $ω$-automata is crucial in many of these applications. But the problem is non-trivial; even after extensive study during the past four decades, we still have an important type of $ω$-automata, namely Streett automata, for which the gap between the current best lower bound $2^{Ω(n \lg nk)}$ and upper bound $2^{Ω(nk \lg nk)}$ is substantial, for the Streett index size $k$ can be exponential in the number of states $n$. In arXiv:1102.2960 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=ω(n)$. In this paper we establish a matching lower bound $2^{Ω(n \lg n+nk \lg k)}$ for $k = O(n)$ and $2^{Ω(n^{2} \lg n)}$ for $k = ω(n)$, and therefore showing that the construction is asymptotically optimal with respect to the $2^{Θ(\cdot)}$ notation.

Typo correction and section reorganization. To appear in the proceeding of the 31st Foundations of Software Technology and Theoretical Computer Science conference (FSTTCS 2011)