Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-04414-4_25
Title: Uncountable automatic classes and learning
Authors: Jain, S. 
Luo, Q.
Semukhin, P. 
Stephan, F. 
Issue Date: 2009
Source: Jain, S.,Luo, Q.,Semukhin, P.,Stephan, F. (2009). Uncountable automatic classes and learning. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5809 LNAI : 293-307. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-04414-4_25
Abstract: In this paper we consider uncountable classes recognizable by ω-automata and investigate suitable learning paradigms for them. In particular, the counterparts of explanatory, vacillatory and behaviourally correct learning are introduced for this setting. Here the learner reads in parallel the data of a text for a language L from the class plus an ω-index α and outputs a sequence of ω-automata such that all but finitely many of these ω-automata accept the index α iff α is an index for L. It is shown that any class is behaviourally correct learnable if and only if it satisfies Angluin's tell-tale condition. For explanatory learning, such a result needs that a suitable indexing of the class is chosen. On the one hand, every class satisfying Angluin's tell-tale condition is vacillatory learnable in every indexing; on the other hand, there is a fixed class such that the level of the class in the hierarchy of vacillatory learning depends on the indexing of the class chosen. We also consider a notion of blind learning. On the one hand, a class is blind explanatory (vacillatory) learnable if and only if it satisfies Angluin's tell-tale condition and is countable; on the other hand, for behaviourally correct learning there is no difference between the blind and non-blind version. This work establishes a bridge between automata theory and inductive inference (learning theory). © 2009 Springer.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/43282
ISBN: 3642044131
ISSN: 03029743
DOI: 10.1007/978-3-642-04414-4_25
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

3
checked on Dec 13, 2017

Page view(s)

48
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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