TAILIEUCHUNG - Báo cáo khoa học: "HORN EXTENDED FEATURE STRUCTURES: FAST UNIFICATION WITH NEGATION AND LIMITED DISJUNCTION"

The notion of a Horn extended feature structure (HoXF) is introduced, which is a feature structure constrained so that its only allowable extensions are those satisfying some set of llorn clauses in featureterm logic, l l o X F ' s greatly generalize ordinary feature structures in admitting explicit representation of negative and implicational constraints. In contradistinction to the general case in which arbitrary logical constraints are allowed (for which the best known algorithms are exponential), there is a highly tractable algorithm for the unification of HoXF's. . | HORN EXTENDED FEATURE STRUCTURES FAST UNIFICATION WITH NEGATION AND LIMITED DISJUNCTION Stephen J. Hegner Department of Computer Science and Electrical Engineering Votey Building University of Vermont Burlington VT 05405 USA telephone 802 656-3330 internet hegner@ uucp .uunetluvm-genlhegner ABSTRACT The notion of a Horn extended feature structure HoXF is introduced which is a feature structure constrained so that its only allowable extensions are those satisfying some set of Horn clauses in featureterm logic. IIoXF s greatly generalize ordinary feature structures in admitting explicit representation of negative and implicational constraints. In contradistinction to the general case in which arbitrary logical constraints are allowed for which the best known algorithms are exponential there is a highly tractable algorithm for the unification of HoXF s. 1. PRELIMINARY CONCEPTS Unification-based grammar formalisms Unification-based grammar formalisms constitute a cornerstone of many of the most important approaches to natural-language understanding Shieber 1986 Colban 1988 Fenstad et al. 1989 . The basic idea is that the parser generates a number of partial representations of the total parse which are subsequently checked for consistency and combined by a second process known as a unifier. A common form of representation for the partial representations is that of feature structures which are record-like data structures which are allowed to grow in three distinct ways by adding missing values by adding attributes and by coalescing existing attributes forcing therti to be the same . The last operation may lead to cyclic structures which we do not exclude. If the feature structure S2 is an extension of Si . Si grows into S2 by application of some sequence of the above rules we write Si c S2 and say that Si subsumes S2- Intuitively if Si c S2 S2 contains more information than does Si. It is easy to show that c is a partial order on the class of all feature .

• Báo cáo khoa học
• HORN EXTENDED FEATURE STRUCTURES
• FAST UNIFICATION WITH NEGATION
• LIMITED DISJUNCTION
• scientific reports
• model language
• process natural language
• Dialog Control
• Natural Language System
• Dialog Control in a Natural Language System
• Expanding the Horizons
• Natural Language Interfaces
• Phil Hayes
• PROSPECTS OR PRACTICAL
• NATURAL LANGUAGE SYSTEMS
• Workshops
• NATURAL LANGUAGE
• INTERACTION WITH MACHINES
• Long Papers
• COMPUTER INTEBFACE DESIGN MURRAY TUROFF DEPARTMENT OF COMPUTER
• IiVFORMATION SCIENCE IIEW JERSEY INSTITUTE OF TECHNOLOGY
• EVALUATION OF NATURAL LANGUAGE
• INTERFACES TO DATABASE SYSTEMS
• A PANEL DISCUSSION
• database query system
• J
• Norwood Crout
• INTERFACES TO DATA BASE SYSTEMS
• Bozena Henisz
• INTERPRETING NATURAL LANGUAGE
• DATABASE UPDATES
• S
• Jermld Kaplan Jim David
• TRANSPORTABLE NATURAL LANGUAGE
• INTERFACES TO DATABASES
• Gary G
• Hendrlx and William H
• Lewis
• DATABASES THEORETICAL
• TECHNICAL ISSUES
• TRANSPORTABLE NATURAL LANGUAGE INTERFACES
• PROBLEMS AND TECHNIQUES
• Barbara J
• Grosz
• THEORETICAL TECHNICAL ISSUES
• NATURAL LANGUAGE ACCESS TO DATABASES
• R
• Petrick
• Domain Independent
• Database Access Systems
• ISSUES IN NATURAL LANGUAGE
• ACCESS TO DATABASES
• A LOGIC PROGRAMMING PERSPECTIVE
• Sharon C
• Salveter David Maier
• PLANNING NATURAL LANGUAGE
• EXPRESSIONS REFERRING
• Douglas E
• Appelt
• THE TEXT SYSTEM
• NATURAL LANGUAGE GENERATION
• Kathleen R
• M
• MENTING A DATABASE
• KNOWLEDGE REPRESENTATION
• THE KEY TO THE SELECTION PROBLEM
• E
• Jeffrey Conklin David D
• McDonald
• A KNOWLEDGE ENGINEERING
• NATURAL LANGUAGE UNDERSTANDING
• Stuart C
• Shapiro
• NATURAL LANGUAGE TEXTS
• NECESSARILY GRAMMATICAL
• EVEN COMPLETE
• UNGRAMHATICALITY
• EXTRA GRAMMATICALITY
• NATURAL LANGUAGE UNDERSTANDING SYSTEMS
• Taxonomy
• Descriptions
• Individuals in Natural
• Language Understanding
• The Use of Ooject Special Knowledge
• Natural Language Processing
• Mark H
• Bursteln