Regular Expressions with Nested Levels of Back Referencing Form a Hierarchy

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review


For many years, regular expressions with back referencing have been used in a variety of software products in common use, including operating systems, editors, and programming languages. In these products, regular expressions have been extended with a naming construct. If a subexpression is named by some variable, whenever this subexpression matches some string, that string is assigned to the variable. Later occurrences of the same variable will then match the string assigned to it. This construction greatly increases the power of regular expressions and is useful in text searching as well as in text substitution in large documents. We study the nested usage of this operator, and prove that the power of the expressions increase with the number of nested levels that are allowed.
TidsskriftInformation Processing Letters
Udgave nummer4
Sider (fra-til)169-172
StatusUdgivet - 1998

Fingeraftryk Dyk ned i forskningsemnerne om 'Regular Expressions with Nested Levels of Back Referencing Form a Hierarchy'. Sammen danner de et unikt fingeraftryk.