\input zb-basic
\input zb-ioport
\iteman{io-port 06073863}
\itemau{Holzer, Markus; Kutrib, Martin}
\itemti{The complexity of regular(-like) expressions.}
\itemso{Int. J. Found. Comput. Sci. 22, No. 7, 1533-1548 (2011).}
\itemab
Summary: 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, on 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.
\itemrv{~}
\itemcc{}
\itemut{regular expressions; finite automata; transformations; descriptional complexity; computational complexity; formal language problems; operation problems}
\itemli{doi:10.1142/S0129054111008866}
\end