Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/13171

Title: Succinctness of the Complement and Intersection of Regular Expressions
Authors: Gelade, Wouter
Neven, Frank
Issue Date: 2012
Citation: ACM Transactions on Computational Logic, 13(1), (ART N° 4)
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, cannot 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, that is, 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 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.
URI: http://hdl.handle.net/1942/13171
DOI: 10.1145/2071368.207137
ISI #: 000300196400004
ISSN: 1529-3785
Category: A1
Type: Journal Contribution
Validation: ecoom, 2013
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Main article301.73 kBAdobe PDF
Preprint430.9 kBAdobe PDF

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