IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

An Effective Algorithm for the Membership Problem for Extended Regular Expressions

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/11167

Files in this item

File Description Format
PDF An Effective Al ... ed Regular Expressions.pdf (228KB) (no description provided) PDF
Title: An Effective Algorithm for the Membership Problem for Extended Regular Expressions
Author(s): Rosu, Grigore
Subject(s): algorithms
Abstract: By adding the complement operator (\neg), extended regular expressions ({\ERE}) can encode regular languages non-elementarily more succinctly than regular expressions. The {\ERE} membership problem asks whether a word w of size n belongs to the language of an {\ERE} R of size m. Unfortunately, the best known membership algorithms are either non-elementary in m or otherwise require space \Omega(n^2) and time \Omega(n^3); since in many practical applications n can be very large (in the order of billions, e.g., in testing where w represents the execution trace of some system), these space and time requirements could be prohibitive. In this paper we present a simple to implement {\ERE} membership algorithm that runs in space O(n \cdot (m + \log n) \cdot 2^{m} \cdot k) and in time O(n^2 \cdot (m + \log n)^2 \cdot 2^m \cdot k), where k is the number of complement operators in R. The presented algorithm outperforms the best known algorithms when n is large.
Issue Date: 2005-08
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/11167
Other Identifier(s): UIUCDCS-R-2005-2694
Rights Information: You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS: 2009-04-20
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 178
  • Downloads this Month: 4
  • Downloads Today: 0

Browse

My Account

Information

Access Key