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
The Output Size Problem for String-to-Tree Transducers
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Natural and Formal Languages)ORCID-id: 0000-0001-7349-7693
University of Stellenbosch.
University of Stellenbosch.
2016 (Engelska)Ingår i: / [ed] A. Maletti, 2016Konferensbidrag, Enbart muntlig presentation (Övrigt vetenskapligt)
Abstract [en]

The output size problem, for a string-to-tree transducer, is to determine the rate of growth of the function describing the maximum size of output trees, with respect to the length of the input strings. We study the complexity of this problem. Our motivation is that a solution to the output size problem can be used in order to determine the worst-case matching time (for a given regular expression) of a backtracking regular expression matcher, with respect to the length of the input strings.

Ort, förlag, år, upplaga, sidor
2016.
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-122472OAI: oai:DiVA.org:umu-122472DiVA, id: diva2:939167
Konferens
Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2016), Seoul, South Korea, July 18, 2016
Tillgänglig från: 2016-06-17 Skapad: 2016-06-17 Senast uppdaterad: 2019-06-26Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

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

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 665 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