The first problem is to determine exactly what each adjective modifies. In general, this can only be done by taking account of the semantic properties of the adjective in question, as well as those of other adjectives to its right and of the noun itself. ``Real-world'' knowledge and contextual factors also play a role in this process. This is addressed by developing a classification scheme for adjectives which allows us to substantially reduce the number of candidate interpretations, in some cases to a single one. A system is presented which takes account of the disparate semantic behaviour of different classes of adjectives, word order, punctuation in the noun phrase, and a frame-based store of real-world knowledge, in order to determine the scope of adjectives within a noun phrase.

The second problem is to construct a representation of the description embodied in such a noun phrase. Here, it is desirable that the structure of the representation correspond to the structure of modification within the phrase. Particular adjectives are taken to indicate restrictions on the values that objects may take on for associated properties. These properties may be featural, dimensional, or functional in nature. Frame-like structures are used to represent the generic concepts that are taken to be associated with noun phrases.

There has been much interest lately in the automatic generation of documentation; however, much of this research has not considered the cost involved in the production of the natural language generation systems to be a major issue: the benefits obtained from automating the construction of the documentation should outweigh the cost of designing and coding the knowledge base.

This study is centred on the generation of instructional text, as is found in instruction manuals for household appliances. We show how knowledge about a device that already exists as part of the engineering effort, together with adequate, domain-independent knowledge about the environment, can be used for reasoning about natural language instructions.

The knowledge selected for communication can be planned for, and all the knowledge necessary for the planning should be contained (possibly in a more abstract form) in the knowledge of the artifact together with the world knowledge. We present the planning knowledge for two example domains, in the form of axioms in the situation calculus. This planning knowledge formally characterizes the behaviour of the artifact, and it is used to produce a basic plan of actions that both the device and user take to accomplish a given goal. We explain how the instructions are generated from the basic plan. This plan is then used to derive further plans for states to be avoided. We will also explain how warning instructions about potentially dangerous situations are generated from these plans. These ideas have been implemented using Prolog and the Penman natural language generation system.

Finally, this thesis makes the claim that the planning knowledge should be derivable from the device and world knowledge; thus the need for cost effectiveness would be met. To this end, we suggest a framework for an integrated approach to device design and instruction generation.

Any natural language processing system that does not have a knowledge of non-compositional idioms and their interpretation will make mistakes. Previous authors have attempted to automatically identify these expressions through the property of non-substitutability: similar words cannot be successfully substituted for words in non-compositional idiom expressions without changing their meaning.

In this study, we use the non-substitutability property of idioms to contrast and expand the ideas of previous works, drawing on WordNet for the attempted substitutions. We attempt to determine the best way to automatically identify idioms through the comparison of algorithms including frequency counts, pointwise mutual information and PMI ranges; the evaluation of the importance of relative word position; and the assessment of the usefulness of syntactic relations. We discover that many of the techniques which we try are not useful for identifying idioms and confirm that non-compositionality doesn't appear to be a necessary or sufficient condition for idiomaticity.

Much of the development of the current Government-Binding (GB) theory of syntax has progressed independently of concerns raised in theories of language processing. Similarly, models of syntactic processing are often proposed that lack any underpinning in syntactic theory. The work described in this report focuses on the language Warlpiri, an Australian aboriginal language with properties that are difficult to reconcile with most theories of Universal Grammar -- properties such as free word-order and discontinuity. This language is studied from the two-fold perspective of establishing a linguistically and computationally sound processing model. This forces the linguistic model to be sufficiently precise to satisfy the demands of implementation as well as forcing the implementation to proceed in a linguistically principled way.

This report presents a portion of Warlpiri grammar in a revised GB-based account, addressing the issues of parsability, as well as more theoretical syntactic issues, that together force a reassessment and parametrization of certain linguistic principles. In particular, a revised version of theta theory and the notion of thematic identification are readily interpreted into processing strategies that extend naturally to deal with adjuncts and non-subcategorized arguments in a wide range of languages. The complementary nature of the syntax and morpho-syntax in the satisfaction of syntactic principles as well as in the construction of syntactic representations is addressed, as is the crucial relevance of prosodic information for preserving determinism in the parsing algorithm.

This paper describes an approach to computer-assisted language instruction based on the application of artificial intelligence technology to grammatical error diagnosis. We have developed a prototype system, Scripsi, capable of recognising a wide range of errors in the writing of language learners. Scripsi not only detects ungrammaticality, but hypothesizes its cause and provides corrective information to the student. These diagnostic capabilities rely on the application of a model of the learner's linguistic knowledge.

Scripsi operates interactively, accepting the text of the student's composition and responding with diagnostic information about its grammatical structure. In contrast to the narrowly defined limits of interaction available with automated grammatical drills, the framework of interactive composition provides students with the opportunity to express themselves in the language being learned.

Although Scripsi's diagnostic functions are limited to purely structural aspects of written language, the way is left open for the incorporation of semantic processing. The design of Scripsi is intended to lay the groundwork for the creation of intelligent tutoring systems for second language instruction. The development of such expertise will remedy many of the deficiencies of existing technology by providing a basis for genuinely communicative instructional tools --- computerised tutors capable of interacting linguistically with the student.

The research is based on the assumption that the language produced by the language learner, ``learner language'', differs in systematic ways from that of the native speaker. In particular, the learner's errors can be attributed primarily to two causes: the operation of universal principles of language acquisition and the influence of the learner's native language. A central concern in the design of Scripsi has been the incorporation of a psychologically sound model of the linguistic competence of the second language learner.

We describe an approach to grammatical error diagnosis in computer-assisted language instruction (CALI). Our prototype system, Scripsi, employs a model of the linguistic competence of the second language learner in diagnosing ungrammaticality in learners' writing. Scripsi not only detects errors, but hypothesises their cause and provides corrective information to the student.

Scripsi's grammatical model reflects the results of research in second language acquisition, which has identified language transfer and rule overgeneralisation as the chief sources of error in learner language. Thus, in characterizing the learner's ``transitional competence'', we model not only the grammar of the learner's native language, but also the strategies that give rise to overgeneralisation. Although the approach is language-independent, our implementation targets French-speaking and Chinese-speaking learners of English.

The computational realization of the model assumes that linguistic behaviour is rule-governed. We have adopted a rule-oriented grammatical formalism in which the processes of transfer and overgeneralisation are readily interpreted. Linguistic rules are expressed in a feature-based grammatical framework closely related to the Standard Theory of transformational grammar. We have extended the shift-reduce parsing algorithm in order to accommodate context-sensitive and transformational aspects of the formalism.

We argue that the development of expertise in intelligent grammatical diagnosis is a prerequisite for the next generation of CALI tools -- genuinely communicative systems capable of interacting linguistically with the student.

This thesis presents the first application of the state-of-the-art head-driven statistical parsing model of Michael Collins as a simultaneous language model and parser for large-vocabulary speech recognition. The model is adapted to an online left-to-right chart-parser for word lattices, integrating acoustic, n-gram and parser probabilities.

The parser uses structural and lexical dependencies not considered by n-gram models, conditioning recognition on more linguistically-grounded relationships. By preferring paths through the word lattice for which a probable parse exists, word error rate can be reduced and important syntactic and semantic relationships can be determined in a single step process.

New forms of heuristic search and pruning are employed to improve efficiency. Experiments on the Wall Street Journal treebank and lattice corpora show word error rates competitive with the standard n-gram language model while extracting additional structural information useful for speech understanding.

Marvin Minsky writes at the beginning of The Society of Mind (1986, page 18) that ``to explain the mind, we have to show how minds are built from mindless stuff, from parts that are much smaller and simpler than anything we'd consider smart.'' In this dissertation, I develop a model of a strictly quantitative (i.e., non-semantic) memory that can be used to specify a conceptual analyzer for teuchistic (i.e., `constructionist') text comprehension. I view this model as a prototype of Minsky's ``agents of the mind''.

Most importantly, I acknowledge the real-time processing constraints derived from the biological constraint (Feldman, 1984) and therefore, assume that linguistic comprehension is a race defined in terms of time-constrained memory processes.

Because I do not model an adaptable memory, I partition memory into a static component, which consists of a massively parallel network of simple computing elements whose processes allow for the construction of clusters, and a dynamic component, where these clusters reside. Through specification browsers, the user of the system can input and modify both the topology of the network and the individual behavior of each computing element of static memory, which forms a `knowledge' base. Clusters are built from the processing of an input text with respect to this `knowledge' base and constitute the output of the system. Given that there is widespread disagreement on the nature, modus operandi, and use of inferences in text comprehension, the focus in this work is not on the knowledge required for comprehension, but rather on its specification in terms of constraints to satisfy through the exchange of simple signals and sequences of primitive memory operations to execute upon constraint satisfaction. I demonstrate at length how typical rules for the problems of syntax, referential resolution, lexical and structural disambiguation, and bridging inferences can be encoded in the proposed representational scheme, and thus illustrate how a theory of text understanding may be `grounded' into a more fundamental quantitative time-constrained memory.

Statistical parsers that simultaneously generate both phrase-structure and lexical dependency trees have been limited in two important ways: the detection of non-projective dependencies has not been integrated with other parsing decisions, or the constraints between phrase-structure and dependency structure have been overly strict. I develop context-free filtering grammar as a generalization of the more restrictive lexicalized factored parsing model, and I develop for the new grammar formalism a scoring model to resolve parsing ambiguities. I demonstrate the flexibility of the new model by implementing a statistical parser for German, a freer-word-order language exhibiting a mixture of context-free and non-projective behaviours.

A recent and growing development in Web applications has been the advent of various tools that claim to ``customize'' access to information on the Web by allowing users to specify the kinds of information they want to receive without having to search for it or sift through masses of irrelevant material. But this kind of customization is really just a crude filtering of raw Web material in which the user simply selects the ``channels'' of information she wishes to receive; this selection of information sources is hardly more ``customization'' than someone deciding to tune their television to a certain station. True customization, or tailoring, of information would be done for the user by a system that had access to an actual model of the user, a profile of the user's interests and characteristics. And such tailoring would involve much more than just selecting streams of basic content: the content of the text, whether for on-line Web page or a paper document, would be carefully selected structured, and presented in the manner best calculated to appeal to a particular individual. Adaptive-hypertext presentation comes closest to achieving this kind of document tailoring, but the current techniques used for adapting the content of a document to a particular user generally only involve some form of selectively showing (or hiding) portions of text or choosing whole variants of larger parts of the document.

If the Web document designer wishes to write and present material in a way that will communicate well with the user, then just displaying the most relevant chunks of information will not be sufficient. For effective communication, both the form and content of the language used in a document should be tailored in rhetorically significant ways to best suit a user's particular personal characteristics and preferences. Ideally, we would have Web-based natural language generation systems that could produce fully customized and customizable documents on demand by individual users, according to a formal user model. As a first step in this direction, we have been investigating applications of our earlier work on pragmatics in natural language processing to building systems for the automated generation of Web documents tailored to the individual reader.

Many studies have shown that health-education messages and patient instructions are more effective when closely tailored to the particular condition and characteristics of the individual recipient. But in situations where many factors interact -- for example, in explaining the pros and cons of hormone replacement therapy -- the number of different combinations is far too large for a set of appropriately tailored messages to be produced in advance.

The HealthDoc project is presently developing linguistic techniques for producing, on demand, health-education and patient-information brochures that are customized to the medical and personal characteristics of an individual patient.

For each topic, HealthDoc requires a `master document' written by an expert on the subject with the help of a program called an `authoring tool'. The writer decides upon the basic elements of the text -- clauses and sentences -- and the patient conditions under which each element should be included in the output. The program assists the writer in building correctly structured master-document fragments and annotating them with the relationships and conditions for inclusion.

When a clinician wishes to give a patient a particular brochure from HealthDoc, she will select it from a menu and specify the name of the patient. HealthDoc will use information from the patient's on-line medical record to then create and print a version of the document appropriate to that patient, by selecting the appropriate pieces of material and then performing the necessary linguistic operations to combine them into a single, coherent text.

The problem of style is highly relevant to computational linguistics, but current systems deal only superficially, if at all, with subtle but significant nuances of language. Expressive effects, together with their associated meaning, contained in the style of a text are lost to analysis and absent from generation.

We have developed an approach to the computational treatment of style that is intended to eventually incorporate three selected components---lexical syntactic, and semantic. In this paper, we concentrate on certain aspects of syntactic style. We have designed and implemented a computational theory of goal-directed stylistics that can be used in various applications, including machine translation, second-language instruction and natural language generation.

We have constructed a vocabulary of style that contains both primitive and abstract elements of style. The primitive elements describe the stylistic effects of individual sentence components. These elements are combined into patterns that are described by a stylistic meta-language, the abstract elements, that define the concordant and discordant stylistic effects common to a group of sentences. Higher-level patterns are built from the abstract elements and associated with specific stylistic goals, such as clarity or concreteness. Thus, we have defined rules for a syntactic stylistic grammar at three interrelated levels of description: primitive elements, abstract elements, and stylistic goals. Grammars for both English and French have been constructed, using the same vocabulary and the same development methodology. Parsers that implement these grammars have also been built.

The stylistic grammars codify aspects of language that were previously defined only descriptively. The theory is being applied to various problems in which the form of an utterance conveys an essential part of meaning and so must be precisely represented and understood.

If we want to describe the action of someone who is looking out a window for an extended time, how do we choose between the words gazing, staring, and peering? What exactly is the difference between an argument, a dispute, and a row? In this paper, we describe our research in progress on the problem of lexical choice and the representations of world knowledge and of lexical structure and meaning that the task requires. In particular, we wish to deal with nuances and subtleties of denotation and connotation---shades of meaning and of style---such as those illustrated by the examples above.

We are studying the task in two related contexts: machine translation and the generation of multilingual text from a single representation of content. In the present paper, we concentrate on issues in lexical representation. We describe a methodology, based on dictionary usage notes, that we are using to discover the dimensions along which similar words can be differentiated, and we discuss a two-part representation for lexical differentiation.

A significant part of the meaning of any text lies in the author's style. Different choices of words and syntactic structure convey different nuances in meaning, which must be carried through in any translation if it is to be considered faithful. Up to now, machine translation systems have been unable to do this. Subtleties of style are simply lost to current machine-translation systems.

The goal of the present research is to develop a method to provide machine-translation systems with the ability to understand and preserve the intent of an author's stylistic characteristics. Unilingual natural language understanding systems could also benefit from an appreciation of these aspects of meaning. However, in translation, style plays an additional role, for here one must also deal with the generation of appropriate target-language style.

Consideration of style in translation involves two complementary, but sometimes conflicting, aims:

• The translation must preserve, as much as possible, the author's stylistic intent --- the information conveyed through the manner of presentation.
• But it must have a style that is appropriate and natural to the target language.

The study of comparative stylistics is, in fact, guided by the recognition that languages differ in their stylistic approaches: each has its own characteristic stylistic preferences. The stylistic differences between French and English are exemplified by the predominance of the pronominal verb in French. This contrast allows us to recognize the greater preference of English for the passive voice:

• (a) Le jambon se mange froid.
  (b) Ham is eaten cold.

Such preferences exist at the lexical, syntactic, and semantic levels, but reflect differences in the two languages that can be grouped in terms of more-general stylistic qualities. French words are generally situated at a higher level of abstraction than that of the corresponding English words which tend to be more concrete (Vinay and Darbelnet 1958, 59). French aims for precision while English is more tolerant of vagueness. (Duron 1963 109).

So, a French source text may be abstract and very precise in style, but the translated English text should be looser and less abstract, while still retaining the author's stylistic intent. Translators use this kind of knowledge about comparative stylistics as they clean up raw machine-translation output, dealing with various kinds of stylistic complexities.

The problem of style is highly relevant to machine translation, but current systems deal only superficially, if at all, with the preservation of stylistic effects. At best, MT output is syntactically correct but aims no higher than a strict uniformity in style. The expressive effects contained in the source text, together with their associated meaning, are lost.

I have developed an approach to the computational treatment of style that incorporates three selected components --- lexical, syntactic and semantic --- and focuses on certain aspects of syntactic style. I have designed and implemented the foundations of a computational model of goal-directed stylistics that could serve as the basis of a system to preserve style in French-to-English translation. First, I developed a vocabulary of style that contains both primitive and abstract elements of style. The primitive elements describe the stylistic effects of individual sentence components. These elements are combined into patterns that are described by a stylistic meta-language, the abstract elements, that define the stylistic effects common to a group of sentences. These elements have as their basis the notions of concord and discord, for it is my contention that style is created by patterns of concord and discord giving an overall integrated arrangement. These patterns are built from the abstract elements and associated with specific stylistic goals such as clarity or concreteness. Thus, I have developed a syntactic stylistic grammar at three interrelated levels of description: primitive shapes, abstract elements, stylistic goals. Grammars for both French and English have been constructed, using the same vocabulary and the same development methodology. As well, Mark Ryan has used this vocabulary and methodology to construct a semantic stylistic grammar. Parsers that implement these grammars have also been implemented.

Together, the English and French parsers could form the basis of a system that would preserve many aspects of style in translation. The incorporation of stylistic analysis into MT systems should significantly reduce the current reliance on human post-editing and improve the quality of MT output.

We are developing stylistic grammars to provide the basis for a French and English stylistic parser. Our stylistic grammar is a branching stratificational model, built upon a foundation dealing with lexical, syntactic, and semantic stylistic realizations. Its central level uses a vocabulary of constituent stylistic elements common to both English and French, while the top level correlates stylistic goals, such as clarity and concreteness, with patterns of these elements.

Overall, we are implementing a computational schema of stylistics in French-to-English translation. We believe that the incorporation of stylistic analysis into machine translation systems will significantly reduce the current reliance on human post-editing and improve the quality of the systems' output

Ideally, a case-law retrieval system would provide the lawyer with conceptual access to cases and help him or her to develop an argument. This research constitutes an attempt to move from contemporary information retrieval towards the ideal by using natural language understanding techniques.

A knowledge base of contract cases has been constructed to demonstrate the advantages of using a conceptual representation rather than keywords. The KB consists of knowledge representations of the cases, a lexicon of legal concepts and some semantic constraints. The ratio decidendi or principal argument of each of the cases has been analyzed according to Toulmin's ``good reasons'' argument model. The argument schema is used to structure the representation of the discourse. Sowa's conceptual graphs have been used as a near-first-order notation. Conceptual graphs have an established group of users and a growing software base. The notation is augmented by Somers's 28 definitive deep cases, which are designed to answer the strongest criticisms of case.

The lexicon of legal concepts is integrated with the argument representations. Each legal concept has its own definition and pointers to instances. In a full-scale implementation, as the KB grew the legal concepts would be augmented, continuously being redefined, by knowledge from incoming cases. The open-textured concepts are used in the design to improve retrieval.

It might be argued that constructing such a KR is slow, requires human ability and is impractical for large-scale applications. Nevertheless in future, KR construction can reasonably be expected to be automatic. Here, we are not looking to write language in logic just yet, but to model conceptual content in order to facilitate the retrieval of information. We demonstrate that retrieval based on semantics and inference, is perceptive and powerful.

The dissertation concludes with a retrieval demonstration using questions derived from cases following those represented in the KB. LOG, a frame-matching algorithm based on spreading activation, is used. The demonstration focuses on pattern-matching among conceptual definitions. Semantic constraints facilitate inference within the type hierarchy.

We develop a new computational model for representing the fine-grained meanings of near-synonyms and the differences between them. We also develop a sophisticated lexical-choice process that can decide which of several near-synonyms is most appropriate in a particular situation. This research has direct applications in machine translation and text generation.

We first identify the problems of representing near-synonyms in a computational lexicon and show that no previous model adequately accounts for near-synonymy. We then propose a preliminary theory to account for near-synonymy, relying crucially on the notion of granularity of representation, in which the meaning of a word arises out of a context-dependent combination of a context-independent core meaning and a set of explicit differences to its near-synonyms. That is, near-synonyms cluster together.

We then develop a clustered model of lexical knowledge, derived from the conventional ontological model. The model cuts off the ontology at a coarse grain, thus avoiding an awkward proliferation of language-dependent concepts in the ontology, and groups near-synonyms into subconceptual clusters that are linked to the ontology. A cluster differentiates near-synonyms in terms of fine-grained aspects of denotation, implication, expressed attitude, and style. The model is general enough to account for other types of variation, for instance in collocational behaviour.

An efficient, robust, and flexible fine-grained lexical-choice process is a consequence of a clustered model of lexical knowledge. To make it work, we formalize criteria for lexical choice as preferences to express certain concepts with varying indirectness, to express attitudes, and to establish certain styles. The lexical-choice process itself works on two tiers: between clusters and between near-synonyns of clusters. We describe our prototype implementation of the system, called I-Saurus.

We develop a new computational model for representing the fine-grained meanings of near-synonyms and the differences between them. We also develop a sophisticated lexical-choice process that can decide which of several near-synonyms is most appropriate in any particular context. This research has direct applications in machine translation and text generation, and also in intelligent electronic dictionaries and automated style-checking and document editing.

We first identify the problems of representing near-synonyms in a computational lexicon and show that no previous model adequately accounts for near-synonymy. We then propose a preliminary theory to account for near-synonymy in which the meaning of a word arises out of a context-dependent combination of a context-independent core meaning and a set of explicit differences to its near-synonyms. That is near-synonyms cluster together.

After considering a statistical model and its weaknesses, we develop a clustered model of lexical knowledge, based on the conventional ontological model. The model cuts off the ontology at a coarse grain thus avoiding an awkward proliferation of language-dependent concepts in the ontology, and groups near-synonyms into subconceptual clusters that are linked to the ontology. A cluster acts as a formal usage note that differentiates near-synonyms in terms of fine-grained aspects of denotation, implication, expressed attitude and style. The model is general enough to account for other types of variation, for instance, in collocational behaviour.

We formalize various criteria for lexical choice as preferences to express certain concepts with varying indirectness, to express attitudes, and to establish certain styles. The lexical-choice process chooses the near-synonym that best satisfies the most preferences. The process uses an approximate-matching algorithm that determines how well the set of lexical distinctions of each near-synonym in a cluster matches a set of input preferences.

We implemented the lexical-choice process in a prototype sentence-planning system. We evaluate the system to show that it can make the appropriate word choices when given a set of preferences.

In a conversation, a speaker sometimes has to refer to an object that is not previously known to the hearer. This type of reference occurs frequently in dialogues where the speaker is giving directions to a particular place. To make a reference, the speaker attempts to build a description of the object that will allow the hearer to identify it when she later reaches it.

This thesis presents a computational model of how an agent collaborates on reference in direction-giving dialogues. Viewing language as goal-oriented behaviour, we encode route descriptions referring expressions, and discourse actions in the planning paradigm. This allows an agent to construct plans that achieve communicative goals by means of surface speech actions, and to infer plans and goals from these actions. The basis is that a referring expression plan is acceptable to an agent if she is confident that the plan is adequate as an executable identification plan. By considering the salience of the features used in a referring expression plan, an agent can evaluate her confidence in its adequacy. Driven by the implicit intention of making plans mutually acceptable, the conversants collaborate until the hearer is confident in the adequacy of the current referring expression plan. In doing so, the conversants use suggestion and elaboration discourse actions that operate on the current plan. While collaborating, an agent is in a mental state that includes the intention to achieve the goal of having the direction recipient understand the directions, the plan the agents are currently considering, and a focus of attention into the plan. This collaborative state governs the discourse by sanctioning both the adoption of goals, and the mutual acceptance of plans. Reflecting the inherent symmetry in collaborative dialogue, the model can act as both speaker and hearer, and can play the roles of both the direction-giver and the recipient.

Ambiguities related to intension and their consequent inference failures are a diverse group, both syntactically and semantically. One particular kind of ambiguity that has received little attention so far is whether it is the speaker or the third party to whom a description in an opaque third-party attitude report should be attributed. The different readings lead to different inferences in a system modeling the beliefs of external agents.

We propose that a unified approach to the representation of the alternative readings of intension-related ambiguities can be based on the notion of a descriptor that is evaluated with respect to intensionality, the beliefs of agents, and a time of application. We describe such a representation, built on a standard modal logic, and show how it may be used in conjunction with a knowledge base of background assumptions to license restricted substitution of equals in opaque contexts.

A knowledge of intensions, which are used to designate concepts of objects, is important for natural language processing systems. Certain linguistic phrases can refer either to the concept of an entity or to the entity itself. To properly understand a phrase and to prevent invalid inferences from being drawn, the system must determine the type of reference being asserted. We identify a set of ``opaque'' constructs and suggest that a common mechanism be developed to handle them.

To account for the ambiguities of opaque contexts, noun phrases are translated into descriptors. It must be made explicit to whom the descriptor is ascribed and whether its referent is non-specific or specific. Similarly, sentential constituents should be treated as propositions and evaluated relative to conjectured states of affairs. As a testbed for these ideas we define a Montague-style meaning representation and implement the syntactic and semantic components of a moderate-size NLP system in a logic programming environment.

One must also consider how to disambiguate and interpret such a representation with respect to a knowledge base. Much contextual and world knowledge is required. We characterize what facilities are necessary for an accurate semantic interpretation, considering what is and is not available in current knowledge representation systems.

We propose a statistical measure for the degree of acceptability of light verb constructions, such as take a walk, based on their linguistic properties. Our measure shows good correlations with human ratings on unseen test data. Moreover, we find that our measure correlates more strongly when the potential complements of the construction (such as walk, stroll, or run) are separated into semantically similar classes. Our analysis demonstrates the systematic nature of the roductivity of these constructions.

Generally, when quantitative information is to be presented, some form of graphical presentation is used, often with a textual caption to ensure that the audience notices particular aspects of the data.

This thesis presents the principles that should be followed by a system aiming to produce such captions automatically. The process of caption generation is examined in the context of the standard tasks in text generation. Most previous systems in this area produce textual summaries intended to stand alone; the issues involved in producing a caption differ as the text must be coordinated with the graphic it is to accompany. The thesis also presents CAPUT, a prototype caption-generation system which follows these principles to generate single-sentence captions for information graphics of the type that might appear in a newspaper article. Finally, extensions to CAPUT that would bring it from a prototype to a full-fledged caption generation system are proposed.

Since the introduction of the Lambek calculus in Lambek (1958), there has been a great deal of interest in its usefulness as a grammar for parsing in natural language. Sev- eral variants have been introduced and for each, questions of tractability and usefulness have been posited and answered. Pentus (2003) answered the question of tractability of the original calculus by providing an NP-completeness proof.

The simplest of these variants is the version of the original calculus without the product, the computational complexity of which is as yet unknown. This thesis seeks to identify the precise implications of products on the complexity of parsing in the calculus. Towards this goal, a graph formalism for proofs in the original calculus is extended from the work in Penn (2001).

We then present a simplified, graphical NP-completeness proof for derivability in the Lambek calculus with product and consider the potential intractability of the Lambek calculus without product.

We propose an iterative approach to high-quality pitch-marking of speech recordings without the use of laryngographic data. Our method first identifies islands of pitch marks that can be determined with high confidence. These islands are then extended into neighboring regions. A second round of island identification and extension with lower quality requirements fills the remaining gaps. We evaluate this pitch-marking method against pitch-marks produced with the Praat sound analysis software.

Collaborative writing is increasingly common in both professional and academic fields. One difficulty that collaborative writers face is trying to produce a consistent style, as each writer may bring a distinctive style to the collaborative writing task. I investigated the viability of using stylostatistical techniques to discover describable, computationally tractable stylistic tests to help collaborative writers eliminate such differences.

Writing samples were collected by having graduate students watch two halves of a television episode, then write a summary of each half. Automatically generated syntactic information was used in statistical analyses to ascertain which halves differed significantly. Examination of the statistically significant results revealed a wide variety of inconsistencies on various levels. Many of these inconsistencies were not immediately obvious before the stylostatistical test results were known. I therefore conclude that stylostatistical techniques provide a promising approach for creating a computer tool to accelerate and improve people's detection of stylistic inconsistencies.

When two or more writers collaborate on a document by each contributing pieces of text, the problem can arise that while each might be an exemplary piece of writing, they do not cohere into a document that speaks with a single voice. That is, they are stylistically inconsistent. But given a stylistically inconsistent document, people often find it hard to articulate exactly where the problems lie. Rather, they feel that something is wrong but can't quite say why.

An example of stylistic inconsistency can be seen in the following sentence, which is from a brochure given to hospital patients who are to undergo a cardiac catheterization. (The parenthesized numbers are ours, to refer to the individual clauses.)

(1) Once the determination for a cardiac catheterization has been made, (2) various tests will need to be performed (3) to properly assess your condition prior to the procedure.

Clause 1 and (to a slightly lesser extent) clause 3 are in medical talk, as if in a formal communication from physician to physician; clause 2 is much more informal, and is expressed in ordinary lay language. The effect of the two styles mixed together in the one sentence is a feeling of incongruity---which was presumably not intended by the author or authors. This example, however, is unusual in its brevity. More often, the problem of inconsistency emerges only over longer stretches of text, especially where the granularity of the multiple authorship is at the paragraph, section, or chapter level. Moreover, while stylistic inconsistencies arise primarily in jointly written documents, we do not exclude the possibility of their occurrence in singly authored texts, especially those where different parts were written at different times or, initially, for different purposes.

Our ultimate goal in this research is to build software that will help with this problem---that will point out stylistic inconsistencies in a document, and perhaps suggest how they can be fixed. In this paper, we report some of our initial explorations and data collection.

One of the most difficult tasks facing anyone who must compile or maintain any large, collaboratively-written document is to foster a consistent style throughout. In this thesis, we explore whether it is possible to identify stylistic inconsistencies within documents even in principle given our understanding of how style can be captured statistically.

We carry out this investigation by computing stylistic statistics on very small samples of text comprising a set of synthetic collaboratively-written documents, and using these statistics to train and test a series of neural networks. We are able to show that this method does allow us to recover the boundaries of authors' contributions. We find that time-delay neural networks, hitherto ignored in this field, are especially effective in this regard. Along the way, we observe that statistics characterizing the syntactic style of a passage appear to hold much more information for small text samples than those concerned with lexical choice or complexity.

We describe a novel method for automatically generating hypertext links within and between newspaper articles. The method is based on lexical chaining a technique for extracting the sets of related words that occur in texts. Links between the paragraphs of a single article are built by considering the distribution of the lexical chains in that article. Links between articles are built by considering how the chains in the two articles are related. By using lexical chaining we mitigate the problems of synonymy and polysemy that plague traditional information retrieval approaches to automatic hypertext generation.

In order to motivate our research, we discuss the results of a study that shows that humans are inconsistent when assigning hypertext links within newspaper articles. Even if humans were consistent, the time needed to build a large hypertext and the costs associated with the production of such a hypertext make relying on human linkers an untenable decision. Thus we are left to automatic hypertext generation.

Because we wish to determine how our hypertext generation methodology performs when compared to other proposed methodologies, we present a study comparing the hypertext linking methodology that we propose with a methodology based on a traditional information retreival approach. In this study, subjects were asked to perform a question-answering task using a combination of links generated by our methodology and the competing methodology. The result is that links between articles generated using our methodology have a significant advantage over links generated by the competing methodology. We show combined results for all subjects tested, along with results based on subjects' experience in using the World Wide Web.

We detail the construction of a system for performing automatic hypertext generation in the context of an online newspaper. The proposed system is fully capable of handling large databases of news articles in an efficient manner.

In order to refer to an object, a speaker attempts to build a description of the object that will allow the hearer to identify it. Since the description might not enable the hearer to identify the referent, the speaker and hearer might engage in a clarification subdialogue in which they collaborate in order to make the referring action successful.

This thesis presents a computational model of how conversational participants collaborate in order to make a referring action successful. The model is based on the view of language as goal-directed behavior. We propose that the content of a referring expression can be accounted for by the planning paradigm. Not only does this approach allow the process of building referring expressions and identifying their referent to be captured by plan construction and plan inference, it also allows us to account for clarifications of referring expressions by using meta-plans. These meta-plans reason about and manipulate referring expression plans in order to capture how conversational participants collaborate in order to make the referring action successful. To complete this picture we show how participants can infer goals underlying referring expression plans or clarification plans, and how these inferred goals can be used by the participant to adopt its own goals to clarify the referring expression. An important aspect of this process is that subsequent clarifications can either clarify the previous clarification or can clarify the referring expression resulting from the previous clarification. Hence, for the latter case, the same meta-plans that are used to clarify the original referring expression can be used to model the subsequent clarifications.

This implicit philosophy is challenged in two ways: 1. Reader-based views of meaning and language understanding: Fish and other postmodernists claim that readers bring their own knowledge and experience to the interpretation of text, which is not necessarily the same as that of the writer or any other reader. Hence the annotation methodology is useful only if working within what Fish calls an ``interpretive community''. 2. Individual differences in cognitive language comprehension processes: It is well established that there are individual differences in the cognitive processes and strategies of language comprehension and that these can sometimes lead to different interpretations of a text.

It's thus not a surprise that CL often finds itself with relatively low inter-annotator agreement on its marked-up data, and systems whose performance is mediocre when trained with or tested on this data. CL needs to recognize the limitations of its implicit philosophy of language understanding and aim instead for systems that are more-explicitly adapted to the individual user -- sytems in which aspects of language that are subject to notable individual differences are indeed modelled on an individual basis.

Knowing the degree of antonymy between words has widespread applications in natural language processing. Manually-created lexicons have limited coverage and do not include most semantically contrasting word pairs. We present a new automatic and empirical measure of antonymy that combines corpus statistics with the structure of a published thesaurus. The approach is evaluated on a set of closest-opposite questions, obtaining a precision of over 80%. Along the way, we discuss what humans consider antonymous and how antonymy manifests itself in utterances.

Words in the context of a target word have long been used as features by supervised word-sense classifiers. Mohammad and Hirst (2006a) proposed a way to determine the strength of association between a sense or concept and co-occurring words --- the distributional profile of a concept (DPC) --- without the use of manually annotated data. We implemented an unsupervised naive Bayes word sense classifier using these DPCs that was best or within one percentage point of the best unsupervised systems in the Multilingual Chinese--English Lexical Sample Task (task #5) and the English Lexical Sample Task (task #17). We also created a simple PMI-based classifier to attempt the English Lexical Substitution Task (task #10); however, its performance was poor.

We present the idea of estimating semantic distance in one, possibly resource-poor, language using a knowledge source in another, possibly resource-rich, language. We do so by creating cross-lingual distributional profiles of concepts, using a bilingual lexicon and a bootstrapping algorithm, but without the use of any sense-annotated data or word-aligned corpora. The cross-lingual measures of semantic distance are evaluated on two tasks: (1) estimating semantic distance between words and ranking the word pairs according to semantic distance, and (2) solving Reader's Digest `Word Power' problems. In task (1), cross-lingual measures are superior to conventional monolingual measures based on a wordnet. In task (2) cross-lingual measures are able to solve more problems correctly, and despite scores being affected by many tied answers, their overall performance is again better than the best monolingual measures.

We present a method to automatically acquire a new type of lexical resource: a knowledge-base of near-synonym differences. We develop an unsupervised decision-list algorithm that learns extraction patterns from a special dictionary of synonym differences. The patterns are then used to extract knowledge from the text of the dictionary.

The initial knowledge-base is later enriched with information from other machine-readable dictionaries. Information about the collocational behavior of the near-synonyms is acquired from free text. The knowledge-base is used by Xenon, a natural language generation system that shows how the new lexical resource can be used to choose the best near-synonym in specific situations.

We develop a new computational model for representing the fine-grained meanings of near-synonyms and the differences between them. We also develop a sophisticated lexical-choice process that can decide which of several near-synonyms is most appropriate in a particular situation. This research has direct applications in machine translation and text generation.

We first identify the problems of representing near-synonyms in a computational lexicon and show that no previous model adequately accounts for near-synonymy. We then propose a preliminary theory to account for near-synonymy, relying crucially on the notion of granularity of representation, in which the meaning of a word arises out of a context-dependent combination of a context-independent core meaning and a set of explicit differences to its near-synonyms. That is, near-synonyms cluster together.

We then develop a clustered model of lexical knowledge, derived from the conventional ontological model. The model cuts off the ontology at a coarse grain, thus avoiding an awkward proliferation of language-dependent concepts in the ontology, and groups near-synonyms into subconceptual clusters that are linked to the ontology. A cluster differentiates near-synonyms in terms of fine-grained aspects of denotation, implication, expressed attitude, and style. The model is general enough to account for other types of variation, for instance in collocational behaviour.

An efficient, robust, and flexible fine-grained lexical-choice process is a consequence of a clustered model of lexical knowledge. To make it work, we formalize criteria for lexical choice as preferences to express certain concepts with varying indirectness, to express attitudes, and to establish certain styles. The lexical-choice process itself works on two tiers: between clusters and between near-synonyns of clusters. We describe our prototype implementation of the system, called I-Saurus.

Because chains of semantically related words express semantic continuity, such lexical chains can play an important role in the detection of malapropisms. A malapropism is a correctly spelled word that does not fit in the context where it is used because it is the result of a spelling error on a different word that was intended.

We first assume that such a word has much less probability of being inserted in any chain with other words. If this assumption is correct, words that failed to be inserted with other words can be considered as potential malapropisms. A mechanism that generates spelling replacements can then be used to generate replacement candidates. The second assumption is that whenever a spelling replacement can be inserted in a chain with other words, this replacement is likely to be the intended word for which a malapropism has been substituted.

The algorithm proposed here to detect lexical chains uses the on-line thesaurus WordNet to automatically quantify semantic relations between words. Chains identified by the algorithm may have two major problems: over- or under-chaining. Under-chaining---the inability to link a pair of related words---might be caused by an inadequacy of WordNet's set of relations, a lack of connections in WordNet's set of relations, a lack of connections in WordNet, a lack of consistency in the semantic proximity expressed by WordNet's links, and a poor algorithm for chaining. Over-chaining---the linking of two poorly related words---might happen whenever two semantically distant words are close to each other in WordNet's graph. Over-chaining often results in the merging of two chains.

The results of the experiment show the validity of the basic assumptions. However, improvements to the lexical-chaining algorithm are required before the malapropism detection algorithm can be integrated into a commercial spelling checker.

A recent and growing development in Web applications has been the advent of various tools that claim to ``customize'' access to information on the Web by allowing users to specify the kinds of information they want to receive without having to search for it or sift through masses of irrelevant material. But this kind of customization is really just a crude filtering of raw Web material in which the user simply selects the ``channels'' of information she wishes to receive; this selection of information sources is hardly more ``customization'' than someone deciding to tune their television to a certain station. True customization, or tailoring, of information would be done for the user by a system that had access to an actual model of the user, a profile of the user's interests and characteristics. And such tailoring would involve much more than just selecting streams of basic content: the content of the text, whether for on-line Web page or a paper document, would be carefully selected structured, and presented in the manner best calculated to appeal to a particular individual. Adaptive-hypertext presentation comes closest to achieving this kind of document tailoring, but the current techniques used for adapting the content of a document to a particular user generally only involve some form of selectively showing (or hiding) portions of text or choosing whole variants of larger parts of the document.

If the Web document designer wishes to write and present material in a way that will communicate well with the user, then just displaying the most relevant chunks of information will not be sufficient. For effective communication, both the form and content of the language used in a document should be tailored in rhetorically significant ways to best suit a user's particular personal characteristics and preferences. Ideally, we would have Web-based natural language generation systems that could produce fully customized and customizable documents on demand by individual users, according to a formal user model. As a first step in this direction, we have been investigating applications of our earlier work on pragmatics in natural language processing to building systems for the automated generation of Web documents tailored to the individual reader.

When two or more writers collaborate on a document by each contributing pieces of text, the problem can arise that while each might be an exemplary piece of writing, they do not cohere into a document that speaks with a single voice. That is, they are stylistically inconsistent. But given a stylistically inconsistent document, people often find it hard to articulate exactly where the problems lie. Rather, they feel that something is wrong but can't quite say why.

An example of stylistic inconsistency can be seen in the following sentence, which is from a brochure given to hospital patients who are to undergo a cardiac catheterization. (The parenthesized numbers are ours, to refer to the individual clauses.)

(1) Once the determination for a cardiac catheterization has been made, (2) various tests will need to be performed (3) to properly assess your condition prior to the procedure.

Clause 1 and (to a slightly lesser extent) clause 3 are in medical talk, as if in a formal communication from physician to physician; clause 2 is much more informal, and is expressed in ordinary lay language. The effect of the two styles mixed together in the one sentence is a feeling of incongruity---which was presumably not intended by the author or authors. This example, however, is unusual in its brevity. More often, the problem of inconsistency emerges only over longer stretches of text, especially where the granularity of the multiple authorship is at the paragraph, section, or chapter level. Moreover, while stylistic inconsistencies arise primarily in jointly written documents, we do not exclude the possibility of their occurrence in singly authored texts, especially those where different parts were written at different times or, initially, for different purposes.

Our ultimate goal in this research is to build software that will help with this problem---that will point out stylistic inconsistencies in a document, and perhaps suggest how they can be fixed. In this paper, we report some of our initial explorations and data collection.

Many studies have shown that health-education messages and patient instructions are more effective when closely tailored to the particular condition and characteristics of the individual recipient. But in situations where many factors interact -- for example, in explaining the pros and cons of hormone replacement therapy -- the number of different combinations is far too large for a set of appropriately tailored messages to be produced in advance.

The HealthDoc project is presently developing linguistic techniques for producing, on demand, health-education and patient-information brochures that are customized to the medical and personal characteristics of an individual patient.

For each topic, HealthDoc requires a `master document' written by an expert on the subject with the help of a program called an `authoring tool'. The writer decides upon the basic elements of the text -- clauses and sentences -- and the patient conditions under which each element should be included in the output. The program assists the writer in building correctly structured master-document fragments and annotating them with the relationships and conditions for inclusion.

When a clinician wishes to give a patient a particular brochure from HealthDoc, she will select it from a menu and specify the name of the patient. HealthDoc will use information from the patient's on-line medical record to then create and print a version of the document appropriate to that patient, by selecting the appropriate pieces of material and then performing the necessary linguistic operations to combine them into a single, coherent text.

Any text or dialogue establishes a linguistic context within which subsequent utterances must be understood. And beyond the linguistic context is the participatory context. A speaker or writer directs an utterance or text toward a hearer or reader with a particular purpose --- to inform, to amuse, to collaborate in a task, perhaps. The form and content of the utterance are chosen accordingly, and the listener or reader must infer the underlying intent as part of their understanding.

This article explores recent research on language use in context going beyond sentence boundariees and processing discourse --- treating texts or dialogues as whole units composed of interrelated parts, not merely as sequences of isolated sentences. The article discusses the comprehension and production of language, looking at both texts and dialogues. A text to be processed might be, for example, a newspaper or magazine article being translated into another language or whose content is to be ``understood'' or abstracted in an information storage and retrieval system. A dialogue to be processed might be a conversation, spoken or typed, between a human and a computer, in service of some collaborative task. Many of the problems described here occur in both kinds of discourse.

The underlying goal of the research described in this special section of Communications of the ACM is to move beyond `toy' systems and come to grips with `real language'. While the research described in the other articles in this section focuses on robustly processing massive amounts of text, the work described here focuses on understanding, in computational terms, the complexities and subtleties of language as people really use it.

In an article of this length, we cannot hope to describe all of the recent important work addressing language use in context. For example, we will not cover pronoun resolution, ellipsis, metaphor, or many aspects of belief ascription.

During a conversation, agents can easily come to have different beliefs about the meaning or discourse role of some utterance. Participants normally rely on their expectations to determine whether the conversation is proceeding smoothly: if nothing unusual is detected, then understanding is presumed to occur. Conversely, when an agent says something that is inconsistent with another's expectations, then the other agent may change her interpretation of an earlier turn and direct her response to the reinterpretation accomplishing what is known as a fourth-turn repair.

Here we describe an abductive account of the interpretation of speech acts and the repair of speech act misunderstandings. Our discussion considers the kinds of information that participants use to interpret an utterance, even if it is inconsistent with their beliefs. It also considers the information used to design repairs. We describe a mapping between the utterance-level forms (semantics) and discourse-level acts (pragmatics), and a relation between the discourse acts and the beliefs and intentions that they express. We specify for each discourse act, the acts that might be expected, if the hearer has understood the speaker correctly. We also describe our account of belief and intention, distinguishing the beliefs agents actually have from the ones they act as if they have when they perform a discourse act. To support repair, we model how misunderstandings can lead to unexpected actions and utterances and describe the processes of interpretation and repair. To illustrate the approach we show how it accounts for an example repair.

We show how parsing can be formulated as an energy minimization problem. We describe our model in terms of a connectionist network. In this network we use a parallel computation scheme similar to the one used in the Boltzmann machine and apply simulated annealing, a stochastic optimization method. We show that at low temperatures the time average of the visited states at thermal equilibrium represents the correct parse of the input sentence.

Our treatment of parsing as an energy minimization problem enables us to formulate general rules for the setting of weights and thresholds in the network. We also consider an alternative to the commonly used energy function. Using this new function, one can choose a provably correct set of weights and thresholds for the network and still have an acceptable rate of convergence in the annealing process.

The parsing scheme is built from a small set of connectionist primitives that represent the grammar rules. These primitives are linked together using pairs of computing units that behave like discrete switches. These units are used as binders between concepts represented in the network. They can be linked in such a way that individual rules can be selected from a collection of rules, and are very useful in the construction of connectionist schemes for any form of rule-based processing.

The problem of style is highly relevant to computational linguistics, but current systems deal only superficially, if at all, with subtle but significant nuances of language. Expressive effects, together with their associated meaning, contained in the style of a text are lost to analysis and absent from generation.

We have developed an approach to the computational treatment of style that is intended to eventually incorporate three selected components---lexical syntactic, and semantic. In this paper, we concentrate on certain aspects of syntactic style. We have designed and implemented a computational theory of goal-directed stylistics that can be used in various applications, including machine translation, second-language instruction and natural language generation.

We have constructed a vocabulary of style that contains both primitive and abstract elements of style. The primitive elements describe the stylistic effects of individual sentence components. These elements are combined into patterns that are described by a stylistic meta-language, the abstract elements, that define the concordant and discordant stylistic effects common to a group of sentences. Higher-level patterns are built from the abstract elements and associated with specific stylistic goals, such as clarity or concreteness. Thus, we have defined rules for a syntactic stylistic grammar at three interrelated levels of description: primitive elements, abstract elements, and stylistic goals. Grammars for both English and French have been constructed, using the same vocabulary and the same development methodology. Parsers that implement these grammars have also been built.

The stylistic grammars codify aspects of language that were previously defined only descriptively. The theory is being applied to various problems in which the form of an utterance conveys an essential part of meaning and so must be precisely represented and understood.

If we want to describe the action of someone who is looking out a window for an extended time, how do we choose between the words gazing, staring, and peering? What exactly is the difference between an argument, a dispute, and a row? In this paper, we describe our research in progress on the problem of lexical choice and the representations of world knowledge and of lexical structure and meaning that the task requires. In particular, we wish to deal with nuances and subtleties of denotation and connotation---shades of meaning and of style---such as those illustrated by the examples above.

We are studying the task in two related contexts: machine translation and the generation of multilingual text from a single representation of content. In the present paper, we concentrate on issues in lexical representation. We describe a methodology, based on dictionary usage notes, that we are using to discover the dimensions along which similar words can be differentiated, and we discuss a two-part representation for lexical differentiation.

Intelligent text-based systems will vary as to the degree of difficulty of the texts they deal with. Some may have a relatively easy time with texts for which fairly superficial processes will get useful results, such as, say, The New York Times or Julia Child's Favorite Recipes. But many systems will have to work on more difficult texts. Often, it is the complexity of the text that makes the system desirable in the first place. It is for such systems that we need to think about making the deeper methods that are already studied in AI and computational linguistics more robust and suitable for processing long texts without interactive human help. The dilemma is that on one hand, we have the limitations of raw text databases and superficial processing methods; on the other we have the difficulty of deeper methods and conceptual representations. Our proposal here is to have the best of both, and accordingly we develop the notion of a heterogeneous, or mixed, type of representation.

In our model, a text base permits two parallel representations of meaning: the text itself, for presentation to human users, and a conceptual encoding of the text, for use by intelligent components of the system. The two representations are stored in parallel; that is, there are links between each unit of text (a sentence or paragraph in most cases) and the corresponding conceptual encoding. This encoding could be created en masse when the text was entered into the system. But if it is expected that only a small fraction of the text base will ever be looked at by processes that need the conceptual representations, then the encoding could be performed on each part of the text as necessary for inference and understanding to answer some particular request. The results could then be stored so that they don't have to be redone if the same area of the text is searched again. Thus, a text would gradually grow its encoding as it continues to be used. (And the work will never be done for texts or parts of texts that are never used.)

So far, this is straightforward. But we can go one step further. The encoding itself may be deep or shallow at different places, depending on what happened to be necessary at the time it was generated---or on what was possible. Or, to put it a different way, we can view natural-language text and AI-style knowledge representations as two ends of a spectrum.

This article describes an intelligent computer-assisted language instruction system that is designed to teach principles of syntactic style to students of English. Unlike conventional style checkers, the system performs a complete syntactic analysis of its input, and takes the student's stylistic intent into account when providing a diagnosis. Named STASEL, for Stylistic Treatment At the Sentence Level, the system is specifically developed for the teaching of style, and makes use of artificial intelligence techniques in natural language processing to analyze free-form input sentences interactively.

An important contribution of STASEL is its ability to provide stylistic guidance according to the specific writing goals of clarity and conciseness. In an attempt to remedy some of the deficiencies of existing instructional software, STASEL's design demonstrates how stylistic instruction can be effectively computerized, while laying the groundwork for the creation of intelligent tutoring systems for teaching writing.

The enterprise of artificial intelligence has given rise to a new class of software systems. These software systems, commonly called expert systems, or knowledge-based systems, are distinguished in that they contain, and can apply, knowledge or some particular skill or expertise in the execution of a task. These systems embody, in some form, humanlike expertise. The construction of such software therefore requires that we somehow get hold of the knowledge and transfer it into the computer, representing it in a form usable by the machine. This total process has come to be called knowledge acquisition (KA). The necessity for knowledge representation---the describing or writing down of the knowledge in machine-usable form---underlies and shapes the whole KA process and the development of expert system software.

Concern with knowledge is nothing new, but some genuinely new issues have been introduced by the construction of expert systems. The processes of KA and KR are envisaged as the means through which software is endowed with expertise-producing knowledge. This vision however, is problematic. The connection between knowledge and expertise itself is not clearly understood, though the phrases ``knowledge-based system'' and ``expert system'' tend to be used interchangeably, as if all expertise were knowledge-like. This haziness about basics also leads to the unrealistic expectation that the acquisition of knowledge in machine-usable form will convey powers of expert performance upon computer software. These assumptions are questionable. For a deeper understanding, we must clarify the concepts of knowledge acquisition and knowledge representation, and the concept of knowledge itself, as they are used in the computer context. That is the first goal of this chapter. The second goal is to explicate the issues involved in KA and show how they are amenable to research by experimental or cognitive psychologists.

The chapter will be organized as follows. In the second section we will set the stage for cross-disciplinary discussion by sketching the history of artificial intelligence and KA. In the third section, we try to answer the question, What is knowledge? by examining the various approaches that people have taken in trying to grasp the nature of knowledge. In the fourth section, we discuss the KA problem. In particular, we present a model of the KA process to reconcile and pull together the various approaches to KA that are found in the literature. This basic model of KA will be used in the commentaries chapter (chapter 17 of this book) to compare the contributions to this volume. In the present introductory chapter, we outline some crucial current issues, especially those that could be fruitfully addressed by experimental psychologists, and as a conclusion we try to point to some future directions for research.

Computational linguists are a vicious warrior tribe. Unconstrained by traditional disciplinary boundaries, they invade and plunder neighboring disciplines for attractive theories to incorporate into their own. The latest victim of these attacks is sociology---in particular, a branch of ethnomethodological sociolinguistics called Conversation Analysis.

The book reviewed here, Computers and conversation, is the first significant result of this. It is based on a symposium held at the University of Surrey in September 1989. Its purpose is to show what CA has to offer to the study of human--computer interaction especially interaction in natural language. In this review article, I use the book to explore at some length the question of whether Conversation Analysis has indeed anything to say to computational linguistics.

If knowledge representation formalisms are to be suitable for semantic interpretation of natural language, they must be more adept with representations of existence and non-existence than they presently are. Quantifiers must sometimes range over non-existent entities. I review the philosophical background, including Anselm and Kant, and exhibit some ontological problems that natural language sentences pose for knowledge representation. The paraphrase methods of Russell and Quine are unable to deal with many of the problems.

Unfortunately, the shortcomings of the Russell--Quine ontology are reflected in most current knowledge representation formalisms in AI. Several alternatives are considered, including some intensional formalisms and the work of Hobbs, but all have problems. Free logics and possible worlds don't help either. But useful insights are found in the Meinongian theory of Parsons, in which a distinction between nuclear and extranuclear kinds of predicates is made and used to define a universe over which quantification ranges. If this is combined with a naive ontology, with about eight distinct kinds of existence, a better approach to the representation of non-existence can be developed within Hobbs's basic formalism.

The most successful example of distributed artificial intelligence ever constructed is the modern corporation. It is our view that a corporation is an instance of AI---a generalized, distributed AI system. We believe that this more general view carries lessons for the construction of computer-based intelligence.

We use the term corporation to include not only large companies, but also similar organizations such as government departments. Such organizations are typically composed of small management groups that, in turn, are organized into larger sections or divisions. The result is usually a tree structure, or something close to that.

The hardware from which this structure is built is of two kinds: equipment and people. The equipment includes all the corporation's buildings, machinery, furniture, and so on. The people are its employees. But, we submit, the intelligence in the corporation lies not so much in the people as in the other components of its hierarchy. Each management group, each corporate division, and, indeed, the corporation itself may be regarded as an abstract intelligent agent: an entity with its own `mind', a mind that the other components influence through symbolic communication.

This paper describes an approach to computer-assisted language instruction based on the application of artificial intelligence technology to grammatical error diagnosis. We have developed a prototype system, Scripsi, capable of recognising a wide range of errors in the writing of language learners. Scripsi not only detects ungrammaticality, but hypothesizes its cause and provides corrective information to the student. These diagnostic capabilities rely on the application of a model of the learner's linguistic knowledge.

Scripsi operates interactively, accepting the text of the student's composition and responding with diagnostic information about its grammatical structure. In contrast to the narrowly defined limits of interaction available with automated grammatical drills, the framework of interactive composition provides students with the opportunity to express themselves in the language being learned.

Although Scripsi's diagnostic functions are limited to purely structural aspects of written language, the way is left open for the incorporation of semantic processing. The design of Scripsi is intended to lay the groundwork for the creation of intelligent tutoring systems for second language instruction. The development of such expertise will remedy many of the deficiencies of existing technology by providing a basis for genuinely communicative instructional tools --- computerised tutors capable of interacting linguistically with the student.

The research is based on the assumption that the language produced by the language learner, ``learner language'', differs in systematic ways from that of the native speaker. In particular, the learner's errors can be attributed primarily to two causes: the operation of universal principles of language acquisition and the influence of the learner's native language. A central concern in the design of Scripsi has been the incorporation of a psychologically sound model of the linguistic competence of the second language learner.

A significant part of the meaning of any text lies in the author's style. Different choices of words and syntactic structure convey different nuances in meaning, which must be carried through in any translation if it is to be considered faithful. Up to now, machine translation systems have been unable to do this. Subtleties of style are simply lost to current machine-translation systems.

The goal of the present research is to develop a method to provide machine-translation systems with the ability to understand and preserve the intent of an author's stylistic characteristics. Unilingual natural language understanding systems could also benefit from an appreciation of these aspects of meaning. However, in translation, style plays an additional role, for here one must also deal with the generation of appropriate target-language style.

Consideration of style in translation involves two complementary, but sometimes conflicting, aims:

• The translation must preserve, as much as possible, the author's stylistic intent --- the information conveyed through the manner of presentation.
• But it must have a style that is appropriate and natural to the target language.

The study of comparative stylistics is, in fact, guided by the recognition that languages differ in their stylistic approaches: each has its own characteristic stylistic preferences. The stylistic differences between French and English are exemplified by the predominance of the pronominal verb in French. This contrast allows us to recognize the greater preference of English for the passive voice:

• (a) Le jambon se mange froid.
  (b) Ham is eaten cold.

Such preferences exist at the lexical, syntactic, and semantic levels, but reflect differences in the two languages that can be grouped in terms of more-general stylistic qualities. French words are generally situated at a higher level of abstraction than that of the corresponding English words which tend to be more concrete (Vinay and Darbelnet 1958, 59). French aims for precision while English is more tolerant of vagueness. (Duron 1963 109).

So, a French source text may be abstract and very precise in style, but the translated English text should be looser and less abstract, while still retaining the author's stylistic intent. Translators use this kind of knowledge about comparative stylistics as they clean up raw machine-translation output, dealing with various kinds of stylistic complexities.

Research on computer programs for understanding natural language can be both a consumer of psycholinguistic research on ambiguity and a contributor to such work. The fields have different ways of thinking, different concerns, and different criteria as to what counts as a result. I will show that, nevertheless, both fields may profit from cooperation, by giving examples from my own work and from that of some of my students showing how issues raised or results obtained in one field can be of use in the other. The examples will include computer systems for lexical, structural, and thematic disambiguation that were inspired by recent psycholinguistic work. I will also show computational work on ambiguities of description attribution and other ``large ambiguities'' that raise, I will argue interesting problems for psycholinguists.

If knowledge representation formalisms are to be suitable for semantic interpretation of natural language, they must be more adept with representations of existence and non-existence than they presently are. I review the philosophical background, and exhibit some ontological problems for KR. I then look at the shortcomings of current approaches, including several intensional formalisms and the work of Hobbs. The Meinongian theory of Parsons is considered. Lastly, I present a naïve ontology for knowledge representation, identifying about nine distinct kinds of existence.

SORTAL is a software assistant for performing meaning-triangle-based sortal analysis. This paper describes its architecture and possible implementations. Conceptual analysis and conceptual modelling are central components of the informant-and-analyst-based, natural language-mediated knowledge acquisition process, but focusing on concepts is not enough. The ``aboutness'' of the language used in the interview forces the analyst to recognize distinctions between words, concepts, referents, and cogniting agents. Creating frame-like representations for agent-centred meaning triangles, as well as updating ontologies, keeping track of multiple domains of discourse, and the creation of knowledge bases for use in other systems are tasks that can be assisted by a software tool such as SORTAL. We sketch the requirements for such an assistant give examples of its operation, and address implementation issues.

We are developing stylistic grammars to provide the basis for a French and English stylistic parser. Our stylistic grammar is a branching stratificational model, built upon a foundation dealing with lexical, syntactic, and semantic stylistic realizations. Its central level uses a vocabulary of constituent stylistic elements common to both English and French, while the top level correlates stylistic goals, such as clarity and concreteness, with patterns of these elements.

Overall, we are implementing a computational schema of stylistics in French-to-English translation. We believe that the incorporation of stylistic analysis into machine translation systems will significantly reduce the current reliance on human post-editing and improve the quality of the systems' output

Any computer system for understanding natural language input (even in relatively weak senses of the word understanding) needs to be able to resolve lexical ambiguities. In this paper, I describe the lexical ambiguity resolution component of one such system.

The basic strategy used for disambiguation is ``do it the way people do.'' While cognitive modeling is not the primary goal of this work, it is often a good strategy in artificial intelligence to consider cognitive modeling anyway; finding out how people do something and trying to copy them is a good way to get a program to do the same thing. In developing the system below, I was strongly influenced by psycholinguistic research on lexical access and negative priming---in particular by the results of Swinney; Seidenberg, Tanenhaus, Leiman, and Bienkowski; and Reder. I will discuss the degree to which the system is a model of ambiguity resolution in people.

A new approach to semantic interpretation in natural language understanding is described, together with mechanisms for both lexical and structural disambiguation that work in concert with the semantic interpreter.

ABSITY, the system described, is a Montague-inspired semantic interpreter. Like Montague formalisms, its semantics is compositional by design and is strongly typed, with semantic rules in one-to-one correspondence with the meaning-affecting rules of a Marcus parser. The Montague semantic objects---functors and truth conditions---are replaced with elements of the frame language FRAIL. ABSITY's partial results are always well-formed FRAIL objects.

A semantic interpreter must be able to provide feedback to the parser to help it handle structural ambiguities. In ABSITY, this is done by the ``Semantic Enquiry Desk,'' a process that answers the parser's questions on semantic preferences. Disambiguation of word senses and of case slots is done by a set of procedures, one per word or slot, each of which determines the word or slot's correct sense, in cooperation with the other processes.

It is from the fact that partial results are always well-formed semantic objects that the system gains much of its power. This, in turn, comes from the strict correspondence between syntax and semantics in ABSITY. The result is a foundation for semantic interpretation superior to previous approaches.

Most theories of presupposition implicitly assume that presuppositions are facts, and that all agents involved in a discourse share belief in the presuppositions that it generates. These unrealistic assumptions can be eliminated if each presupposition is treated as the belief of an agent. However, it is not enough to consider only the beliefs of the speaker; we show that the beliefs of other agents are often involved. We describe a new model, including an improved definition of presupposition, that treats presuppositions as beliefs and considers the beliefs of all agents involved in the discourse. We show that treating presuppositions as beliefs makes it possible to explain phenomena that cannot be explained otherwise.

Ambiguities related to intension and their consequent inference failures are a diverse group, both syntactically and semantically. One particular kind of ambiguity that has received little attention so far is whether it is the speaker or the third party to whom a description in an opaque third-party attitude report should be attributed. The different readings lead to different inferences in a system modeling the beliefs of external agents.

We propose that a unified approach to the representation of the alternative readings of intension-related ambiguities can be based on the notion of a descriptor that is evaluated with respect to intensionality, the beliefs of agents, and a time of application. We describe such a representation, built on a standard modal logic, and show how it may be used in conjunction with a knowledge base of background assumptions to license restricted substitution of equals in opaque contexts.

Human language understanding sometimes jumps to conclusions without having all the information it needs or even using all that it has. So, therefore should any psychologically real language-understanding program. How this can be done in a discrete computational model is not obvious. In this paper, I look at three aspects of the problem:

• When is information ignored?
• When is a decision made out of impatience?
• When is no decision made at all?

Traditionally, translation from the parse tree representing a sentence to a semantic representation (such as frames or procedural semantics) has always been the most ad hoc part of natural language understanding (NLU) systems. However, recent advances in linguistics most notably the system of formal semantics known as Montague semantics, suggest ways of putting NLU semantics onto a cleaner and firmer foundation. We are using a Montague-inspired approach to semantics in an integrated NLU and problem-solving system that we are building. Like Montague's, our semantics are compositional by design and strongly typed, with semantic rules in one-to-one correspondence with the meaning-affecting rules of a Marcus-style parser. We have replaced Montague's semantic objects, functors and truth conditions with the elements of the frame language Frail, and added a word sense and case slot disambiguation system. The result is a foundation for semantic interpretation that we believe to be superior to previous approaches.

Recent research in anaphora resolution has emphasized the effects of discourse structure and cohesion in determining what concepts are available as possible referents, and how discourse cohesion can aid reference resolution. Five approaches, all within this paradigm and yet all distinctly different, are presented, and their strengths and weaknesses evaluated.

This paper seeks to improve HPSG engineering through the design of more terse, readable, and intuitive type signatures. It argues against the exclusive use of IS-A networks and, with reference to the English Resource Grammar, demonstrates that a collection of higher-order datatypes are already acutely in demand in contemporary HPSG design. Some default specification conventions to assist in maximizing the utility of higher-order type constructors are also discussed.

Any text or dialogue establishes a linguistic context within which subsequent utterances must be understood. And beyond the linguistic context is the participatory context. A speaker or writer directs an utterance or text toward a hearer or reader with a particular purpose --- to inform, to amuse, to collaborate in a task, perhaps. The form and content of the utterance are chosen accordingly, and the listener or reader must infer the underlying intent as part of their understanding.

This article explores recent research on language use in context going beyond sentence boundariees and processing discourse --- treating texts or dialogues as whole units composed of interrelated parts, not merely as sequences of isolated sentences. The article discusses the comprehension and production of language, looking at both texts and dialogues. A text to be processed might be, for example, a newspaper or magazine article being translated into another language or whose content is to be ``understood'' or abstracted in an information storage and retrieval system. A dialogue to be processed might be a conversation, spoken or typed, between a human and a computer, in service of some collaborative task. Many of the problems described here occur in both kinds of discourse.

The underlying goal of the research described in this special section of Communications of the ACM is to move beyond `toy' systems and come to grips with `real language'. While the research described in the other articles in this section focuses on robustly processing massive amounts of text, the work described here focuses on understanding, in computational terms, the complexities and subtleties of language as people really use it.

In an article of this length, we cannot hope to describe all of the recent important work addressing language use in context. For example, we will not cover pronoun resolution, ellipsis, metaphor, or many aspects of belief ascription.

Most theories of presupposition implicitly assume that presuppositions are facts, and that all agents involved in a discourse share belief in the presuppositions that it generates. These unrealistic assumptions can be eliminated if each presupposition is treated as the belief of an agent. However, it is not enough to consider only the beliefs of the speaker; we show that the beliefs of other agents are often involved. We describe a new model, including an improved definition of presupposition, that treats presuppositions as beliefs and considers the beliefs of all agents involved in the discourse. We show that treating presuppositions as beliefs makes it possible to explain phenomena that cannot be explained otherwise.

The full communicative content of an utterance consists of its direct meaning as well as a variety of indirect information which can be inferred from the utterance. Presupposition is one category of such information.

Many theories of presupposition have been postulated. Most implicitly assume that presuppositions are facts, and that all agents involved in discourse share knowledge of them. We argue that these are unrealistic assumptions and propose a new view which considers presuppositions to be beliefs associated with particular agents. We then develop a definition of presupposition which embodies this view. We conclude that a model of presupposition which incorporates agents' beliefs, in addition to being more correct, is able to account for presuppositional phenomena which could not be accounted for otherwise.

We present a method to automatically acquire a new type of lexical resource: a knowledge-base of near-synonym differences. We develop an unsupervised decision-list algorithm that learns extraction patterns from a special dictionary of synonym differences. The patterns are then used to extract knowledge from the text of the dictionary.

The initial knowledge-base is later enriched with information from other machine-readable dictionaries. Information about the collocational behavior of the near-synonyms is acquired from free text. The knowledge-base is used by Xenon, a natural language generation system that shows how the new lexical resource can be used to choose the best near-synonym in specific situations.

Current natural language generation or machine translation systems cannot distinguish among near-synonyms --- words that share the same core meaning but vary in their lexical nuances. This is due to a lack of knowledge about differences between near-synonyms in existing computational lexical resources.

The goal of this thesis is to automatically acquire a lexical knowledge-base of near-synonym differences (LKB of NS) from multiple sources, and to show how it can be used in a practical natural language processing system.

I designed a method to automatically acquire knowledge from dictionaries of near-synonym discrimination written for human readers. An unsupervised decision-list algorithm learns patterns and words for classes of distinctions. The patterns are learned automatically, followed by a manual validation step. The extraction of distinctions between near-synonyms is entirely automatic. The main types of distinctions are: stylistic (for example, inebriated is more formal than drunk), attitudinal (for example skinny is more pejorative than slim), and denotational (for example, blunder implies accident and ignorance, while error does not).

I enriched the initial LKB of NS with information extracted from other sources. First, information about the senses of the near-synonym was added (WordNet senses). The other near-synonyms in the same dictionary entry and the text of the entry provide a strong context for disambiguation. Second, knowledge about the collocational behaviour of the near-synonyms was acquired from free text. Collocations between a word and the near-synonyms in a dictionary entry were classified into: preferred collocations, less-preferred collocations and anti-collocations. Third, knowledge about distinctions between near-synonyms was acquired from machine-readable dictionaries (the General Inquirer and the Macquarie Dictionary). These distinctions were merged with the initial LKB of NS, and inconsistencies were resolved.

The generic LKB of NS needs to be customized in order to be used in a natural language processing system. The parts that need customization are the core denotations and the strings that describe peripheral concepts in the denotational distinctions. To show how the LKB of NS can be used in practice, I present Xenon, a natural language generation system system that chooses the near-synonym that best matches a set of input preferences. I implemented Xenon by adding a near-synonym choice module and a near-synonym collocation module to an existing general-purpose surface realizer.

Machine translation of locative prepositions is difficult, even between closely related languages such as English and French. We investigate translating the three prepositions in, on, and at into the French prepositions dans, sur, and à. Often, in corresponds to dans on to sur, and at to à. This correspondence, however, is not perfect: in a number of cases, the uses of these prepositions were observed to differ from one language to the other. These cases are not simply exceptional. Following recent work in cognitive science, we use the notion of conceptualization to account for this problem. A conceptualization (or metaphor) is a mental representation of an object or an idea. We believe that the differences in the uses of locative prepositions are caused by differences in the way objects are conceptualized in English and French.

We have implemented a system that translates sentences involving one of the locative prepositions we studied from English to French, based on this idea. In addition, our system is able to detect ambiguities, as well as errors and abnormalities in input sentences.

We cluster verbs into lexical semantic classes, using a general set of noisy features that capture syntactic and semantic properties of the verbs. The feature set was previously shown to work well in a supervised learning setting, using known English verb classes. In moving to a scenario of verb class discovery, using clustering, we face the problem of having a large number of irrelevant features for a particular clustering task. We investigate various approaches to feature selection, using both unsupervised and semi-supervised methods, comparing the results to subsets of features manually chosen according to linguistic properties. We find that the unsupervised method we tried cannot be consistently applied to our data. However the semi-supervised approach (using a seed set of sample verbs) overall outperforms not only the full set of features, but the hand-selected features as well.

Genetically related languages originate from a common proto-language. In the absence of historical records, proto-languages have to be reconstructed from surviving cognates, that is words that existed in the proto-language and are still present in some form in its descendants. The language reconstruction methods have so far been largely based on informal and intuitive criteria. In this thesis, I present techniques and algorithms for performing various stages of the reconstruction process automatically.

The thesis is divided into three main parts that correspond to the principal steps of language reconstruction. The first part presents a new algorithm for the alignment of cognates, which is sufficiently general to align any two phonetic strings that exhibit some affinity. The second part introduces a method of identifying cognates directly from the vocabularies of related languages on the basis of phonetic and semantic similarity. The third part describes an approach to the determination of recurrent sound correspondences in bilingual wordlists by inducing models similar to those developed for statistical machine translation.

The proposed solutions are firmly grounded in computer science and incorporate recent advances in computational linguistics, articulatory phonetics, and bioinformatics. The applications of the new techniques are not limited to diachronic phonology, but extend to other areas of computational linguistics, such as machine translation.

Agents act upon and perceive the world from a particular perspective. It is important to recognize this relativity to perspective if one is not to be overly demanding in specifying what they need to know in order to be able to achieve goals through action. An agent may not know where he is, what time it is, which objects are around him, what the absolute positions of these objects are, and even who he is, and still be able to achieve his goals. This is because the knowledge required is indexical knowledge, knowledge about how one is related to things in one's environment or to events in one's history.

This thesis develops a formal theory of knowledge and action that handles the distinction between indexical and objective knowledge and allows a proper specification of the knowledge prerequisites and effects of action. The theory is embodied in a logic. The semantics of knowledge proposed is a natural extension of the standard possible-world semantic scheme. The notion of ``ability to achieve a goal by doing an action'' is formalized within the logic; the formalization does not require an agent to know in an absolute sense who he is or what time it is.

We then formalize various domains within the logical system proposed. These examples show how actions can be specified so as to avoid making excessive requirement upon the knowledge of agents, and how such specifications can be used to prove that an agent is able to achieve a goal by doing an action if he knows certain facts. We direct a significant part of our formalization efforts at a robotics domain since this kind of application provides the most intuitive examples of situations where indexical knowledge is sufficient for ability. But we also formalize other domains involving temporal knowledge, knowledge of the phone system, and knowledge of one's position in a data structure. The examples involved show that the notion of indexical knowledge is more abstract than one might first imagine. On the basis of evidence provided by the temporal examples, we provide an argument to the effect that the distinction between indexical and objective knowledge accommodated by our framework is of practical interest and that it cannot be handled within previous theories.

Situation semantics proposes novel and attractive treatments for several problem areas of natural language semantics, such as efficiency (context sensitivity) and propositional attitude reports. Its focus on the information carried by utterances makes the approach very promising fro accounting for pragmatic phenomena. However, situation semantics seems to oppose several basic assumptions underlying current approaches to natural language processing and the design of intelligent systems in general. It claims that efficiency undermines the standard notions of logical form entailment, and proof theory, and objects to the view that mental processes necessarily involve internal representations. The paper attempts to clarify these issues and discusses the impact of situation semantics' criticisms for natural language processing, knowledge representation, and reasoning. I claim that the representational approach is the only currently practical one for the design of large intelligent systems, but argue that the representations used should be efficient in order to account for the system's embedding in its environment. The paper concludes by stating some constraints that a computational interpretation of situation semantics should obey and discussing remaining problems.

In practice, lexical chains are typically built using term reiteration or resource-based measures of semantic distance. The former approach misses out on a significant portion of the inherent semantic information in a text, while the latter suffers from the limitations of the linguistic resource it depends upon. In this paper, chains are constructed using the framework of distributional measures of concept distance, which combines the advantages of resource-based and distributional measures of semantic distance. These chains were evaluated on the task of text segmentation and in a study that asked linguistically-trained judges to rate them qualitatively. While performing as well as or better than state-of-the-art methods in the former task, they were rated significantly lower for coherence than chains built using Lin's WordNet-based measure.

Until now, most discourse researchers have assumed that full semantic understanding is necessary to derive the discourse structure of texts. This book documents the first serious attempt to construct automatically and use nonsemantic computational structures for text summarization. Daniel Marcu develops a semantics-free theoretical framework that is both general enough to be applicable to naturally occurring texts and concise enough to facilitate an algorithmic approach to discourse analysis. He presents and evaluates two discourse parsing methods: one uses manually written rules that reflect common patterns of usage of cue phrases such as ``however'' and ``in addition to''; the other uses rules that are learned automatically from a corpus of discourse structures. By means of a psycholinguistic experiment, Marcu demonstrates how a discourse-based summarizer identifies the most important parts of texts at levels of performance that are close to those of humans.

Marcu also discusses how the automatic derivation of discourse structures may be used to improve the performance of current natural language generation, machine translation, summarization, question answering, and information retrieval systems.

Coherent texts are not just simple sequences of clauses and sentences, but rather complex artifacts that have highly elaborate rhetorical structure. This paper explores the extent to which well-formed rhetorical structures can be automatically derived by means of surface-form-based algorithms. These algorithms identify discourse usages of cue phrases and break sentences into clauses, hypothesize rhetorical relations that hold among textual units, and produce valid rhetorical structure trees for unrestricted natural language texts. The algorithms are empirically grounded in a corpus analysis of cue phrases and rely on a first-order formalization of rhetorical structure trees.

The algorithms are evaluated both intrinsically and extrinsically. The intrinsic evaluation assesses the resemblance between automatically and manually constructed rhetorical structure trees. The extrinsic evaluation shows that automatically derived rhetorical structures can be successfully exploited in the context of text summarization.

Researchers in computational linguistics have long speculated that the nuclei of the rhetorical structure tree of a text form an adequate ``summary'' of the text for which that tree was built. However, to my knowledge, there has been no experiment to confirm how valid this speculation really is.

In this paper, I describe a psycholinguistic experiment that shows that the concepts of discourse structure and nuclearity can be used effectively in text summarization. More precisely, I show that there is a strong correlation between the nuclei of the discourse structure of a text and what readers perceive to be the most important units in that text. In addition, I propose and evaluate the quality of an automatic discourse-based summarization system that implements the methods that were validated by the psycholinguistic experiment. The evaluation indicates that although the system does not match yet the results that would be obtained if discourse trees had been built manually, it still significantly outperforms both a baseline algorithm and Microsoft's Office97 summarizer.

This thesis is an inquiry into the nature of the high-level rhetorical structure of unrestricted natural language texts computational means to enable its derivation, and two applications (in automatic summarization and natural language generation) that follow from the ability to build such structures automatically.

The thesis proposes a first-order formalization of the high-level rhetorical structure of text. The formalization assumes that text can be sequenced into elementary units; that discourse relations hold between textual units of various sizes; that some textual units are more important to the writer's purpose than others; and that trees are a good approximation of the abstract structure of text. The formalization also introduces a linguistically motivated compositionality criterion, which is shown to hold for the text structures that are valid.

The thesis proposes, analyzes theoretically, and compares empirically four algorithms for determining the valid text structures of a sequence of units among which some rhetorical relations hold. Two algorithms apply model-theoretic techniques; the other two apply proof-theoretic techniques.

The formalization and the algorithms mentioned so far correspond to the theoretical facet of the thesis. An exploratory corpus analysis of cue phrases provides the means for applying the formalization to unrestricted natural language texts. A set of empirically motivated algorithms were designed in order to determine the elementary textual units of a text, to hypothesize rhetorical relations that hold among these units, and eventually, to derive the discourse structure of that text. The process that finds the discourse structure of unrestricted natural language texts is called rhetorical parsing.

The thesis explores two possible applications of the text theory that it proposes. The first application concerns a discourse-based summarization system, which is shown to significantly outperform both a baseline algorithm and a commercial system. An empirical psycholinguistic experiment not only provides an objective evaluation of the summarization system, but also confirms the adequacy of using the text theory proposed here in order to determine the most important units in a text. The second application concerns a set of text planning algorithms that can be used by natural language generation systems in order to construct text plans in the cases in which the high-level communicative goal is to map an entire knowledge pool into text.