Richard Mayr

Date: 16:00, Tuesday, November 4, 2014
Speaker: Richard Mayr
Venue: IST Austria
Notes:

16:00 – 17:00 

Consider nondeterministic finite automata (NFA) 
and nondeterministic Buchi automata (NBA), which describe regular 
languages and omega-regular languages, respectively.
Central problems for these are computationally hard (PSPACE-complete), e.g.,
checking language inclusion, equivalence and universality, 
as well as finding automata of minimal size for a given language.

In spite of the high worst-case complexity, recent algorithms and
software-tools can solve many instances of nontrivial size. 
Here we give an overview over these techniques. They include antichain techniques 
exploiting logical subsumption, the construction of congruence bases,
and automata minimization methods based on transition pruning 
and state-space quotienting w.r.t. generalized simulation preorders.
In particular, multipebble simulations and the more practical
lookahead simulations can in polynomial time compute very good
under-approximations of the PSPACE-complete relations of 
(trace-)language inclusion.
A collection of current papers and tools is available at www.languageinclusion.org.
Posted in RiSE Seminar