Testing extended regular language membership incrementally by rewriting

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

Abstract

In this paper we present lower bounds and rewriting algorithms for testing membership of a word in a regular language described by an extended regular expression. Motivated by intuitions from monitoring and testing, where the words to be tested (execution traces) are typically much longer than the size of the regular expressions (patterns or requirements), and by the fact that in many applications the traces are only available incrementally, on an event by event basis, our algorithms are based on an event-consumption idea: a just arrived event is “consumed” by the regular expression, i.e., the regular expression modifies itself into another expression discarding the event. We present an exponential space lower bound for monitoring extended regular expressions and argue that the presented rewriting-based algorithms, besides their simplicity and elegance, are practical and almost as good as one can hope. We experimented with and evaluated our algorithms in Maude.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsRobert Nieuwenhuis
PublisherSpringer
Pages499-514
Number of pages16
ISBN (Print)3540402543, 9783540402541
DOIs
StatePublished - 2003
Event14th International Conference on Rewriting Techniques and Applications, RTA 2003 - Valencia, Spain
Duration: Jun 9 2003Jun 11 2003

Publication series

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

Other

Other14th International Conference on Rewriting Techniques and Applications, RTA 2003
Country/TerritorySpain
CityValencia
Period6/9/036/11/03

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Testing extended regular language membership incrementally by rewriting'. Together they form a unique fingerprint.

Cite this