Informatik-Logo Technischen Berichte der
Fakultät für Informatik
Technischen Universität München

[Übersicht]    [Suchen]    [Ausgewählte Publikationen Ausgewählte Publikationen]
Suche: Citkey=TUM-I0814
Als [bib] [pdf] [ps] [dvi] [xml]  herunterladen.

Language Operations with Regular Expressions of Polynomial Size Publikation auswählen
Hermann Gruber, Markus Holzer
Technical Report, 2008

Revision-Date:  2008-05-01
Category:  Technical Report
Format:   Postscript, gzipped
PDF, gzipped
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 can 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 in size. For the latter operation, at least an almost quadratic blow-up can be necessary in the worst case.
Classification:  F.1.1 F.4.3
Keywords:   regular expressions, derivatives, language quotient, cyclic shift, circular shift, descriptional complexity
Version:  1.0
Length:  16 Pages