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
Uniform vs. Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)ORCID-id: 0000-0002-4696-9787
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Foundations of Language Processing)
2016 (Engelska)Ingår i: Algorithms, ISSN 1999-4893, E-ISSN 1999-4893, Vol. 9, nr 2, artikel-id 32Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

Parsing for mildly context-sensitive language formalisms is an important area within natural language processing. While the complexity of the parsing problem for some such formalisms is known to be polynomial, this is not the case for all of them. This article presents a series of results regarding the complexity of parsing for linear context-free rewriting systems and deterministic tree-walking transducers. We discuss the difference between uniform and nonuniform complexity measures and how parameterized complexity theory can be used to investigate how different aspects of the formalisms influence how hard the parsing problem is. The main results we survey are all hardness results and indicate that parsing is hard even for relatively small values of parameters such as rank and fan-out in a rewriting system.

Ort, förlag, år, upplaga, sidor
MDPI , 2016. Vol. 9, nr 2, artikel-id 32
Nyckelord [en]
mildly context sensitive languages, parsing, formal languages, parameterized complexity
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-120238DOI: 10.3390/a9020032ISI: 000379833700011OAI: oai:DiVA.org:umu-120238DiVA, id: diva2:927418
Projekt
Parameterized Natural Language Parsing
Forskningsfinansiär
Vetenskapsrådet, 621-2011-6080Tillgänglig från: 2016-05-12 Skapad: 2016-05-12 Senast uppdaterad: 2018-06-07Bibliografiskt granskad

Open Access i DiVA

fulltext(576 kB)75 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 576 kBChecksumma SHA-512
37130584032e69c1653cadc3b1ae55c61d5726c2d27fa5fc0fe7f69dc8fbda8dff2963d673aa05f3d98c58054c60b7588bda6a4087c430a3f69979a934cace3c
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Personposter BETA

Björklund, HenrikBerglund, MartinPetter, Ericson

Sök vidare i DiVA

Av författaren/redaktören
Björklund, HenrikBerglund, MartinPetter, Ericson
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Algorithms
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 75 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

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