Skip to content
Show report in:

UMINF 11.01

Recognizing Shuffled Languages

Language models that use interleaving, or shuffle, operators have applications in various areas of computer science, including system verification, plan recognition, and natural language processing. We study the complexity of the membership problem for such models, i.e., how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.


Formal languages, interleaving, shuffle languages, membership problems


Back Edit this report
Entry responsible: Martin Berglund

Page Responsible: Frank Drewes