Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Re-examining regular expressions with backreferences
Centre for AI Research, CSIR, Department of Information Science, Stellenbosch University, South Africa.ORCID iD: 0000-0002-3692-6994
Department of Computer Science, Stellenbosch University, South Africa.ORCID iD: 0000-0001-5010-9934
2023 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 940, p. 66-80Article in journal (Refereed) Published
Abstract [en]

Most modern regular expression matching libraries (one of the rare exceptions being Google's RE2) allow backreferences, operations which bind a substring to a variable, allowing it to be matched again verbatim. However, both real-world implementations and definitions in the literature use different syntactic restrictions and have differences in the semantics of the matching of backreferences. Our aim is to compare these various flavors by considering the classes of formal languages that each can describe, establishing, as a result, a hierarchy of language classes. Beyond the hierarchy itself, some complexity results are given, and as part of the effort on comparing language classes new pumping lemmas are established, old classes are extended to new ones, and several incidental results on the nature of these language classes are given.

Place, publisher, year, edition, pages
Elsevier, 2023. Vol. 940, p. 66-80
Keywords [en]
Regular expressions, Backreferences
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-200951DOI: 10.1016/j.tcs.2022.10.041Scopus ID: 2-s2.0-85141509500OAI: oai:DiVA.org:umu-200951DiVA, id: diva2:1710142
Available from: 2022-11-11 Created: 2022-11-11 Last updated: 2023-04-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Berglund, Martin

Search in DiVA

By author/editor
Berglund, Martinvan der Merwe, Brink
In the same journal
Theoretical Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 144 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf