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
On Regular Expressions with Backreferences and Transducers
Stellenbosch University.
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0001-7349-7693
University of Stellenbosch.
2018 (English)In: Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA 2018) / [ed] Rudolf Freund, Michal Hospodár, Galina Jirásková, Giovanni Pighizzini, Österreichische Computer Gesellschaft , 2018, p. 49-64Conference paper, Published paper (Refereed)
Abstract [en]

Modern regular expression matching software features many extensions, some general, while some are very narrowly specified. Here we consider the generalization of adding a class of operators which can be described by, e.g. finite-state transducers. Combined with backreferences, they enable new classes of languages to be matched. The addition of finite-state transducers is shown to make membership testing undecidable. Following this result, we study the complexity of membership testing for various restricted cases of the model.

Place, publisher, year, edition, pages
Österreichische Computer Gesellschaft , 2018. p. 49-64
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-149995ISBN: 978-3-903035-21-8 (print)OAI: oai:DiVA.org:umu-149995DiVA, id: diva2:1229457
Conference
10th Workshop on Non-Classical Models of Automata and Applications (NCMA 2018), Košice, Slovakia, August 21 - 22, 2018
Available from: 2018-06-30 Created: 2018-06-30 Last updated: 2019-07-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

URL

Authority records BETA

Drewes, Frank

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 431 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