COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Beyond regular: Pattern matching with extended regular expressions
by Carle, Benjamin, Ph.D., State University of New York at Albany, 2010, 60; 3402517
Abstract (Summary)

Regular expression pattern matching or some variant thereof is present in almost all software that deal with textual data. In this work we have considered three types of extensions to the traditional regular expression, or regex pattern matching format. Regex pattern matching tools such as those in the Unix utility egrep and the popular scripting language Perl commonly include extended functionality beyond the classical definition of regular expressions. The main focus is on Extended Regular Expressions as studied by Câmpeanu, Salomaa and Yu [1]. We offer an additional pumping lemma that will show that a new class of languages is not recognizable by extended regular expressions and discuss closure properties, decidability, and complexity issues relating to these languages.

Another extension of the regular languages considered is the class of Extended Multi-Pattern Languages (EMPL), introduced by Nagy in [2]. We show that this class is a strict subclass of the family of languages recognized by extended regular expressions and discuss the decidability of the equivalence problem for these languages.

Synchronized Regular Expressions, as introduced by Penna, Intrigila, Tronci and Zilli [3], extend the EREG languages by allowing exponent variables that range over the natural numbers. We offer some clarifications of the matching semantics and a surprising result regarding linear synchronized regular expressions. A simplified proof of the language of palindromes is provided, showing that the family of languages defined by synchronized regular expressions is not a superset of the context-free languages.

Finally, we provide an overview of the relative expressive power of these three classes of languages and relate them to other significant language classes. In conclusion we discuss some current and potential future applications of extended pattern matching and some open problems.

Indexing (document details)
Advisor: Narendran, Paliath
Commitee: Guda, Chittibabu, Murray, Neil
School: State University of New York at Albany
Department: Computer Science
School Location: United States -- New York
Source: DAI-B 71/05, Dissertation Abstracts International
Subjects: Computer science
Keywords: Extended expressions, Language, Pattern matching, Regular expressions
Publication Number: 3402517
ISBN: 978-1-109-74654-9
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy