A Tight Lower Bound for Streett Complementation

Details A Tight Lower Bound for Streett Complementation A Tight Lower Bound for Streett Complementation

2011-02-15

arxiv.org/abs/1102.2963v3

Computer Science

Logic in Computer Science

Typo correction and section reorganization. To appear in the proceeding of the 31st Foundations of Software Technology and The

Scientific paper

Finite automata on infinite words ($\omega$-automata) proved to be a powerful weapon for modeling and reasoning infinite behaviors of reactive systems. Complementation of $\omega$-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 $\omega$-automata, namely Streett automata, for which the gap between the current best lower bound $2^{\Omega(n \lg nk)}$ and upper bound $2^{\Omega(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=\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 $2^{\Theta(\cdot)}$ notation.

Affiliated with

Also associated with

No associations

Rating

A Tight Lower Bound for Streett Complementation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Tight Lower Bound for Streett Complementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Tight Lower Bound for Streett Complementation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377837