An effective algorithm for the membership problem for extended regular expressions

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

By adding the complement operator (¬), 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 Ω(n2) and time Ω(n3); since in many practical applications n can be very large, these space and time requirements could be prohibitive. In this paper we present an ERE membership algorithm that runs in space O(n- (log n + m) ·2m) and time O(n2 · (logri + m) · 2m). The presented algorithm outperforms the best known algorithms when n is exponentially larger than m.

Original languageEnglish (US)
Title of host publicationFoundations of Software Science and Computational Structures - 10th International Conference, FOSSACS 2007. Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007
PublisherSpringer
Pages332-345
Number of pages14
ISBN (Print)3540713883, 9783540713883
DOIs
StatePublished - 2007
Event10th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2007 - Braga, Portugal
Duration: Mar 24 2007Apr 1 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4423 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2007
Country/TerritoryPortugal
CityBraga
Period3/24/074/1/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'An effective algorithm for the membership problem for extended regular expressions'. Together they form a unique fingerprint.

Cite this