Linear Time Membership in a Class of Regular Expressions with Counting, Interleaving, and Unordered Concatenation

摘要

Regular Expressions (REs) are ubiquitous in database and programming languages. While many applications make use of REs extended with interleaving (shuffle) and unordered concatenation operators, this extension badly affects the complexity of basic operations, and, especially, makes membership NP-hard, which is unacceptable in most practical scenarios.