Foundational Issues in Natural Language Processing

William Rounds, Avarind Joshi, Janet Fodor, and Robert Berwick are leading scholars in the multidisciplinary field of natural language processing. In four separate essays they address the complex and difficult connections among grammatical theory, mathematical linguistics, and the operation of real natural-language-processing systems, both human and electronic. The editors' substantial introduction details the progress and problems involved in attempts to relate these four areas of research. William Rounds discusses the relevance of complexity results to linguistics and computational linguistics, providing useful caveats about how results might be misinterpreted and pointing out promising avenues of future research. Avarind Joshi (with K. Vijay-Shanker and David Weir) surveys results showing the equivalence of several different grammatical formalisms, all of which are mildly context-sensitive, with special attention to variants of tree adjoining grammar. Janet Fodor discusses how psycholinguistic results can bear on the choice among competing grammatical theories, surveying a number of recent experiments and their relevance to issues in grammatical theory. Robert Berwick considers the relationship between issues in linguistic theory and the construction of computational parsing systems, in particular the question of what it means to implement a theory of grammar in a computational system. He argues for the advantages of a principle-based approach over a ruleshy;based one, and surveys several recent parsing systems based on the theory of government and binding. Peter Sells is Assistant Professor of Linguistics at Stanford University. Stuart M. Shieber is Assistant Professor of Computer Science on the Gordon McKay Endowment at Harvard University. Thomas Wasow is Professor of Linguistics and Philosophy at Stanford University.