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.