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 | Source: | 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. | Keywords: | Complexity; regular expressions; intersection; complement; succinctness; XML schema languages | Document URI: | http://hdl.handle.net/1942/13171 | ISSN: | 1529-3785 | e-ISSN: | 1557-945X | DOI: | 10.1145/2071368.207137 | ISI #: | 000300196400004 | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2013 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
a4-gelade.pdf Restricted Access | Published version | 301.73 kB | Adobe PDF | View/Open Request a copy |
401neven.pdf | Non Peer-reviewed author version | 430.9 kB | Adobe PDF | View/Open |
WEB OF SCIENCETM
Citations
15
checked on Oct 14, 2024
Page view(s)
78
checked on Sep 6, 2022
Download(s)
108
checked on Sep 6, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.