TAILIEUCHUNG - Báo cáo khoa học: "Free Indexation: Combinatorial Analysis and A Compositional Algorithm*"

The principle known as 'free indexation' plays an important role in the determination of the referential properties of noun phrases in the principleand-parameters language framework. First, by investigating the combinatorics of free indexation, we show that the problem of enumerating all possible indexings requires exponential time. Secondly, we exhibit a provably optimal free indexation algorithm. In (1), the pronominal "him" can be interpreted as being coreferential with "John", or with some other person not named in (1), but not with "Bill". . | Free Indexation Combinatorial Analysis and A Compositional Algorithm Sandiway Fong 545 Technology Square Rm. NE43-810 MIT Artificial Intelligence Laboratory Cambridge MA 02139 Internet sandiway@ Abstract The principle known as free indexation plays an important role in the determination of the referential properties of noun phrases in the principle-and-parameters language framework. First by investigating the combinatorics of free indexation we show that the problem of enumerating all possible indexings requires exponential time. Secondly we exhibit a provably optimal free indexation algorithm. 1 Introduction In the principles-and-parameters model of language the principle known as free indexation plays an important part in the process of determining the referential properties of elements such as anaphors and pronominals. This paper addresses two issues. 1 We investigate the combinatorics of free indexation. By relating the problem to the n-set partitioning problem we show that free indexation must produce an exponential number of referentially distinct phrase structures given a structure with n independent noun phrases. 2 We introduce an algorithm for free indexation that is defined compositionally on phrase structures. We show how the compositional nature of the algorithm makes it possible to incrementally interleave the computation of free indexation with phrase structure construction. Additionally we prove the algorithm to be an optimal procedure for free indexation. More precisely by relating the compositional structure of the formulation to the combinatorial analysis we show that the algorithm enumerates precisely all possible indexings without duplicates. 2 Free Indexation Consider the ambiguous sentence 1 John believes Bill will identify him The author would like to acknowledge Eric s. Ris-tad whose interaction helped to motivate much of the analysis in this paper. Also Robert c. Berwick Michael B. Kashket and Tan veer Syeda provided many useful .

• Báo cáo khoa học
• Free Indexation
• Combinatorial Analysis
• A Compositional Algorithm
• 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