Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/8266
Title: Succinctness of the complement and intersection of regular expressions
Authors: GELADE, Wouter 
NEVEN, Frank 
Issue Date: 2008
Publisher: LABRI-LABORATOIRE BORDELAIS RECHERCHE INFORMATIQUE
Source: Albers, S Weil, P (Ed.) STACS 2008: PROCEEDINGS OF THE 25TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE. p. 325-336.
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 worst-case 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 by-product, 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 four-letter alphabet. When the given regular expressions are one-unambiguous, 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 single-occurrence regular expressions, we prove a tight exponential lower bound for intersection.
Notes: Hasselt Univ, Diepenbeek, Belgium.Gelade, W, Hasselt Univ, Diepenbeek, Belgium.
Document URI: http://hdl.handle.net/1942/8266
Link to publication: http://drops.dagstuhl.de/opus/volltexte/2008/1354/
ISBN: 978-3-939897-06-4
ISI #: 000254982900027
Category: C1
Type: Proceedings Paper
Validations: ecoom 2009
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
stacs08.pdfPreprint181.59 kBAdobe PDFView/Open
Show full item record

WEB OF SCIENCETM
Citations

13
checked on May 22, 2022

Page view(s)

54
checked on May 20, 2022

Download(s)

92
checked on May 20, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.