Computation of Language

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.