Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique

Details Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique

2008-02-08

arxiv.org/abs/0802.1226v3

LMCS-2007-244

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-4(1:5)2008

In this paper, we first introduce a lower bound technique for the state complexity of transformations of automata. Namely we suggest first considering the class of full automata in lower bound analysis, and later reducing the size of the large alphabet via alphabet substitutions. Then we apply such technique to the complementation of nondeterministic \omega-automata, and obtain several lower bound results. Particularly, we prove an \omega((0.76n)^n) lower bound for B\"uchi complementation, which also holds for almost every complementation or determinization transformation of nondeterministic omega-automata, and prove an optimal (\omega(nk))^n lower bound for the complementation of generalized B\"uchi automata, which holds for Streett automata as well.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique 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 Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds for Complementation of omega-Automata Via the Full Automata Technique will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-402614