Computer science colloquia: Ting Zhang
| Date/Time: | Thursday, 04 Feb 2010 at 3:40 pm |
|---|---|
| Location: | 223 Atanasoff |
| Cost: | Free |
| Phone: | 515-294-6516 |
| Channel: | College of Liberal Arts and Sciences |
| Categories: | Lectures |
| Actions: | Download iCal/vCal | Email Reminder |
Automata on infinite words have wide application in logic, formal languages and program verification. Automata complementation plays a central role in these applications and is of particular importance for automata with rich acceptance conditions, such as Rabin automata and Streett automata, because they can express properties much more naturally and succinctly.
Obtaining tight complexity bounds on automata complementation has been difficult. For the Rabin complementation and Streett complementation, significant gaps existed between the best lower and upper bounds. In previous work, using Multidimensional Ranking Functions combined with a Pumping-Lemma argument, we established an essentially tight lower bound for Rabin complementation. In this talk, we show a tight bound for Streett complementation, improving from both presently known lower and upper bounds. We also show an improved upper bound for the complementation of Parity automata, which have obtained the central position in logic games and program synthesis. This is a joint work with Yang Cai at Computer Science, Department of Massachusetts Institute of Technology.
Dr. Ting Zhang is an assistant professor of computer science. He received his Ph.D. in computer science from Stanford University in 2006, and also holds a B.S. in computer science from Peking University. His current research interests include Temporal Logic, Automata Theory, Automated Reasoning and their
applications to Program Analysis and Verification. Prior to joining Iowa State, he was a researcher at Microsoft Research Asia.