Browse by Topic

Locality and the Complexity of Minimalist Derivation Tree Languages

Graf, Thomas

Abstract Minimalist grammars provide a formalization of Minimalist syntax which allows us to study how the components of said theory affect its expressivity. A central concern of Minimalist syntax is the locality of the displacement operation Move. In Minimalist grammars, however, Move is unbounded. This paper is a study of the repercussions of limiting movement with respect to the number of slices a moved constituent is allowed to cross, where a slice is the derivation tree equivalent of the phrase projected by a lexical item in the derived tree. I show that this locality condition 1) has no effect on weak generative capacity 2) has no effect on a Minimalist derivation tree language’s recognizability by top-down automata 3) renders Minimalist derivation tree languages strictly locally testable, whereas their unrestricted counterparts aren’t even locally threshold testable.

Files [pdf] [code]

  author    = {Graf, Thomas},
  title     = {Locality and the Complexity of {M}inimalist Derivation Tree
  year      = {2012},
  booktitle = {{F}ormal {G}rammar 2010\slash 2011},
  pages     = {208--227},
  editor    = {de Groot, Philippe and Nederhof, Mark-Jan},
  volume    = {7395},
  series    = {Lecture Notes in Computer Science},
  address   = {Heidelberg},
  publisher = {Springer},
  doi       = {10.1007/978-3-642-32024-8_14},
  url       = {}