Speaker: Qiqi Yan Shanghai Jiao Tong University
Time: 2007-04-20 15:30-2007-04-20 16:30
Venue: FIT Building,Tsinghua University

Abstract:

Ranking-based constructions have been proposed for the complementation of various types of omega-automata. Compared to previous methods which usually involve Safra's construction, they are simpler to understand or to implement, and have better complexity upperbounds as well. In the first part of this talk, we first present Kupferman and Vardi's construction, which applies co-Buchi rankings to complement nondeterministic Buchi word automata. In the second part, we present our work published in ICALP06, showing that the idea of co-Buchi rankings can be applied to lowerbound analysis as well to obtain many sharper lower bound results.
 

Short Bio:

Qiqi Yan is from the BASICS Laboratory of Shanghai Jiao Tong University, where he got his Bachelor and Master degrees. He has worked on the areas of automata theory and formal languages, finite model theory etc. during his master study, and has written one ICALP paper plus one TCS paper.