Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Richard Mayr

LFCS Seminar: Richard Mayr

— filed under:

Automata Minimization and Language Inclusion Checking

What
  • LFCS Seminar
When Feb 05, 2013
from 04:00 PM to 05:00 PM
Contact Name
Add event to calendar vCal
iCal

Checking language inclusion of nondeterministic Buchi word automata is PSPACE-complete, and so are related problems like language equivalence and language universality. While many algorithms exist (Rank, Ramsey, Safra, Piterman, Slice) they can
only handle very small instances. We present a different approach based on automata minimization, i.e., finding smaller automata with the same language (see our POPL 2013 paper). The minimization uses quotienting and transition pruning techniques, using the semantic relations of trace-inclusion (and multipebble simulation). Since these relations are themselves PSPACE-complete, we describe efficient algorithms to compute good under-approximations of them. These methods minimize automata substantially better than previous techniques and help to solve language inclusion problems for much larger instances. An implementation of the tools is available at www.languageinclusion.org

References:

Lorenzo Clemente and Richard Mayr. Advanced Automata Minimization. POPL 2013.
http://arxiv.org/abs/1210.6624

Document Actions