Abstract
The shuffle operator models communication free concurrency and has little expressive power (it does not produce new languages when added to regular expressions). Decidability problems for languages involving this operation were previously tackled but remained unsolved (except for a weak conjecture). We prove that language equivalence is undecidable even for a very restricted class of expressions involving the shuffle operator. This also re-proves that language equivalence is undecidable for Basic Parallel Processes.
Get full access to this article
View all access options for this article.