• Hans-Martin Gärtner & Jens Michaelis. A Note on the Complexity of Constraint Interaction: Locality Conditions and Minimalist Grammars. Paper presented at the conference Logical Aspects of Computational Linguistics (LACL `05), Bordeaux, April 28-30, 2005. Appeared in: P. Blache, E. Stabler, J. Busquets and R. Moot (eds.), Logical Aspects of Computational Linguistics, LNCS/LNAI Vol. 3492, pp. 114-130, Springer, Berlin, Heidelberg, 2005.

Abstract

Locality Conditions (LCs) on (unbounded) dependencies have played a major role in the development of generative syntax ever since the seminal work by Ross (1967). Descriptively, they fall into two groups. On the one hand there are intervention-based LCs (ILCs) often formulated as "minimality constraints" ("minimal link condition," "minimize chain links," "shortest move," "attract closest," etc.). On the other hand there are containment-based LCs (CLCs) typically defined in terms of (generalized) grammatical functions ("adjunct island," "subject island," "specifier island," etc.). Research on LCs has been dominated by two very general trends. First, attempts have been made at unifying ILCs and CLCs on the basis of notions such as "government" and "barrier" (e.g. Chomsky 1986). Secondly, research has often been guided by the intuition that, beyond empirical coverage, LCs somehow contribute to restricting the formal capacity of grammars (cf. Comsky 1977-p. 125, 2001-p. 14f). Both these issues, we are going to argue, can be fruitfully studied within the framework of minimalist grammars (MGs) as defined by Stabler (1997). In particular, we are going to demonstrate that there is a specific asymmetry between the influence of ILCs and CLCs on complexity. Thus, MGs, including an ILC, namely, the shortest move condition (SMC) have been shown to belong to the mildly context-sensitive grammar formalisms by Michaelis (2001). The same has been shown in Michaelis 2001, 2002 for a revised version of MGs introduced in Stabler 1999, which includes the SMC and an additional CLC, namely, the specifier island condition (SPIC). In particular Michaelis 2001 and Michaelis 2002 show that, in terms of derivable string languages, both the original MG-type and the revised MG-type constitute a subclass of the class of linear context-free rewriting systems (LCFRSs) in the sense of Vijay-Shanker et al. 1987, and thus, a series of other formalism classes all generating the same class of string languages as LCFRSs. Here we will demonstrate that removing the SMC from the revised MG-version increases the generative power in such a way that the resulting formalism is not mildly context-sensitive anymore. This suggests that intuitions to the contrary notwithstanding, imposing an LC as such, here the SPIC, does not necessarily reduce formal complexity.

previous page personal homepage