Skip to main content

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)

Speaker bio

Richard Mayr received a Msc in computer science from TU-Munich, Germany, (1994) and a PhD in computer science from TU-Munich (1998). 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.

Share this: