THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS
Markus Holzer, Martin Kutrib · International Journal of Foundations of Computer Science · 2011
We summarize results on the complexity of regular(-like) expressions and tour a fragment of the literature. In particular we focus on the descriptional complexity of the conversion of regular expressions to equivalent finite automata and vice versa, to the computational complexity of problems on regular-like expressions such as, e.g., membership, inequivalence, and non-emptiness of complement, and finally on the operation problem measuring the required size for transforming expressions with additional language operations (built-in or not) into equivalent ordinary regular expressions.