The statistical induction of stochastic context free grammars from bracketed corpora with the Inside Outside Algorithm is an appealing method for grammar learning, but the computational complexity of this algorithm has made it impossible to generate a large scale grammar. Researchers from natural language processing and speech recognition have suggested various methods to reduce the computational complexity and, at the same time, guide the learning algorithm towards a solution by, for example, placing constraints on the grammar. We suggest a method that strongly reduces that computational cost of the algorithm without placing constraints on the grammar. This method can in principle be combined with any of the constraints on grammars that have been suggested in earlier studies. We show that it is feasible to achieve results equivalent to earlier research, but with much lower computational effort. After creating a small grammar, the grammar is incrementally increased while rules that have become obsolete are removed at the same time. We explain the modifications to the algorithm, give results of experiments and compare these to results reported in other publications.

With the emergence of broad-coverage parsers, quantitative evaluation of parsers becomes increasingly more important. We propose a dependency-based method for evaluating broad-coverage parsers that offers more meaningful performance measures than previous approaches. We also present a structural pattern-matching mechanism that can be used to eliminate inconsequential differences among different parse trees. Previous evaluation methods have only evaluated the overall performance of parsers. The dependency-based method can also evaluate parsers with respect to different kinds of grammatical relationships or different types of lexical categories. An algorithm for transforming constituency trees into dependency trees is presented, which makes the evaluation method applicable to both constituency grammars and dependency grammars.

This paper presents a number of linguistic and computational issues identified during the implementation of a general use grammar checker for contemporary Brazilian Portuguese, ReGra, that has been incorporated in the word processor REDATOR by Itautec/Philco (Brazil). Two main strategies were employed in the implementation of correction rules: an error-driven, localist approach based on the identification of patterns indicative of grammatical mistakes; and a more generic approach that requires automatic syntactic analysis. In this discussion, particular emphasis is given to the development of a parser based on a phrase structure grammar comprising over 600 production rules. As for the computational performance, ReGra permits texts to be revised at a rate of ca. 200 words per second.

Alternative and Augmentative Communication (AAC) for people with speech and language disorders is an interesting and challenging application field for research in Natural Language Processing. Further advances in the development of AAC systems require robust language processing techniques and versatile linguistic knowledge bases. Also NLP research can benefit from studying the techniques used in this field and from the user-centred methodologies used to develop and evaluate AAC systems. Until recently, however, apart from some exceptions, there was little scientific exchange between the two research areas. This paper aims to make a contribution to closing this gap. We will argue that current interest in language use, which can be shown by the large amount of research on comprehensive dictionaries and on corpora processing, makes the results of NLP research more relevant to AAC. We will also show that the increasing interest of AAC researchers in NLP is having positive results. To situate research on communication aids, the first half of this paper gives an overview of the AAC research field. The second half is dedicated to an overview of research prototype systems and commercially available communication aids that specifically involve more advanced language processing techniques.

This paper describes the work carried out at the Center for Sprogteknologi in Copenhagen to validate the LE evaluation methodology developed by the LRE project TEMAA. TEMAA has developed a framework for the evaluation of LE products, implemented in a Parameterisable Testbed (PTB). The framework allows for a modular, formal and exible description of user requirements and objects of evaluation, it accommodates test methods of various kind and provides a methodology for assessing test results in the light of the requirements expressed by different user types. While the fundamentals of the TEMAA framework are meant to apply to adequacy evaluation of LE products in general, a detailed methodology has been worked out for the evaluation of spelling and grammar checkers, and applied to the concrete evaluation of Danish and Italian spelling checkers. The main focus of this paper is on showing that the general methodology provides a valid model for designing and carrying out a concrete evaluation, as in the case study on Danish spelling checkers.

Currently, word tokenization and segmentation are still a hot topic in natural language processing, especially for languages like Chinese in which there is no blank space for word delimitation. Three major problems are faced: (1) tokenizing direction and efficiency; (2) insufficient tokenization dictionary and new words; and (3) ambiguity of tokenization and segmentation. Most existing tokenization and segmentation methods have not dealt with the above problems together. To tackle the three problems in one basket, this paper presents a novel dictionary-based method called the Splitting-Merging Model (SMM) for Chinese word tokenization and segmentation. It uses the mutual information of Chinese characters to find the boundaries and the non-boundaries of Chinese words, and finally leads to a word segmentation by resolving ambiguities and detecting new words.

This article focuses on the need for technological aid for agrammatics, and presents a system designed to meet this need. The field of Augmentative and Alternative Communication (AAC) explores ways to allow people with speech or language disabilities to communicate. The use of computers and natural language processing techniques offers a range of new possibilities in this direction. Yet AAC addresses speech deficits mainly, not linguistic disabilities. A model of aided AAC interfaces with a place for natural language processing is presented. The PVI system, described in this contribution, makes use of such advanced techniques. It has been developed at Thomson-CSF for the use of children with cerebral palsy. It presents a customizable interface helping the disabled to compose sequences of icons displayed on a computer screen. A semantic parser, using lexical semantics information, is used to determine the best case assignments for predicative icons in the sequence. It maximizes a global value, the ‘semantic harmony’ of the sequence. The resulting conceptual graph is fed to a natural language generation module which uses Tree Adjoining Grammars (TAG) to generate French sentences. Evaluation by users demonstrates the system's strengths and limitations, and shows the ways for future developments.

This paper describes tactical generation in Turkish, a free constituent order language, in which the order of the constituents may change according to the information structure of the sentences to be generated. In the absence of any information regarding the information structure of a sentence (i.e. topic, focus, background, etc.), the constituents of the sentence obey a default order, but the order is almost freely changeable, depending on the constraints of the text flow or discourse. We have used a recursively structured finite state machine (much like a Recursive Transition Network (RTN)) for handling the changes in constituent order, implemented as a right-linear grammar backbone. Our implementation environment is the GenKit system, developed at Carnegie Mellon University, Center for Machine Translation. Morphological realization has been implemented using an external morphological analysis/generation component which performs concrete morpheme selection and handles morphographemic processes.

In this paper, we present results of a project that investigated the application of lexicon based text retrieval techniques to Alternative and Augmentative Communication (AAC). As a practical outcome of this research, a communication aid based on message retrieval by key words was designed, implemented and evaluated. The message retrieval module in the system uses a large semantic lexicon, derived from the WordNet database, for query expansion. Trials have been carried out with the device to evaluate whether the approach is suitable for AAC, and to determine the semantic relations that lead to efficient message retrieval. The first part of this paper describes the background of the project and highlights the retrieval requirements for a communication aid, which differ considerably from the requirements in standard text retrieval. We then present the overall design of the WordKeys communication aid and describe the tasks of its sub-modules. We summarise trials that have been carried out to determine the effect of semantic query expansion on the success of message retrieval. Evaluation results show that information about word frequency can solve problems that occurred in the semantic query expansion because of taxonomies that have too many intermediate steps between closely related words. Finally, a user evaluation with the improved system showed that full text retrieval is an effective approach to message access in a communication aid.

Most existing Natural Language Database Interfaces (NLDB) were designed to be used with database systems that provide very limited facilities for manipulating time-dependent data, and they do not support adequately temporal linguistic mechanisms (verb tenses, temporal adverbials, temporal subordinate clauses, etc.). The database community is becoming increasingly interested in temporal database systems, which are intended to store and manipulate in a principled manner information not only about the present, but also about the past and future. When interfacing to temporal databases, supporting temporal linguistic mechanisms becomes crucial.

We present a framework for constructing Natural Language Interfaces for Temporal Databases (NLTDB), which draws on research in tense and aspect theories, temporal logics and temporal databases. The framework consists of a temporal intermediate representation language, called TOP, an HPSG grammar that maps a wide range of questions involving temporal mechanisms to appropriate TOP expressions, and a provably correct method for translating from TOP to TSQL2, TSQL2 being a recently proposed temporal extension of the SQL database language. This framework was employed to implement a prototype NLTDB.

Semantically tagging a corpus is useful for many intermediate NLP tasks such as: acquisition of word argument structures in sublanguages; acquisition of syntactic disambiguation cues; terminology learning; etc. The general idea is that semantic tags allow the generalization of observed word patterns, and facilitate the discovery of recurrent sublanguage phenomena and selectional rules of various types. Yet, as opposed to POS tags in morphology, there is no consensus in the literature about the type and granularity of the semantic tags to be used. In this paper, we argue that an appropriate selection of semantic tags should be domain-dependent. We propose a method by which we select from WordNet an inventory of semantic tags that are ‘optimal’ for a given corpus, according to a scoring function defined as a linear combination of general and corpus-dependent performance factors. We believe that an optimal selection of a category inventory is a necessary premise for obtaining better results in all lexically learning algorithms that are based on, or concerned with, semantic categorization of words. Furthermore, an adequate inventory (one which intuitively ‘fits’ with the semantics of a domain, e.g. phenomenon for Natural Science, or part, piece for a technical handbook) may facilitate the manual annotation of large corpora.

This paper describes two experiments: one exploring the amount of information relevant to sense disambiguation contained in the part-of-speech field of entries in a Machine Readable Dictionary (MRD); the other, more practical, experiment attempts sense disambiguation of all content words in a text assigning MRD homographs as sense tags using only part-of-speech information. We have implemented a simple sense tagger which successfully tags 94% of words using this method. A plan to extend this work and implement an improved sense tagger is included.

Quantified expressions present an interesting case for understanding pronominal reference because the quantifier which appears in the expression affects how the pronoun will be understood. The quantifier determines which sets will be placed in focus and predicts the relation between the sentence containing the quantifier and the following sentence (Moxey and Sanford 1993a). This information is essential to understanding the pronominal reference. In this paper, we discuss how a natural language processing system can take advantage of this information to understand pronominal references to quantified expressions.

Non-speaking people often rely on AAC (Augmentative and Alternative Communication) devices to assist them to communicate. These AAC devices are slow to operate, however, and as a result conversations can be very difficult and frequently break down. This is especially the case when the conversation partner is unfamiliar with this method of communication, and is a big obstacle to many people when they wish to conduct simple everyday transactions. A way of improving the performance of AAC devices by using scripts is discussed. A prototype system to test this idea was constructed, and a preliminary experiment performed with promising results. A practical AAC device which incorporates scripts was then developed, and is described.

This paper deals with the development of parsing techniques for the analysis of natural language sentences. We present a paradigm of a multi- path shift-reduce parser which combines two differently structured computational subsystems. The first uses information concerning native speakers' preferences, and the second deals with the linguistic knowledge. To apply preferences on parsing, we propose a method to rank the alternative partial analyses on the basis of parse context and frequency of use effects. The method is mainly based on psycholinguistic evidence, since we hope eventually to build a parser working as closely as possible to the way native speakers analyse natural sentences. We also discuss in detail techniques for optimizing the effectiveness of the proposed model. The system has worked successfully in parsing sentences in Modern Greek, a language where the relatively free word order characteristic results in many ambiguity problems. The proposed parsing model is consistent with many directions in the field of preference-based parsing, and it is proved to be adequate in building effective and maintainable natural language analysers. It is believed that this model can also be used in parsing sentences in languages other than Greek.

Augmentative and Alternative Communication (AAC) is the field of study concerned with providing devices and techniques to augment the communicative ability of a person whose disability makes it difficult to speak or otherwise communicate in an understandable fashion. For several years, we have been applying natural language processing techniques to the field of AAC to develop intelligent communication aids that attempt to provide linguistically correct output while increasing communication rate. Previous effort has resulted in a research prototype called Compansion that expands telegraphic input. In this paper we describe that research prototype and introduce the Intelligent Parser Generator (IPG). IPG is intended to be a practical embodiment of the research prototype aimed at a group of users who have cognitive impairments that affect their linguistic ability. We describe both the theoretical underpinnings of Compansion and the practical considerations in developing a usable system for this population of users.