Computation of Language

The study of linguistics has been forever changed by the advent of the computer. Not only does the machine permit the processing of enormous quantities of text­ thereby securing a better empirical foundation for conclusions-but also, since it is a modelling device, the machine allows the implementation of theories of grammar and other kinds of language processing. Models can have very unexpected properties­ both good and bad-and it is only through extensive tests that the value of a model can be properly assessed. The computer revolution has been going on for many years, and its importance for linguistics was recognized early on, but the more recent spread of personal workstations has made it a reality that can no longer be ignored by anyone in the subject. The present essay, in particular, could never have been written without the aid of the computer. I know personally from conversations and consultations with the author over many months how the book has changed. If he did not have at his command a powerful typesetting program, he would not have been able to see how his writing looked and exactly how it had to be revised and amplified. Even more significant for the evolution of the linguistic theory is the easy testing of examples made possible by the implementation of the parser and the computer-held lexicon. Indeed, the rule set and lexicon grew substantially after the successes of the early implementations created the desire to incorporate more linguistic phenomena.

I Natural Language and Formal Grammar.- 1 Goals and Results.- 1.1 A Unified Perspective.- 1.2 Assumptions Accepted and Assumptions Rejected.- 1.3 Theory and Practice.- 1.4 Summary of the Formal Results.- 1.5 Applications and Future Work.- 2 Grammar and Interpretation.- 2.1 Limitations of Constituent Structures.- 2.2 Basic Communication.- 2.3 Database Semantics and Pragmatic Interpretation.- 2.4 Criteria of Adequacy of Grammar.- 2.5 Current Paradigms.- 3 Outline of Left-Associative Grammar.- 3.1 Left-Associative Syntax.- 3.2 Newcat parsers.- 3.3 Semantic Interpretation.- 3.4 An Example.- 3.5 Two Fallacies of Constituent Structure.- 4 Continuations in Natural Language.- 4.1 Scheduling Access to Grammatical Information.- 4.2 Agreement.- 4.3 Valency.- 4.4 Word Order.- 4.5 Pronouns.- 5 Analysis and Generation.- 5.1 Incremental Pragmatic Interpretation.- 5.2 The Generation Paradox.- 5.3 The Linear Path Hypothesis.- 5.4 The Extraction Problem of Generation.- 5.5 Remarks on the Choice Problem.- II Algebraic and Automata-Theoretic Characterization.- 6 The Left-Associative Algorithm.- 6.1 Basic Concepts of PS-, C-, and LA-Grammar.- 6.2 The Mathematical Definition of Left-Associative Syntax.- 6.3 The Derivational Structure of LA-Grammar.- 6.4 An Example: the Formal Language akbkck.- 6.5 On the Generative Power of LA-Grammar.- 7 Language Hierarchies.- 7.1 LA-Grammars for Regular, CF, and CS Languages.- 7.2 The Hierarchy of A-LAGs, B-LAGs, and C-LAGs.- 7.3 Ambiguity of Languages.- 7.4 Syntactically-Ambiguous LA-grammars.- 7.5 Lexically-Ambiguous LA-grammars.- 8 LA-Grammar and Automata.- 8.1 Input-Output Equivalence of Grammars and Parsers.- 8.2 Simulating Finite Automata in LA-grammar.- 8.3 The LAG Control Structure Compared with RTNs.- 8.4 Predictive Analyzers and Deterministic Parsers.- 8.5 LA-Grammar and Register Machines.- 9 Decidability and Efficiency.- 9.1 Recognition of Grammatical Recursion.- 9.2 The Recursion Factor of C-LAGs.- 9.3 Equivalence of C-LAGs.- 9.4 Improving Efficiency.- 9.5 Sound LA-Grammars.- 10 Computational Complexity Results.- 10.1 Complexity of Unambiguous C-LAGs.- 10.2 Empirical Results.- 10.3 Packing vs. Restricting Ambiguities.- 10.4 Complexity of Syntactically Ambiguous C-LAGs.- 10.5 Complexity of Lexically Ambiguous C-LAGs.- III Logic and Communication.- 11 Principles of Pragmatics.- 11.1 Peirce and the Theory of Signs.- 11.2 Meaning, Use, and Grice’s Intentions.- 11.3 The Principles of Reference.- 11.4 Successful Communication.- 11.5 Non-Literal Uses.- 12 Meaning, Truth and Ontology.- 12.1 Tarski’s Truth Definition.- 12.2 Model Theory and Natural Language.- 12.3 A Simple Robot: the Color Reader.- 12.4 Intensional and Extensional Meaning Analysis.- 12.5 Four Basic Approaches to Meaning.- 13 Model Theory and Artificial Intelligence.- 13.1 Reconstructing Truth in a Robot.- 13.2 Autonomy from the Metalanguage.- 13.3 Semantics and Reference.- 13.4 Why Meanings are in the Head.- 13.5 The Speaker-Simulation Device.- 14 Reference and Denotation.- 14.1 The Epimenides Paradox.- 14.2 Consistency and Truth.- 14.3 Reconstructing Epimenides Pragmatically.- 14.4 Vagueness.- 14.5 The Sorites Paradox.- 15 Surface Compositional Semantics.- 15.1 Presuppositions.- 15.2 Restricted Quantification.- 15.3 Tautologies, Presupposition Failure, and Vagueness.- 15.4 Intensional Contexts.- 15.5 A Unified Semantic Account.- Conclusion.- Appendices.- Introductory Remarks.- A ECAT Category Segments and Categories.- A.l Alphabetical List of Category Segments.- A.2 List of ELEX Categories.- A.3 Derived ECAT Categories.- B Sample Derivations.- B.l Yes/No Interrogative.- B.2 Ambiguity in a Passive Sentence.- B.3 Recursion of Control.- B.4 Unbounded Dependency.- B.5 Relative Clauses.- B.6 Genitive Recursion.- B.7 Idiom.- C The Current Example Set of ECAT.- References.- Name Index.