Minimizing nondeterministic automata: From words to trees
Richard Mayr ( University of Edinburgh; currently on sabbatical at Oxford )
This talk gives an overview on recent methods tominimize nondeterministic automata.In particular, we focus on the differences between word automata and tree automata.Moreover, we discuss some algorithmic problems in approximating the PSPACE/EXPTIME-complete word/tree language inclusion.(Further reading: www.languageinclusion.org)
Richard Mayr received a Msc in computer science from
TU-Munich, Germany, (1994) and a PhD in computer science from
He received scholarships from the DAAD and the DFG in support
of his research at the University of Edinburgh, UK, (1999) and the
University of Paris 7, France, (2000), and completed his Habilitation
for Informatics at the University of Freiburg, Germany, in 2002.
He was assistant professor at the University of Freiburg (2001-2004)
and at North Carolina State University, USA, (2004-2007).
In 2008 he was appointed to the post of Lecturer at the School
of Informatics (LFCS) at the University of Edinburgh, UK.
His research interests include automated verification,
automata and temporal logic, model-checking and semantic
equivalence checking, formal verification of real-time and
probabilistic systems, infinite-state Markov chains
and stochastic games.