Succinctness of the Complement and Intersection of Regular Expressions

Details Succinctness of the Complement and Intersection of Regular Expressions Succinctness of the Complement and Intersection of Regular Expressions

2008-02-20

arxiv.org/abs/0802.2869v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Succinctness of the Complement and Intersection of Regular Expressions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Succinctness of the Complement and Intersection of Regular Expressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinctness of the Complement and Intersection of Regular Expressions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647945