liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the Complexity of CCG Parsing
Linköpings universitet, Institutionen för datavetenskap, Interaktiva och kognitiva system. Linköpings universitet, Tekniska fakulteten.ORCID-id: 0000-0002-2492-9872
Univ Padua, Italy.
Linköpings universitet, Institutionen för datavetenskap, Programvara och system. Linköpings universitet, Tekniska fakulteten.
2018 (engelsk)Inngår i: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 44, nr 3, s. 447-482Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir (1994). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir (1994) apart from weakly equivalent formalisms such as Tree Adjoining Grammar, for which parsing can be performed in time polynomial in the combined size of grammar and input sentence. Our results contribute to a refined understanding of the class of mildly context-sensitive grammars, and inform the search for new, mildly context-sensitive versions of CCG.

sted, utgiver, år, opplag, sider
MIT PRESS , 2018. Vol. 44, nr 3, s. 447-482
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-152098DOI: 10.1162/coli_a_00324ISI: 000445216700004OAI: oai:DiVA.org:liu-152098DiVA, id: diva2:1256684
Tilgjengelig fra: 2018-10-17 Laget: 2018-10-17 Sist oppdatert: 2018-11-12

Open Access i DiVA

fulltext(285 kB)32 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 285 kBChecksum SHA-512
407d3d5fa42ab5a4e257b219f2cc5d0829066d1dbfca69713c12230569a75622b4a9b9fd8e81f123745dd238422210dc5947ec3ce5c4d7f5d0aba933ee97f924
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekst

Søk i DiVA

Av forfatter/redaktør
Kuhlmann, MarcoJonsson, Peter
Av organisasjonen
I samme tidsskrift
Computational linguistics - Association for Computational Linguistics (Print)

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 32 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 45 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf