CSLI Publications logo
new books
catalog
series
knuth books
contact
for authors
order
search
CSLI Publications
Facebook
 
Collected Papers of Martin Kay cover

Collected Papers of Martin Kay

A Half-Century of Computational Linguistics

Martin Kay
with the editorial assistance of Dan Flickinger & Stephan Oepen

Since the dawn of the age of computers, researchers have been pushing the limits of available processing power to tackle the formidable challenge of developing software that can understand ordinary human language. At the forefront of this quest for the past fifty years, Martin Kay has been a constant source of new algorithms that have proven fundamental to progress in computational linguistics. Martin Kay's Half-Century of Computational Linguistics, the premier comprehensive collection of his works, opens a window into the growth of this important and increasingly fruitful field of scientific research and development.

Combining a sharp wit with the remorseless logic of a mathematician, Kay addresses topics ranging from machine translation to the proper design of electronic dictionaries, from chart parsing to unification. Kay also offers a well-informed perspective on which natural language processing research challenges to tackle next, and how. This book will be important for computational linguists and students, and illuminating for readers with an interest in the central role of language processing in the future of the Internet.

picture of Martin Kay Martin Kay is one of the preeminent computational linguists in the world, having helped to shape and advance this field for the past fifty years. He is currently the Chair of the International Committee on Computational Linguistics, and the former Chair of the Association for Computational Linguistics. Born and raised in the United Kingdom, he received his M.A. from Trinity College, Cambridge, in 1961. In 1958 he started to work at the Cambridge Language Research Unit, one of the earliest centers for research in what is now known as computational linguistics. In 1961, he moved to the Rand Corporation in Santa Monica, California, where he eventually became head of research in linguistics and machine translation. He left Rand in 1972 to become Chair of the Department of Computer Science at the University of California, Irvine. In 1974, he moved to the Xerox Palo Alto Research Center as a Research Fellow. In 1985, while retaining his position at Xerox PARC, he joined the faculty of Stanford University half-time. He is currently Professor of Linguistics at Stanford University and Honorary Professor of Computational Linguistics at Saarland University. He holds an honorary doctorate of Gothenburg University. In 2005, he received the Lifetime Achievement Award of the Association for Computational Linguistics for his sustained role as an intellectual leader of NLP research. His research interests include translation, both by people and machines, and computational linguistics algorithms, especially in the fields of morphology and syntax.

Dan Flickinger is project manager of the Linguistic Grammars Online Project at the Center for the Study of Language and Information, Stanford University.

Stephan Oepen is professor in computational linguistics at the University of Oslo and senior researcher at the Center for the Study of Language and Information, Stanford University.

Contents

  • Foreword vii
  • Acknowledgements ix
  • 1 Introduction 1
  • 2 A Parsing Procedure 19
  • 3 Rules of Interpretation 22
    • 3.1 Traditional Grammar and Descriptive Linguistics 22
    • 3.2 Rules of Formation 23
    • 3.3 Rules of Interpretation 24
    • 3.4 A Model for Qualification 25
    • 3.5 Computation Methods 26
    • 3.6 Machine Translation 27
  • 4 The Logic of Cognate Recognition in Historical Linguistics 31
    • 4.1 Correspondences and Decompositions 33
    • 4.2 Representation by Truth Functions 35
    • 4.3 The Theory and the Practice 37
    • 4.4 Implementing the Theory 38
  • 5 Natural Language in Computer Form
    with Theodore Ziehe 40
    • 5.1 Codes 44
    • 5.2 Organized Files of Text 52
    • 5.3 Writing Text Catalogs 58
    • 5.4 Printing 67
  • 6 The Tabular Parser 78
    • 6.1 Dependency Phrase Grammar 78
    • 6.2 Rule Tables 81
    • 6.3 Functions and Dependency Phrase Rule Tables 88
    • 6.4 The Punched Card Format 90
    • 6.5 The Computer Program 92
    • 6.6 Input and Output 95
  • 7 Experiments with a Powerful Parser 100
    • 7.1 The Form of Rules 101
    • 7.2 Phrase-Structure Grammar 105
    • 7.3 Transformational Grammar 107
  • 8 From Semantics to Syntax 114
  • 9 Computational Linguistics at RAND — 1967 126
  • 10 A Computer System to Aid the Linguistic Field Worker 136
  • 11 Computational Competence and Linguistic Performance 143
  • 12 Performance Grammars 151
  • 13 The MIND Translation System: A Study in Man-Machine Collaboration
    with R. Bisbey 158
    • 13.1 What is a Translation Machine? 158
    • 13.2 Why is Translation Difficult? 161
    • 13.3 Conventional Machine Translation 163
    • 13.4 Human-Aided Translation 166
    • 13.5 An Experimental Translator 166
    • 13.6 Extensions to Human-Aided Translation 168
    • 13.7 The Future of the System 170
  • 14 The MIND System 173
    • 14.1 Motivation 173
    • 14.2 The Overall Structure of the System 175
    • 14.3 Syntactic Analysis and the Chart 176
    • 14.4 The Disambiguator 181
    • 14.5 Semantics 183
    • 14.6 The Output Component 187
    • 14.7 Summary 188
  • 15 Automatic Translation of Natural Languages 201
  • 16 Morphological Analysis 212
  • 17 Syntactic Processing and Functional Sentence Perspective 227
    • 17.1 Reversible Grammars 227
    • 17.2 The Processor 228
    • 17.3 The Use of Registers 230
    • 17.4 Functional Sentence Perspective 231
  • 18 Overview of Computer Aids in Translation 234
  • 19 The Proper Place of Men and Machines in Language Translation 240
    • 19.1 The Prima Facie Case Against Machine Translation 242
    • 19.2 Machine Translation and Linguistics 242
    • 19.3 Machine Translation and Computer Science 244
    • 19.4 The Statistical Defense 246
    • 19.5 The Sorcerer's Apprentice Defense 247
    • 19.6 The Translator's Amanuensis 249
    • 19.7 Machine Translation 255
  • 20 Functional Grammar 258
  • 21 Algorithm Schemata and Data Structures in Syntactic Processing 276
    • 21.1 Configuration Tables and Algorithm Schemata 279
    • 21.2 The Chart 293
    • 21.3 The Agenda 304
  • 22 When Meta-Rules are not Meta-Rules 308
    • 22.1 A Straw Man 310
    • 22.2 Phonological and Graphological Rules 312
    • 22.3 Context-Free Rules as Transition Networks 315
    • 22.4 Meta-Rules as Transducers 316
    • 22.5 Constructing Meta-Rule Transducers 318
    • 22.6 Composing Transducers 319
  • 23 Functional Unification Grammar: A Formalism for Machine Translation 333
    • 23.1 Overview 333
    • 23.2 The Formalism 335
    • 23.3 Translation 339
  • 24 Parsing in Functional Unification Grammar 343
    • 24.1 Functional Unification Grammar 344
    • 24.2 Compilation 345
    • 24.3 The Parser 355
    • 24.4 The Compiler 361
  • 25 Parsing in a Free Word Order Language
    with Lauri Karttunen 365
    • 25.1 Data 367
    • 25.2 A unification grammar for Finnish 375
    • 25.3 Parser 383
  • 26 Structure Sharing with Binary Trees
    with Lauri Karttunen 373
  • 27 Unification in Grammar 397
    • 27.1 Simple Unification Grammar 398
    • 27.2 Semantics 402
    • 27.3 Control structure 404
  • 28 Machine Translation will not Work 406
  • 29 The Linguistic Connection 408
  • 30 Nonconcatenative Finite-State Morphology 414
  • 31 Head-Driven Parsing 426
  • 32 Machines and People in Translation 435
  • 33 Semantic Abstraction and Anaphora
    with Mark Johnson 437
    • 33.1 A Grammar using Semantic Constructors 439
    • 33.2 The Predicate-Logic Constructors 442
    • 33.3 The Sets-of-Infons Constructors 443
    • 33.4 The Discourse-Representation Constructors 445
    • 33.5 Extending the Grammar to Handle Quantifier-Raising 446
  • 34 Computational Linguistics 450
  • 35 Ongoing Directions in Computational Linguistics 460
  • 36 Unification 462
    • 36.1 Productivity 462
    • 36.2 Phrase structure 464
    • 36.3 Multiple structures 466
    • 36.4 Descriptions 468
    • 36.5 Grammar rules 470
    • 36.6 Augmented Transition Networks 472
    • 36.7 Logical variables 475
    • 36.8 Clausal form and term unification 476
    • 36.9 Path equations 480
    • 36.10 Long-distance dependency 480
  • 37 Foreword to “An Introduction to Machine Translation” 483
  • 38 Text-Translation Alignment
    with Martin Roscheisen 486
    • 38.1 The Problem 486
    • 38.2 The Alignment Algorithm 488
    • 38.3 Morphology 492
    • 38.4 Experimental Results 494
    • 38.5 Related Work 502
    • 38.6 Future Work 503
  • 39 Regular Models of Phonological Rule Systems
    with Ronald M. Kaplan 505
    • 39.1 Introduction 505
    • 39.2 Rewriting Rules and Transducers 507
    • 39.3 Mathematical Concepts and Tools 510
    • 39.4 Rewriting Rule Formalisms 517
    • 39.5 Rewriting Rules as Regular Relations 524
    • 39.6 Grammars of Rewriting Rules 535
    • 39.7 Two-Level Rule Systems 538
  • 40 Parsing and Empty Nodes
    with Mark Johnson 551
    • 40.1 The Problem with Empty Nodes 551
    • 40.2 Sponsoring 553
    • 40.3 Linguistic Aspects of Sponsoring 554
    • 40.4 Implementation 556
  • 41 Machine Translation: The Disappointing Past and Present 565
  • 42 Chart Generation 568
    • 42.1 Charts 568
    • 42.2 Generation 569
    • 42.3 The Algorithm Schema 570
    • 42.4 Internal and External Indices 571
    • 42.5 Indexing 572
  • 43 It's Still the Proper Place 574
  • 44 Chart Translation 577
    • 44.1 Translation and Knowledge
    • 44.2 History 578
    • 44.3 The Translation Relation 579
    • 44.4 Charts and Contexted Sets
    • 44.5 Choosing the Best Translation 583
  • 45 David G. Hays 585
  • 46 Preface to “Parallel Text Processing” 590
  • 47 Guides and Oracles for Linear-Time Parsing 594
  • 48 Introduction to Handbook of Computational Linguistics 599
  • 49 Substring Alignment Using Suffix Trees 602
  • 50 Translation, Meaning and Reference 611
  • 51 Antonio Zampolli 621
  • 52 A Life of Language 624
  • Cumulative References 637
  • Complete List of Publications to Date 647
  • Name Index 653
  • Subject Index 657

October 2010

ISBN (Cloth): 9781575865713
ISBN (Electronic): 9781575866796

Add to Cart
View Cart

Check Out

Distributed by the
University of
Chicago Press

pubs @ csli.stanford.edu