Search

The paper proposes a new type of negation in multi-valued logics, providing a different way to answer the following question: what does it mean that some object language formula does not have a given truth-value. Along the way, the paper provides a general definition of truth and falsity in an arbitrary many-valued logic.

Contemporary linguistic theories (in particular, HPSG) are declarative in nature: they specify constraints on permissible structures, not how such structures are to be computed. Grammars designed under such theories are, therefore, suitable for both parsing and generation. However, practical implementations of such theories don't usually support bidirectional processing of grammars. We present a grammar development system that includes a compiler of grammars (for parsing and generation) to abstract machine instructions, and an interpreter for the abstract machine language. The generation compiler inverts input grammars (designed for parsing) to a form more suitable for generation. The compiled grammars are then executed by the interpreter using one control strategy, regardless of whether the grammar is the original or the inverted version. We thus obtain a unified, efficient platform for developing reversible grammars., Comment: 8 pages postscript

Typed feature structures are used extensively for the specification of linguistic information in many formalisms. The subsumption relation orders TFSs by their information content. We prove that subsumption of acyclic TFSs is well-founded, whereas in the presence of cycles general TFS subsumption is not well-founded. We show an application of this result for parsing, where the well-foundedness of subsumption is used to guarantee termination for grammars that are off-line parsable. We define a new version of off-line parsability that is less strict than the existing one; thus termination is guaranteed for parsing with a larger set of grammars., Comment: 19 pages, 1 postscript figure, uses fullname.sty

In this paper we provide for parsing with respect to grammars expressed in a general TFS-based formalism, a restriction of ALE. Our motivation being the design of an abstract (WAM-like) machine for the formalism, we consider parsing as a computational process and use it as an operational semantics to guide the design of the control structures for the abstract machine. We emphasize the notion of abstract typed feature structures (AFSs) that encode the essential information of TFSs and define unification over AFSs rather than over TFSs. We then introduce an explicit construct of multi-rooted feature structures (MRSs) that naturally extend TFSs and use them to represent phrasal signs as well as grammar rules. We also employ abstractions of MRSs and give the mathematical foundations needed for manipulating them. We formally define grammars and the languages they generate, and then describe a model for computation that corresponds to bottom-up chart parsing: grammars written in the TFS-based formalism are executed by the parser. We show that the computation is correct with respect to the independent definition. Finally, we discuss the class of grammars for which computations terminate and prove that termination can be guaranteed for off-line parsable grammars., Comment: PostScript, 29 pages

This paper describes an abstract machine for linguistic formalisms that are based on typed feature structures, such as HPSG. The core design of the abstract machine is given in detail, including the compilation process from a high-level language to the abstract machine language and the implementation of the abstract instructions. The machine's engine supports the unification of typed, possibly cyclic, feature structures. A separate module deals with control structures and instructions to accommodate parsing for phrase structure grammars. We treat the linguistic formalism as a high-level declarative programming language, applying methods that were proved useful in computer science to the study of natural languages: a grammar specified using the formalism is endowed with an operational semantics., Comment: Self-contained LaTeX, 15 pages, to appear in NLULP95

This paper presents an analysis of temporal anaphora in sentences which contain quantification over events, within the framework of Discourse Representation Theory. The analysis in (Partee 1984) of quantified sentences, introduced by a temporal connective, gives the wrong truth-conditions when the temporal connective in the subordinate clause is "before" or "after". This problem has been previously analyzed in (de Swart 1991) as an instance of the proportion problem, and given a solution from a Generalized Quantifier approach. By using a careful distinction between the different notions of reference time, based on (Kamp and Reyle 1993), we propose a solution to this problem, within the framework of DRT. We show some applications of this solution to additional temporal anaphora phenomena in quantified sentences., Comment: 6 pages, LaTeX, uses eaclap.sty, to appear in Proceedings of EACL-95

This paper describes a first step towards the definition of an abstract machine for linguistic formalisms that are based on typed feature structures, such as HPSG. The core design of the abstract machine is given in detail, including the compilation process from a high-level specification language to the abstract machine language and the implementation of the abstract instructions. We thus apply methods that were proved useful in computer science to the study of natural languages: a grammar specified using the formalism is endowed with an operational semantics. Currently, our machine supports the unification of simple feature structures, unification of sequences of such structures, cyclic structures and disjunction., Comment: 38 pages, uuencoded compressed postscript