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 . 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 . 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 , 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.
|Commitee:||Guda, Chittibabu, Murray, Neil|
|School:||State University of New York at Albany|
|School Location:||United States -- New York|
|Source:||DAI-B 71/05, Dissertation Abstracts International|
|Keywords:||Extended expressions, Language, Pattern matching, Regular expressions|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be