Free Indexation: Combinatorial Analysis and A Compositional Algorithm

Free Indexation: Combinatorial Analysis and A Compositional Algorithm* Sandiway Fong 545 Technology Square, Rm. NE43-810, MIT Artificial Intelligence Laboratory, Cambridge MA 02139 Internet: sandiway@ai.mit.edu Abstract The principle known as 'free indexation' plays an important role in the determination of the refer- ential properties of noun phrases in the principle- and-parameters language framework. First, by in- vestigating the combinatorics of free indexation, we show that the problem of enumerating all possi- ble indexings requires exponential time. Secondly, we exhibit a provably optimal free indexation al- gorithm. 1 Introduction In the principles-and-parameters model of lan- guage, the principle known as 'free indexation' plays an important part in the process of deter- mining the referential properties of elements such as anaphors and pronominals. This paper ad- dresses two issues. (1) We investigate the combi- natorics of free indexation. By relating the prob- lem to the n-set partitioning problem, we show that free indexation must produce an exponen- tial number of referentially distinct phrase struc- tures given a structure with n (independent) noun phrases. (2) We introduce an algorithm for free in- dexation that is defined compositionally on phrase structures. We show how the compositional na- ture of the algorithm makes it possible to incre- mentally interleave the computation of free index- ation with phrase structure construction. Addi- tionally, we prove the algorithm to be an 'optimal' procedure for free indexation. More precisely, by relating the compositional structure of the formu- lation to the combinatorial analysis, we show that the algorithm enumerates precisely all possible in- dexings, without duplicates. 2 Free Indexation Consider the ambiguous sentence: (1) John believes Bill will identify him *The author would like to acknowledge Eric S. Ris- tad, whose interaction helped to motivate much of the analysis in this paper. Also, Robert C. Berwick, Michael B. Kashket, and Tanveer Syeda provided many useful comments on earlier drafts. This work is supported by an IBM Graduate Fellowship. In (1), the pronominal "him" can be interpreted as being coreferential with "John", or with some other person not named in (1), but not with "Bill". We can represent these various cases by assigning indices to all noun phrases in a sentence together with the interpretation that two noun phrases are coreferential if and only if they are coindexed, that is, if they have the same index. Hence the follow- ing indexings represent the three coreference op- tions for pronominal "him" :1 (2) a. John1 believes Bill2 will identify him1 b. John1 believes Bill2 will identify him3 c. *John1 believes Bills will identify him2 In the principles-and-parameters framework (Chomsky [3]), once indices have been assigned, general principles that state constraints on the lo- cality of reference of pronominals and names (e.g. "John" and "Bill") will conspire to rule out the impossible interpretation (2c) while, at the same time, allow the other two (valid) interpretations. The process of assigning indices to noun phrases is known as "free indexation," which has the fol- lowing general form: (4) Assign indices freely to all noun phrases? In …

Content truncated to 500 words