Artificial languages for person-machine communication seldom display the most characteristic properties of natural languages, such as the use of anaphoric or other referring expressions, or ellipsis. This paper argues that useful use could be made of such devices in artificial languages, and proposes a mechanism for the resolution of ellipsis and anaphora in them using finite state transduction techniques. This yields an interpretation system displaying many desirable properties: easily implementable, efficient, incremental and reversible.

Linguists in general, and computational linguists in particular, do well to employ finite state devices wherever possible. They are theoretically appealing because they are computationally weak and best understood from a mathematical point of view. They are computationally appealing because they make for simple, elegant, and highly efficient implementations. In this paper, I hope I have shown how they can be applied to a problem… which seems initially to require heavier machinery.

Morphological analysis, which is at the heart of the processing of natural language requires computationally effective morphological processors. In this paper an approach to the organization of an inflectional morphological model and its application for the Russian language are described. The main objective of our morphological processor is not the classification of word constituents, but rather an efficient computational recognition of morpho-syntactic features of words and the generation of words according to requested morpho-syntactic features. Another major concern that the processor aims to address is the ease of extending the lexicon. The templated word-paradigm model used in the system has an engineering flavour: paradigm formation rules are of a bottom-up (word specific) nature rather than general observations about the language, and word formation units are segments of words rather than proper morphemes. This approach allows us to handle uniformly both general cases and exceptions, and requires extremely simple data structures and control mechanisms which can be easily implemented as a finite-state automata. The morphological processor described in this paper is fully implemented for a substantial subset of Russian (more then 1,500,000 word-tokens – 95,000 word paradigms) and provides an extensive list of morpho-syntactic features together with stress positions for words utilized in its lexicon. Special dictionary management tools were built for browsing, debugging and extension of the lexicon. The actual implementation was done in C and C++, and the system is available for the MS-DOS, MS-Windows and UNIX platforms.

Due to recent developments in the area of computational formalisms for linguistic representation, the task of designing a parser for a specified natural language is now shifted to the problem of designing its grammar in certain formal ways. This paper describes the results of a project whose aim was to design a formal grammar for modern Hebrew. Such a formal grammar has never been developed before. Since most of the work on grammatical formalisms was done without regarding Hebrew (and other Semitic languages as well), we had to choose a formalism that would best fit the specific needs of the language. This part of the project has been described elsewhere. In this paper we describe the details of the grammar we developed. The grammar deals with simple, subordinate and coordinate sentences as well as interrogative sentences. Some structures were thoroughly dealt with, among which are noun phrases, verb phrases, adjectival phrases, relative clauses, object and adjunct clauses; many types of adjuncts; subcategorization of verbs; coordination; numerals, etc. For each phrase the parser produces a description of the structure tree of the phrase as well as a representation of the syntactic relations in it. Many examples of Hebrew phrases are demonstrated, together with the structure the parser assigns them. In cases where more than one parse is produced, the reasons of the ambiguity are discussed.

We discuss a hierarchical probabilistic model whose predictions are similar to those of the popular language modelling procedure known as ‘smoothing’. A number of interesting differences from smoothing emerge. The insights gained from a probabilistic view of this problem point towards new directions for language modelling. The ideas of this paper are also applicable to other problems such as the modelling of triphomes in speech, and DNA and protein sequences in molecular biology. The new algorithm is compared with smoothing on a two million word corpus. The methods prove to be about equally accurate, with the hierarchical model using fewer computational resources.