Please use this identifier to cite or link to this item: https://doi.org/10.1006/jcss.1996.0030
Title: The intrinsic complexity of language identification
Authors: Jain, S. 
Sharma, A.
Issue Date: Jun-1996
Citation: Jain, S., Sharma, A. (1996-06). The intrinsic complexity of language identification. Journal of Computer and System Sciences 52 (3) : 393-402. ScholarBank@NUS Repository. https://doi.org/10.1006/jcss.1996.0030
Abstract: A new investigation of the complexity of language identification is undertaken using the notion of reduction from recursion theory and complexity theory. The approach, referred to as the intrinsic complexity of language identification, employs notions of "weak" and "strong" reduction between learnable classes of languages. The intrinsic com-plexity of several classes is considered and the results agree with the intuitive difficulty of learning these classes. Several complete classes are shown for both the reductions and it is also established that the weak and strong reductions are distinct. An interesting result is that the self-referential class of Wiehagen in which the minimal element of every language is a grammar for the language and the class of pattern languages introduced by Angluin are equivalent in the strong sense. This study has been influenced by a similar treatment of function identification by Freivalds, Kinber, and Smith. © 1996 Academic Press, Inc.
Source Title: Journal of Computer and System Sciences
URI: http://scholarbank.nus.edu.sg/handle/10635/99436
ISSN: 00220000
DOI: 10.1006/jcss.1996.0030
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

23
checked on Sep 16, 2020

WEB OF SCIENCETM
Citations

22
checked on Sep 8, 2020

Page view(s)

72
checked on Sep 12, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.