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
Uniform vs. Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)ORCID iD: 0000-0002-4696-9787
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Foundations of Language Processing)
2016 (English)In: Algorithms, ISSN 1999-4893, E-ISSN 1999-4893, Vol. 9, no 2, 32Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
MDPI , 2016. Vol. 9, no 2, 32
Keyword [en]
mildly context sensitive languages, parsing, formal languages, parameterized complexity
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-120238DOI: 10.3390/a9020032ISI: 000379833700011OAI: oai:DiVA.org:umu-120238DiVA: diva2:927418
Projects
Parameterized Natural Language Parsing
Funder
Swedish Research Council, 621-2011-6080
Available from: 2016-05-12 Created: 2016-05-12 Last updated: 2017-11-30Bibliographically approved

Open Access in DiVA

fulltext(576 kB)29 downloads
File information
File name FULLTEXT01.pdfFile size 576 kBChecksum SHA-512
37130584032e69c1653cadc3b1ae55c61d5726c2d27fa5fc0fe7f69dc8fbda8dff2963d673aa05f3d98c58054c60b7588bda6a4087c430a3f69979a934cace3c
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Björklund, HenrikBerglund, MartinPetter, Ericson
By organisation
Department of Computing Science
In the same journal
Algorithms
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 29 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 120 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