Stuart M. Shieber

COMPUTATIONAL APPROACHES TO LANGUAGE AND COMMUNICATION

Professor Shieber studies communication: with humans through natural languages, with computers through programming languages, and with both through graphical languages.

How natural languages are structured to permit efficient communication is a difficult and multi-faceted question, involving issues in linguistics (the syntactic and semantic structure of natural languages), theoretical computer science (the inherent complexity of aspects of human language); computer systems (in connection with the design and deployment of algorithms for natural-language analysis and generation); psychology (human sentence processing and misprocessing); and artificial intelligence (the encoding of general knowledge and its application to the understanding of utterances).

To answer such difficult questions, Shieber synthesizes knowledge from several of these fields. In work on the computational properties of grammar formalisms, formal metalanguages for specifying the syntactic and semantic structure of natural languages, he uses techniques from theoretical computer science to analyze the expressivity and computational effectiveness of the formalisms, and builds on algorithms from the field of computer systems. (Such studies shed light on computer languages as well as natural languages. For example, they reveal some deep similarities between the grammar formalisms proposed for natural languages and the static semantics of programming languages.) In his research on psycholinguistics, a simpler model of human misparsing of sentences was developed by applying technology from the efficient parsing of programming languages. Similarly, his research on semantics makes use of the technology of higher-order logic to explicate the workings of elliptical and quantificational constructions of natural language.

Professor Shieber also looks at problems in automated graphic design with the aim of developing a more graphically articulate computer. (As human beings have been using natural language for perhaps many hundreds of thousands of years, but widespread use of symbolic graphical languages dates from only the late 18th century, graphical artifacts are quite a bit more conventional, providing some basis for the expectation that building a graphically articulate computer may be much more practical than building a linguistically articulate one.) Many graphic-design problems -- for instance, the automatic layout of network diagrams, and the automatic placement of labels on maps -- are computationally intractable. Good approximate solutions to such problems can however, often be obtained by stochastic methods, and such methods are increasingly becoming a large component of his research.