Finite automata over infinite structures - Tight bounds for some transformations

20^th 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.