Valid Identity Problem for Shuffle Regular Expressions
Albert R. Meyer, Alexander Rabinovich · 2002
We show that the following problem is decidable: given are expressions $E_1$ and $E_2$ constructed from variables by the regular operations and shuffle. Is the identity $E_1=E_2$ true for all instantiations of its variables by formal languages?