umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On Regular Expressions with Backreferences and Transducers
Stellenbosch University.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0001-7349-7693
University of Stellenbosch.
2018 (Engelska)Ingår i: 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, s. 49-64Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Österreichische Computer Gesellschaft , 2018. s. 49-64
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-149995ISBN: 978-3-903035-21-8 (tryckt)OAI: oai:DiVA.org:umu-149995DiVA, id: diva2:1229457
Konferens
10th Workshop on Non-Classical Models of Automata and Applications (NCMA 2018), Košice, Slovakia, August 21 - 22, 2018
Tillgänglig från: 2018-06-30 Skapad: 2018-06-30 Senast uppdaterad: 2019-07-19Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

URL

Personposter BETA

Drewes, Frank

Sök vidare i DiVA

Av författaren/redaktören
Drewes, Frank
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 835 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf