Christian Wartena:

    Extending LIGs

    Abstract

    Linear Indexed Grammars (LIGs) can be used to describe non--local dependencies. The indexing mechanism however can only account for dependencies that are nested. In natural languages one can easily find examples in which this simple model cannot be applied straightforwardly. In this talk I will show that a formalism fitting better to linguistic structures can be obtained by using a sequence of pushdowns instead of one pushdown for the storage of the indices in a derivation. Crucially, we haveto avoid unwanted interactions between the pushdowns that would make possible the simulation of a turing machine. Cherubini et al.(1996) solves this problem for multi-pushdown automata by restricting reading to the first non--empty pushdown. I will argue that the corresponding restriction on writing is more natural from a linguistic point of view. I will show that, under each of both restrictions, grammars with a sequence of n pushdowns give rise to a subclass of the n-th member of the hierarchy defined by Weir (1988,1992), and therefore are mildly context sensitive.