Understanding language is a seemingly effortless task for people. Not only can they understand the meaning of sentences with great accuracy, they do so quickly: in most cases, people understand language in linear time. In constrast, understanding language is not so easy for computers. Even ignoring problems of accuracy, natural language processing systems ane much slower than people aje. All current NL P systems that fully analyze both the syntactic structure and semantic meaning of text fall short of human performance in this respect. In this paper, we present an attempt to develop a linear time algorithm for parsing natural language using unification grammcirs. While the computational complexity of the algorithm is, in the worst case, no better than that of many other algorithms, empirical testing indicates improved average-case performance. Although linear performance has not yet been achieved, we will discuss possible improvements that may result in an average-case linear time algorithm.

This paper addresses the role that examples play in instructional learning. We discuss several roles examples can serve when they complement an instruction. W e provide functional evidence for some of these roles, arguing why instructions and examples are both necessary for efficient learning. We present a system that lezirns from instructions which are enhanced by examples. The system, A N T (Acquisition using Native-language Transfer), learns a second language by reading instructions about grammatical rules of the second language as well as examples which use these rules. Finally, we argue for the functional utility of examples in instructional learning on more general grounds, showing how such a strategy can beappHcable to other domains besides second language learning.

One major element of discourse understcinding is to perceive coherence relations between portions of the discourse. Previous computational approaches to coherence relations reasoning have focused only on expository discourse, such as task-oriented dialog or database querying. For these approaches, the main processing concern is the clarity of the information that is to be conveyed. However, in a persuasive discourse, such as debates or advertising, the emphasis is on the adequacy of presenting the information, not just on clarity. This paper proposes a formaUsm and a system in which coherence relations corresponding to speech actions such as clarify, make adequate and remind are represented. Furthermore, in relating to human reasoning in general where studies have revealed that implicational and associative reasoning schema are prevalent across various domains, this formalism demonstrates that coherence relation reasoning is similar to this human reasoning, in the sense that coherence relations can be defined by domain independent implicational and associative schema. A prototype system based on this formalism is also demonstrated in this paper in which real world advertisements are processed.

This paper describes a lexical acquisition mechanism that was implemented in order to increase the robustness of a Natural Language Processing system. Although the mechanism was not intended to be a cognitive model of children's language acquisition, it demonstrates many similarities with psycholinguistic findings. In particular, the structure of the domain knowledge representation forces the system to take a bipolar approach to learning nouns and verbs. Psycholinguistic studies demonstrate differing treatment of nouns and verbs by children and suggest a structural basis for this difference. The knowledge-level similarities between our system and human linguistic knowledge make it possible to infer that children must adopt a similar strategy to effectively learn word meanings.