Free Indexation: Combinatorial Analysis and A Compositional Algorithm 
 
 The principle known as free indexation plays an important role in the determination of the referential properties of noun phrases in the principle-and-parameters language framework . First, by investigating the combinatorics of free indexation , we show that the problem of enumerating all possible indexings requires exponential time . Secondly, we exhibit a provably optimal free indexation algorithm .  