TY - GEN
T1 - Locality and the complexity of minimalist derivation tree languages
AU - Graf, Thomas
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - first-order logic
KW - locality
KW - Minimalist grammars
KW - subregular tree languages
KW - top-down tree automata
UR - https://www.scopus.com/pages/publications/84865497557
U2 - 10.1007/978-3-642-32024-8_14
DO - 10.1007/978-3-642-32024-8_14
M3 - Conference contribution
AN - SCOPUS:84865497557
SN - 9783642320231
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 208
EP - 227
BT - Formal Grammar - 16th International Conference, FG 2011, Revised Selected Papers
T2 - 16th International Conference on Formal Grammar, FG 2011
Y2 - 6 August 2011 through 7 August 2011
ER -