Journalartikel
Autorenliste: Holzer, Markus; Kutrib, Martin
Jahr der Veröffentlichung: 2011
Seiten: 1533-1548
Zeitschrift: International Journal of Foundations of Computer Science
Bandnummer: 22
Heftnummer: 7
ISSN: 0129-0541
eISSN: 1793-6373
DOI Link: https://doi.org/10.1142/S0129054111008866
Verlag: 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.
Zitierstile
Harvard-Zitierstil: 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-Zitierstil: 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
Schlagwörter
BOUNDS; computational complexity; DESCRIPTIONAL COMPLEXITY; EPSILON-FREE NFA; FINITE AUTOMATA; FOLLOW; formal language problems; LOOP COMPLEXITY; operation problems; Regular expressions
