Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/114325
Title: Elementary formal systems, intrinsic complexity, and procrastination
Authors: Jain, Sanjay 
Sharma, Arun
Issue Date: 1996
Citation: Jain, Sanjay,Sharma, Arun (1996). Elementary formal systems, intrinsic complexity, and procrastination. Proceedings of the Annual ACM Conference on Computational Learning Theory : 181-191. ScholarBank@NUS Repository.
Abstract: The learnability of the subclasses of elementary formal systems (EFS) are analyzed by employing two distinct bodies of abstract studies in the inductive inference literature. The first approach uses constructive ordinals to bound the number of mind changes, while the second adapts reductions for the intrinsic complexity of learnable classes. Results show that ordinal mind change complexity for identification of languages formed by unions of up to n pattern languages is ω+n$/. Results that relate topological properties of learnable classes to that of intrinsic complexity and ordinal mind change complexity are also presented.
Source Title: Proceedings of the Annual ACM Conference on Computational Learning Theory
URI: http://scholarbank.nus.edu.sg/handle/10635/114325
Appears in Collections:Staff Publications

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

Page view(s)

38
checked on Oct 12, 2018

Google ScholarTM

Check


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