View Related Documents

Abstract

Linear indexed grammars (LIGs) can be used to describe nonlocal dependencies. The indexing mechanism, however, can only account for dependencies that are nested. In natural languages one can easily find examples to which this simple model cannot be applied straight forwardly. In this paper 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 have to avoid unwanted interactions between the push-downs that would make possible the simulation of a turing machine. [1] solves this problem for multi– pushdown automata by restricting reading to the first nonempty 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 nth member of the hierarchy defined by [15,16], and therefore are mildly context sensitive.

Fulltext Preview

Image of the first page of the fulltext document