Conference paper

Publication year: 2009

Pages: 3281-3289

Journal: Theoretical Computer Science

Volume number: 410

Issue number: 35

ISSN: 0304-3975

DOI Link: https://doi.org/10.1016/j.tcs.2009.04.009

Conference: 10th International Workshop on Descriptional Complexity of Formal Systems

Publisher: Elsevier

Abstract: 
This work deals with questions regarding to what extent regularity-preserving language operations affect the descriptional complexity of regular expressions. Some language operations are identified which are feasible for regular expressions in the sense that the result of the operation call be represented as a regular expression of size polynomial in that of the operands. We prove that taking language quotients, in particular the prefix and suffix closures, of a regular set can incur at most a quadratic blow-up on the required expression size. The circular shift operation can cause only a cubic increase ill size and at least a quadratic bloat can be necessary in the worst case. (C) 2009 Elsevier B.V. All rights reserved.

Harvard Citation style: Gruber, H. and Holzer, M. (2009) Language operations with regular expressions of polynomial size, Theoretical Computer Science, 410(35), pp. 3281-3289. https://doi.org/10.1016/j.tcs.2009.04.009

APA Citation style: Gruber, H., & Holzer, M. (2009). Language operations with regular expressions of polynomial size. Theoretical Computer Science. 410(35), 3281-3289. https://doi.org/10.1016/j.tcs.2009.04.009