Linear time membership in a class of regular expressions with interleaving and counting
Giorgio Ghelli, Dario Colazzo, Carlo Sartiani · 2008
The extension of Regular Expressions (REs) with an interleaving (shuffle) operator has been proposed in many occasions, since it would be crucial to deal with unordered data. However, interleaving badly affects the complexity of basic operations, and, expecially, makes membership NP-hard [13], which is unacceptable for most uses of REs.