From Strings to Trees to Strings to Trees ... (Abstract)

Aravind K. JoshiACL 1994 · DOI

Introduction

In this theoretical reflection, the late Aravind K. Joshi—a foundational figure in computational linguistics and the architect of Tree-Adjoining Grammar (TAG)—examines the historical and theoretical "tug-of-war" between two fundamental ways of representing language: as simple sequences of words (strings) and as complex hierarchical structures (trees). This work explores the persistent oscillation in the field as researchers attempt to determine the "correct" amount of structure required to model human language effectively.

The Fundamental Problem: The Structural Goldilocks Zone

At the core of computational linguistics lies a recurring disagreement: How much structure is necessary to represent a sentence?

Sentences are inherently dualistic. On the surface, they are linear sequences of words (strings). However, they also possess a hierarchical organization where words relate to one another across significant distances (trees). This creates a tension for grammar formalisms:

  • String-based views often struggle to explain how clauses embed within one another or how a verb relates to an object separated by several modifiers.
  • Tree-based views provide the necessary depth for linguistic accuracy but often lead to an explosion in computational complexity.

Joshi’s analysis seeks to categorize how various formalisms—from dependency trees to phrase structure trees—attempt to find a "Goldilocks zone": a representation rich enough to be linguistically valid yet simple enough to remain computationally manageable.

Theoretical Perspectives and Methodology

Joshi employs a comparative theoretical analysis rather than an empirical study. He traces the evolution of linguistic theory through several key stages:

  1. Early Transformational Grammars: Joshi notes a historical irony where early systems conceptually utilized tree transformations but formulated their rules as if they were manipulating strings.
  2. Non-Transformational Grammars: He compares modern systems that utilize string-rewriting versus those that utilize tree-rewriting operations.
  3. Structural Variation: The analysis looks at the spectrum of "minimal clause" representations, ranging from flat, one-level trees (which behave almost like strings) to deep, multi-layered hierarchies.

Key Insights: The Pendulum of Representation

The Stringiness vs. Treeness Pendulum

Joshi observes that the field of linguistics does not move linearly toward greater complexity. Instead, it swings back and forth. Formalisms often begin as "stringy" systems to maintain efficiency, become more "tree-like" to solve specific linguistic problems (such as long-distance dependencies), and then attempt to simplify back toward string-like operations to regain computational speed.

The Pseudo-String Paradox

A significant historical curiosity identified by Joshi is that while early transformational grammars were conceptually about trees, their formal operations were often "pseudo string-like." This suggests a deep-seated desire in the field to compute in strings even when thinking in trees.

Drivers of Complexity

The choice between a string-based or tree-based approach is rarely arbitrary; it is a response to specific linguistic phenomena:

  • Locality: The need to keep predicates near their arguments.
  • Discontinuity: The challenge of handling related words that are separated by intervening phrases.
  • Dominance vs. Precedence: The decision of whether the "vertical" relationship (hierarchy) or the "horizontal" relationship (word order) should take priority in the formalism.

Conclusion and the State of the Field

Joshi’s analysis concludes that the "minimal clause" remains one of the most heatedly debated topics in the field, with no consensus on whether it should be represented as a string, a set of dependencies, or a rich phrase structure.

Ultimately, the paper suggests that most successful modern formalisms are hybrids. They do not strictly choose one side of the string-tree divide; instead, they find novel ways to combine the two. The interplay between constituency, dependency, and adjacency is too complex for any single, simple representation to satisfy all linguistic and computational requirements. While the question of exactly how much structure is needed remains open, Joshi’s framework provides the essential vocabulary for navigating this ongoing theoretical oscillation.

Summary updated

BibTeX
@inproceedings{joshi1994from,
  author = {Aravind K. Joshi},
  title = {{From Strings to Trees to Strings to Trees ... (Abstract)}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1994},
  doi = {10.3115/981732.981737},
}
Figure