Home
Scholarly Works
Fast Algorithms for Extended Regular Expression...
Conference

Fast Algorithms for Extended Regular Expression Matching and Searching

Abstract

Extended regular expressions are an extension of ordinary regular expressions by the operations of intersection and complement. We give new algorithms for extended regular expression matching and searching which improve significantly the (very old) best upper bound for this problem, due to Hopcroft and Ullman. For an extended regular expression of size m with p intersection and complement operators and an input word of length n our algorithms run in time O(mn2) and space O(pn2) while the one of Hopcroft and Ullman runs in time O(mn3) and space O(mn2). Since the matching problem for semiextended regular expressions (only intersection is added) has been very recently shown to be LOGCFL complete, our algorithms are very likely the best one can expect. We also emphasize the importance of the extended regular expressions for software programs currently using ordinary regular expressions and show how the algorithms presented can be improved to run significantly faster in practical applications.

Authors

Ilie L; Shan B; Yu S

Series

Lecture Notes in Computer Science

Volume

2607

Pagination

pp. 179-190

Publisher

Springer Nature

Publication Date

January 1, 2003

DOI

10.1007/3-540-36494-3_17

Conference proceedings

Lecture Notes in Computer Science

ISSN

0302-9743
View published work (Non-McMaster Users)

Contact the Experts team