Collected Papers of Martin Kay

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.

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.

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

Collected Papers of Martin Kay

Contents