TAILIEUCHUNG - Báo cáo khoa học: " CONSTRAINT PROPAGATION IN KIMMO SYSTEMS"

Taken abstractly, the two-level (Kimmo) morphological framework allows computationally difficult problems to arise. For example, N + 1 small a u t o m a t a are sufficient to encode the Boolean satisfiability problem (SAT) for formulas in N variables. However, the suspicion arises that natural-language problems may have a special structure - not shared with SAT - - that is not directly captured in the two-level model. In particular, the natural problems may generally have a modular and local nature that distinguishes them from more "global" SAT problems. By exploiting this structure, it may be possible to. | CONSTRAINT PROPAGATION IN KIMMO SYSTEMS G. Edward Barton Jr. . Artificial Intelligence Laboratory 545 Technology Square Cambridge MA 02139 ABSTRACT Taken abstractly the two-level Kimmo morphological framework allows computationally difficult problems to arise. For example N 1 small automata are sufficient to encode the Boolean satisfiability problem SAT for formulas in N variables. However the suspicion arises that natural-language problems may have a special structure not shared with SAT that is not directly captured in the two-level model. In particular the natural problems may generally have a modular and local nature that distinguishes them from more global SAT problems. By exploiting this structure it may be possible to solve the natural problems by methods that do not involve combinatorial search. We have explored this possibility in a preliminary way by applying constraint propagation methods to Kimmo generation and recognition. Constraint propagation can succeed when the solution falls into place step-by-step through a chain of limited and local inferences but it is insufficiently powerful to solve unnaturally hard SAT problems. Limited tests indicate that the constraint-propagation algorithm for Kimmo generation works for English Turkish and Warlpiri. When applied to a Kimmo system that encodes SAT problems the algorithm succeeds on easy SAT problems but fails as desired on hard problems. INTRODUCTION A formal computational model of a linguistic process makes explicit a set of assumptions about the nature of the process and the kind of information that it fundamentally involves. At the same time the formal model will ignore some details and introduce others that are only artifacts of formalization. Thus whenever the formal model and the actual process seem to differ markedly in properties a natural assumption is that something has been missed in formalization though it may be difficult to say exactly what. When the difference is one of worst-case .

• Báo cáo khoa học
• CONSTRAINT PROPAGATION
• KIMMO SYSTEMS
• G
• Edward Barton
• scientific reports
• model language
• process natural language
• STRUCTURAL DISAMBIGUATION
• Hiroshi Maruyama
• BMC Bioinformatics
• Constraint based model
• Gene network
• Bayesian network
• Model integration
• Probabilistic reasoning
• Belief propagation
• 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