Computational Consequences of Agreement and Ambiguity in Natural Language
Abstract
We argue that the modern computer science technique of computational complexity analysis can provide powerful insights into the algorithm-neutral analysis of information-processing tasks. In particular, we show that a simple, theory-neutral linguistic model of syntactic agreement and lexical ambiguity demonstrates that natural language parsing may be computationally intractable, extending the classic work of Chomsky and Miller (1963). Significantly, we show that it may be syntactic features rather than complex rules that can cause this difficulty. Informally, human languages and the computationally intractable satisfiability problem (SAT) share two costly computational mechanisms: both enforce agreement among terminal symbols across unbounded distances and both allow terminal symbol ambiguity. In natural languages, lexical elements may be required to agree (or disagree) on such features as person, number and gender (e.g., subject/verb agreement in English); in SAT, agreement ensures the consistency of variable truth assignments. (kr)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1988
- Accession Number
- ADA225794
Entities
People
- Eric S. Ristad
- Robert C. Berwick
Organizations
- Massachusetts Institute of Technology