Minimalist Grammar Transition-Based Parsing

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Current chart-based parsers of Minimalist Grammars exhibit prohibitively high polynomial complexity that makes them unusable in practice. This paper presents a transition-based parser for Minimalist Grammars that approximately searches through the space of possible derivations by means of beam search, and does so very efficiently: the worst case complexity of building one derivation is O(n2) and the best case complexity is O(n). This approximated inference can be guided by a trained probabilistic model that can condition on larger context than standard chart-based parsers. The transitions of the parser are very similar to the transitions of bottom-up shift-reduce parsers for Context-Free Grammars, with additional transitions for online reordering of words during parsing in order to make non-projective derivations projective.
Original languageEnglish
Title of host publicationProceedings of Logical Aspects of Computational Linguistics 2016
Place of PublicationNancy, France
PublisherSpringer Berlin Heidelberg
Pages273-290
Number of pages28
ISBN (Electronic)978-3-662-53826-5
ISBN (Print)978-3-662-53825-8
DOIs
Publication statusPublished - 2016
EventLogical Aspects of Computational Linguistics 2016 - Nancy, France
Duration: 5 Dec 20167 Dec 2016
http://lacl.gforge.inria.fr/lacl-2016/index-presentation.html

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Berlin, Heidelberg
Volume10054
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameTheoretical Computer Science and General Issues
Volume10054

Conference

ConferenceLogical Aspects of Computational Linguistics 2016
Abbreviated titleLACL 2016
CountryFrance
CityNancy
Period5/12/167/12/16
Internet address

Fingerprint Dive into the research topics of 'Minimalist Grammar Transition-Based Parsing'. Together they form a unique fingerprint.

Cite this