liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Complexity of CCG Parsing
Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2492-9872
Univ Padua, Italy.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
2018 (English)In: Computational linguistics - Association for Computational Linguistics (Print), ISSN 0891-2017, E-ISSN 1530-9312, Vol. 44, no 3, p. 447-482Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
MIT PRESS , 2018. Vol. 44, no 3, p. 447-482
National Category
Language Technology (Computational Linguistics)
Identifiers
URN: urn:nbn:se:liu:diva-152098DOI: 10.1162/coli_a_00324ISI: 000445216700004OAI: oai:DiVA.org:liu-152098DiVA, id: diva2:1256684
Available from: 2018-10-17 Created: 2018-10-17 Last updated: 2018-11-12

Open Access in DiVA

fulltext(285 kB)32 downloads
File information
File name FULLTEXT01.pdfFile size 285 kBChecksum SHA-512
407d3d5fa42ab5a4e257b219f2cc5d0829066d1dbfca69713c12230569a75622b4a9b9fd8e81f123745dd238422210dc5947ec3ce5c4d7f5d0aba933ee97f924
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Kuhlmann, MarcoJonsson, Peter
By organisation
Human-Centered systemsFaculty of Science & EngineeringSoftware and Systems
In the same journal
Computational linguistics - Association for Computational Linguistics (Print)
Language Technology (Computational Linguistics)

Search outside of DiVA

GoogleGoogle Scholar
Total: 32 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 45 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf