liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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 (Engelska)Ingår i: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 44, nr 3, s. 447-482Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
MIT PRESS , 2018. Vol. 44, nr 3, s. 447-482
Nationell ämneskategori
Språkteknologi (språkvetenskaplig databehandling)
Identifikatorer
URN: urn:nbn:se:liu:diva-152098DOI: 10.1162/coli_a_00324ISI: 000445216700004OAI: oai:DiVA.org:liu-152098DiVA, id: diva2:1256684
Tillgänglig från: 2018-10-17 Skapad: 2018-10-17 Senast uppdaterad: 2018-11-12

Open Access i DiVA

fulltext(285 kB)34 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 285 kBChecksumma SHA-512
407d3d5fa42ab5a4e257b219f2cc5d0829066d1dbfca69713c12230569a75622b4a9b9fd8e81f123745dd238422210dc5947ec3ce5c4d7f5d0aba933ee97f924
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Kuhlmann, MarcoJonsson, Peter
Av organisationen
Interaktiva och kognitiva systemTekniska fakultetenProgramvara och system
I samma tidskrift
Computational linguistics - Association for Computational Linguistics (Print)
Språkteknologi (språkvetenskaplig databehandling)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 34 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 46 träffar
RefereraExporteraLänk till posten
Permanent länk

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