Department Seminar Series
Finite automata over infinite structures - Tight bounds for some transformations
20th January 2015, 14:00
Ashton Lecture Theater
Thomas Varghese
Computer Science Department
University of Liverpool
Abstract
Finite automata over infinite structures (or: omega-automata) and games of infinite duration on finite graphs are essential tools in algorithmic verification and synthesis. Determinisation and complementation are two transformations on omega-automata that are particularly important. We provide an overview of results on tight bounds for these transformations and expand on some techniques used to obtain these tight bounds.
Maintained by Othon Michail