Umeå University's logo

umu.sePublications
EnglishSvenskaNorsk
Change search
ExportLink to record
Permanent link

Direct link
BETA

Project

Project type/Form of grant
Project grant
Title [sv]
Parametriserad syntaktisk analys för naturliga språk
Title [en]
Parameterized Natural Language Parsing
Abstract [sv]
Language technology, including natural language processing, is a wide area of great scientific and commercial interest. Parsing, i.e., analysis of syntactic structure, is still a bottleneck in many such applications.We propose a detailed study of the time complexity of natural language parsing problems. A number of different grammatical frameworks have been suggested in the literature. We wish to study them in order to find out which aspects of such frameworks make parsing too expensive and under what conditions parsing is tractable. The complexity of parsing problems has been studied before, but the classifications these studies have yielded is generally to coarse. We want to study in more detail how various aspects of the grammatical frameworks contribute to the parsing complexity.As a main tool in our study, we will employ the theory of parameterized complexity, which is ideally suited for isolating the factors that contribute the most to the complexity. Once we have investigated under which conditions parsing is tractable, we want to turn our results into concrete algorithms that can be evaluated empirically. The goal is to help developers of natural language processing applications to choose the tools best suited for the specific needs of their applications.
Principal InvestigatorBjörklund, Henrik
Coordinating organisation
Umeå University
Funder
Period
2012-01-01 － 2015-12-31
National Category
Computer ScienceLanguage Technology (Computational Linguistics)
Identifiers
DiVA, id: project:1146Project, id: 2011-06080_VR
v. 2.44.0
|
WCAG
|
Umeå University Library
|
Register in DiVA
|
Support
|
Search DiVA Portal