Output details
11 - Computer Science and Informatics
University of St Andrews
Return to search
Output 0 of 0 in the submission
Article title
Splittability of bilexical context-free grammars is undecidable
Type
D - Journal article
Title of journal
Computational Linguistics
Article number
-
Volume number
37
Issue number
4
First page of article
867
ISSN of journal
0891-2017
Year of publication
2011
Number of additional authors
1
Additional information
<22>Bilexical context-free grammars are a component in a considerable number of natural language parsers used today. In general, the running time of parsing with these grammars is O(|w|^4), where |w| denotes the length of a sentence. This is often too expensive in practice, which is why there have been attempts to restrict grammars to a form allowing O(|w|^3) parsing. This paper shows that it is undecidable whether an existing grammar can be brought into this restricted form. This brings central concepts used in NLP for the last 10 years into a clearer perspective.
Interdisciplinary
-
Cross-referral requested
-
Research group
C - Artificial intelligence
Citation count
0
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
