Skip to content
printicon
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.

Keywords

Formal languages, interleaving, membership problems, shuffle languages

Authors

Back Edit this report
Entry responsible: Martin Berglund

Page Responsible: Frank Drewes
2022-09-30