Can Nondeterminism Help Complementation?

Details Can Nondeterminism Help Complementation? Can Nondeterminism Help Complementation?

2011-10-26

arxiv.org/abs/1110.5942v3

Computer Science

Logic in Computer Science

22 pages, 5 figures

Scientific paper

Complementation and determinization are two fundamental notions in automata theory. The close relationship between the two has been well observed in the literature. In the case of nondeterministic finite automata on finite words (NFA), complementation and determinization have the same state complexity, namely $\Theta(2^{n})$ where $n$ is the state size. The same similarity between determinization and complementation was found for B\"{u}chi automata, where both operations were shown to have $2^{\Theta(n \lg n)}$ state complexity. Of theoretical interest is whether there exists a type of $\omega$-automata whose determinization is considerably harder than its complementation. In this paper, we show that for all common type $\omega$-automata, the determinization problem has the same state complexity as the corresponding complementation problem at the granularity of $2^{\Theta(\cdot)}$.

Affiliated with

Also associated with

No associations

Rating

Can Nondeterminism Help 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 Can Nondeterminism Help Complementation?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Can Nondeterminism Help Complementation? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-374838