Undecidability Results for Shuffle Languages
Joanna Jędrzejowicz · Journal of automata, languages and combinatorics · 1996
We consider shuffle languages which are an extension of regular languages with two operators, that is shuffle (sometimes called interleaving) and shuffle closure. The class of shuffle languages is a proper subset of context-sensitive languages, incomparable with context-free ones. For this class we give two undecidability results. First of all we show that the intersection emptiness problem for shuffle languages is undecidable and then we prove that there is no algorithm to determine the shuffle closure height of shuffle expressions.