Journal article
Authors list: Holzer, Markus; Kutrib, Martin
Publication year: 2011
Pages: 1533-1548
Journal: International Journal of Foundations of Computer Science
Volume number: 22
Issue number: 7
ISSN: 0129-0541
eISSN: 1793-6373
DOI Link: https://doi.org/10.1142/S0129054111008866
Publisher: World Scientific Publishing
Abstract:
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.
Citation Styles
Harvard Citation style: Holzer, M. and Kutrib, M. (2011) THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS, International Journal of Foundations of Computer Science, 22(7), pp. 1533-1548. https://doi.org/10.1142/S0129054111008866
APA Citation style: Holzer, M., & Kutrib, M. (2011). THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS. International Journal of Foundations of Computer Science. 22(7), 1533-1548. https://doi.org/10.1142/S0129054111008866
Keywords
BOUNDS; computational complexity; DESCRIPTIONAL COMPLEXITY; EPSILON-FREE NFA; FINITE AUTOMATA; FOLLOW; formal language problems; LOOP COMPLEXITY; operation problems; Regular expressions
