THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS
We summarize complexity (-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.
descriptional complexity regular expressions finite automata computational complexity operation problems transformations formal language problems