Inclusion problems for formal languages

It is a classic phenomenon in formal language theory that inclusion between languages is hard to decide: For context-free languages, it is undecidable, and already for NFAs, the problem is PSPACE-complete. However, recent work by various authors has shown that under some restrictions on the input languages, deciding inclusion is surprisingly tractable and admits interesting new techniques. The talk will survey such results (and open problems), with a focus on non-regular languages.

Authors

• Georg Zetzsche

Keywords

No keywords are indexed for this paper.