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.