Free Indexation: Combinatorial Analysis and a Compositional Algorithm

Sandiway FongACL 1990 · DOI

Abstract

In computational linguistics, assigning coreference indices to noun phrases (NPs) presents a significant combinatorial challenge. This paper formalizes the "free indexation" problem as an n-set partitioning task, proving that the search space grows at a super-exponential rate governed by Bell Numbers. To address this complexity, we propose a provably optimal compositional algorithm that interleaves indexation with sentence parsing, allowing for early pruning of invalid interpretations through the application of linguistic constraints.

Introduction

Within the "Principles and Parameters" framework of linguistics, free indexation is the process of assigning labels (indices) to noun phrases to indicate referential identity. For example, in the sentence "John believes Bill will identify him," the pronoun "him" could refer to "John" (co-indexed) or a third party (distinct index), but typically cannot refer to "Bill."

The challenge in automating this process is twofold. First, as the number of nouns in a sentence increases, the number of ways to group them into coreferential sets grows massively. Second, traditional parsers often wait until a sentence is fully constructed before attempting to index it. This "generate-and-test" approach is computationally inefficient and prevents linguistic rules, such as binding principles, from filtering out impossible meanings early in the process.

Combinatorial Complexity and Bell Numbers

The author first maps the linguistic problem of free indexation to the mathematical problem of n-set partitioning. If a sentence contains $n$ independent noun phrases, the number of ways to assign them indices is equivalent to the number of ways to partition a set of $n$ elements into non-empty, disjoint subsets.

The number of such partitions is defined by the Bell Number ($B_n$). The growth of these numbers is super-exponential; for a sentence with 12 noun phrases, there are 4,123,597 referentially distinct ways to index it. The paper argues that natural language utilizes this entire space, providing specific English sentences for every possible partition of 3 and 4 nouns to prove that a parser must be capable of representing the entire space to be linguistically accurate.

Figure 4: The decision tree for free indexation, illustrating how coreference choices (i=j vs i ≠ j) branch the search space.

The Compositional Algorithm

To manage this complexity, the paper introduces a compositional algorithm designed for principle-based parsers like the PO-PARSER. Unlike methods that collect all nouns at the end of a parse, this algorithm works incrementally:

  1. Bottom-Up Construction: It maintains sets of indices at each sub-phrase level of a parse tree.
  2. Merging and Cross-Indexing: When two phrases merge (e.g., a Subject NP and a Verb Phrase), the algorithm generates potential coreference patterns by merging their respective index sets.
  3. Early Pruning: By interleaving indexation with parsing, linguistic constraints (such as Binding Theory) can be applied immediately to discard impossible indexings before the search space expands further.
Figure 1: The compositional structure of the algorithm, showing how index sets are propagated and merged up the parse tree.

The author uses a recurrence relation to prove that this algorithm is mathematically optimal, meaning it generates exactly $B_n$ indexings without any redundant computations.

Key Insights and Results

  • Mathematical Formalization: Identifying the isomorphism between free indexation and set partitioning provides a rigorous bound on the problem's complexity, showing it grows at the rate of $B_n$.
  • Algorithm Optimality: The proposed compositional method reaches the theoretical lower bound for enumerating the indexing space, making it a robust foundation for computational models.
  • Interleaving for Efficiency: The primary benefit of the compositional approach is the ability to apply "binding principles" early. This pruning is essential for making large-scale sentence parsing computationally feasible by preventing the exponential search space from exploding.

Limitations and Future Work

While the algorithm is optimal for "simple indexation," the author acknowledges that more complex linguistic phenomena, such as "inclusion of reference" (e.g., "John told Bill that they should leave"), require extensions beyond basic set partitioning. Furthermore, while the mechanism for interleaving is established, future work is needed to quantify the exact reduction in search space achieved by specific linguistic constraints in real-world parsing scenarios.

Summary updated

BibTeX
@inproceedings{fong1990free,
  author = {Sandiway Fong},
  title = {{Free Indexation: Combinatorial Analysis and a Compositional Algorithm}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1990},
  doi = {10.3115/981823.981837},
}
Figure