Articles

We introduce an algorithm for designing a predictive left to right shift-reduce non-deterministic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The perfor- mance of the resulting parser is formally proven to be superior to Earley's parser (1970). The …...

We describe a method for obtaining subject-dependent word sets relative to some (subjecO domain. Using the subject classifications given in the machine-readable ver- sion of Longman's Dictionary of Contemporary English, we established subject-dependent co- occurrence links between words of the defining vocabulary to construct these "neighborhoods". Here, we describe the …...

* Efficient syntactic and semantic parsing for ambiguous context-free languages are generally characterized as complex, specialized, highly formal algorithms. In fact, they are readily constructed from straightforward recursive Iransition networks (RTNs). In this paper, we introduce LR-RTNs, and then computationally motivate a uniform progression from basic LR parsing, to Earley's …...

Two new parsing algorithms for context-free phrase structure gram- mars are presented which perform a bounded amount of processing per word per analysis path, independently of sentence length. They are thus ca- pable of parsing in real-time in a par- allel implementation which forks pro- cessors in response to non-determinis- …...

Some problems are discussed that arise for incremental pro- cessing using certain flezible categorial grammars, which in- volve either undesirable parsing properties or failure to allow combinations useful to incrementality. We suggest a new cal- culus which, though 'designed' in relation to categorial inter- pretatious of some notions of dependency …...

1 Certain pronoun contexts are argued to establish a local center (LC), i.e., a conventionalized indexical similar to lst/2nd pers. pronouns. Demonstrative pronouns, also indexicals, are shown to access en- tities that are not LCs because they lack discourse relevance or because they are not yet in the uni- verse …...

1 This paper presents a tripartite model of dialogue in which three different kinds of actions are modeled: domain actions, problem-solving actions, and dis- course or communicative actions. We contend that our process model provides a more finely differenti- ated representation of user intentions than previous models; enables the incremental …...

In this study we map out a way to build event representations incrementally, using information which may be widely distributed across a dis- course. An enhanced Discourse Representation (Kamp, 1981) provides the vehicle both for car- rying open event roles through the discourse until they can be instantiated by NPs, …...

We investigate the logical structure of concepts generated by conjunction and disjunction over a monotonic multiple inheritance network where concept nodes represent linguistic categories and links indicate basic inclusion (ISA) and disjoint- hess (ISNOTA) relations. We model the distinction between primitive and defined concepts as well as between closed- and …...

A model of plan recognition in discourse must be based on intended recognition, distinguish each agent's be- liefs and intentions from the other's, and avoid as- sumptions about the correctness or completeness of the agents' beliefs. In this paper, we present an algo- rithm for plan recognition that is based …...

This paper propo~s a reversible architecture to handle not orily syntactic and semantic information but also pragmatic information. • I Existing architectures cannot represent prag- matic informatioil explicitly, and lack rea- soning capability;given insufficient informa- tion. I argue that the techniques of plan rep- resentation and approximate reasoning are, in …...

This paper describes a method for obtaining the semantic representation for a syntax tree in Sys- temic Grammar (SG). A prototype implementation of this method -- the REVELATION1 semantic inter- preter -- has been ldeveloped. It is derived from a SG generator foe a large subset of English -- GENESYS …...

This paper attempts to develop a theory of heuristics or preferences that can be shared be- tween understanding and generation systems. We first develop a formal analysis of preferences and consider the relation between their uses in gener- ation and understanding. We then present a bi- directional algorithm for applying …...

In this paper ,we deal with issues that face an interlingua-based, reversible machine translation system when the~ literal meaning of the source text is not identical to the literal meaning of the nat- ural target translation. We present an algorithm for lexical choice that handles such cases and that relies …...

A considerable amount of study has recently been concentrated on the use of linguistically motivated unification based grammars for sen- tence generation (see for example Appelt 1987, Calder 1989, Shieber 1988, Shieber et al. 1989). The grammars state correspondences between semantic structures and syntactic ones. In most grammars, several syntactic …...

We present a new architecture for reversible NLP. Separate parsing and generation grammars are constructed from the underlying application's semantic model and knowledge base. By having two grammars we are free to use process-specific representations and control techniques, thereby permitting highly efficient processing. The single semantic source ensures the parsimony …...

This paper discussers general hem'istics to control computation on symbolic constraints represented in terms of first-order logic programs. These heuristics are totally independen! of specific domains and tasks. Efficient computation for sentence parsing and genera- tion naturally emerge fi'om these heuristics, capturing the essence of standar d parsing procedures and …...

A consequent use of reversible grammars within natural language generation systems has strong implications for the separation into strategic and tactical components. A central goal of this paper is to make plausible that a uniform architecture for grammatical Processing will serve as a basis to achieve more flexible and efficient …...

This paper attempts to clarify two distinct notions of "reversibility": (i) Uniformity of implementa- tion of parsing and generation, and (it) reversibil- ity as an inherent (or intrinsic) property of gram- mars. On the one hand, we explain why gram- mars specified as definite programs (or the vari- ous related …...

In this document, we present a formalism for natural language processing which associates type construction principles to constraint logic programming. We show that it provides more uniform, expressive and efficient tools for parsing and generating language. Next, we present two abstract machines which enable us to design, in a symmetric …...