TAILIEUCHUNG - Báo cáo khoa học: "Rigid Grammars in the Associative-Commutative Lambek Calculus are not Learnable"

In (Kanazawa, 1998) it was shown that rigid Classical Categorial Grammars are learnable (in the sense of (Gold, 1967)) from strings. Surprisingly there are recent negative results for, among others, rigid associative Lamb ek (L) grammars. In this paper the non-lcarnability of the class of rigid grammars in LP (Associative-Commutative Lambek calculus) and LP0 (same, but allowing the empty sequent in derivations) will be shown. | Rigid Grammars in the Associative-Commutative Lambek Calculus are not Learnable Christophe Costa Florencio UiL OTS Faculty of Arts Utrecht University costa@ Abstract In Kanazawa 1998 it was shown that rigid Classical Categorial Grammars are learnable in the sense of Gold 1967 from strings. Surprisingly there are recent negative results for among others rigid associative Lambek L grammars. In this paper the non-lcarnability of the class of rigid grammars in LP Associative-Commutative Lam-bek calculus and LPg same but allowing the empty sequent in derivations will be shown. 1 Introduction The question of learnability of catcgorial grammar CG was first taken up in Kanazawa 1998 . Categorial grammar is an example of a radically lexicalized formalism the details of which will be discussed in Section 2. Kanazawa studied only subclasses of Classical Categorial Grammar results for subclasses of Lam-bek grammars can be found in Foret and Nir 2002a Foret and Nir 2002b . The model of learnability used here is identification in the limit from positive data as introduced in Gold 1967 .1 In order to show the non-learnability of rigid LP and LPj we 1 Space restrictions do not allow a full exposition of this model. The interested reader is referred to the first two chapters of Kanazawa 1998 . construct so-called limit points to be defined in Section 3 for these classes. 2 The Lambek Calculus Categorial grammar originated in Aj-dukiewicz 1935 and was further developed in Bar-Hillel 1953 and Lambek 1958 . This paper will only give a brief introduction in this field Casadio 1988 or Moortgat 1997 offers a more comprehensive overview. A categorial grammar is a set of assignments of types to symbols from a fixed alphabet B the types are either primitives or are composed from types with the binary connectives Rules specify how types are to be combined to form new types. A string is said to be in the language generated by grammar G written as s G L G L is knowm as a naming .

• Báo cáo khoa học
• Rigid Grammars
• Associative Commutative
• Lambek Calculus are not Learnable
• 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