Abstract
We study the succinctness of the complement and intersection of
regular expressions. In particular, we show that when constructing
a regular expression defining the complement of a given regular
expression, a double exponential size increase cannot be avoided.
Similarly, when constructing a regular expression defining the
intersection of a fixed and an arbitrary number of regular
expressions, an exponential and double exponential size increase,
respectively, can in worstcase not be avoided. All mentioned
lower bounds improve the existing ones by one exponential and are
tight in the sense that the target expression can be constructed in
the corresponding time class, i.e., exponential or double
exponential time. As a byproduct, we generalize a theorem by
Ehrenfeucht and Zeiger stating that there is a class of DFAs which
are exponentially more succinct than regular expressions, to a
fixed fourletter alphabet. When the given regular expressions are
oneunambiguous, as for instance required by the XML Schema
specification, the complement can be computed in polynomial time
whereas the bounds concerning intersection continue to hold. For
the subclass of singleoccurrence regular expressions, we prove a
tight exponential lower bound for intersection.
BibTeX  Entry
@InProceedings{gelade_et_al:LIPIcs:2008:1354,
author = {Wouter Gelade and Frank Neven},
title = {{Succinctness of the Complement and Intersection of Regular Expressions}},
booktitle = {25th International Symposium on Theoretical Aspects of Computer Science},
pages = {325336},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897064},
ISSN = {18688969},
year = {2008},
volume = {1},
editor = {Susanne Albers and Pascal Weil},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1354},
URN = {urn:nbn:de:0030drops13541},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2008.1354},
annote = {Keywords: }
}
Seminar: 

25th International Symposium on Theoretical Aspects of Computer Science 
Issue Date: 

2008 
Date of publication: 

06.02.2008 