Articles

A new approach to bottom-up parsing that extends Augmented Context-Free Grammar to a Process Grammar is formally presented. A Process Grammar (PG) defines a set of rules suited for bottom-up parsing and conceived as processes that are applied by a P G Processor. The matching phase is a crucial step …...

This paper describes a new hardware algorithm for morpheme extraction and its implementation on a specific machine (MEX-I), as the first step toward achieving natural language parsing accel- erators. It also shows the machine's performance, 100-1,000 times faster than a personal computer. This machine can extract morphemes from 10,000 character …...

according to this definition 2. Each elementary tree is constrained to have at least one terminal at its frontier which serves as 'head' (or 'anchor'). Sentences of a Tag language are derived from the composition of an S-rooted initial tree with other elementary trees by two operations: substitution (the same …...

In the literature, Tree Adjoining Grammars (TAGs) are propagated to be adequate for nat- ural language description -- analysis as well as generation. In this paper we concentrate on the direction of analysis. Especially important for an implementation of that task is how efficiently this can be done, i.e., how …...

We define a set of deterministic bottom-up left to right parsers which analyze a subset of Tree Adjoining Lan- guages. The LR parsing strategy for Context Free Grammars is extended to Tree Adjoining Grammars (TAGs). We use a machine, called Bottom-up Embed- tied Push Down Automaton (BEPDA), that recognizes in …...

A method of determining the similarity of nouns on the basis of a metric derived from the distribution of subject, verb and object in a large text corpus is described. The resulting quasi-semantic classification of nouns demonstrates the plausibility of the distributional hypothesis, and has potential application to a variety …...

To achieve our goal of building a compre- hensive lexical database out of various on-line resources, it is necessary to interpret and disambiguate the information found in these resources. In this paper we describe a Disambiguation Module which analyzes the content of dictionary dcf'mitions, in particular, definitions of the form …...

This paper 1 presents a rapid and robust pars- ing system currently used to learn from large bodies of unedited text. The system contains a multivalued part-of-speech disambiguator and a novel parser employing bottom-up recogni- tion to find the constituent phrases of larger structures that might be too difficult to …...

We analyse the computational complexity of phonological models as they have developed over the past twenty years. The major results ate that generation and recognition are undecidable for segmental models, and that recognition is NP- hard for that portion of segmental phonology sub- sumed by modern autosegmental models. Formal restrictions …...

A user may typically need to combine the strengths of more than one system in order to perform a task. In this paper, we describe a component of the Janus natural language interface that translates inten- sional logic expressions representing the meaning of a request into executable code for each …...

We discuss algorithms for generation within the Lambek Theorem Proving Framework. Efficient algorithms for generation in this framework take a semantics-driven strategy. This strategy can be modeled by means of rules in the calculus that are geared to generation, or by means of an al- gorithm for the Theorem Prover. …...

We describe a system of reversible grammar in which, given a logic-grammar specification of a natural language, two efficient PROLOG programs are derived by an off-line compilation process: a parser and a generator for this language. The centerpiece of the system is the inversion algorithm designed to compute the generator …...

Recent developments in generation algorithms have enabled work in nnificafion-based computational linguistics to approach more closely the ideal of grammars as declarative statements of linguistic facts, neutral between analysis an0_ synthesis, x-"~-oui this perspective, however, the situation is still far from perfect; all known methods of generation impose constraints on …...

Collocational knowledge is necessary for language gener- ation. The problem is that collocations come in a large variety of forms. They can involve two, three or more words, these words can be of different syntactic cate- gories and they can be involved in more or less rigid ways. This leads …...

Current complex-feature based grammars use a sin- gle procedure--unification--for a multitude of pur- poses, among them, enforcing formal agreement between purely syntactic features. This paper presents evidence from several natural languages that unification--variable-matching combined with variable substitution--is the wrong mechanism for effecting agreement. The view of grammar developed here is …...

In contrast to the "designer logic" approach, this paper shows how the attribute-value feature structures of unification grammar and constraints on them can be axiomatized in classical first-order logic, which can express disjunctive and negative constraints. Because only quantifier-free formulae are used in the axiomatization, the satisfiability problem is NP- …...

Functional Unification Grammars (FUGs) are popular for natural language applications because the formalism uses very few primitives and is uniform and expressive. In our work on text generation, we have found that it also has annoying limitations: it is not suited for the expression of simple, yet very common, taxonomic …...

This paper describes an operational system which can acquire the core meanings of words without any prior knowledge of either the category or meaning of any words it encounters. The system is given as input, a description of sequences of scenes along with sentences which describe the [EVENTS] taking place …...

Though most translation systems have some mechanism for translating certain types of divergent predicate-argument structures, they do not provide a genera] procedure that takes advantage of the relationship between lexical-semantic struc- ture and syntactic structure. A divergent predicate-argument structure is one in which the predicate (e.g., the main verb) or …...

This paper proposes a set of representations for tenses and a set of constraints on how they can be com- bined in adjunct clauses. The semantics we propose ex- plains the possible meanings of tenses in a variety of sen- tential contexts. It also supports an elegant constraint on tense …...