Splittability of Bilexical Context-Free Grammars is Undecidable.
Saved in:
| Title: | Splittability of Bilexical Context-Free Grammars is Undecidable. |
|---|---|
| Authors: | Nederhof, Mark-Jan1 markjan.nederhof@gmail.com, Satta, Giorgio2 satta@dei.unipd.it |
| Source: | Computational Linguistics. Sep2011, Vol. 37 Issue 3, Special section p1-23. 23p. |
| Subjects: | Linguistic String Parser (Computer grammar), Lexical-functional grammar, Lexicon, Parsing (Grammar), Content analysis, Document style semantics & specification language, Corpora |
| Abstract: | Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(|w|4), where w is the input string. A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotically improved to O(|w|³). Testing this property is therefore of central interest to parsing efficiency. However, in this article we show the negative result that splittability of 2-LCFGs is undecidable. [ABSTRACT FROM AUTHOR] |
| Copyright of Computational Linguistics is the property of MIT Press and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 69934063 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Splittability of Bilexical Context-Free Grammars is Undecidable. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Nederhof%2C+Mark-Jan%22">Nederhof, Mark-Jan</searchLink><relatesTo>1</relatesTo><i> markjan.nederhof@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Satta%2C+Giorgio%22">Satta, Giorgio</searchLink><relatesTo>2</relatesTo><i> satta@dei.unipd.it</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Computational+Linguistics%22">Computational Linguistics</searchLink>. Sep2011, Vol. 37 Issue 3, Special section p1-23. 23p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Linguistic+String+Parser+%28Computer+grammar%29%22">Linguistic String Parser (Computer grammar)</searchLink><br /><searchLink fieldCode="DE" term="%22Lexical-functional+grammar%22">Lexical-functional grammar</searchLink><br /><searchLink fieldCode="DE" term="%22Lexicon%22">Lexicon</searchLink><br /><searchLink fieldCode="DE" term="%22Parsing+%28Grammar%29%22">Parsing (Grammar)</searchLink><br /><searchLink fieldCode="DE" term="%22Content+analysis%22">Content analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Document+style+semantics+%26+specification+language%22">Document style semantics & specification language</searchLink><br /><searchLink fieldCode="DE" term="%22Corpora%22">Corpora</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(|w|4), where w is the input string. A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotically improved to O(|w|³). Testing this property is therefore of central interest to parsing efficiency. However, in this article we show the negative result that splittability of 2-LCFGs is undecidable. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Computational Linguistics is the property of MIT Press and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=69934063 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1162/COLI_a_00079 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 23 StartPage: 1 Subjects: – SubjectFull: Linguistic String Parser (Computer grammar) Type: general – SubjectFull: Lexical-functional grammar Type: general – SubjectFull: Lexicon Type: general – SubjectFull: Parsing (Grammar) Type: general – SubjectFull: Content analysis Type: general – SubjectFull: Document style semantics & specification language Type: general – SubjectFull: Corpora Type: general Titles: – TitleFull: Splittability of Bilexical Context-Free Grammars is Undecidable. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Nederhof, Mark-Jan – PersonEntity: Name: NameFull: Satta, Giorgio IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 09 Text: Sep2011 Type: published Y: 2011 Identifiers: – Type: issn-print Value: 08912017 Numbering: – Type: volume Value: 37 – Type: issue Value: 3 Titles: – TitleFull: Computational Linguistics Type: main |
| ResultId | 1 |
