On the Computational Complexity of Head Movement and Affix Hopping

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

Abstract

Head movement is a syntactic operation used in most generative syntactic analyses. However, its computational properties have not been extensively studied. Stabler (2001) formalises head movement in the framework of Minimalist Grammars by extending the item representation to allow for easy extraction of the head. This work shows that Stabler’s representation is in fact suboptimal because it causes higher polynomial parsing complexity. A new algorithm is derived for parsing head movement and affix hopping by changing the kinds of representations that the parser deals with. This algorithm has much better asymptotic worst-case runtime of O(n2k+5). This result makes parsing head movement and affix hopping computationally as efficient as parsing a single phrase movement.
Original languageEnglish
Title of host publicationFormal Grammar 2019
Subtitle of host publication24th International Conference, FG 2019, Riga, Latvia, August 10-11, 2019, Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages101-116
Number of pages16
ISBN (Electronic)978-3-662-59648-7
ISBN (Print)978-3-662-59647-0
DOIs
Publication statusE-pub ahead of print - 5 Jul 2019
Event24th Conference on Formal Grammar - Riga, Latvia
Duration: 10 Aug 201911 Aug 2019
http://fg.phil.hhu.de/2019/

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer, Cham
ISSN (Electronic)0302-9743

Conference

Conference24th Conference on Formal Grammar
Abbreviated titleFG 2019
CountryLatvia
CityRiga
Period10/08/1911/08/19
Internet address

Fingerprint Dive into the research topics of 'On the Computational Complexity of Head Movement and Affix Hopping'. Together they form a unique fingerprint.

Cite this