The Formal Complexity of Natural Language

1. Front Matter

   Pages i-xviii

   PDF

2. Prologue

   1. What is Mathematical Linguistics?

      • Stanley Peters

      Pages 1-18

3. Early Nontransformational Grammar

   1. Front Matter

      Pages 19-23

      PDF

   2. Formal Linguistics and Formal Logic

      • Janet Dean Fodor

      Pages 24-40

   3. An Elementary Proof of the Peters-Ritchie Theorem

      • Emmon Bach, William Marsh

      Pages 41-55

   4. On Constraining the Class of Transformational Languages

      • Thomas Wasow

      Pages 56-86

   5. Generative Grammars Without Transformation Rules

      • Gilbert H. Harman

      Pages 87-116

   6. A Program for Syntax

      • P. T. Geach

      Pages 117-131

4. Modern Context-Free-Like Models

   1. Front Matter

      Pages 133-137

      PDF

   2. Natural Languages and Context-Free Languages

      • Geoffrey K. Pullum, Gerald Gazdar

      Pages 138-182

   3. Unbounded Dependencies and Coordinate Structure

      • Gerald Gazdar

      Pages 183-226

   4. On some Formal Properties of Metarules

      • Hans Uszkoreit, Stanley Peters

      Pages 227-250

   5. Some Generalizations of Categorial Grammars

      • Emmon Bach

      Pages 251-279

5. More than Context-Free and Less than Transformational Grammar

   1. Front Matter

      Pages 281-285

      PDF

   2. Cross-Serial Dependencies in Dutch

      • Joan Bresnan, Ronald M. Kaplan, Stanley Peters, Annie Zaenen

      Pages 286-319

   3. Evidence Against the Context-Freeness of Natural Language

      • Stuart M. Shieber

      Pages 320-334

   4. English is Not a Context-Free Language

      • James Higginbotham

      Pages 335-348

   5. The Complexity of the Vocabulary of Bambara

      • Christopher Culy

      Pages 349-357

   6. Context-Sensitive Grammar and Natural Language Syntax

      • Walter J. Savitch

      Pages 358-368

   7. How Non-Context Free is Variable Binding?

      • William Marsh, Barbara H. Partee

      Pages 369-386

Ever since Chomsky laid the framework for a mathematically formal theory of syntax, two classes of formal models have held wide appeal. The finite state model offered simplicity. At the opposite extreme numerous very powerful models, most notable transformational grammar, offered generality. As soon as this mathematical framework was laid, devastating arguments were given by Chomsky and others indicating that the finite state model was woefully inadequate for the syntax of natural language. In response, the completely general transformational grammar model was advanced as a suitable vehicle for capturing the description of natural language syntax. While transformational grammar seems likely to be adequate to the task, many researchers have advanced the argument that it is "too adequate. " A now classic result of Peters and Ritchie shows that the model of transformational grammar given in Chomsky's Aspects [IJ is powerful indeed. So powerful as to allow it to describe any recursively enumerable set. In other words it can describe the syntax of any language that is describable by any algorithmic process whatsoever. This situation led many researchers to reasses the claim that natural languages are included in the class of transformational grammar languages. The conclu­ sion that many reached is that the claim is void of content, since, in their view, it says little more than that natural language syntax is doable algo­ rithmically and, in the framework of modern linguistics, psychology or neuroscience, that is axiomatic.

• Prolog
• Syntax
• complexity
• formal logic
• grammar
• linguistics
• natural language

` .. Savitch et al. have done an excellent job, both in their selections and in their commentaries, of giving a solid introduction to a sparsely cultivated but already complex field. They have also done much to foster the dissemination and the comprehension of formal complexity results in liguistics and to encourage accuracy and lucidity in the formulation, presentation, and interpretation of such results.'
A. Manaster-Ramer in Computational Linguistics, 14:4 (December 1988)

• Department of Electrical Engineering & Computer Sciences, University of California, San Diego, USA

  Walter J. Savitch

• Department of Linguistics, University of Massachusetts, Amherst, USA

  Emmon Bach

• Xerox PARC, Palo Alto, USA

  William Marsh

• College of Arts & Sciences, University of Cincinnati, USA

  Gila Safran-Naveh

Policies and ethics