View in EDS PDF Full Text

Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication.

Saved in:
Bibliographic Details
Title: Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication.
Authors: Cohen, Shay B.1 scohen@inf.ed.ac.uk, Gildea, Daniel2 gildea@cs.rochester.edu
Source: Computational Linguistics. Sep2016, Vol. 42 Issue 3, p421-455. 35p.
Subjects: Parsing (Computer grammar), Rewriting systems (Computer science), Speech perception, Boolean matrices, Matrix multiplications, Computational linguistics
Abstract: We describe a recognition algorithm for a subset of binary linear context-free rewriting systems (LCFRS) with running time O(nωd) where M(m) = O(mω) is the running time for m × m matrix multiplication and d is the "contact rank" of the LCFRS-the maximal number of combination and non-combination points that appear in the grammar rules. We also show that this algorithm can be used as a subroutine to obtain a recognition algorithm for general binary LCFRS with running time O(nωd+1). The currently best known ω is smaller than 2.38. Our result provides another proof for the best known result for parsing mildly context-sensitive formalisms such as combinatory categorial grammars, head grammars, linear indexed grammars, and tree-adjoining grammars, which can be parsed in time O(n4.76). It also shows that inversion transduction grammars can be parsed in time O(n5.76). In addition, binary LCFRS subsumes many other formalisms and types of grammars, for some of which we also improve the asymptotic complexity of parsing. [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: 118276495
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Cohen%2C+Shay+B%2E%22">Cohen, Shay B.</searchLink><relatesTo>1</relatesTo><i> scohen@inf.ed.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Gildea%2C+Daniel%22">Gildea, Daniel</searchLink><relatesTo>2</relatesTo><i> gildea@cs.rochester.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Computational+Linguistics%22">Computational Linguistics</searchLink>. Sep2016, Vol. 42 Issue 3, p421-455. 35p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Parsing+%28Computer+grammar%29%22">Parsing (Computer grammar)</searchLink><br /><searchLink fieldCode="DE" term="%22Rewriting+systems+%28Computer+science%29%22">Rewriting systems (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Speech+perception%22">Speech perception</searchLink><br /><searchLink fieldCode="DE" term="%22Boolean+matrices%22">Boolean matrices</searchLink><br /><searchLink fieldCode="DE" term="%22Matrix+multiplications%22">Matrix multiplications</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+linguistics%22">Computational linguistics</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We describe a recognition algorithm for a subset of binary linear context-free rewriting systems (LCFRS) with running time O(nωd) where M(m) = O(mω) is the running time for m × m matrix multiplication and d is the "contact rank" of the LCFRS-the maximal number of combination and non-combination points that appear in the grammar rules. We also show that this algorithm can be used as a subroutine to obtain a recognition algorithm for general binary LCFRS with running time O(nωd+1). The currently best known ω is smaller than 2.38. Our result provides another proof for the best known result for parsing mildly context-sensitive formalisms such as combinatory categorial grammars, head grammars, linear indexed grammars, and tree-adjoining grammars, which can be parsed in time O(n4.76). It also shows that inversion transduction grammars can be parsed in time O(n5.76). In addition, binary LCFRS subsumes many other formalisms and types of grammars, for some of which we also improve the asymptotic complexity of parsing. [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=118276495
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1162/COLI_a_00254
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 35
        StartPage: 421
    Subjects:
      – SubjectFull: Parsing (Computer grammar)
        Type: general
      – SubjectFull: Rewriting systems (Computer science)
        Type: general
      – SubjectFull: Speech perception
        Type: general
      – SubjectFull: Boolean matrices
        Type: general
      – SubjectFull: Matrix multiplications
        Type: general
      – SubjectFull: Computational linguistics
        Type: general
    Titles:
      – TitleFull: Parsing Linear Context-Free Rewriting Systems with Fast Matrix Multiplication.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Cohen, Shay B.
      – PersonEntity:
          Name:
            NameFull: Gildea, Daniel
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 08912017
          Numbering:
            – Type: volume
              Value: 42
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: Computational Linguistics
              Type: main
ResultId 1