Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Marked Items 
Alerts
Order History
Saved Items
All
Favorites
    
Book Chapter Printable view
Consistent Identification in the Limit of Any of the Classes <i>k</i>-Valued Is NP-hard

Consistent Identification in the Limit of Any of the Classes k-Valued Is NP-hard

Book SeriesLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
ISSN0302-9743 (Print) 1611-3349 (Online)
VolumeVolume 2099/2001
BookLogical Aspects of Computational Linguistics
DOI10.1007/3-540-48199-0
Copyright2001
ISBN978-3-540-42273-0
DOI10.1007/3-540-48199-0_8
Pages125-138
Subject CollectionComputer Science
SpringerLink DateMonday, January 01, 2001
Add to marked items

Consistent Identification in the Limit of Any of the Classes k-Valued Is NP-hard

Christophe Costa Florêncio4 Contact Information

(4)  UiL OTS (Utrecht University), Trans 10, 3512 JK Utrecht, Netherlands
Abstract
In [Bus87], [BP90] ‘discovery procedures’ for CCGs were defined that accept a sequence of structures as input and yield a set of grammars.
In [Kan98] it was shown that some of the classes based on these procedures are learnable (in the technical sense of [Gol67]). In [CF00] it was shown that learning some of these classes by means of a consistent learning function is NP-hard.
The complexity of learning classes from one particular family, Gk-valued, was still left open. In this paper it is shown that learning any (except one) class from this family by means of a consistent learning function is NP-hard as well.

Keywords  Categorial grammars - Formal language theory - Grammatical inference - Learning theory

Contact Information Christophe Costa Florêncio
Email: costa@let.uu.nl
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.
more options
Find


Export this chapter
Export this chapter as RIS | Text
 
Frequently asked questions | General information on journals and books | Send us your feedback | Impressum | Contact
© Springer. Part of Springer Science+Business Media
Privacy, Disclaimer, Terms and Conditions, © Copyright Information
Remote Address: 38.107.191.108 • Server: mpweb21
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)