Skip to content
printicon
Show report in:

UMINF 12.09

The Membership Problem for the Shuffle of Two Deterministic Linear Context-Free Languages is NP-complete

Formal language models which employ shuffling, or interleaving, of strings are of interest in many areas of computer science. Notable examples include system verification, plan recognition, and natural language processing. Membership problems for the shuffle of languages are especially interesting. It is known that deciding membership for shuffles of regular languages can be done in polynomial time, and that deciding (non-uniform) membership in the shuffle of two deterministic context-free languages is NP-complete. In this paper we narrow the gap by showing that the non-uniform membership problem for the shuffle of two deterministic *linear* context-free languages is NP-complete.

Keywords

formal languages, interleaving, membership problems, shuffle languages

Authors

Back Edit this report
Entry responsible: Martin Berglund

Page Responsible: Frank Drewes
2022-09-30