Name
Abstract | ||
|---|---|---|
Automata on infinite words (omega-automata) have wide applications in formal language theory as well as in modeling and verifying reactive systems. Complementation of omega-automata is a crucial instrument in many these applications, and hence there have been great interests in determining the state complexity of the complementation problem. However, obtaining nontrivial lower bounds has been difficult. For the complementation of Rabin automata, a significant gap exists between the state-of-the-art lower bound 2Omega(NlgN) and upper bound 2O(kNlgN), where k, the number of Rabin pairs, can be as large as 2N. In this paper we introduce multidimensional rankings to the full automata technique. Using the improved technique we establish an almost tight lower bound for the complementation of Rabin automata. We also show that the same lower bound holds for the determinization of Rabin automata. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/LICS.2009.13 | LICS |
Keywords | DocType | ISSN |
automata theory,full automata,rabin automata,complementation,graduate students e.a,automatic verification technique,model checking,state complexity,state-transition system,infinite word,formal language theory,computational complexity,omega-automata,formal languages,joint paper,improved lower bound,a.p. sistla,upper bound,determinization,rabin automata technique,finite-state abstraction,lower bound,reactive system,data mining,construction industry,bismuth,formal language,automata | Conference | 1043-6871 |
ISBN | Citations | PageRank |
978-0-7695-3746-7 | 5 | 0.45 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yang Cai | 1 | 330 | 25.53 |
| Ting Zhang | 2 | 15 | 3.36 |
| Haifeng Luo | 3 | 27 | 2.44 |